RSA is really simple, there can't be any mistakes, right?
Solution
Given code below
#!/usr/bin/env -S python3 -u
import os
from Crypto.Util.number import isPrime, bytes_to_long
import random
def getPrime(n_bits, verbose=False):
while True:
a = random.getrandbits(n_bits)
if isPrime(a):
return a
elif verbose:
print(f"Sadly, {a} was not prime")
p = getPrime(1024, verbose=True)
q = getPrime(1024)
flag = os.getenv("flag","EPFL{fake_flag}").encode()
n = p * q
e = 65537
print(f"Ciphertext: {pow(bytes_to_long(flag), e, n)}")
getPrime function generate random number using random.getrandbits and if random number is prime it will be returned from the function. random.getrandbits is not secure random generator, we can predict next value if we have 624 * 32 bits number generated by getrandbits. So in this case, because we know random number generated from getrandbits we can regenerate the p and q and decrypt the ciphertext. Since randcrack need 32 bits value so we submit each value received from the server in 32 bit format. Here is my solve script
from pwn import *
from randcrack import RandCrack
import os
from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytes
def getPrime(n_bits):
while True:
a = rc.predict_randrange(0, (2**1024)-1)
if isPrime(a):
return a
def submit_crack(tmp):
while tmp > 0:
try:
rc.submit(tmp % (1 << 32))
tmp = tmp >> 32
except Exception as e:
break
r = remote("chall.polygl0ts.ch", 9022)
rc = RandCrack()
tmp = int(r.recvline().strip().decode().split("Sadly, ")[-1].split(" was not prime")[0])
while tmp > 0:
if(tmp.bit_length() <= 512):
rc.submit(tmp % (1 << 32))
tmp = tmp >> 32
for i in range(19):
tmp = int(r.recvline().strip().decode().split("Sadly, ")[-1].split(" was not prime")[0])
submit_crack(tmp)
tmp = r.recvline().strip().decode()
while "Ciphertext: " not in tmp:
tmp = r.recvline().strip().decode()
ct = int(tmp.split(" ")[-1])
p = getPrime(1024)
q = getPrime(1024)
e = 65537
n = p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(ct, d, n)))
