MENU

CTF中的RSA题学习开坑

• 2018 年 04 月 04 日 • 爬坑教程

CTF中的RSA题学习开坑

前言

一直想学习下RSA的解密方法来着,可是数学太差,真的看着超级难受,终于,今天找到了一个能看懂一点点的了。

需要的概念知识

素数(质数)、合数、互质数

素数:一个数如果除了1与它本身之外没有其他的因数,那么这个数就被称为素数(或者质数,取自英文单词prime的首字母)。
合数:如果一个数大于1,且该数本身不是素数,那么这个数就是一个合数。
互质数:如果两个整数a,b的最大公因数(greatest common divisor)为1,即gcb(a,b)=1,那么称a,b两数互质。

欧拉函数值

设m为正整数,则1,2,3,4…….,m中与m互素的整数的个数记为,叫做欧拉函数,欧拉函数的值叫做欧拉函数值。

取模运算与同余的概念

如果存在一个正整数m与两个整数a,b,如果a-b能够被m整除,也就是说m|(a-b),那么a和b同余。$$a === b mod(m)$$

模指数运算

模指数运算即先进行指数运算,之后对结果取模运算。例如:$$a === pow(b, c, m)$$

在RSA中涉及的元素

  • N大整数N,我们称之为模数(modulus
  • pq :大整数N的两个因子(factor
  • ed:互为模反数的两个指数(exponent
  • cm:分别是密文和明文,这里一般指的是一个十进制的数还有一个就是n的欧拉函数值,在求解d的时候常用。

RSA算法中密钥的产生

(1)选择两个满足需要的大素数p和q,计算n=p*qphin = (p - 1) * (q - 1),其中phin是n的欧拉函数值。
(2)选一个整数e,满足条件1<e<phin,且gcd(phin,e)=1。通过d * e === 1 mod(phin),计算出d
(3)以{e,n}公开密钥,简称公钥,{d,n}秘密密钥,简称私钥。

针对RSA的攻击方法(未更新完)

对模数n直接攻击(分解)

分解模数n是最直接的攻击方法,也是最困难的方法。攻击者可以获得公钥e和模数n,如果n = p q被成功分解,则攻击者可以计算出phin = (p - 1) (q - 1),进而从d * e === 1 mod(phin) 解得私钥d,之后即可进行解密。

分解因数的网站

推荐链接:http://www.factordb.com/index.php

求解过程及可套用脚本

首先将拿到那个网站上去分解成p和q,然后套用下面脚本:

import gmpy2
p =gmpy2.mpz(18443)    # 这里放p
q =gmpy2.mpz(49891)    # 这里放q
e =gmpy2.mpz(19)    # 这里就是e
phi_n= (p - 1) * (q - 1)    # 这是欧拉函数值
d = gmpy2.invert(e, phi_n)    # 这就是求d * e === 1 mod(phin)的函数
print("d is:" + d)
import gmpy2
n = 920139713     # 这里是n的值
d = 96849619
result = []
with open("rsa.txt") as f:
for i in f:
        result.append(chr(pow(int(i),d,n)))
print(result)

这就是我学的第一种RSA攻击方式了。

公共模攻击

模型

已知两个加密消息,两个e,和同一个大整数N

求解过程及可套用脚本

# coding=utf-8
import os
import gmpy2
import libnum


# 公共模攻击
# 先去http://factordb.com/index.php分解n得到pq即可用本脚本计算
def byte2hex(file):
    return "".join(["%02X" % (ord(bt)) for bt in file]).strip()


def i2s(intnum):
    hexnum = hex(intnum)[2:]
    if len(hexnum) % 2 == 1:
        hexnum = "0" + hexnum
    return ''.join([chr(int(b, 16)) for b in [hexnum[i:i + 2] for i in range(0, len(hexnum), 2)]])


n = gmpy2.mpz(
    0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929)
e1 = gmpy2.mpz(17)    # 这里是你的第一个e
e2 = gmpy2.mpz(65537)    # 这里是你的第二个e
s = gmpy2.gcdext(e1, e2)     # 原本有3个数据,除掉第一个
s1 = s[1]
s2 = s[2]
f1 = open("flag.enc1", "rb").read()
c1 = int(byte2hex(f1), 16)
f2 = open("flag.enc2", "rb").read()
c2 = int(byte2hex(f2), 16)
if s1 < 0:  # 剩下两个数据一正一负,这就是对正负的数做不同的变换
    s1 = -s1
    c1 = gmpy2.invert(c1, n)
elif s2 < 0:
    s2 = -s2
    c2 = gmpy2.invert(c2, n)
m = (gmpy2.powmod(c1, s1, n) * gmpy2.powmod(c2, s2, n)) % n
print str(i2s(m))

小指数e的攻击

貌似是爆破,但是我脚本写不出来了,一直有点问题。

其他(待续)

待续

标签: 无
返回文章列表 文章二维码
本页链接的二维码
打赏二维码