RsaCtfTool — Ataques Matemáticos a RSA

🔐

Cómo Funciona RSA

Fundamentos matemáticos de la criptografía de clave pública

RSA (Rivest-Shamir-Adleman, 1977) es el algoritmo de clave pública más utilizado en la historia de la criptografía. Basa su seguridad en la dificultad computacional de factorizar el producto de dos números primos grandes. Comprender por qué es seguro cuando se implementa correctamente es la clave para entender por qué se rompe cuando se implementa mal.

🔐GENERACIÓN DE CLAVES RSA PASO A PASO

Paso 1: Elegir dos primos grandes

p y q — primos aleatorios grandes (al menos 1024 bits cada uno en la práctica)

Deben ser grandes, aleatorios e independientes. La seguridad de RSA depende enteramente de que p y q sean secretos.

Paso 2: Calcular el módulo

N = p × q

N es la parte pública. Cualquiera puede conocer N. Factorizar N para recuperar p y q es computacionalmente inviable con primos grandes.

Paso 3: Calcular la función de Euler

φ(N) = (p-1) × (q-1)

También conocido como la función totient. Es completamente secreta porque requiere conocer p y q.

Paso 4: Elegir el exponente público

e: 1 < e < φ(N), mcd(e, φ(N)) = 1

Los valores más comunes son e=65537 (0x10001), e=3 y e=17. La clave pública es el par (N, e).

Paso 5: Calcular el exponente privado

d: e × d ≡ 1 (mod φ(N))

d es el inverso modular de e. Se calcula con el algoritmo extendido de Euclides. La clave privada es (N, d).

Cifrado: c = m^e mod N — Descifrado: m = c^d mod N

⚠

Debilidades Matemáticas de RSA

Cuándo y por qué RSA es vulnerable

RSA es seguro en teoría, pero en la práctica existen numerosas formas en que una implementación incorrecta lo hace completamente rompible. Las vulnerabilidades no son fallos en el algoritmo matemático, sino errores en cómo se generan o usan los parámetros.

Debilidad	Causa	Ataque resultante	Dificultad de romperlo
N muy pequeño	Primos p, q pequeños (<512 bits)	Factorización directa	Trivial (<segundos)
p y q cercanos entre sí	p ≈ q, ambos cerca de √N	Factorización de Fermat	Muy fácil
d pequeño (e enorme)	e > N^3/4	Ataque de Wiener	Fácil
Primos compartidos	Mismo p en dos módulos distintos	GCD attack	Trivial
e pequeño (e=3) + sin padding	Mismo mensaje cifrado con 3 claves distintas	Ataque de Hastad (CRT)	Fácil
Mensajes relacionados + e=3	Dos mensajes m, m+k cifrados con la misma clave	Franklin-Reiter	Moderado
Sin padding (textbook RSA)	Cifrado directo sin OAEP/PKCS	Múltiples ataques	Moderado

📌 CONTEXTO EDUCATIVOEstos ataques se estudian en cursos de criptografía universitarios, certificaciones de seguridad y competiciones CTF. Comprender por qué RSA se rompe cuando se implementa mal es fundamental para implementarlo correctamente.

🔧

RsaCtfTool

Instalación y uso básico

RsaCtfTool es una herramienta Python de código abierto que implementa docenas de ataques matemáticos conocidos contra implementaciones débiles de RSA. Es la herramienta de referencia en competiciones CTF (Capture The Flag) para los retos de criptografía RSA. Acepta claves en múltiples formatos (PEM, n/e directamente, archivos de texto) y puede intentar todos los ataques automáticamente.

Instalar RsaCtfTool

# Clonar el repositorio
git clone https://github.com/RsaCtfTool/RsaCtfTool.git
cd RsaCtfTool

# Instalar dependencias
pip3 install -r requirements.txt

# O con pipx:
pipx install rsactftool

# Verificar instalaci&oacute;n:
python3 RsaCtfTool.py --help

# Dependencias importantes:
# - sympy      (factorizaci&oacute;n algebraica)
# - gmpy2      (aritm&eacute;tica de precisi&oacute;n m&uacute;ltiple rapida)
# - pycryptodome (operaciones criptograficas)
# - requests   (consultas a factordb.com)
sudo apt install python3-gmpy2 -y

🔧SINTAXIS GENERAL DE RSACTFTOOL

Opciones principales de RsaCtfTool

# Modo 1: Solo n y e (sin clave PEM)
python3 RsaCtfTool.py --n N_VALUE --e E_VALUE --uncipher CIPHERTEXT

# Modo 2: Archivo de clave publica PEM
python3 RsaCtfTool.py --publickey clave_publica.pem --uncipher cifrado.txt

# Modo 3: Descifrar archivo con multiples claves
python3 RsaCtfTool.py --publickey *.pem --uncipher cifrado.txt

# Listar todos los ataques disponibles:
python3 RsaCtfTool.py --list-attacks

# Forzar un ataque especifico:
python3 RsaCtfTool.py --publickey key.pem --attack wiener --uncipher c.txt
python3 RsaCtfTool.py --publickey key.pem --attack fermat --uncipher c.txt

# Intentar TODOS los ataques automaticamente:
python3 RsaCtfTool.py --publickey key.pem --attack all --uncipher c.txt

# Solo obtener la clave privada (sin descifrar):
python3 RsaCtfTool.py --publickey key.pem --private

📊

Ejercicio 1 — Factorización Directa (N Pequeño)

Cuando N es tan pequeño que se puede factorizar en segundos

Factorización Directa

N pequeño: bases de datos de primos o algoritmos de factorización general

N PEQUEÑO

Si N tiene menos de ~512 bits (155 dígitos decimales), puede factorizarse en segundos con herramientas modernas. Con N menor de 200 bits, es trivial incluso en CPU. La web factordb.com mantiene una base de datos de millones de números ya factorizados.

Por qué funciona

N = p × q → si N es pequeño, probar todos los primos hasta √N es rápido

Para N de 64 bits, √N ≈ 4 × 10⁹, y los algoritmos modernos lo factorizan en microsegundos.

Generar una clave RSA débil (N pequeño)

# LABORATORIO: generamos primos pequenos a proposito
# para demostrar el ataque

# Generar clave RSA debil en Python:
python3 << 'EOF'
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

# Primos DELIBERADAMENTE pequenos para el laboratorio
p = getPrime(64)   # Solo 64 bits - trivialmente factorizable
q = getPrime(64)
N = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)  # Inverso modular

print(f'p = {p}')
print(f'q = {q}')
print(f'N = {N}')
print(f'e = {e}')
print(f'd = {d}')
print(f'Bits de N: {N.bit_length()}')

# Cifrar un mensaje de prueba
mensaje = b'Hola RSA CTF'
m = bytes_to_long(mensaje)
c = pow(m, e, N)
print(f'Ciphertext c = {c}')
EOF

Romper la clave con RsaCtfTool

# Usando los valores N, e, c del paso anterior:

# Metodo 1: RsaCtfTool con ataque automatico
python3 RsaCtfTool.py \
  --n TU_N_AQUI \
  --e 65537 \
  --uncipher TU_C_AQUI

# Metodo 2: RsaCtfTool consulta factordb.com automaticamente
# para N pequenos ya conocidos

# Metodo 3: Factorizar con sympy directamente (Python)
python3 << 'EOF'
from sympy import factorint
from Crypto.Util.number import long_to_bytes

N = TU_N_AQUI
e = 65537
c = TU_C_AQUI

# Factorizar N (instantaneo para 128 bits)
factores = factorint(N)
print('Factores encontrados:', factores)

p, q = list(factores.keys())
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, N)

print('Mensaje descifrado:', long_to_bytes(m))
EOF

❓ Ejercicio práctico

Genera una clave RSA con primos de 64 bits, cifra el mensaje 'CTF_FLAG_AQUI' y luego factoriza N para recuperar el mensaje original. Usa RsaCtfTool con --attack factordb

💡 Pista: Genera el N, e, c con el script de Python, luego pasa esos valores a RsaCtfTool.py --n ... --e ... --uncipher ...

Ver solución

python3 RsaCtfTool.py --n N --e 65537 --uncipher C --- RsaCtfTool intentara factorizar N via factordb.com y otros metodos. Con N de 128 bits lo resuelve en segundos. El resultado muestra el plaintext descifrado.

🧮

Ejercicio 2 — Factorización de Fermat

Cuando p y q son demasiado cercanos entre sí

Factorización de Fermat

p y q muy próximos: N = (a+b)(a-b) = a² - b²

p ≈ q

El método de factorización de Fermat (1643) explota que si p y q son próximos, N puede expresarse como diferencia de cuadrados: N = a² - b² = (a+b)(a-b). El algoritmo busca el valor de a partiendo de √N hacia arriba hasta que a² - N sea un cuadrado perfecto.

Principio matemático

N = p × q , sea a = (p+q)/2 , b = (p-q)/2 Entonces: N = a² - b² Si p ≈ q → b ≈ 0 → a ≈ √N Buscamos a partiendo de ceil(√N) hasta que a² - N sea cuadrado perfecto Luego: p = a + b , q = a - b

Si p y q difieren en menos de N^(1/4), Fermat lo factoriza casi instantáneamente.

Generar clave vulnerable a Fermat (p y q cercanos)

python3 << 'EOF'
from Crypto.Util.number import getPrime, bytes_to_long
import random

# Generamos p, y luego q muy cercano a p
p = getPrime(512)
# q generado en el rango [p, p + 2^20] -- DEBIL a proposito
q = p + random.randint(2, 2**20)
# Aseguramos que q sea primo
from sympy import nextprime
q = nextprime(q)

N = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

mensaje = b'Fermat_Attack_Demo'
m = bytes_to_long(mensaje)
c = pow(m, e, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'Diferencia p-q = {abs(p-q)}')
print(f'N = {N}')
print(f'c = {c}')
EOF

Implementar el ataque de Fermat en Python

python3 << 'EOF'
import math
from Crypto.Util.number import long_to_bytes

def fermat_factorization(N):
    """Factorizacion de Fermat: busca a tal que a^2 - N sea cuadrado perfecto"""
    a = math.isqrt(N)  # Raiz cuadrada entera de N
    if a * a == N:
        return a, a  # N es cuadrado perfecto
    
    a += 1  # Empezar desde ceil(sqrt(N))
    b2 = a * a - N
    
    iteraciones = 0
    while True:
        b = math.isqrt(b2)
        if b * b == b2:  # b2 es cuadrado perfecto!
            return a + b, a - b  # p = a+b, q = a-b
        a += 1
        b2 = a * a - N
        iteraciones += 1
        if iteraciones % 10000 == 0:
            print(f'  Iteracion {iteraciones}...')

# Usar con N del ejercicio anterior:
N = TU_N_AQUI
e = 65537
c = TU_C_AQUI

print('Ejecutando factorizacion de Fermat...')
p, q = fermat_factorization(N)
print(f'p encontrado: {p}')
print(f'q encontrado: {q}')
print(f'Verificacion: p*q == N? {p*q == N}')

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, N)
print(f'Mensaje: {long_to_bytes(m)}')
EOF

Usar RsaCtfTool con el ataque de Fermat

# RsaCtfTool implementa Fermat automaticamente
python3 RsaCtfTool.py \
  --n TU_N \
  --e 65537 \
  --uncipher TU_C \
  --attack fermat

# O con archivo PEM:
python3 RsaCtfTool.py \
  --publickey clave_fermat.pem \
  --attack fermat \
  --uncipher cifrado.bin

❓ Ejercicio práctico

Genera una clave donde p y q difieren en menos de 1000. Aplica la factorización de Fermat. ¿Cuántas iteraciones necesita el algoritmo? ¿Qué pasa si la diferencia es 2^30?

💡 Pista: Si la diferencia es muy pequeña, Fermat termina en 1-2 iteraciones. Si es grande, necesita muchas más.

Ver solución

Con diferencia menor de 1000: 1-500 iteraciones (instantaneo). Con diferencia de 2^30: ~500 millones de iteraciones (puede tardar minutos/horas dependiendo del hardware). La defensa: generar p y q completamente independientes con fuentes de aleatoriedad separadas, lo que hace su diferencia del orden de N/2.

📈

Ejercicio 3 — Ataque de Wiener

Cuando d es demasiado pequeño (e demasiado grande)

Ataque de Wiener (1990)

d pequeño → e enorme: fracciones continuas revelan d

d PEQUEÑO

El ataque de Wiener explota que, para acelerar el descifrado RSA, algunos implementadores eligen un exponente privado d pequeño (lo que implica que e será enormemente grande). Michael Wiener demostró en 1990 que si d < N^1/4/3, entonces d puede recuperarse eficientemente usando aproximaciones de fracciones continuas de e/N.

Condición de vulnerabilidad

Si d < (1/3) × N^(1/4) Entonces d puede recuperarse de la expansion en fracciones continuas de e/N

Para N de 2048 bits, esto significa que d debe ser menor de aproximadamente N^0.25 ≈ 2^512. Parece grande, pero un implementador que elige d=3 o d=65537 directamente crea exactamente este problema en reversa.

Generar clave vulnerable a Wiener

python3 << 'EOF'
import random
from sympy import isprime
from math import gcd
from Crypto.Util.number import bytes_to_long

# Para Wiener necesitamos d pequeno, lo que implica e enorme
# Generamos p, q normales pero elegimos d pequeno

def generate_wiener_vulnerable():
    # Primos de 512 bits
    from Crypto.Util.number import getPrime
    p = getPrime(512)
    q = getPrime(512)
    N = p * q
    phi = (p-1)*(q-1)
    
    # Elegir d PEQUENO a proposito (vulnerable a Wiener)
    # d debe ser < N^(1/4) / 3 para que el ataque funcione
    umbral = int(N**(0.25) / 3)
    
    # Encontrar un d pequeno que sea invertible mod phi
    d = random.randint(2, umbral)
    while gcd(d, phi) != 1:
        d = random.randint(2, umbral)
    
    # Calcular e como inverso de d mod phi
    e = pow(d, -1, phi)  # e sera enorme
    
    return N, e, d, p, q

N, e, d, p, q = generate_wiener_vulnerable()
print(f'N = {N}')
print(f'e = {e}')
print(f'd = {d}  (secret - pequeno!)')
print(f'Bits de d: {d.bit_length()}')
print(f'Umbral Wiener (N^1/4/3): {int(N**(0.25)/3)}')
print(f'Vulnerable: {d < int(N**(0.25)/3)}')

mensaje = b'Wiener_Attack'
m = bytes_to_long(mensaje)
c = pow(m, e, N)
print(f'c = {c}')
EOF

Implementar el ataque de Wiener con fracciones continuas

python3 << 'EOF'
from math import isqrt
from Crypto.Util.number import long_to_bytes

def continued_fraction(numerator, denominator):
    """Genera los coeficientes de la fraccion continua de num/den"""
    coeffs = []
    while denominator:
        q = numerator // denominator
        coeffs.append(q)
        numerator, denominator = denominator, numerator - q * denominator
    return coeffs

def convergents(coeffs):
    """Calcula los convergentes de una fraccion continua"""
    convergents_list = []
    h_prev, h_curr = 1, coeffs[0]
    k_prev, k_curr = 0, 1
    convergents_list.append((h_curr, k_curr))
    for i in range(1, len(coeffs)):
        h_prev, h_curr = h_curr, coeffs[i]*h_curr + h_prev
        k_prev, k_curr = k_curr, coeffs[i]*k_curr + k_prev
        convergents_list.append((h_curr, k_curr))
    return convergents_list

def wiener_attack(e, N):
    """Ataque de Wiener: recuperar d de e/N via fracciones continuas"""
    coeffs = continued_fraction(e, N)
    convs = convergents(coeffs)
    
    for k, d in convs:
        if k == 0:
            continue
        # Si k es un convergente valido, phi = (e*d - 1) / k
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        # Verificar si phi es valido: resolver x^2 - (N-phi+1)x + N = 0
        b = N - phi + 1
        discriminante = b*b - 4*N
        if discriminante < 0:
            continue
        sqrt_disc = isqrt(discriminante)
        if sqrt_disc * sqrt_disc == discriminante:
            # Encontrado! p y q son las raices del polinomio
            p = (b + sqrt_disc) // 2
            q = (b - sqrt_disc) // 2
            if p * q == N:
                return d, p, q
    return None

# Usar con los valores del ejercicio anterior:
N = TU_N_AQUI
e = TU_E_AQUI
c = TU_C_AQUI

print('Ejecutando ataque de Wiener...')
result = wiener_attack(e, N)
if result:
    d, p, q = result
    print(f'd recuperado: {d}')
    print(f'p = {p}')
    print(f'q = {q}')
    m = pow(c, d, N)
    print(f'Mensaje: {long_to_bytes(m)}')
else:
    print('Wiener no encontro solucion')
EOF

Wiener con RsaCtfTool

# RsaCtfTool implementa Wiener directamente
python3 RsaCtfTool.py \
  --n TU_N \
  --e TU_E_ENORME \
  --uncipher TU_C \
  --attack wiener

# Wiener mejorado (Boneh-Durfee, permite d hasta N^0.292):
python3 RsaCtfTool.py \
  --n TU_N \
  --e TU_E \
  --attack boneh_durfee \
  --uncipher TU_C

❓ Ejercicio práctico

El ataque de Wiener usa fracciones continuas de e/N. ¿Por qué esto funciona? ¿Qué propiedad matemática garantiza que uno de los convergentes sea k/d?

💡 Pista: Piensa en el teorema de aproximación de fracciones continuas: si |x - p/q| < 1/(2q²), entonces p/q es un convergente de x.

Ver solución

El teorema de Wiener demuestra que si d < N^(1/4)/3, entonces k/d (donde k es un entero relacionado con phi) satisface |e/N - k/d| < 1/(2d^2). Esto garantiza que k/d sea un convergente de la fraccion continua de e/N por el teorema de aproximacion de Dirichlet. Por eso el algoritmo simplemente itera sobre todos los convergentes hasta encontrar uno que, al reconstruir phi, permita verificar que p*q=N.

🧮

Ejercicio 4 — Ataque de Factores Comunes (GCD)

Cuando dos módulos distintos comparten un factor primo

GCD Attack (Factores Comunes)

mcd(N1, N2) revela un factor primo compartido instantáneamente

PRIMOS COMPARTIDOS

Si dos módulos N1 y N2 comparten un factor primo p (es decir, N1 = p*q1 y N2 = p*q2), entonces el Máximo Común Divisor de N1 y N2 revela p instantáneamente. Este error ocurre cuando el generador de números aleatorios del sistema está sesgado o tiene poca entropía, produciendo el mismo primo en múltiples generaciones.

Un estudio de 2012 (Lenstra et al.) analizó millones de claves RSA públicas en internet y descubrió que el 0.2% de las claves de 1024 bits eran vulnerables a este ataque.

Por qué funciona

Si N1 = p × q1 y N2 = p × q2 (comparten p) Entonces: mcd(N1, N2) = p Una vez conocido p: q1 = N1 / p q2 = N2 / p phi1 = (p-1)(q1-1) → d1 = e^-1 mod phi1 phi2 = (p-1)(q2-1) → d2 = e^-1 mod phi2

La complejidad del ataque es O(log N), simplemente el algoritmo de Euclides. Trivialmente rápido incluso para claves de 4096 bits.

Demostrar el ataque GCD

python3 << 'EOF'
from math import gcd
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

# Simular generador de numeros aleatorios defectuoso:
# reutiliza el mismo primo p en dos claves distintas
p = getPrime(512)   # Primo compartido (ERROR del generador)
q1 = getPrime(512)  # Primos independientes
q2 = getPrime(512)

N1 = p * q1  # Clave 1
N2 = p * q2  # Clave 2 - comparte p con N1
e = 65537

# Cifrar mensajes distintos
phi1 = (p-1)*(q1-1)
d1 = pow(e, -1, phi1)
phi2 = (p-1)*(q2-1)
d2 = pow(e, -1, phi2)

m1 = bytes_to_long(b'Mensaje secreto 1')
m2 = bytes_to_long(b'Mensaje secreto 2')
c1 = pow(m1, e, N1)
c2 = pow(m2, e, N2)

print('=== ATAQUE GCD ===')
print(f'N1 (publico) = {N1}')
print(f'N2 (publico) = {N2}')

# El ataque: calcular mcd(N1, N2)
p_encontrado = gcd(N1, N2)
print(f'\nmcd(N1, N2) = {p_encontrado}')
print(f'Es el primo p? {p_encontrado == p}')

# Recuperar claves privadas
q1_rec = N1 // p_encontrado
d1_rec = pow(e, -1, (p_encontrado-1)*(q1_rec-1))
m1_rec = pow(c1, d1_rec, N1)

q2_rec = N2 // p_encontrado
d2_rec = pow(e, -1, (p_encontrado-1)*(q2_rec-1))
m2_rec = pow(c2, d2_rec, N2)

print(f'\nMensaje 1 descifrado: {long_to_bytes(m1_rec)}')
print(f'Mensaje 2 descifrado: {long_to_bytes(m2_rec)}')
EOF

GCD masivo sobre muchas claves (Batch GCD)

python3 << 'EOF'
# Con muchas claves publicas, usar Batch GCD (producto-arbol)
# es mas eficiente que calcular mcd de todos los pares
from math import gcd
from functools import reduce

def batch_gcd(modulos):
    """Encuentra todos los pares de modulos con factor comun"""
    resultados = []
    for i in range(len(modulos)):
        for j in range(i+1, len(modulos)):
            g = gcd(modulos[i], modulos[j])
            if g != 1 and g != modulos[i] and g != modulos[j]:
                resultados.append((i, j, g))
                print(f'Factor comun entre N[{i}] y N[{j}]: {g}')
    return resultados

# RsaCtfTool tiene implementado el batch GCD:
# python3 RsaCtfTool.py --publickey key1.pem key2.pem key3.pem --attack commonmodulus
EOF

❓ Ejercicio práctico

Genera 5 claves RSA donde dos de ellas comparten el mismo primo p (simula un generador defectuoso). Aplica el ataque GCD para identificar qué par de claves está comprometido.

💡 Pista: Calcula mcd(Ni, Nj) para todos los pares. El par con mcd distinto de 1 comparte un primo.

Ver solución

Crear 5 claves donde N3 y N5 comparten el primo p. Calcular todos los pares: gcd(N1,N2), gcd(N1,N3)... El par (N3,N5) devolvera gcd = p != 1. Con ese p factorizas ambas claves instantaneamente.

💯

Ejercicio 5 — Ataque de Hastad (Broadcast Attack)

Mismo mensaje cifrado con e=3 para múltiples destinatarios

Hastad Broadcast Attack (1985)

e=3 + mismo mensaje a 3 destinatarios → Teorema Chino del Resto revela m

e PEQUEÑO

Principio

Si el mismo mensaje m se cifra para 3 claves distintas con e=3: c1 = m^3 mod N1 c2 = m^3 mod N2 c3 = m^3 mod N3 Por el Teorema Chino del Resto (TCR), podemos calcular: C = m^3 mod (N1 * N2 * N3) Y como m < min(N1,N2,N3), tenemos m^3 < N1*N2*N3 Luego: m = raiz_cubica(C) (raiz entera exacta, no modular)

Con e=3 se necesitan solo 3 claves distintas. Con e=17 se necesitarian 17. Con e=65537, el ataque no es práctico.

Demostrar el ataque de Hastad

python3 << 'EOF'
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from sympy.ntheory.modular import crt
from sympy import integer_nthroot

# Tres destinatarios con e=3 cada uno
e = 3
N1_list = []
c_list = []

mensaje = b'Hastad_Secret'
m = bytes_to_long(mensaje)

for i in range(3):
    p = getPrime(512)
    q = getPrime(512)
    N = p * q
    # Aseguramos que e < phi(N) y mcd(e, phi) = 1
    phi = (p-1)*(q-1)
    from math import gcd
    while gcd(e, phi) != 1:
        p = getPrime(512)
        q = getPrime(512)
        N = p * q
        phi = (p-1)*(q-1)
    
    c = pow(m, e, N)
    N1_list.append(N)
    c_list.append(c)
    print(f'Clave {i+1}: N = {N}')
    print(f'        c = {c}')

# ATAQUE DE HASTAD:
print('\n=== ATAQUE DE HASTAD ===')
# Aplicar TCR para encontrar m^3 mod (N1*N2*N3)
m_cubo, _ = crt(N1_list, c_list)
print(f'm^3 = {m_cubo}')

# Calcular la raiz cubica entera exacta
m_recuperado, exacto = integer_nthroot(m_cubo, 3)
print(f'Raiz cubica exacta: {exacto}')
print(f'Mensaje: {long_to_bytes(m_recuperado)}')
EOF

Hastad con RsaCtfTool

# Con archivos PEM de 3 claves distintas:
python3 RsaCtfTool.py \
  --publickey key1.pem key2.pem key3.pem \
  --uncipher c1.bin c2.bin c3.bin \
  --attack hastad

# Con n y e directamente (si todas tienen e=3):
# Proporcionar los 3 pares (N,e) con sus cifrados correspondientes

❓ Ejercicio práctico

¿Por qué el ataque de Hastad no funciona si se usa padding OAEP correctamente antes de cifrar? ¿Qué propiedad del padding lo previene?

💡 Pista: El padding añade aleatoriedad al mensaje antes de cifrar. Piensa en qué pasa si cada destinatario recibe un mensaje ligeramente diferente.

Ver solución

Con padding OAEP, aunque el mensaje original m sea el mismo, el valor que se cifra en realidad es diferente para cada destinatario (porque el padding anade bytes aleatorios). Esto significa que m1 != m2 != m3 (los mensajes paddeados), haciendo imposible aplicar el TCR para recuperar m^3, ya que en realidad se habrian cifrado tres mensajes distintos. Por eso RSA sin padding (textbook RSA) es seguro en teoria pero no en practica.

🌞

Ejercicio 6 — Ataque de Franklin-Reiter

Dos mensajes relacionados linealmente cifrados con la misma clave y e=3

Franklin-Reiter (1996)

m2 = a*m1 + b conocido → polinomios MCD revelan m1

MENSAJES RELACIONADOS

Condición

Dados: c1 = m1^e mod N y c2 = m2^e mod N con m2 = a*m1 + b (relacion lineal conocida) Entonces el MCD de los polinomios: f1(x) = x^e - c1 y f2(x) = (a*x + b)^e - c2 en Z_N[x] es el polinomio (x - m1) El ataque calcula este MCD y revela m1.

Requiere conocer la relacion lineal entre m1 y m2, que en algunos protocolos es fija o predecible (ej: m2 = m1 + 1).

Demostrar Franklin-Reiter con SageMath

# Franklin-Reiter se implementa mejor con SageMath
# (Python con algebra computacional)
# Instalar: sudo apt install sagemath

# sage_franklin_reiter.sage:
from sage.all import *

def franklin_reiter(N, e, c1, c2, a, b):
    """
    Franklin-Reiter: recuperar m1 dado que m2 = a*m1 + b
    c1 = m1^e mod N,  c2 = m2^e mod N
    """
    R = Zmod(N)['x']
    x = R.gen()
    
    f1 = x**e - c1
    f2 = (a*x + b)**e - c2
    
    # MCD de los dos polinomios
    g = gcd(f1, f2)
    
    # Si g es de grado 1, g = x - m1
    if g.degree() == 1:
        m1 = -g[0] / g[1]
        return int(m1)
    return None

# Ejemplo de uso:
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
p = getPrime(512)
q = getPrime(512)
N = p * q
e = 3

m1 = bytes_to_long(b'Franklin_Secret')
a, b = 1, 42  # m2 = m1 + 42 (relacion conocida)
m2 = a * m1 + b

c1 = pow(m1, e, N)
c2 = pow(m2, e, N)

print(f'N = {N}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

m1_recuperado = franklin_reiter(N, e, c1, c2, a, b)
if m1_recuperado:
    print(f'Mensaje recuperado: {long_to_bytes(m1_recuperado)}')
    print(f'Correcto: {m1_recuperado == m1}')
else:
    print('El ataque no convergio')

# Guardar y ejecutar con: sage sage_franklin_reiter.sage

Franklin-Reiter con RsaCtfTool

# RsaCtfTool incluye Franklin-Reiter:
python3 RsaCtfTool.py \
  --n TU_N \
  --e 3 \
  --uncipher c1.txt c2.txt \
  --attack franklin_reiter

🔧

Ejercicio 7 — RsaCtfTool en Modo Automático

Dejar que la herramienta pruebe todos los ataques secuencialmente

RsaCtfTool puede intentar automáticamente todos sus ataques implementados en orden de complejidad creciente. Es la forma más cómoda de atacar una clave RSA desconocida en un CTF: prueba primero los más rápidos y si ninguno funciona, pasa a los más costosos.

Modo ataque automatico completo

# Listar TODOS los ataques disponibles:
python3 RsaCtfTool.py --list-attacks

# Intentar TODOS los ataques:
python3 RsaCtfTool.py \
  --publickey clave.pem \
  --attack all \
  --uncipher cifrado.txt

# Ataques mas comunes en CTF (en orden de frecuencia):
python3 RsaCtfTool.py \
  --publickey clave.pem \
  --attack factordb smallfactors wiener fermat commonprimes \
  --uncipher cifrado.txt

# Con n y e en lugar de PEM:
python3 RsaCtfTool.py \
  --n 1234567890...  \
  --e 65537 \
  --uncipher 9876543210... \
  --attack all

# Si el cifrado esta en base64:
python3 RsaCtfTool.py \
  --publickey key.pem \
  --uncipher <(base64 -d cifrado_b64.txt) \
  --attack all

Generar y resolver un CTF challenge completo

python3 << 'EOF'
# Generamos un challenge CTF completo con clave debil (Fermat)
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from Crypto.PublicKey import RSA
from sympy import nextprime
from base64 import b64encode

# Clave debil: p y q muy cercanos
p = getPrime(256)
q = nextprime(p + random.randint(2, 100))
N = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)

# Clave publica RSA en formato PEM
clave = RSA.construct((N, e))
pem = clave.export_key().decode()
with open('challenge_key.pem', 'w') as f:
    f.write(pem)

# Flag cifrada
flag = b'CTF{RSA_is_math_not_magic}'
m = bytes_to_long(flag)
c = pow(m, e, N)

with open('challenge_cipher.txt', 'w') as f:
    f.write(str(c))

print('Challenge generado:')
print(f'  challenge_key.pem')
print(f'  challenge_cipher.txt')
print(f'  N = {N} ({N.bit_length()} bits)')
print(f'  Diferencia p-q = {abs(p-q)}')
print()
print('Resolver con:')
print('  python3 RsaCtfTool.py --publickey challenge_key.pem --attack fermat --uncipher challenge_cipher.txt')
EOF

💻

Laboratorio 1 — Generar Claves RSA Débiles en Python

Script completo para generar claves con distintas debilidades

Script: generar_claves_debiles.py

#!/usr/bin/env python3
"""
Generador de claves RSA deliberadamente debiles para laboratorio educativo.
GhostAcademy - unfantasmaenelsistema.com
"""
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from Crypto.PublicKey import RSA
from sympy import nextprime, isprime
from math import gcd
import random

def gen_rsa_normal(bits=2048):
    """RSA correctamente generado (referencia)"""
    p = getPrime(bits // 2)
    q = getPrime(bits // 2)
    N = p * q
    e = 65537
    phi = (p-1)*(q-1)
    d = pow(e, -1, phi)
    return {'N': N, 'e': e, 'd': d, 'p': p, 'q': q, 'tipo': 'SEGURO'}

def gen_rsa_pequeno(bits=64):
    """RSA con N pequeno: factorizable directamente"""
    p = getPrime(bits)
    q = getPrime(bits)
    N = p * q
    e = 65537
    phi = (p-1)*(q-1)
    d = pow(e, -1, phi)
    return {'N': N, 'e': e, 'd': d, 'p': p, 'q': q, 'tipo': 'VULNERABLE: N PEQUENO'}

def gen_rsa_fermat(bits=512):
    """RSA con p y q cercanos: vulnerable a Fermat"""
    p = getPrime(bits)
    q = nextprime(p + random.randint(2, 100))
    N = p * q
    e = 65537
    phi = (p-1)*(q-1)
    d = pow(e, -1, phi)
    return {'N': N, 'e': e, 'd': d, 'p': p, 'q': q,
            'tipo': f'VULNERABLE: FERMAT (diff={abs(p-q)})'}

def gen_rsa_wiener(bits=512):
    """RSA con d pequeno: vulnerable a Wiener"""
    p = getPrime(bits)
    q = getPrime(bits)
    N = p * q
    phi = (p-1)*(q-1)
    umbral = int(N**(0.25) / 3)
    d = random.randint(2, umbral)
    while gcd(d, phi) != 1:
        d = random.randint(2, umbral)
    e = pow(d, -1, phi)
    return {'N': N, 'e': e, 'd': d, 'p': p, 'q': q,
            'tipo': 'VULNERABLE: WIENER (d pequeno)'}

# Generar todas las claves debiles
for gen, nombre in [
    (gen_rsa_pequeno,  'N_pequeno'),
    (gen_rsa_fermat,   'fermat'),
    (gen_rsa_wiener,   'wiener'),
]:
    params = gen()
    mensaje = b'Flag{RSA_weak_key_demo}'
    m = bytes_to_long(mensaje)
    c = pow(m, params['e'], params['N'])
    params['c'] = c
    params['mensaje_original'] = mensaje
    
    # Guardar clave publica PEM
    clave = RSA.construct((params['N'], params['e']))
    with open(f'key_{nombre}.pem', 'wb') as f:
        f.write(clave.export_key())
    
    with open(f'cipher_{nombre}.txt', 'w') as f:
        f.write(str(c))
    
    print(f'=== {params["tipo"]} ===')
    print(f'  N ({params["N"].bit_length()} bits) guardado en key_{nombre}.pem')
    print(f'  Cifrado guardado en cipher_{nombre}.txt')
    print()

print('Para romperlas:')
print('  python3 RsaCtfTool.py --publickey key_fermat.pem --attack fermat --uncipher cipher_fermat.txt')
print('  python3 RsaCtfTool.py --publickey key_wiener.pem --attack wiener --uncipher cipher_wiener.txt')
print('  python3 RsaCtfTool.py --publickey key_N_pequeno.pem --attack factordb --uncipher cipher_N_pequeno.txt')

💻

Laboratorio 2 — Cifrar y Descifrar RSA Manualmente

Implementación completa de RSA desde cero en Python

rsa_manual.py: RSA desde cero sin librerías criptográficas

#!/usr/bin/env python3
"""
Implementacion educativa de RSA desde cero.
USO EXCLUSIVAMENTE EDUCATIVO: no usar en produccion.
"""
import random

def es_primo_miller_rabin(n, k=20):
    """Test de primalidad de Miller-Rabin"""
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False
    
    # Escribir n-1 como 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def generar_primo(bits):
    """Generar primo aleatorio de 'bits' bits"""
    while True:
        n = random.getrandbits(bits) | (1 << bits-1) | 1  # impar, bit alto puesto
        if es_primo_miller_rabin(n):
            return n

def mcd_extendido(a, b):
    """Algoritmo extendido de Euclides: devuelve (mcd, x, y) tal que a*x + b*y = mcd"""
    if a == 0:
        return b, 0, 1
    g, x, y = mcd_extendido(b % a, a)
    return g, y - (b // a) * x, x

def inverso_modular(e, phi):
    """Calcular d = e^-1 mod phi con el algoritmo extendido de Euclides"""
    g, x, _ = mcd_extendido(e % phi, phi)
    if g != 1:
        raise ValueError('No existe inverso modular: mcd(e, phi) != 1')
    return x % phi

def generar_claves_rsa(bits=1024):
    """Generar par de claves RSA"""
    p = generar_primo(bits // 2)
    q = generar_primo(bits // 2)
    while q == p:
        q = generar_primo(bits // 2)
    
    N = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = inverso_modular(e, phi)
    
    return (
        {'N': N, 'e': e},    # Clave publica
        {'N': N, 'd': d},    # Clave privada
        {'p': p, 'q': q}     # Factores secretos
    )

def cifrar(mensaje: bytes, clave_publica: dict) -> int:
    """Cifrar bytes con la clave publica (textbook RSA, sin padding)"""
    N, e = clave_publica['N'], clave_publica['e']
    m = int.from_bytes(mensaje, 'big')
    if m >= N:
        raise ValueError('Mensaje demasiado grande para esta clave')
    return pow(m, e, N)

def descifrar(c: int, clave_privada: dict) -> bytes:
    """Descifrar con la clave privada"""
    N, d = clave_privada['N'], clave_privada['d']
    m = pow(c, d, N)
    longitud = (m.bit_length() + 7) // 8
    return m.to_bytes(longitud, 'big')

# Uso del sistema:
pub, priv, secreto = generar_claves_rsa(bits=512)
mensaje = b'Hola RSA'
c = cifrar(mensaje, pub)
m_rec = descifrar(c, priv)

print(f'Mensaje original:   {mensaje}')
print(f'Cifrado (c):        {c}')
print(f'Mensaje descifrado: {m_rec}')
print(f'Correcto: {mensaje == m_rec}')

💻

Laboratorio 3 — Pipeline Completo: Generar, Atacar, Descifrar

Flujo end-to-end con clave Fermat vulnerable

pipeline_fermat.py: flujo completo

#!/usr/bin/env python3
"""
Pipeline completo de demostracion:
1. Generar clave RSA deliberadamente vulnerable (Fermat)
2. Cifrar un mensaje con ella
3. Aplicar el ataque de Fermat para factorizar N
4. Recuperar el mensaje original
GhostAcademy - unfantasmaenelsistema.com
"""
import math
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from sympy import nextprime
import random

print('=== PIPELINE DE DEMOSTRACION RSA + FERMAT ===')
print()

# FASE 1: Generar clave debil
print('[1] Generando clave RSA con p y q cercanos...')
p = getPrime(256)
q = nextprime(p + random.randint(2, 50))
N = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(f'    p = {p}')
print(f'    q = {q}')
print(f'    N = {N} ({N.bit_length()} bits)')
print(f'    Diferencia |p-q| = {abs(p-q)}')

# FASE 2: Cifrar
print()
print('[2] Cifrando el mensaje...')
flag = b'GhostAcademy{RSA_Fermat_Demo}'
m = bytes_to_long(flag)
c = pow(m, e, N)
print(f'    Mensaje: {flag}')
print(f'    c = {c}')

# FASE 3: Ataque (ahora solo conocemos N, e, c -- olvidamos p y q)
print()
print('[3] ATACANDO: Factorizacion de Fermat...')
print('    (Solo usando N, e, c -- p y q son desconocidos para el atacante)')

def fermat_factor(N):
    a = math.isqrt(N) + 1
    b2 = a*a - N
    iters = 0
    while True:
        b = math.isqrt(b2)
        if b*b == b2:
            return a+b, a-b
        a += 1
        b2 = a*a - N
        iters += 1

p_rec, q_rec = fermat_factor(N)
print(f'    p recuperado = {p_rec}')
print(f'    q recuperado = {q_rec}')
print(f'    Verificacion p*q==N: {p_rec*q_rec == N}')

# FASE 4: Descifrar
print()
print('[4] Reconstruyendo clave privada y descifrando...')
phi_rec = (p_rec - 1) * (q_rec - 1)
d_rec = pow(e, -1, phi_rec)
m_rec = pow(c, d_rec, N)
flag_rec = long_to_bytes(m_rec)
print(f'    d recuperado = {d_rec}')
print(f'    Mensaje descifrado: {flag_rec}')
print(f'    Correcto: {flag_rec == flag}')
print()
print('=== ATAQUE COMPLETADO ===')
print(f'FLAG: {flag_rec.decode()}')

# Tiempo de ataque:
import time
start = time.time()
fermat_factor(N)
elapsed = time.time() - start
print(f'Tiempo del ataque Fermat: {elapsed*1000:.2f} ms')

✓ EJECUTAR EL PIPELINEGuarda el script como pipeline_fermat.py e instala las dependencias: pip3 install pycryptodome sympy. Luego: python3 pipeline_fermat.py. Verás todo el proceso: generación de la clave débil, cifrado, ataque de Fermat y recuperación del mensaje en menos de un segundo.

📚

Tabla Resumen de Ataques RSA

Referencia rápida para CTF y estudio

Ataque	Condición necesaria	Complejidad	Flag RsaCtfTool	Base matemática
Factorización directa	N < ~512 bits	Trivial	`--attack factordb`	Criba de Eratostenes, GNFS
Fermat	\|p - q\| muy pequeño	O(\|p-q\|)	`--attack fermat`	N = a² - b²
Wiener	d < N^1/4/3	O(log N)	`--attack wiener`	Fracciones continuas
Boneh-Durfee	d < N^0.292	Polinomial	`--attack boneh_durfee`	Reticulados (LLL)
GCD / Primos comunes	Dos N comparten un primo	O(log N)	`--attack commonmodulus`	Algoritmo de Euclides
Hastad (broadcast)	e pequeño + mismo m	Polinomial	`--attack hastad`	Teorema Chino del Resto
Franklin-Reiter	Mensajes relacionados + e pequeño	Polinomial	`--attack franklin_reiter`	MCD de polinomios
Blinding (Coppersmith)	Parte de m conocida	Polinomial	`--attack coppersmith`	Reticulados, LLL
e=1	e = 1 (trivial)	Trivial	`--attack e_is_1`	c = m^1 mod N = m
Small e + small m	m^e < N	Trivial	`--attack smallfactors`	Raiz e-ésima entera

🏆

RSA en CTFs: Metodología de Ataque

Flujo de trabajo cuando encuentras un reto RSA en un CTF

🏆FLOWCHART: ¿QUÉ HACER CON UNA CLAVE RSA EN UN CTF?

Metodologia CTF RSA

# 1. Extraer los parametros de la clave publica
openssl rsa -pubin -in clave.pem -text -noout
# Muestra: Modulus (N) y Exponent (e)

# 2. Ejecutar RsaCtfTool con todos los ataques rapidos
python3 RsaCtfTool.py --publickey clave.pem --attack all --uncipher cifrado.bin

# 3. Si falla, analizar los parametros manualmente:
python3 << 'EOF'
from Crypto.PublicKey import RSA
import math

clave = RSA.import_key(open('clave.pem').read())
N = clave.n
e = clave.e

print(f'N tiene {N.bit_length()} bits')
print(f'e = {e}')
print(f'sqrt(N) aprox: {math.isqrt(N)}')

# Pistas para elegir el ataque:
if N.bit_length() < 512:
    print('-> PROBAR: factorizacion directa / factordb')
if e > N ** 0.5:
    print('-> PROBAR: Wiener (e muy grande = d pequeno)')
if e == 3:
    print('-> PROBAR: Hastad si hay multiples cifrados del mismo msg')
if e == 1:
    print('-> TRIVIAL: m = c')
EOF

# 4. Buscar N en factordb.com directamente:
# https://factordb.com/?query=TU_N_AQUI

# 5. Si el challenge da multiples claves, probar GCD entre todas:
python3 << 'EOF'
from math import gcd
Ns = [N1, N2, N3]  # Todos los modulos del challenge
for i in range(len(Ns)):
    for j in range(i+1, len(Ns)):
        g = gcd(Ns[i], Ns[j])
        if g > 1:
            print(f'Factor comun entre N{i} y N{j}: {g}')
EOF

🛡

RSA Seguro: Buenas Prácticas

Cómo generar e implementar RSA correctamente

🛡CHECKLIST DE RSA SEGURO

Requisito	Valor correcto	Ataque que previene
Tamaño de N	≥ 2048 bits (4096 para secretos a largo plazo)	Factorización directa
Generación de p y q	Completamente independientes, fuente criptográficamente aleatoria	Fermat, GCD attack
Diferencia \|p-q\|	Del orden de N/2 (automático si son aleatorios independientes)	Fermat
Exponente público e	65537 (0x10001) estándar de la industria	Hastad, Wiener
Exponente privado d	Calculado como inverso de e (no elegido directamente)	Wiener, Boneh-Durfee
Padding	OAEP (RSA-OAEP) para cifrado, PSS para firma	Hastad, Franklin-Reiter, textbook attacks
Fuente de aleatoriedad	CSPRNG del sistema operativo (/dev/urandom, os.urandom())	GCD attack (primos repetidos)

Generar RSA correctamente en Python

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Signature import pss
from Crypto.Hash import SHA256

# Generar clave de 2048 bits correctamente
clave = RSA.generate(2048)  # Usa /dev/urandom internamente

# Guardar clave privada (protegida con passphrase)
with open('clave_privada.pem', 'wb') as f:
    f.write(clave.export_key(passphrase='mi_passphrase_segura'))

# Guardar clave publica
with open('clave_publica.pem', 'wb') as f:
    f.write(clave.publickey().export_key())

# Cifrar con OAEP (padding correcto)
cipher = PKCS1_OAEP.new(clave.publickey())
c = cipher.encrypt(b'Mensaje secreto')

# Descifrar
decipher = PKCS1_OAEP.new(clave)
m = decipher.decrypt(c)
print(f'Descifrado: {m}')

# Firmar con PSS
firmador = pss.new(clave)
hash_msg = SHA256.new(b'Mensaje a firmar')
firma = firmador.sign(hash_msg)

# Verificar firma
verificador = pss.new(clave.publickey())
hash_msg = SHA256.new(b'Mensaje a firmar')
try:
    verificador.verify(hash_msg, firma)
    print('Firma valida')
except Exception:
    print('Firma invalida')

✓ CONCLUSIÓNHas completado el laboratorio de RSA y RsaCtfTool. Los conceptos de factorización de Fermat, el ataque de Wiener con fracciones continuas, el ataque GCD sobre primos compartidos y el ataque de Hastad vía TCR son contenido fundamental en cualquier curso universitario de criptografía moderna. RsaCtfTool automatiza estos ataques para CTFs y demostraciones educativas. La defensa es clara: claves de 2048+ bits, generación aleatoria correcta y padding OAEP.