Midnight Sun CTF Qualifiers 2023 | ikea

#midnight_sun_ctf_qualifiers_2023

p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)

def read_flag(file='flag.txt'):
    with open(file, 'rb') as fin:
        flag = fin.read()
    return flag

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

def generate_keys(p, q):
    n = p * q
    e = 0x10001
    return n, e

def encrypt_message(m, e, n):
    return pow(m, e, n)

flag = read_flag()
m = pad_flag(flag)

n, e = generate_keys(p, q)
assert m < n

c = encrypt_message(m, e, n)

print(c)
print(n)
print(p + b^2 * q)
print(a^2 * p + q)

RSA でヒントがあるので素因数分解せよ、という問題

$X = p + b^2q$ と $Y = a^2p + q$ が渡されている
$XY = a^2p^2 + n + a^2b^2n + b^2q^2$ で、 $a^2b^2n$ の項が他に比べて大きいから、 $\sqrt{XY / n} \approx ab$ という近似ができる
これで4式4変数になるのであとは groebner basis とかでゴリ押す

with open("output.txt") as f:
    c = int(f.readline().strip())
    n = int(f.readline().strip())
    X = int(f.readline().strip())
    Y = int(f.readline().strip())

for d in range(-50, 50):
    Z = ceil(sqrt(X*Y / n)) + d


    PR.<a,b,p,q> = QQ[]
    polys = [
        n - p*q,
        Z - a*b,
        X - (p + b**2*q),
        Y - (a**2*p + q),
    ]
    I = Ideal(polys)
    ans = I.variety(ring=ZZ)
    if len(ans) == 0:
        continue

    p = int(ans[0][p])
    assert n % p == 0
    q = n // p

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

    print(bytes.fromhex(hex(m)[2:]))
    quit()