ACTF 2022 | impossible RSA - crypto-writeup-public

#ACTF_2022

from Crypto.Util.number import *
from Crypto.PublicKey import RSA

e = 65537
flag = b'ACTF{...}'

while True:
    p = getPrime(1024)
    q = inverse(e, p)
    if not isPrime(q):
        continue
    n = p * q;
    public = RSA.construct((n, e))
    with open("public.pem", "wb") as file:
        file.write(public.exportKey('PEM'))
    with open("flag", "wb") as file:
        file.write(long_to_bytes(pow(bytes_to_long(flag), e, n)))
    break

RSAで $q = e^{-1} \mod p$

$eq = 1 + kp$ なので $en = peq = p + kp^2$

$k$ は十分小さいだろうから全探索して、 $kp^2 + p - ne = 0$ という二次方程式を解く

from Crypto.Util.number import getPrime, inverse, isPrime, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from tqdm import tqdm
from gmpy2 import iroot

key = RSA.import_key(open("public.pem").read())

n = key.n
e = key.e


for k in tqdm(range(1, e)):
    a = k
    b = 1
    c = -n*e

    x, ok = iroot(b**2 - 4*a*c, 2)
    if not ok:
        continue

    if (b + x) % (2*a) == 0:
        p = int(abs((b + x) // (2*a)))
        break

    if (b - x) % (2*a) == 0:
        p = int(abs((b - x) // (2*a)))
        break

q = n // p
d = pow(e, -1, (p-1)*(q-1))

c = bytes_to_long(open("flag", "rb").read())
m = pow(c, d, n)

print(long_to_bytes(m))