Después de RSA: la firma poscuántica.

En 1994, Peter Shor, en los Laboratorios Bell, presentó un algoritmo que todavía no podía ejecutarse en ninguna máquina existente y que, sin embargo, cambió el horizonte de toda la criptografía de clave pública. Mostró que una computadora cuántica suficientemente grande y estable podría factorizar enteros y calcular logaritmos discretos en tiempo polinomial. Los tres problemas sobre los que descansan RSA, Diffie y Hellman y las curvas elípticas caerían a la vez.

Tres décadas después, esa máquina todavía no existe, pero nadie serio apuesta a que no existirá. Este último artículo de la serie explica qué rompe exactamente el algoritmo de Shor, qué no rompe, y cómo son por dentro las firmas diseñadas para sobrevivirle.

Qué hace Shor, y qué no

La idea central es convertir la factorización en un problema de encontrar el período de una función. Si se elige un a al azar, la sucesión a^x mod n es periódica, y conocer su período r permite, con alta probabilidad, obtener un factor de n calculando mcd(a^r/2 1, n). Encontrar ese período es difícil para una computadora clásica, pero una computadora cuántica puede preparar una superposición de todos los valores de la función y extraer el período con la transformada cuántica de Fourier. El mismo principio, aplicado a grupos, resuelve el logaritmo discreto, incluido el de curvas elípticas.

Las funciones resumen y los cifrados simétricos quedan en otra categoría. El algoritmo de Grover acelera la búsqueda sin estructura de manera cuadrática: buscar una preimagen entre 2ⁿ posibilidades pasa a costar unas 2^n/2 evaluaciones, y esas evaluaciones son además secuenciales y muy difíciles de paralelizar. Con 256 bits, el margen sigue siendo enorme. Por eso la criptografía poscuántica se concentra en reemplazar la clave pública, no las funciones resumen.

La firma más antigua es la más moderna

Paradójicamente, una de las familias poscuánticas más sólidas es casi tan antigua como RSA. En 1979, Leslie Lamport describió una firma construida sólo con una función resumen.

1. Clave privada. 256 pares de valores aleatorios de 256 bits: (x_i,0, x_i,1) para i de 1 a 256.
2. Clave pública. Los resúmenes de todos ellos: (H(x_i,0), H(x_i,1)).
3. Firmar. Se resume el mensaje y, para cada uno de sus 256 bits, se revela x_i,0 si el bit es 0 o x_i,1 si es 1.
4. Verificar. Se resume cada valor revelado y se compara con la mitad correspondiente de la clave pública.

Falsificar exige invertir la función resumen. No hay ninguna estructura algebraica que Shor pueda explotar. Pero tiene un límite severo: cada clave sirve para una sola firma, porque cada firma revela la mitad de los secretos, y dos firmas de mensajes distintos revelan lo suficiente para combinar una tercera.

Ralph Merkle resolvió el problema con un árbol. Se generan 2^h claves de un solo uso y se ubican sus claves públicas como hojas de un árbol binario de resúmenes. La raíz, 32 bytes, es la única clave pública. Cada firma incluye la firma de un solo uso, su clave pública y los h resúmenes hermanos que permiten recalcular la raíz. Es el mismo árbol de Merkle que sostiene la transparencia de certificados y los registros de evidencia.

Con estado y sin estado

Los descendientes modernos se dividen en dos ramas. XMSS (RFC 8391) y LMS (RFC 8554), recomendados por NIST en SP 800 208, son esquemas con estado: el firmante debe recordar qué hojas usó y no repetir ninguna nunca. Es una exigencia peligrosa en la práctica, porque una copia de seguridad restaurada o un módulo clonado pueden reutilizar una hoja sin que nadie lo note. Por eso se reservan para usos controlados, como firmar el software de arranque de un dispositivo.

SPHINCS, presentado en 2015, y su sucesor SPHINCS+, normalizado en 2024 como SLH DSA en FIPS 205, eliminaron el estado. Usa un hiperárbol, un árbol de árboles, y en el último nivel un esquema de «pocas firmas» llamado FORS; la hoja se elige de forma pseudoaleatoria a partir del mensaje, y el árbol es tan grande que la probabilidad de reutilizar una hoja de manera peligrosa es despreciable. El precio son firmas grandes: entre unos 8 y 50 kilobytes según el conjunto de parámetros. La recompensa es la hipótesis de seguridad más conservadora posible: si la función resumen es buena, la firma es segura.

Retículos: el problema de la aguja con ruido

La otra gran familia se basa en retículos. Un retículo es el conjunto de todas las combinaciones enteras de unos vectores base, una grilla regular en un espacio de muchas dimensiones. Encontrar el vector no nulo más corto de un retículo, dada una base «mala», es difícil en dimensiones altas, y no se conoce algoritmo cuántico que lo resuelva eficientemente.

En 2005, Oded Regev formuló el problema de aprendizaje con errores, LWE, que se convirtió en la base de la criptografía de retículos práctica:

ML DSA, derivado del esquema CRYSTALS Dilithium y normalizado en FIPS 204, usa una versión con módulos, MLWE, más eficiente. Su firma sigue la estructura de Schnorr con una vuelta de tuerca, el método de Fiat y Shamir con abortos propuesto por Vadim Lyubashevsky:

ML DSA tiene tres niveles, 44, 65 y 87, que corresponden a las categorías de seguridad 2, 3 y 5 de NIST. Firma mucho más rápido que RSA y verifica a una velocidad comparable, pero sus claves y firmas miden kilobytes. NIST seleccionó además Falcon, otro esquema de retículos con firmas más compactas, que se normaliza como FN DSA; su implementación segura es más delicada porque requiere muestreo gaussiano en aritmética de punto flotante.

Cómo se hace la transición

Ninguna migración criptográfica fue rápida. Pasar de SHA 1 a SHA 256 en los certificados llevó más de una década. La transición poscuántica es más grande, porque afecta a los algoritmos de firma mismos, y en la firma con valor legal intervienen dispositivos seguros, tarjetas de identidad con años de vida útil, raíces nacionales y normas de formato.

• Firmas híbridas o compuestas. Durante la transición, un mismo documento o certificado puede llevar una firma clásica y una poscuántica, de modo que sea seguro mientras lo sea cualquiera de las dos. Protege contra la amenaza cuántica y, a la vez, contra un error en los algoritmos nuevos, que tienen mucha menos historia.
• Raíces primero. Una raíz se distribuye y se confía durante décadas. Es el primer lugar donde conviene tener claves poscuánticas, aunque las hojas sigan siendo clásicas un tiempo.
• Archivos con sello de tiempo renovado. Las firmas existentes no hace falta rehacerlas. Basta con que, antes de que los algoritmos clásicos se vuelvan falsificables, un sello de tiempo de archivo con algoritmos resistentes cubra la firma y su información de validación. Es el mecanismo que se describe en la primera serie de este blog, aplicado a un nuevo cambio de algoritmos.
• Agilidad. Los sistemas que puedan cambiar de algoritmo por configuración harán la transición; los que tengan RSA grabado en el código, no.

El método científico de la criptografía es, en el fondo, un método de transiciones. Diffie y Hellman reemplazaron el reparto de claves por la clave pública; las curvas elípticas reemplazaron, en buena parte, a RSA; SHA 2 reemplazó a SHA 1. El paso a la criptografía poscuántica es el siguiente, y no será el último. Lo que no cambia es el esquema que recorrió toda esta serie: un resumen que atrapa el documento, un problema difícil que separa lo privado de lo público, una cadena que pone nombre a las claves y evidencia que prueba cuándo pasó cada cosa.

← Todas las notas