本文简略总结了前人的一些RSA攻击思路,代码或来源于网上或本人原创。
https://github.com/yifeng-lee/RSA-In-CTF
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))sudo apt install libmpc-devhttps://mirrors.tuna.tsinghua.edu.cn/sagemath/linux/64bit/index.htmld = gmpy2.invert(e,(p-1) * (q-1))给出 p,q,c,e且gcd(e, (p-1)*(q-1))非常小(可能为3)。p,q = 3881, 885445853681787330351086884500131209939c = 1926041757553905692219721422025224638913707给出n1,n2,e1,e2,c1,c2求满足以下式子:assert pow(flag,e1,n1)==c1assert pow(flag,e2,n2)==c2assert gcd(e1,(p1-1) (q1-1))==gcd(e2,(p2-1) (q2-1))
m ^ e = kn + c 其中一般 e = 3,k比较小(k小于10亿爆破时间一般小于半小时)。如以上所示,e比较小,题目给出n[e]和c[e],且m相同,利用中国剩余定理可以求m。与低加密指数攻击相反,需要满足e非常大,接近于N。0x05 Boneh and Durfee attacke 非常大接近于N,跟低解密指数攻击类似,比低解密指数攻击更强,可以解决d<N的0.292次方的问题。0x06 Coppersmith 攻击:已知p的高位攻击0x07 Coppersmith攻击:已知明文高位攻击0x08 Coppersmith攻击:已知d的高位攻击如果知道d的低位,低位约为n的位数的1/4就可以恢复d。0x09 Coppersmith攻击:明文高位相同0x0A 已知dp或dq(dp=d mod p-q , dq=d mod q-1)0x0B Least Significant Bit Oracle Attackn1,c1,e1,n2,c2,e2且无以上特征可尝试gcd(n1,n2)得到公因子(存在的话)。尝试yafu或http://www.factordb.com分解n(p,q相差过大或过小yafu可分解成功)。p,q,nextprime(p),nextprime(q)n2 = nextprime(p) * nextprime(q)https://www.tr0y.wang/2017/11/06/CTFRSA/index.html
http://inaz2.hatenablog.com/entry/2016/01/20/022936看雪ID:丿feng
https://bbs.pediy.com/user-809191htm
*本文由看雪论坛 丿feng 原创,转载请注明来自看雪社区进阶安全圈,不得不读的一本书
文章来源: http://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458298868&idx=1&sn=da18d859dc6984a1c08e4dc264045294&chksm=b181997e86f6106885bda9c93252689866ce7c10af117c3e7f1d0cb01a922b4b43664b71e667#rd
如有侵权请联系:admin#unsafe.sh