-
-
[原创]看雪CTF2017第10题
-
2017-6-19 18:21 2961
-
1. 处理逻辑(大数运算用的gmp)
sn长度为70, 前6位是e, 后面的是p
已知 n, d, p<q, 求e, p, q
n: 6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189 d: 2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B
2. 求解
因为e<0x1000000, 所以可以穷举e, 得到e: F552B3
有了e, 因为e过小, 可以直接得到p和q
这里借用stackoverflow上的内容
3. 脚本
import itertools from gmpy2 import * #e=0xF552B3 n=0x6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189 d=0x2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B def get_e(n,d): for i in itertools.count(0xFFFFFF, -1): if i <= 2: return 0 e=i if not is_prime(e, 500): continue m=0x12345678 c=powmod(m,d,n) m2=powmod(c,e,n) if m == m2: return e return 0 def get_p_q(e,n,d): ed=mul(e,d) k1=div(ed, n) kk=[k1-1,k1,k1+1] for i in range(len(kk)): k=kk[i] (t, rem)=t_divmod(ed-1,k) if (rem != 0): continue s = n + (1) - (t) r =isqrt(mul(s,s)-mul(4,n)) p=div(s+r,2) q=div(s-r,2) if (p > q): p=q print('sn: %X%X' % (e,p)) return e=get_e(n,d) print('e: %X' % e) get_p_q(e,n,d)
[培训]二进制漏洞攻防(第3期);满10人开班;模糊测试与工具使用二次开发;网络协议漏洞挖掘;Linux内核漏洞挖掘与利用;AOSP漏洞挖掘与利用;代码审计。
赞赏
他的文章
KCTF2022春季赛 第三题 石像病毒
8276
KCTF2022春季赛 第二题 末日邀请
15399
KCTF2021秋季赛 第二题 迷失丛林
17935
KCTF2020秋季赛 第十题 终焉之战
8106
KCTF2020秋季赛 第九题 命悬一线
5831
看原图