本文简略总结了前人的一些RSA攻击思路，代码或来源于网上或本人原创
并已在GitHub上开源，github地址
aa2K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6&6K9h3k6W2L8X3N6Q4x3X3c8D9k6h3g2Q4x3V1k6d9f1@1q4Q4x3X3c8u0L8W2)9J5k6p5y4f1c8R3`.`.
同时exp也附于附件上
RSA加密算法是一种非对称加密算法，1977年由Ron Rivest、Adi Shamir和Leonard Adleman一起提出的，算法安全性依赖于极大整数做因数分解的难度
1.随意选择两个大素数p和q，且p不等于q，计算N=p*q
2.计算n的欧拉函数φ(n) = (p-1)(q-1)（常用phi(n)表示φ(n)）
3.选择一个整数e，满足1< e < φ(n)，且e与φ(n) 互质（e通常取65537）
4.计算模反元素d，ed ≡ 1 (mod φ(n)) 即求解ex + φ(n)y = 1方程组（利用扩展欧几里得算法可以求出d）
d = gmpy2.invert(e, (p-1)*(q-1))
5.得到公钥（N，e）私钥（N，d）
6.加密 c = pow(m,e,N)
7.解密 m = pow(c,d,N)
gmpy2 安装
sudo apt install libmpc-dev
pip/pip3 install gmpy2
sage安装
ee8K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6E0K9i4u0J5L8%4u0K6i4K6u0W2N6s2g2F1j5g2)9J5k6i4c8K6K9h3&6Y4K9s2g2S2i4K6u0W2k6h3c8#2i4K6u0W2j5$3&6Q4x3V1k6K6j5h3N6W2L8h3q4@1K9q4)9J5c8X3I4A6L8Y4g2^5i4K6u0r3y4U0c8T1K9i4c8Q4x3V1k6A6L8X3c8W2P5q4)9J5k6h3S2@1L8h3H3`.
d = gmpy2.invert(e,(p-1) * (q-1))
m = gmpy2.powmod(c,d,n)
第一种情况
给出 p,q,c,e且gcd(e, (p-1)*(q-1))非常小(可能为3)
example:
p,q = 3881, 885445853681787330351086884500131209939
c = 1926041757553905692219721422025224638913707
e = 33
第二种情况
给出n1,n2,e1,e2,c1,c2求满足以下式子
assert p = gcd(n1,n2)
assert pow(flag,e1,n1)==c1
assert pow(flag,e2,n2)==c2
assert gcd(e1,(p1-1) (q1-1))==gcd(e2,(p2-1) (q2-1))
m ^ e = kn + c 其中一般 e = 3，k比较小(k小于10亿爆破时间一般小于半小时)
c1 ≡ m^e mod n1
c2 ≡ m^e mod n2
……
ce ≡ m^e mod ne
如以上所示，e比较小，题目给出n[e]和c[e],且m相同，利用中国剩余定理可以求m
与低加密指数攻击相反，需要满足e非常大，接近于N
c1 ≡ m^e1 mod n
c2 ≡ m^e2 mod n
如以上使用了相同的模数N对相同的明文进行加密
e 非常大接近于N，跟低解密指数攻击类似，比低解密指数攻击更强，可以解决d<N的0.292次方的问题
知道p的高位为p的位数的约1/2时即可
如果知道d的低位，低位约为n的位数的1/4就可以恢复d
给出两组数据
n1,c1,e1,n2,c2,e2且无以上特征可尝试gcd(n1,n2)得到公因子（存在的话）
给出一组数据
n1,c1,e1
尝试yafu或856K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3k6S2j5%4c8G2M7X3c8T1i4K6u0W2j5$3!0E0i4@1f1#2i4K6R3^5i4K6R3$3i4@1f1^5i4@1p5%4i4@1p5K6L8W2)9J5z5s2m8Q4x3V1y4I4i4@1f1%4i4K6W2n7i4@1t1^5i4@1f1#2i4@1t1%4i4@1q4q4i4@1f1^5i4@1u0r3i4K6R3%4i4@1f1#2i4@1p5@1i4@1p5%4i4@1f1$3i4K6R3^5i4K6V1$3i4@1f1^5i4@1u0r3i4K6R3%4i4@1f1#2i4@1t1H3i4K6S2r3P5h3q4X3N6g2!0q4y4g2)9^5c8W2!0m8c8W2!0q4y4g2)9^5z5q4)9^5y4W2!0q4z5q4!0m8y4#2!0m8x3#2!0q4y4W2)9^5z5q4)9&6x3q4!0q4y4g2)9^5b7g2)9&6c8W2)9J5z5b7`.`.
给出如下数据
p,q,nextprime(p),nextprime(q)
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
