Ron was wrong, Whit is right

Se nos proporciona el código fuente utilizado para cifrar la 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}")

También tenemos el resultado (1336 pares de n y c).

Contexto de RSA

Vamos a recordar cómo funciona RSA: $n = p q$, donde $p$ y $q$ son números primos grandes. El exponente $e$ se utiliza para cifrar un mensaje $m$ como se muestra:

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

El proceso de descifrado necesita $\phi(n) = (p - 1) (q - 1)$ y $d = e^{-1} \mod{\phi(n)}$. Luego para descifrar el texto cifrado $c$ podemos calcular:

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

Realizando el ataque

Esta vez, tenemos muchos módulos $n$ diferentes, por lo que es cuestión de suerte que haya algún número primo que sea un factor común de estos valores.

La idea es calcular el Maximo Común Divisor (Greatest Common Divisor, GCD) entre cada par de módulos públicos y mirar si el resultado no es $1$. En ese caso, ambos módulos comparten un factor primo, por lo que podemos descifrar RSA.

Flag

Después de programar un script en Python para comprobar lo expuesto anteriormente, podemos descifrar RSA y capturar la flag:

$ python3 solve.py
ictf{bad_prngs_can_cause_collisions_349d}  

El script completo se puede encontrar aquí: solve.py.