CakeCTF 2022 | frozen cake - crypto-writeup-public

#CakeCTF2022

from Crypto.Util.number import getPrime
import os

flag = os.getenv("FLAG", "FakeCTF{warmup_a_frozen_cake}")
m = int(flag.encode().hex(), 16)

p = getPrime(512)
q = getPrime(512)

n = p*q

print("n =", n)
print("a =", pow(m, p, n))
print("b =", pow(m, q, n))
print("c =", pow(m, n, n))

RSAで、フェルマーの小定理を使う

$c \equiv m^n \equiv m^{n - (n - p - q + 1)} \equiv m^{p + q - 1} \mod n$

より、 $c * (ab)^{-1} \equiv m^{p+q-1 - p - q} \equiv m \mod n$

from Crypto.Util.number import inverse

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

m = inverse(c * inverse(a*b, n) % n, n)
print(bytes.fromhex(hex(m)[2:]))