本文简略总结了前人的一些RSA攻击思路，代码或来源于网上或本人原创
并已在GitHub上开源，github地址
https://github.com/yifeng-lee/RSA-In-CTF
同时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安装
https://mirrors.tuna.tsinghua.edu.cn/sagemath/linux/64bit/index.html
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或http://www.factordb.com分解n(p,q相差过大或过小yafu可分解成功)
给出如下数据
p,q,nextprime(p),nextprime(q)
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
