hmg2021 RSA Attack writeup

Re全程白给了,最后转战crypto,压哨提交上了

已知一个 $1024$ 位的 $p1$,$p2$ 比 $p1$ 稍小,根据代码知道 $p3\equiv p2!\pmod{p1}$

根据 Wilson 定理,$n$ 为质数时有 $(n-1)!\equiv -1\pmod{n}$,所以 $p2! \prod\limits_{i=p2+1}^{p1-2}i\equiv 1\pmod{p1}$,所以可以计算出 $p2+1$ 乘到 $p1-1$ 的结果,然后取模拟并调用 sympy 库即可得到 $p3$

import sympy
from libnum import invmod
p1=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649936031
p2=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649902034

res = 1
for i in range(p2 + 1, p1 - 1):
    res = res * i % p1
res = invmod(res, p1)
p3 = sympy.nextprime(res)
p = p3 >> 50 << 50

得到的 $p$ 是最终 RSA 加密用的 $P$ 的高位,因此可以使用 Factoring with High Bits Known 攻击,用 sage 构造如下攻击脚本(网上找的)

p = 0xe53f2ea1ce33f589db34b4c25cc9ce4b47cf2cad37e8bb39df1bf014b3f9982cb89d845eff02d167a9a5e979a1fa8f53803cca71aee02f65275b75129e589c6150b6105cdcd7452d6852b1337ad25c9487e944d28e1fcdbf3a655ec56ee15769d08de7c7b3b0d9e410b6155081062cbd679290ab22f838f8722c000000000000
N = 0xe27e847b1cece6ad3d8a35c27022d94cc14016f9550d41b87b85f946edf0a1c01d8c79a663244143550cfce88038bf29d65070d021991455e4570ea57ea1effc1cf380d572473dc6ea0dc150c431761181e66c578eaeebf156c445d3b6141dda961aa467f4d2c811859534027e5b9e67eb4db051c82602208cfe92674013aafa5b437ae404876ececc2f453bb16734adccc5fb87b16e980e52484f6b9f4bdeb99f2e7dc606bb65628e3f62c7df11abd553ffc6b95d3dda592fa81df5e584687864de702d10669e3aac75ad9c6284b98b44140f347307243b2485f59fa5c3f0eaeaf0addade803f2f09cd4c77f27d672756b9cc62a6325247d8608390e761dc91
pbits = p.nbits()
kbits = 50
PR.<x> = PolynomialRing(Zmod(N))
f = x + p
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print( "x: %s" %hex(int(x0)))
p = p+x0
print ("p: ", hex(int(p)))
assert N % p == 0
q = N/int(p)
print ("q: ", hex(int(q)))

得到 RSA 的 $P$ 和 $Q$,最终构建解密脚本

from libnum import invmod, n2s
p = 0xe53f2ea1ce33f589db34b4c25cc9ce4b47cf2cad37e8bb39df1bf014b3f9982cb89d845eff02d167a9a5e979a1fa8f53803cca71aee02f65275b75129e589c6150b6105cdcd7452d6852b1337ad25c9487e944d28e1fcdbf3a655ec56ee15769d08de7c7b3b0d9e410b6155081062cbd679290ab22f838f8722fbcdcffc1a2ef
q = 0xfced19c7532be88658aaa5e9566f5274b9aefa4c5d21582a24cc48c70b5e3c05c17eb6f85b4732d57bdc0288d1f548b92f4f13a6f7b07d07a01173cefb06fb8f2e3591e5d518d1584a8e27331a4e769eae98537fe1fb380ee804574d98188a4c327c8a1d180ee44b9148d63a07216b40e711970c9f1ea097bfbecfc3b52e787f
phi_n = (p - 1) * (q - 1)
print (n2s(c, invmod(e, phi_n), N))
# flag{w0_x1hu1n_y0u_b5st}
Built with Hugo
Theme Stack designed by Jimmy