Tokyo Westerns CTF 3rd 2017 BabyRSA

babyrsa.py

from Crypto.Util.number import long_to_bytes, inverse
import gmpy2

n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
e = 65537

enc = 238128932536965734026453335534508678486770867304645614119195536048961186128744314667991999168452564298994773996973787655358503271491181214369796509942047091225518293577154563021214085132019889288510474458242494876257330038265066123460887568813277411779817556316602871932730284368524299559699693787556478631297630514938453794107136748994144175123917418701679413905695916367530746728699301383100433069740863537869450361306987480687067608102552418211244703552910903168179094472596152349098076535870469807035136435631458879919434041758274344589567529971195683495146426258135341109919085270442486183365562919531353370683625

q = gmpy2.isqrt(4*19*n) + 1
print q
q2 = q*q - (4*19*n)
print q2
print gmpy2.iroot(q2,2)

q3 = gmpy2.iroot(q2,2)[0]

p = -q3 + gmpy2.isqrt( q3*q3 + 4 * 19 * n )
p = p / 38
print p
print n%p
q = n/p

d = inverse(e, (p-1)*(q-1))
m = pow(enc,d,n)
print long_to_bytes(m)

exit(0)

# TWCTF{secretly_cherry-blossom-viewing}

今回使われるp,qは、それぞれ

p_ = rand(2**1024)
q_ = 19 * p_ + rand(2**512)
p = next_prime(p_)
q = next_prime(q_)

で生成される。2^1024で試してみると、素数間の距離は長くても1000程度であり、当初のpと大きく差が無いことが分かる。
p = p_ + x, q = q_ + y（x,yは小さな整数）
と表すと、
q = (19*p_) + rand(2^512) + y
となり、最終的に
q = 19*p + z
と表すことができる。(z = -19*x + rand(2^512) + y: 2^512程度の数）
よって、
n = p*q = 19*p^2 + z*p
このことから
19*p^2 + z*p - n = 0
という二次方程式を解けばpが求まることが分かる。この二次方程式の判別式を考えると
z^2 + 4*19*n
ここで、4*19*nは少なくとも2^2048以上という相当に大きい数字になる。
二次方程式の解の公式を考えると
p = (-z + sqrt( z^2 + 4*19*n )) / 2*19
この式に解があることは前提条件から保証されている。4*19*nという2^2048以上の大きな数字にz^2という2^1024程度の数字を足しても、sqrtの変化は1未満であることを考えれば、判別式Dの値はD=isqrt( 4*19*n )+1で導出できる。
ここから、zの値はz = sqrt(D^2-( 4*19*n ))と計算できる。最終的にpは
p = (-z + sqrt(z^2 + 4*19*n ) ) / 2*19
で答えが導出できることが分かる。
あとはRSAを普通に解けば良い。