Cryptography

Challenge

Link

KeySharer (50 pts)

Here

Random RSA (50 pts)

Here

Vigenere-CBC (50 pts)

Here

Choices (460 pts)

Here

KeySharer (50 pts)

Description

Solution

Random RSA (50 pts)

Description

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)))