Serie 7 · Criptografía de la firma · 7.2

RSA por dentro.

Aritmética modular, el teorema de Euler y por qué una firma RSA sin relleno no es una firma.

Octubre de 202610 min de lectura

En abril de 1977, después de una cena de Pésaj en casa de un estudiante, Ron Rivest no podía dormir. Llevaba meses con Adi Shamir y Leonard Adleman probando candidatos para la función con trampa que Diffie y Hellman habían imaginado; Adleman, el matemático del grupo, había ido derribando uno tras otro. Esa noche Rivest escribió una propuesta basada en la factorización de enteros. A la mañana siguiente Adleman no encontró cómo romperla. El artículo que publicaron en Communications of the ACM en febrero de 1978 sigue siendo, casi medio siglo después, la base de buena parte de las firmas digitales del mundo.

RSA se explica en una página. Usarlo bien llevó décadas. Este artículo recorre las dos cosas: la matemática, con un ejemplo que se puede seguir con lápiz, y los detalles que separan una fórmula elegante de una firma segura.

La trampa: multiplicar es fácil, factorizar no

Multiplicar dos primos de 1536 bits lleva microsegundos. Recuperar esos primos a partir del producto, un número de 3072 bits, está fuera del alcance de cualquier computadora clásica conocida. El mejor algoritmo, la criba general del cuerpo de números, tiene un costo subexponencial que, para ese tamaño, equivale a unas 2¹²⁸ operaciones.

Para convertir esa asimetría en una trampa hace falta un resultado de 1763. El teorema de Euler dice que si m y n no tienen factores comunes, entonces m^φ(n) ≡ 1 (mod n), donde φ(n) cuenta los números menores que n coprimos con él. Si n = p · q con p y q primos, ese conteo es fácil de calcular, pero sólo para quien conoce p y q:

φ(n) = (p 1)(q 1)

Conocer φ(n) equivale a conocer la factorización: con n y φ(n), p y q salen de una ecuación de segundo grado.

Generar claves, firmar, verificar

Elegir dos primos grandes p y q, al azar, de igual tamaño y no demasiado próximos entre sí. Su producto n es el módulo.
Elegir el exponente público e, coprimo con (p 1)(q 1). Casi siempre es 65537, es decir 2¹⁶ + 1: es primo y en binario tiene sólo dos unos, así que verificar cuesta 16 elevaciones al cuadrado y una multiplicación.
Calcular el exponente privado d, el inverso de e módulo φ(n) (o módulo λ(n) = mcm(p 1, q 1), como pide FIPS 186 5; ambos funcionan). Se obtiene con el algoritmo extendido de Euclides.
Publicar (n, e) y guardar d. Los primos deben destruirse o protegerse igual que d.

Firmar: s = m^d mod n

Verificar: s^e mod n = m ?

Funciona porque e · d = 1 + k · φ(n) para algún entero k, y entonces s^e = m^e·d = m · (m^φ(n))^k ≡ m · 1^k = m (mod n). Con el teorema chino del resto se ve que vale también cuando m comparte un factor con n.

El ejemplo clásico usa p = 61 y q = 53. Entonces n = 3233, φ(n) = 3120, y con e = 17 resulta d = 2753, porque 17 · 2753 = 46801 = 15 · 3120 + 1. La firma del mensaje 65 es 65²⁷⁵³ mod 3233 = 588, y cualquiera puede comprobar que 588¹⁷ mod 3233 = 65. El laboratorio permite repetir la cuenta con otros primos y ver qué pasa cuando algo cambia.

LaboratorioRSA de juguete, con números que caben en la cabeza

Primo p

Primo q

Exponente público e

Mensaje a firmar, como número m menor que n (en la práctica, el resumen con relleno)

Elija los parámetros y firme.

Por qué esa fórmula, sola, no es una firma

Lo que el laboratorio muestra, y lo que el artículo original describía, se conoce como RSA «de libro de texto». Tiene problemas graves si se usa tal cual sobre mensajes.

Es multiplicativa. Si s₁ firma m₁ y s₂ firma m₂, entonces s₁ · s₂ mod n es una firma válida de m₁ · m₂ mod n. Con dos firmas legítimas se fabrica una tercera.
Admite falsificación existencial. Cualquiera elige un s al azar, calcula m = s^e mod n, y tiene un par válido. El mensaje no tendrá sentido, pero la definición de seguridad exige que ni siquiera eso sea posible.
No admite mensajes largos. Sólo se puede firmar un número menor que n.

La respuesta a las tres es la misma: no se firma el mensaje sino su resumen, y el resumen se codifica con un formato rígido, el relleno, antes de elevarlo a d. El resumen elimina las relaciones algebraicas entre mensajes; el relleno ocupa todo el ancho del módulo y le da una estructura que un número al azar no tiene.

PKCS #1 versión 1.5

El formato más difundido, definido por RSA Laboratories a comienzos de los años noventa y mantenido hoy en el RFC 8017, es determinista. El bloque que se eleva a d es:

EM = 00 ‖ 01 ‖ FF FF … FF ‖ 00 ‖ DigestInfo(algoritmo, H(m))

DigestInfo es una estructura ASN.1 que identifica la función resumen y contiene el resumen. Los bytes FF rellenan hasta el tamaño exacto del módulo.

No se conoce un ataque práctico contra la firma PKCS #1 versión 1.5 bien implementada. Pero «bien implementada» resultó ser exigente. En 2006 Daniel Bleichenbacher mostró que muchos verificadores, en lugar de reconstruir el bloque completo y compararlo, lo leían de izquierda a derecha y no comprobaban que no hubiera bytes sobrantes después del resumen. Con e = 3, eso permitía construir a mano un número cuyo cubo empezara con el prefijo correcto y terminara en basura, y así falsificar firmas sin la clave. Variantes del mismo error reaparecieron en distintas bibliotecas durante años. La lección es general: un verificador debe recalcular lo que espera y compararlo entero, nunca interpretar lo que recibe.

PSS: la firma con prueba

En 1996 Mihir Bellare y Phillip Rogaway propusieron el esquema probabilístico de firma, PSS. Agrega una sal aleatoria y mezcla todo con una función de máscara, de modo que firmar dos veces el mismo mensaje da dos firmas distintas:

M′ = 00…00 (8 bytes) ‖ H(m) ‖ sal

h = H(M′)

DB = relleno ‖ 01 ‖ sal DB enmascarado = DB ⊕ MGF1(h)

EM = DB enmascarado ‖ h ‖ BC → s = EM^d mod n

Su ventaja no es sólo práctica. PSS tiene una demostración de seguridad: en el modelo de oráculo aleatorio, falsificar una firma es tan difícil como invertir RSA, con una reducción ajustada, sin pérdida significativa de seguridad en el camino. PKCS #1 versión 1.5 no tiene una prueba comparable. Por eso las normas recomiendan PSS para sistemas nuevos, aunque la versión 1.5 sigue siendo omnipresente por compatibilidad.

El atajo del resto chino, y su trampa

Firmar es caro: d es tan largo como n. Toda implementación seria usa el teorema chino del resto. Calcula la firma por separado módulo p y módulo q, con exponentes reducidos d mod (p 1) y d mod (q 1), y combina los dos resultados. Como cada mitad opera con números de la mitad de tamaño, firmar se vuelve unas cuatro veces más rápido.

En 1997 Dan Boneh, Richard DeMillo y Richard Lipton señalaron el precio, y Arjen Lenstra mostró que basta una sola firma defectuosa. Si una sola de las dos mitades se calcula mal, por un error de hardware, una variación de voltaje o un pulso de láser provocado a propósito sobre una tarjeta, la firma resultante s′ es correcta módulo un primo y errónea módulo el otro. Entonces:

mcd(s′^e m, n) = p

Una sola firma defectuosa entrega la factorización del módulo, y con ella la clave privada completa.

La contramedida es sencilla y obligatoria: verificar la firma antes de entregarla. Los dispositivos seguros de creación de firma lo hacen, y sus evaluaciones de seguridad incluyen ataques de inyección de fallas por este motivo.

En RSA la matemática es la parte fácil. Lo difícil es todo lo que la rodea: el relleno, la verificación, la generación de primos y el hardware que calcula.

Cuánto debe medir una clave

La seguridad de RSA se mide en bits equivalentes: cuántas operaciones costaría el mejor ataque conocido, expresadas como potencia de dos. NIST publica la equivalencia en su recomendación de gestión de claves.

Módulo RSA	Seguridad equivalente	Situación
1024 bits	unos 80 bits	No aceptado para firmas nuevas.
2048 bits	112 bits	Mínimo aceptado hoy.
3072 bits	128 bits	Recomendado para horizontes largos.
7680 bits	192 bits	Poco usado: firmas lentas y grandes.
15360 bits	256 bits	Impráctico; aquí las curvas elípticas ganan con claridad.

Los récords públicos de factorización muestran el ritmo real de avance. En 2019 un equipo académico factorizó RSA 240, un número de 795 bits, con unos 900 años de núcleo de cómputo. Duplicar el tamaño del módulo multiplica el costo por factores astronómicos, y por eso 2048 bits sigue fuera de alcance clásico con amplio margen. La amenaza que sí cambiaría el panorama es otra: el algoritmo de Shor, que en una computadora cuántica tolerante a fallas factoriza en tiempo polinomial. A ella está dedicado el último artículo de esta serie.

Lo que no se ve en la fórmula

Primos generados con un buen generador aleatorio: si dos dispositivos comparten un primo, un simple máximo común divisor rompe ambos.
Primos de igual tamaño pero no próximos: si |p q| es pequeño, el método de Fermat factoriza al instante.
Relleno PSS o, por compatibilidad, PKCS #1 versión 1.5 con verificación estricta.
Firma verificada antes de salir del dispositivo, como defensa contra fallas.
Implementación de tiempo constante, para no revelar bits de d por el tiempo de cálculo.

Para recordar

RSA firma con s = m^d mod n y verifica con s^e mod n; funciona por el teorema de Euler y es seguro porque calcular d exige factorizar n. Pero la fórmula sola no es una firma: hace falta resumen y relleno, idealmente PSS. Los errores históricos de RSA casi nunca fueron matemáticos, sino de verificación, de generación de claves o de hardware.

Fuentes

← Todas las notas