brevi moduli

3 minutos de lectura

Se nos proporciona el código fuente del servidor en Python:

from Crypto.Util.number import isPrime, getPrime, bytes_to_long
from Crypto.PublicKey import RSA

rounds = 5
e = 65537

for i in range(rounds):
    print('*'*10, f'Round {i+1}/{rounds}', '*'*10)

    pumpkin1 = getPrime(110)
    pumpkin2 = getPrime(110)
    n = pumpkin1 * pumpkin2
    large_pumpkin = RSA.construct((n, e)).exportKey()
    print(f'\n🎃Can you crack this pumpkin🎃?\n{large_pumpkin.decode()}\n')

    assert isPrime(_pmp1 := int(input('enter your first pumpkin = '))), exit()
    assert isPrime(_pmp2 := int(input('enter your second pumpkin = '))), exit()  

    if n != _pmp1 * _pmp2:
        print('wrong! bye...')
        exit()

    print()

print(open('flag.txt').read())

Análisis del código fuente

El código fuente es realmente simple. Básicamente crea una clave privada RSA y nos muestra la clave pública asociada. Nos piden determinar la clave privada un total de 5 veces:

$ nc 94.237.48.144 36050
********** Round 1/5 **********

🎃Can you crack this pumpkin🎃?
-----BEGIN PUBLIC KEY-----
MDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcC5l+O+HbqLmHzutZrecmsJzOiTtoqsNk  
nesPTwIDAQAB
-----END PUBLIC KEY-----

enter your first pumpkin =

Contexto de RSA

En RSA, la clave privada se compone principalmente de dos números primos $p$ y $q$.Se supone que estos números son grandes (normalmente, tienen 1024 bits). Por otro lado, la clave pública posee el exponente $e = 65537$ y el módulo $n = p \cdot q$.

La seguridad de este criptosistema se basa en el hecho de que la factorización de números enteros es un problema computacionalmente difícil incluso para ordenadores potentes. Por lo tanto, dado el módulo público $n$, podemos decir que es imposible factorizarlo en $p$ y $q$ si no se proporciona más información.

Solución

Esta vez, los números primos $p$ y $q$ son muy pequeños en comparación con lo que los estándares recomiendan. Como se puede ver, son enteros de 110 bits. Existen algoritmos de factorización que pueden lidiar con estas longitudes de bits y pueden factorizar estos módulos en un tiempo relativamente corto. Por ejemplo, el método de factorización de curva elíptica (ECM) (también conocido como factorización de curva elíptica de Lenstra).

Implementación

El algoritmo de factorización ECM viene implementado en SageMath, como ecm.factor.Sin embargo, podemos simplemente usar la función factor predeterminada porque hará lo mismo.

Como resultado, estos son los pasos para resolver cada ronda del reto:

Analizar la clave pública y tomar el módulo $n$
Factorizar $n$ en $p$ y $q$
Responder con $p$ y $q$

Y este es el código para la solución:

#!/usr/bin/env python3

from pwn import remote, sys
from Crypto.PublicKey import RSA
from sage.all import factor

host, port = sys.argv[1].split(':')
io = remote(host, port)

for _ in range(5):
    io.recvuntil(b'?\n')

    publickey = io.recvuntil(b'-----END PUBLIC KEY-----').decode()
    key = RSA.import_key(publickey)

    (p, _), (q, _) = factor(key.n)
    io.sendlineafter(b'enter your first pumpkin = ', str(p).encode())
    io.sendlineafter(b'enter your second pumpkin = ', str(q).encode())  

io.interactive()

Flag

Aquí tenemos la flag:

$ python3 solve.py 94.237.48.144:36050
[+] Opening connection to 94.237.48.144 on port 36050: Done  
[*] Switching to interactive mode

HTB{cracking_pumpkins_and_small_rsa_moduli_for_a_living}
[*] Got EOF while reading in interactive
$