ctfshow unusualrsa(续)

unusualrsa4

# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long
from gmpy2 import invert
from secret import flag

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(invert(q,p))

e = 0x10001
d = invert(e,(p-1)*(q-1))
print(d)

c = pow(m,e,n)
print(c)


qp=113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
d=27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
c=619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291

这题不会，看了某些佬的wp，总结一下，题目有如下提示：

 所以我们对e和k的比特位数进行比较

有ed=1+k*phi,phi=(p-1)*(q-1)所以phi差不多有2048位，d和phi大致只相差一位或位数相等，所以e和k的位数应该也大差不差，可以通过爆破求得k,条件是e*d-1模k等于0

 记inv(q,p)=q1,

(q1*phi)modp

=q1*(p-1)*(q-1)modp

=(q1*p*q-q1*p-q1*q+q1)%p           #q1*q=1,它们在模p下互为逆元

=(q1-1)%p

(q1-1)-(q1*phi)=omodp

所以设kp=(q1-1)-(q1*phi)  #kp是p得倍数

 有费小马定理,所以有

对于任意得r,k1,k2当k1为k2得因子时，rmodk2=(rmodk1)mod k2

我们对a取两个简单的值

 再求x1和x2的公因数就可以得到p了，但是这里a取2和3不知道为啥不能出

q1 = 113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
c = 619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291
# print(len(bin(p)))
for k in range(1, e):

    if (e * d - 1) % k == 0:
        phi = (e * d - 1) // k
        print(phi)
        kp = q1 * phi - q1 + 1
        x1 = pow(3, phi, kp) - 1
        x2 = pow(5, phi, kp) - 1
        p = gmpy2.gcd(x1, x2)
        if p.bit_length() == 1024:
            q = phi // (p -1)+1
            n = p * q
            assert d == inverse(e, phi)
            m = pow(c, d, n)
            print(long_to_bytes(m))
#flag{wh47_1f_y0u_kn0w_1nv3r7_q_p~?}