Clave RSA

RSA

RSA es un sistema criptográfico de clave pública desarrollado en 1979, basado en la factorización de números enteros. Su seguridad radica en la dificultad de factorizar un número compuesto grande.

Cada usuario posee dos claves: una pública y otra privada. Cuando se quiere enviar un mensaje confidencial, el emisor cifra el mensaje con la clave pública del receptor. Solo el receptor podrá descifrarlo utilizando su clave privada.

Cifrado y descifrado de un mensaje

Cuando dos dispositivos necesitan comunicarse de forma segura (por ejemplo, un sensor IoT y un servidor central), pueden usar RSA, un algoritmo de cifrado asimétrico. El dispositivo emisor cifra un mensaje con la clave pública del receptor, de modo que solo el receptor puede descifrarlo con su clave privada.

Antes del cifrado, el mensaje se procesa con un mecanismo llamado padding scheme (esquema de relleno), que asegura que el mensaje tenga una forma segura y válida para ser cifrado.

Escenario de ejemplo

• Dispositivo A (emisor): quiere enviar un mensaje seguro.
• Dispositivo B (receptor): tiene un par de claves RSA: una pública (n, e) y una privada (d).

El mensaje original se convierte en un número entero m tal que:

0 < m < n

Donde:

• m es la representación numérica del mensaje.
• n es parte de la clave pública RSA.

Luego, el mensaje se cifra:

c ≡ m^e mod n

El receptor utiliza su clave privada para descifrar:

m ≡ c^d mod n

¿Por qué es necesario el padding?

Porque RSA sin padding es inseguro:

• No introduce aleatoriedad.
• Repite resultados con el mismo mensaje.
• Es vulnerable a varios tipos de ataques.

Los esquemas más usados son:

• OAEP (para cifrado)
• PSS (para firmas digitales)

Ejemplo práctico simplificado (sin padding)

⚠️ Este ejemplo es solo educativo. No debe usarse sin padding en entornos reales.

n = 3233
e = 17
d = 2753
Mensaje original: "OK" → ASCII: 79 75 → combinado: m = 7905

Cifrado:

c = 7905^17 mod 3233 = 2201

Descifrado:

m = 2201^2753 mod 3233 = 7905

Conversión a texto:

7905 → "OK"

Generar claves RSA con Python

from sympy import isprime
from math import gcd

# Paso 1: Elegimos dos números primos p y q
p = 61
q = 53

# Paso 2: Calculamos n
n = p * q

# Paso 3: Calculamos la función de Euler φ(n)
phi_n = (p - 1) * (q - 1)

# Paso 4: Elegimos un e tal que sea coprimo con φ(n)
e = 17  # valor típico

# Paso 5: Calculamos el inverso modular d
def modinv(a, m):
    m0, x0, x1 = m, 0, 1
    while a > 1:
        q = a // m
        a, m = m, a % m
        x0, x1 = x1 - q * x0, x0
    return x1 + m0 if x1 < 0 else x1

d = modinv(e, phi_n)

# Mostramos las claves
print(f"Clave pública (n, e): ({n}, {e})")
print(f"Clave privada (n, d): ({n}, {d})")

# Cifrado y descifrado
mensaje = 42
cifrado = pow(mensaje, e, n)
descifrado = pow(cifrado, d, n)

print(f"Mensaje original: {mensaje}")
print(f"Mensaje cifrado: {cifrado}")
print(f"Mensaje descifrado: {descifrado}")

¿Qué debemos saber como atacante?

1. La clave pública contiene:
   • n = p * q → número grande
   • e → exponente público (comúnmente 65537)
2. Para romper RSA, necesitamos obtener el valor de d, resolviendo:

d * e ≡ 1 mod φ(n)

1. Para ello:
   • Factorizamos n → obtenemos p y q
   • Calculamos φ(n) = (p - 1)(q - 1)
   • Calculamos d = e⁻¹ mod φ(n)

¿Cuándo es vulnerable RSA?

• Tamaño de n muy pequeño (menos de 2048 bits).
• p y q mal elegidos (muy cercanos entre sí).
• Reutilización de primos.
• Uso de RSA sin padding.
• Claves públicas mal implementadas.

Ejemplo completo con SageMath

Datos disponibles

n = 3233      # módulo
e = 17        # exponente público
c = 2557      # mensaje cifrado (c = m^e mod n)

Paso 1: Factorizar n

factors = factor(n)
p = factors[0][0]
q = factors[1][0]

factor(n) devuelve una lista de tuplas con (factor primo, exponente)

Paso 2: Calcular φ(n)

phi = (p - 1) * (q - 1)

Paso 3: Calcular d

d = inverse_mod(e, phi)

Paso 4: Descifrar el mensaje

m = power_mod(c, d, n)

Paso 5: Mostrar resultado

print("Mensaje descifrado:", m)

Fundamentos matemáticos utilizados en RSA

• Teorema de Euler:
  RSA se basa en que, si a es coprimo con n, entonces:
  a^φ(n) ≡ 1 mod n
  Esto permite usar el inverso modular para descifrar el mensaje.

• Inverso modular:
  El valor d se calcula como el inverso modular de e respecto a φ(n): d ≡ e⁻¹ mod φ(n)
  Esto asegura que el cifrado y el descifrado sean operaciones inversas.

• Aritmética modular:
  RSA opera sobre el conjunto de enteros módulo n, es decir, los residuos que se obtienen al dividir por n.
  Esto permite que operaciones como m^e mod n y c^d mod n sean computacionalmente seguras y reversibles.

• Dificultad de factorización:
  El algoritmo se considera seguro porque factorizar n (un número compuesto de dos primos grandes) es computacionalmente muy costoso.