RRSSAA

2 minutos de lectura

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 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 tiene un total de factores primos de 256 bits, por lo que no es fácil de factorizar.

Solución

Obsérvese que 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 , 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 , luego calcular y finalmente usar el CRT para recuperar .

Esto funciona porque es enorme, por lo que con unos cuantos factores es suficiente para descifrar el mensaje. En realidad, la salida del CRT es para cierto . No somos capaces de factorizar en sus factors, pero es suficiente ya que el módulo del CRT es más grande que el mensaje como número entero ( bits de flag y 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.