N1CTF 2021 | checkin - crypto-writeup-public

#n1ctf2021

from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p*q
x = 2021*p+1120*q
h = (inverse(x,n)+x)%n
e = 65537
c = pow(bytes_to_long(flag), e, n)

print('n =', n)
print('c =', c)
print('h =', h)
print('p0 =', p >> 490)

概要

RSA
$x = 2021p + 1120q$ として $h = (x + x^{-1}) \mod n$ と $p$ の上位20bit程度( $p_0$ ）が与えられている

作戦

まず、 $n // (p_0 * 2^{490}) \approx q_0 * 2^{490}$ である
- したがって $x \approx q_0*2^{490} * 2021 + q_0*2^{490}*1120$
また $xh = x(x + x^{-1}) = x^2 + 1 \mod n$ が成り立つ
$x$ の未知bitを univariate coppersmith method で求めるのはどうか

exploit

n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
p0 = 4055618

# ---

approx_p = p0*2**490
approx_q = n // approx_p
approx_x = 2021*approx_p + 1120*approx_q

PR.<x0> = PolynomialRing(Zmod(n))
x = approx_x + x0

f = x*h - (x**2 + 1)
f = f.monic()

t1 = cputime()
roots = f.small_roots(X=2**500, beta=1, epsilon=0.02)
t2 = cputime()

print("[+] time: {}".format(t2 - t1))

x = approx_x + int(roots[0])

PR.<p, q> = PolynomialRing(QQ)
ans = Ideal([n - p*q, x - (2021*p + 1120*q)]).variety(ring=ZZ)[0]
p = ans[p]
q = ans[q]

# ---

d = inverse_mod(65537, (p-1)*(q-1))
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))