Wani CTF 2023 | pqqp

wani_ctf_2023 rsa フェルマーの小定理

#wani_ctf_2023

import os

from Crypto.Util.number import bytes_to_long, getPrime

flag = os.environb.get(b"FLAG", b"FAKE{THIS_IS_FAKE_FLAG}")

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
d = pow(e, -1, (p - 1) * (q - 1))

m = bytes_to_long(flag)
c = pow(m, e, n)
s = (pow(p, q, n) + pow(q, p, n)) % n

print(n)
print(e)
print(c)
print(s)

RSA。 s = (p^q + q^p) \mod n が与えられてる。フェルマーの小定理より p^q + q^p \equiv 0 + q \mod p, p^q + q^p \equiv p + 0 \mod qなので s = p + q \mod n

import ast

f = open("output.txt")

n = ast.literal_eval(f.readline().strip())
e = ast.literal_eval(f.readline().strip())
c = ast.literal_eval(f.readline().strip())
s = ast.literal_eval(f.readline().strip())

d = pow(e, -1, n - s + 1)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))