Layer7 CTF | Child Coppersmith - crypto-writeup-public

from Crypto.Util.number import bytes_to_long

flag = "LAYER7{CENSORED}"

p = random_prime(2^512)
q = random_prime(2^512)

N = p * p * q
e = 0x10001

piN = p * (p-1) * (q-1)

d = inverse_mod(e, piN)
m = bytes_to_long(flag)

ct = pow(m, e, N)

assert pow(ct, d, N) == m

hint = (p * q) % 2^600

print((N, e, ct))
print(hint)

RSA

$N = p^2q$

$hint = pq \mod 2^{600}$

が与えられている $N = hint * p$ としてみてunivariate coppersmith methodでsmall rootを求めるだけでいい

nec, hint = open("enc.txt").read().strip().split("\n")

N, e, c = eval(nec)
hint = int(hint)

PR.<x> = PolynomialRing(Zmod(N), implementation="NTL")
g = x * 2 ** 600  + hint
f = g.monic()

r = f.small_roots(X=2**(1024 - 600), beta=0.5, epsilon=0.05)
# pq = int(r[0]) * 2 ** 600  + hint
pq = int(g(r[0]))

print("[+]pq:", pq)

assert pq != 1
assert pq != N
assert N % pq == 0

p = N // pq
q = N // (p * p)

phi = p * (p-1) * (q-1)
d = inverse_mod(e, phi)
m = power_mod(c, d, N)

print("[+]flag:", bytes.fromhex(hex(m)[2:]))