WeakRSA

点击此处获得更好的阅读体验

---

WriteUp 来源

https://xz.aliyun.com/t/1589

题目考点

解题思路

已知部分 d 的最低有效位，是可以还原出 d 的，原理部分。但对于已知的位数是有要求的

其中 M=2^k，k 是 d 的最低有效位的位数出题时没测试好，本来是要给的位数不够还原，需要爆破的，给下脚本

#!/usr/bin/python
#-*- coding:utf-8 -*-
 
import sys, re
from libnum import nroot
from Crypto.Util.number import size
 
n = 24129492308224479830531863430667763206113500947912894148049103046436751018902380216549212087945014575866175372699327952352562583984599024982322742653474650254469019243745562427155195911292231061633627557914070970650388286259815766552728485153840458510677169495483383264554397982155108666923510839292748291941615629484247125025729363254239159271724680451974211566266307311323012908187153011368890695841034381925365547836453167672856111790684457634738536647974450864723943635507973978195453912898978987904396630176208142995219377309529324099766495068346782530074954504554550936100220114319876296005855618193837568032249
e = 65537
 
low_d2 = 585021050422437790400309277934736421671174903453118287773262727237276990096608684311252820485289582300237832073420122197911787329400438609843024619449229662477502424617432168933632994437196549098808097025413678738558952555239079729908003264517051128647960060385270607296895534639200191803399174999679917012421
low_bits = 1028
test = pow(3, e, n)
 
i = 0
prefix = []
for a in range(2):
    for b in range(2):
        prefix.append(str(a) + str(b))
 
for bf in prefix:
    low_d = int(bin(low_d2)[2:], 2)
    for k in xrange(1, e):
        d = (k * n + 1) / e
        d >>= low_bits
        d <<= low_bits
        d |= low_d
        if (e * d) % k == 1:
            if pow(test, d, n) == 3:
                    print k, d

Flag

无