本文最后更新于51 天前,其中的信息可能已经过时,如有错误可以直接在文章下留言
题目描述
littlE littlE RSA Big Big Dangerous
题目给的附件内容如下
#n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e: 0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?
n的数值很大,无法分解,而e很小,不再是常见的65537。
这要用到低加密指数攻击,根据RSA加密算法的原理,有 c ≡ me (mod n)
在e=3时,则 c ≡ m3 (mod n)
因为这里的n很大,不确定m的大小,则有两种情况
即若 me<n ,则 c = me,可以通过对c进行开方得到m
若 me>n ,则 me = kn+c,我们可以通过爆破k,若k满足kn+c能够开e次方,那么就可以得到明文
解题脚本如下
from Crypto.Util.number import *
import gmpy2
e = 0x3
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
k = 0
while 1:
res = gmpy2.iroot(c+k*n,e) #c+k*n 开3次方根 能开3次方即可
#print(res)
#res = (mpz(13040004482819713819817340524563023159919305047824600478799740488797710355579494486728991357), True)
if(res[1] == True):
print(long_to_bytes(res[0])) #转为字符串
break
k=k+1
#输出b'flag{25df8caf006ee5db94d48144c33b2c3b}'
关键函数,iroot 函数的介绍如下
这里打印返回的mpz(),代表括号内的数字是一个多精度整数
所以flag就是flag{25df8caf006ee5db94d48144c33b2c3b}