Can you imagine this could be so hard for the Oracle?
Files given:
def keygen(nbit):
while True:
p, q = [getStrongPrime(nbit) for _ in '01']
if p % 4 == q % 4 == 3:
return (p**2)*q, p
def encrypt(m, pubkey):
if GCD(m, pubkey) != 1 or m >= 2**(2*nbit - 2):
return None
return pow(m, 2, pubkey)
def flag_encrypt(flag, p, q):
m = bytes_to_long(flag)
assert m < p * q
return pow(m, 65537, p * q)
The cryptosystem here is simply \(m\mapsto m^2\) and we also have access to a decryption function that is not given in the code. The idea is we first recover \(p^2q\) by taking repeated gcds with \(m^2\) and the output of the encryption. Then somehow if we decrypt \(-1\), the result is of the form \(kp+1\) which makes it extremely easy to solve for \(p\), and hence get the flag.
I’m not exactly sure why this works but randomly throwing unexpected inputs sometimes works!
Solution at solve.py
Flag:
CCTF{___Ra8!N_H_Cryp70_5YsT3M___}