foobarCTF 2022 | babyrsa - crypto-writeup-public

#foobarCTF_2022

from Crypto.Util.number import *

flag = b"GLUG{**********REDACTED***************}"

p,q = getPrime(1024),getPrime(1024)
N = p * p * q
e = 0x10001
phi = p * (p-1) * (q-1)

d = inverse(e, phi)
m = bytes_to_long(flag)
c = pow(m, e, N)
x = (p * q) % 2**1337

print("N =  {}".format(N))
print("e =  {}".format(e))
print("c = {}".format(c))
print("x =  {}".format(x))

RSA

$n = p^2q$

$x = pq \mod 2^{1337}$ かつ $p, q < 2^{1024}$

$n * x^{-1} \equiv p \mod 2^{1337}$ が成り立つのでやるだけ

from Crypto.Util.number import inverse

with open("output.txt") as f:
    n = int(f.readline().split(" =  ")[1])
    e = int(f.readline().split(" =  ")[1])
    c = int(f.readline().split(" =  ")[1])
    x = int(f.readline().split(" =  ")[1])


p = n * inverse(x, 2**1337) % (2**1337)
q = n // (p**2)

d = inverse(e, p * (p-1) * (q-1))
m = pow(c, d, n)

print(m.to_bytes(100, "big"))