Ron was wrong, Whit is right

We are given the source code used to encrypt the flag:

#!/usr/bin/env python

from Crypto.Util import number

flag = open("flag.txt", "rb").read()  
m = number.bytes_to_long(flag)
e = 65537

for _ in range(1336):
    q = number.getPrime(1024)
    p = number.getPrime(1024)

    n = p * q
    c = pow(m, e, n)
    print(f"{n},{c}")

We also have the output (1336 pairs of n and c).

RSA background

Let’s review how RSA works: $n = p q$, where $p$ and $q$ are some large prime numbers. The exponent $e$ is used to encrypt a message $m$ as follows:

$$ c = m^e \mod{n} $$

The decryption process needs $\phi(n) = (p - 1) (q - 1)$ and $d = e^{-1} \mod{\phi(n)}$. Then to decrypt the ciphertext $c$ we can compute:

$$ m = c^d \mod{n} $$

Performing the attack

This time, we have so many different public modulus $n$, so it is just a matter of luck that there is a shared prime factor among these values.

The idea is to compute the Greatest Common Divisor (GCD) between each pair of public modulus and check if the output is not $1$. Then, both public moduli share a common prime factor and we can decrypt RSA.

Flag

So, after coding a solution script in Python, we can decrypt RSA and find the flag:

$ python3 solve.py
ictf{bad_prngs_can_cause_collisions_349d}  

The full script can be found in here: solve.py.