Bancarrota

Categoría: Crypto Dificultad: Hard

Descripción del reto

El reto entrega un output.txt con los siguientes datos públicos:

n = 88414814868035811675053476790757183219833077857790658518374191743395116845115061528008085663634920575725860680618605233668935227198665125936037136388097458649126677107202112594942802316604869417510426361858052660647273709287613460403410412181509561538712695138630895924830183589161717870494320335995725649113
e = 65537
c = 30250981509850990129207765287429103048296430271684860662908644684691614716869020256328990837924296007698218340267714279683758265003409499090708049047183680954260669691735105649990968201405808149637466756340163849831054862762698907574073537414698212342127587114243405245474354105150576516832016218254233551030
p_msb = 6384482865957816600821075381730956442412139232241618654154874067983428432778076832168977
unknown_bits = 220

El enunciado indica que el sistema RSA de una entidad bancaria ha filtrado los bits más significativos de uno de los primos usados para generar la clave.

La pregunta real del reto es:

¿Se puede romper RSA si solo conocemos una parte de uno de sus factores?

La respuesta es sí, si esa parte filtrada es suficientemente grande y la parte desconocida es suficientemente pequeña como para usar un ataque de Coppersmith / small roots.

1. Análisis inicial

En un RSA estándar se publica:

• n

• e

• y a veces el ciphertext c

Pero aquí aparece además:

• p_msb

• unknown_bits

Eso ya indica que no estamos ante un RSA “normal”, sino ante un RSA con fuga parcial de clave.

Un jugador que vea esto debería pensar inmediatamente:

• p_msb representa la parte alta de p

• faltan unknown_bits bits por recuperar

• por tanto, p puede modelarse como una parte conocida más una parte pequeña desconocida

La observación clave es:

p = (p_msb << unknown_bits) + x

donde:

• p_msb << unknown_bits es la parte conocida de p

• x es la parte desconocida

• y x < 2^unknown_bits

En este reto:

• conocemos todos los bits altos de p

• faltan 220 bits bajos

• eso hace que x sea una raíz pequeña

Y ahí es donde entra Coppersmith.

2. Fundamento teórico

RSA usa dos primos p y q para construir:

n = p * q

La seguridad depende de que factorizar n sea difícil.

Pero si conocemos parcialmente uno de esos primos, podemos escribir:

p = a + x

donde:

• a es la parte conocida

• x es la parte desconocida y pequeña

En este caso:

a = p_msb << unknown_bits

y el primo real es:

p = a + x

Como p divide a n, si logramos recuperar x, recuperamos p, luego q, y RSA queda roto por completo.

El método de Coppersmith permite encontrar raíces pequeñas de polinomios módulo un entero compuesto. Aquí usamos el polinomio:

f(X) = a + X

y buscamos una raíz pequeña x tal que:

a + x = p

con p divisor de n.

3. Idea del ataque

El atacante piensa así:

1. Tengo n, e, c y una fuga parcial de p

2. Construyo la parte conocida:

3. Escribo:

p = a + x

1. Como x es pequeño, pruebo un ataque de small_roots

2. Recupero p

3. Calculo q = n / p

4. Recupero d

5. Descifro c

4. Solución con Sage

La forma práctica y estándar de resolver este tipo de reto en CTF es con SageMath.

Script completo

from sage.all import *

# Datos públicos del reto
n = Integer(88414814868035811675053476790757183219833077857790658518374191743395116845115061528008085663634920575725860680618605233668935227198665125936037136388097458649126677107202112594942802316604869417510426361858052660647273709287613460403410412181509561538712695138630895924830183589161717870494320335995725649113)

e = Integer(65537)

c = Integer(30250981509850990129207765287429103048296430271684860662908644684691614716869020256328990837924296007698218340267714279683758265003409499090708049047183680954260669691735105649990968201405808149637466756340163849831054862762698907574073537414698212342127587114243405245474354105150576516832016218254233551030)

p_msb = Integer(6384482865957816600821075381730956442412139232241618654154874067983428432778076832168977)

unknown_bits = Integer(220)

# Parte conocida de p
a = p_msb << unknown_bits

print("[*] Parte conocida de p reconstruida")
print("[*] Probando varias configuraciones de Coppersmith...")

# Polinomio f(x) = a + x sobre Z/nZ
PR.<x> = PolynomialRing(Zmod(n))
f = x + a

found = False
x0 = None

# Varias configuraciones para dar margen al ataque
for beta in [0.40, 0.45, 0.49]:
    for extra in [0, 4, 8, 12]:
        X = 2^(int(unknown_bits) + extra)
        print(f"[*] Intentando beta={beta}, X=2^({int(unknown_bits)+extra})")
        roots = f.small_roots(X=X, beta=beta)
        if roots:
            x0 = Integer(roots[0])
            found = True
            break
    if found:
        break

if not found:
    print("[-] No se encontró raíz pequeña con esta instancia.")
    raise SystemExit

p = a + x0

print("[+] Candidato a p encontrado")

if n % p != 0:
    print("[-] La raíz encontrada no factoriza n.")
    raise SystemExit

q = n // p

print("[+] Factorización correcta")
print(f"p = {p}")
print(f"q = {q}")

# Recuperar clave privada
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)

# Descifrar
m = power_mod(c, d, n)

# Convertir a bytes
msg = int(m).to_bytes((int(m).bit_length() + 7) // 8, "big")

print("[+] Flag:")
print(msg.decode())

5. Explicación detallada del script

5.1 Carga de datos

n = Integer(...)
e = Integer(...)
c = Integer(...)
p_msb = Integer(...)
unknown_bits = Integer(220)

Aquí se cargan los parámetros públicos del reto.

• n es el módulo RSA

• e es el exponente público

• c es el ciphertext

• p_msb es la parte alta filtrada del primo p

• unknown_bits indica cuántos bits faltan

5.2 Reconstrucción parcial de p

a = p_msb << unknown_bits

Desplazar a la izquierda unknown_bits posiciones equivale a colocar los bits altos en su posición correcta dentro del entero.

Eso construye la parte conocida del primo:

p ≈ a

pero aún faltan los bits bajos:

p = a + x

5.3 Construcción del polinomio

PR.<x> = PolynomialRing(Zmod(n))
f = x + a

Esto define el polinomio:

f(x) = a + x

trabajando módulo n.

La idea es que queremos encontrar un valor pequeño x tal que a + x sea realmente el factor p de n.

5.4 Búsqueda de raíz pequeña

roots = f.small_roots(X=X, beta=beta)

Esta es la parte central del ataque.

Coppersmith permite encontrar raíces pequeñas de polinomios módulo un entero compuesto. Aquí le decimos a Sage:

• X = tamaño máximo aproximado de la raíz

• beta = parámetro del algoritmo

El script prueba varias combinaciones porque en la práctica algunas instancias necesitan pequeños ajustes para converger.

5.5 Validación del candidato

p = a + x0
if n % p != 0:
    ...

Aunque small_roots devuelva algo, siempre hay que comprobar que de verdad factoriza n.

Si p divide a n, entonces hemos recuperado el primo correcto.

5.6 Recuperación de q

q = n // p

Una vez recuperado p, el otro factor es inmediato.

5.7 Cálculo de la clave privada

phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)

Con los factores ya obtenidos, RSA se rompe de forma estándar:

• calculamos phi(n)

• calculamos el inverso modular de e

• obtenemos d

5.8 Descifrado

m = power_mod(c, d, n)

Aplicamos la fórmula RSA de descifrado:

m = c^d mod n

5.9 Conversión a texto

msg = int(m).to_bytes((int(m).bit_length() + 7) // 8, "big")
print(msg.decode())

Esto transforma el entero descifrado en bytes y luego en texto legible.

6. Resultado

La salida del script es:

THL{...}

Este reto demuestra una idea muy importante en criptografía aplicada:

RSA no solo falla si alguien factoriza n por fuerza bruta; también puede romperse si se filtra suficiente información parcial sobre uno de sus factores.