BUUCTF [NCTF2019]babyRSA解题思路

BUUCTF [NCTF2019]babyRSA

这是一道RSA的题目，前几天看祥云杯的RSA做到自闭，做点简单的题转换一下心情。
下载文件之后是一个压缩包，里面有一个py文件，题目如下：

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

首先明确这个公式：

∵e*d=1mod(p-1)(q-1)
∴e*d-1=k(p-1)(q-1)

根据题目我们已经知道了p和q分别是1024位的，所以他们的乘积是2048位的，接着我们来算e*d,他们的乘积是一个2064位的，所以k最多是一个16位的数字（不可能超过16位）
附上解题脚本：

e = 0x10001
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
import sympy.crypto
import gmpy2
ed1=e*d-1
p=0
q=0
for k in range(pow(2,15),pow(2,16)):
    if ed1%k==0:
        p=sympy.prevprime(gmpy2.iroot(ed1//k,2)[0])
        q=sympy.nextprime(p)
        if (p-1)*(q-1)*k==ed1:
            break
n=p*q
print(n)
m=gmpy2.powmod(c,d,n)
print(m)
import binascii
print(binascii.unhexlify(hex(m)[2:]))

运行稍等一会便得到了flag
flag:NCTF{70u2_nn47h_14_v3ry_gOO0000000d}

来给大家解释一下脚本的含义：我们需要**k来得出p和q,经过分析我们已经确定了k的范围，这是一个大的框架，如果ed-1与k之间的关系满足(ed-1)%k=0,则满足了(ed-1)%(p-1)(q-1)=0，也就满足了这个公式。然后我们在这个框架里面来接着进行**，让(ed-1)与k进行整除，得到的就是(p-1)(q-1),因为q就是p紧接着的下一个素数，所以我们对(e*d-1)//k进行开方，这也就是iroot的用法。
在这里可以画个图给大家，虽然不是很正确但是对于理解有很大的帮助：

A—q------B----p----C
如上图，我们可以想象成一开始是两个相同的数进行相乘得到(ed-1),对(ed-1)进行开方之后得到一个数，我们让这个数小一点变成了一个数，又让这个数大一点变成了另一个数，这个就是这个脚本的意义
于是题目也因此解开