RRSSAA

My primes are prefectly random. I wonder if you can find them.

Challenge contributed by CryptoHack

Challenge files:

• output.txt
• RRSSAA.py

Análisis del código fuente

Se nos proporciona el siguiente script de Python que usa RSA para cifrar la flag:

flag = open("flag.txt", "rb").read().strip()
assert len(flag) == 128
N = prod(get_prime(i) for i in range(2, len(flag)))
print(hex(N), hex(pow(bytes_to_long(flag), 0x10001, N)))  

La configuración de RSA no es la habitual. Esta vez, tenemos una configuración de RSA multiprimo, donde cada factor primo del módulo $n$ se calcula con get_prime:

def get_prime(n):
    p = 1
    r = random.Random()
    r.seed(randbelow(2**n))
    while not isPrime(p):
        p = r._randbelow(2**256) | 1  
    return p

El módulo $n$ tiene un total de $128$ factores primos de 256 bits, por lo que no es fácil de factorizar.

Solución

Obsérvese que $n$ se calcula como N = prod(get_prime(i) for i in range(2, len(flag))), por lo que los primeros factores primos son fáciles de obtener por fuerza bruta, ya que podemos forzar la semilla de random.seed y calcular p = r._randbelow(2**256) | 1 until we have a prime number.

En un poco de tiempo, podemos obtener alrededor de 16 factores primos de $n$, que es lo que necesitamos para encontrar la flag.

Como se usa RSA multiprimo, podemos descifrar la flag usando RSA-CRT. Esto es solo encontrar $d_i = e^{-1} \mod{p_i - 1}$, luego calcular $m_i = c^{d_i} \mod{p_i}$ y finalmente usar el CRT para recuperar $m$.

Esto funciona porque $n$ es enorme, por lo que con unos cuantos factores es suficiente para descifrar el mensaje. En realidad, la salida del CRT es $m \mod{p_1 \cdot p_2 \cdots p_k}$ para cierto $k$. No somos capaces de factorizar $n$ en sus $128$ factors, pero $k = 5$ es suficiente ya que el módulo del CRT es más grande que el mensaje $m$ como número entero ($128 * 8 = 1024$ bits de flag y $256 * 5 = 1280$ bits de módulo de CRT).

Flag

Podemos escribir el procedimiento anterior en un script de Python y encontrar la flag:

$ python3 solve.py
ECSC{brute_it_like_bruce_49a22a7465edcdeab5b01ffcd325110382c6f93f4d1d898be0569e5f97efe557574b28c83b6209a509dbfea1c45f06c5518928}  

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