RSA攻击方法整理

2019-04-13 16:28发布

站内文章 / 模拟电子
15811 0 1696
class="markdown_views prism-github-gist"> RSA算法简述 ① 选两个保密的大素数p和q。 ② 计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。 ③ 选一整数e，满足1 需要注意点
  1. 公钥和私钥互为逆元隐含着1
  2. gcd(φ(n),e)=1(即φ(n)和e互素)则一定存在一组s1，s2使得s1*φ(n)+s2*e=1
    一般出题方式
    pem文件：网络中的证书文件，里面藏着n，e用
    openssl rsa -pubin -text -modulus -in warmup -in public.pem
    可以提取出来
    flag.enc文件：被加密后的文件
    .py文件：加密算法
0x01模数分解 得到φ(n)之后的计算原理：de=1 mod φ(n)且gcd(e,φ(n))=1 即de=k*φ(n)+1 ==> de+k*φ(n)=1 分解思路： 直接分解：爆破（利用工具比较稳） 适用：n比较小的情况（512bit-768bit以内） 查询了解一下：http://factordb.com 利用公约数： 如果有2个n，并且2个n有相同的公约数 欧几里得算法时间复杂度为O(log n)即使是4096bit也是秒破。 分解之后的计算 #coding=utf-8 import gmpy2 p = 3487583947589437589237958723892346254777 q = 8767867843568934765983476584376578389 e = 65537 def modinv(a,m): g,y,x=gmpy2.gcdext(a,m) if g!=1: raise Exception('modular inverse does not exist') else: return x%m #加密的时候说d是e的逆元也就是d和e的取值范围相同,所以得到的d是唯一的 #x*a+y*φ(n)=1 gcd(x,y)=1 #de=1mod φ(n) 即de=k*φ(n)+1==>de+k*φ(n)=1 d=modinv(e,(p-1)*(q-1)) #d=f(e,fai(n)) print d #d为私钥 分解方式
1.直接分解
小素数分解工具msieve
安装方法 wget http://downloads.sourceforge.net/project/msieve/msieve/Msieve%20v1.52/msieve152.tar.gz tar zxvf msieve152.tar.gz mv msieve-1.52 msieve cd msieve make all 测试 ➜ msieve ./msieve 0x1bc89d92391beeb473fbaa776c751f38e9da272c05b835132776a8114df29a7b01286c0f623af 2.利用公约数
简介：如果有2个n，并且2个n有相同的公约数欧几里得算法时间复杂度为O(log n)即使是4096bit也是秒破。
特征：有不止一个n，n比较大，无从下手。 def gcd(a, b): if a < b: a, b = b, a while b != 0: temp = a % b a = b b = temp print a return a if __name__ == '__main__': n1=input("n1:") n2=input("n2:") gcd(n1,n2) 3.查询：
http://factordb.com 4.yafu分解 在p，q的取值差异过大，或者p，q的取值过于相近的时候，Format方法与Pollard rho方法都可以很快将n分解成功。 此类分解方法有一个开源项目yafu将其自动化实现了，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。
使用
在这里插入图片描述
https://www.cnblogs.com/pcat/p/7508205.html 下载
https://sourceforge.net/projects/yafu/ 0x02低加密指数分解 低加密指数：当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。 原理：加密为c=m^e mod n 解密为m=c^d mod n 分析：如果e过小（m^e 在m^e=k*n+c中m是要求的，e，n，c已知，需要爆破n。
在开e次方得到整数的时候这时候的k和m是需要的值。
识别：在e比较小的时候使用这种方法（一般是3）
https://www.jarvisoj.com (Extremely hard RSA) #!/usr/bin/python # coding=utf-8 import gmpy from Crypto.PublicKey import RSA def calc(j): a, b = gmpy.root(cipher + j * N, 3) if b > 0: m = a print '{:x}'.format(int(m)).decode('hex') # pool.terminate() # 读入公钥 with open('pubkey.pem', 'r') as f: key = RSA.importKey(f) N = key.n e = key.e # 读入密文 with open('flag.enc', 'r') as f: cipher = f.read().encode('hex') cipher = int(cipher, 16) # 暴力破解 inputs = range(0, 118720000) result = [] map(calc, inputs) print len(result) 低加密指数广播攻击 c1=m^e mod n1 c2=m^e mod n2 c3=m^e mod n3 在e=3时可以得到c_x=m^3 mod (n_1*n_2*n_3) 对c_x开3次方可以的出明文。 识别：3组密文，公钥相同，由同一个明文加密而成。
https://github.com/ctfs/write-ups-2014/blob/master/hack-you-2014/crypto/400/README.md
低解密指数攻击
就是解密指数也就是秘钥d比较小呗
解法上工具吧https://github.com/pablocelayes/rsa-wiener-attack 识别：只管的看起来就是e比较大 0x03
共模攻击 说明：如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值。(e_1和e_2互素) c_1=m^(e_1)mod n c_2=m^(e_2)mod n 需要：密文c_1,c_2 并且n相同. 结果： c_1^{s_1}*c_2^{s_2}=m mod n s_1*e_1+s_2*e_2=1 证明：gcd (e_1,e_2)=1 即存在s_1 ，s_2使得： s_1*e_1+s_2*e_2=1 又因为： c_1= m^{e_1}mod n c_2= m^{e_2} mod n 通过代入化简可以得出： c_1^{s_1}*c_2^{s_2}= m mod n 识别：不只有一个c，有相同的n
例题 https://www.jarvisoj.com (very hard RSA) #coding=utf-8 import gmpy2 from libnum import n2s,s2n n=0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L e1=17 e2=65537 fo1=open("flag.enc1",'rb') fo2=open("flag.enc2","rb") datafo1=fo1.read() message1=s2n(datafo1) fo1.close() datafo2=fo2.read() message2=s2n(datafo2) gcd,s,t=gmpy2.gcdext(e1,e2) print message1 print gcd,s,t #s和t一定有一个位负数，若s<0,求a^s <=> (1/a)^(-s) plain=gmpy2.powmod(message1 ,s,n)*gmpy2.powmod(message2,t,n)%n print plain print n2s(plain) #gcdext(...) gcdext(a, b) returns a 3-element tuple (g, s, t) such that #g == gcd(a, b) and g == a * s + b * t #invert(...) invert(x, m) returns y such that x * y == 1 modulo m, or 0 if no such y exists.
总结
题目按照如下顺序测试
直接分解：适用n比较短，跑一下msieve
利用公因数：公因数分解有2个n比较大没有其他特征有限使用
查询：接着尝试查询
yafu：再尝试yafu
低加解密指数：如果e比较小，或者比较大，没有其他东西，试一下低加解密指数
共模攻击：2个密文，一个n2个不同的公钥互素
参考https://www.anquanke.com/post/id/84632

热门文章