[NCTF2019]babyRSA1

1.题目代码：

# from Crypto.Util.number import *
# from flag import flag
#
# def nextPrime(n):
#     n += 2 if n & 1 else 1
#     while not isPrime(n):
#         n += 2
#     return n
#
# p = getPrime(1024)
# q = nextPrime(p)
# n = p * q
# e = 0x10001
# d = inverse(e, (p-1) * (q-1))
# c = pow(bytes_to_long(flag.encode()), e, n)
#
# # d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
# # c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

2.复现

题目只给了d,c,e。所以我们要求n,我们知道e*d1 mod (p-1)/(q-1)

所以：e*d-1=k*(p-1)(q-1)

因为p和q是1024位的二进制数，所以(p-1)*(q-1)是2048位的二进制数。

我们用print(len(bin(e*d-1)))算出e*d-1是2066位的，2066-2048=16，所以k是16位的二进制数，化为10进制就是在2^15+1-2^16-1之间，所以可以爆破k。这里直接用e*d-1%k==0爆破出的k有很多，所以我们也要同时爆破p,q。用爆破出来的k,求出(p-1)*(q-1)=e*d-1//k,然后对(p-1)*(q-1)进行开根号，很明显p,q位于(p-1)*(q-1)进行开根号的两边，而q是p的下一个素数，所以取(p-1)*(q-1)进行开根号的前一个素数和后一个素数就是p,q。

import gmpy2
import sympy
import libnum
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e = int(0x10001)
# e∗d-1 = k∗ ( p − 1 ) ( q − 1 )
# print(len(bin(e*d-1)))2066-2048=16,相差16位
# 爆破k
p=0
q=0
for k in range(pow(2,15),pow(2,16)):
    if (e*d-1)%k==0:
        phi=(e*d-1)//k
        p=sympy.prevprime(gmpy2.iroot(phi,2)[0])
        q=sympy.nextprime(p)
        if((p-1)*(q-1)==phi):
            print(p)
            print(q)
            break

n=p*q
m=pow(c,d,n)
flag=libnum.n2s(int(m))
print(flag)
# 143193611591752210918770476402384783351740028841763223236102885221839966637073188462808195974548579833368313904083095786906479416347681923731100260359652426441593107755892485944809419189348311956308456459523437459969713060653432909873986596042482699670451716296743727525586437248462432327423361080811225075839
# 143193611591752210918770476402384783351740028841763223236102885221839966637073188462808195974548579833368313904083095786906479416347681923731100260359652426441593107755892485944809419189348311956308456459523437459969713060653432909873986596042482699670451716296743727525586437248462432327423361080811225076497
# b'NCTF{70u2_nn47h_14_v3ry_gOO0000000d}'

总结：已知e,d,c和p,q的位数和生成方式，知道e*d-1和(p-1)*(q-1)的位数，就知道k=e*d-1//(p-1)*(q-1)的范围,爆破k,再利用p<<q,当p,q相差不大时，可以爆破出p,q。