[NCTF2020]babyRSA

题目描述

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

这道题给出了c,d,e,没有给p,q,但是p,q是相邻的素数，所以只需要知道n或者phiN就能把p,q爆破出来。
根据扩展欧几里得算法:ax+by=gcd(a,b)可以得到一组整数解（d,k），题目d已给出，所以可以列如下方程：
e * d + phiN * y = gcd(e,phiN),phiN * y = 1 - e * d,根据以往经验可知y的值不会很大，所以这里用for循环爆破。
（写脚本的时候忘记加break导致在这道题上浪费了两个多小时。。）
exp如下：

import gmpy2
from Crypto.Util.number import *


def nextPrime(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n


def check(phiN):
    tmp = gmpy2.iroot(phiN, 2)[0]
    while True:
        if isPrime(tmp):
            break
        else:
            tmp = tmp - 1
    if (tmp - 1) * (nextPrime(tmp) - 1) == phiN:
        return tmp


e = 65537
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
phiNy = 1263276724786485833820889643051708344849417985755595487219919790861521311233190055401020770751191124694549589042182800211800883338235699297206179117430743526738441426391986230201786173703879718588289330011662648464832295666077054769889634578358630646511023034020014559708844709384915702114119981847563803823151396546437464442781871774330912743089912241233606515436818023218823232106596887320756980171544889845523493947146416583343202444459446863209442943852835426970462374916733061574745498850302067362222759925985414929821670098656412210796212981431198008380580101528500867414250720415928258285351513440053966549817753280
p = 0
q = 0
for i in range(2, 100000):
    if (gmpy2.gcd(e, phiNy // i) == 1) & (d == gmpy2.invert(e, phiNy // i)):
        phiN = phiNy // i
        p = check(phiN)
        if p is not None:
            q = nextPrime(p)
            break
c = pow(c, d, p * q)
print(long_to_bytes(c))

NCTF{70u2_nn47h_14_v3ry_gOO0000000d}