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: , where and are some large prime numbers. The exponent is used to encrypt a message as follows:

The decryption process needs and . Then to decrypt the ciphertext we can compute:

Performing the attack

This time, we have so many different public modulus , 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 . 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.