CRYSTALS-Kyber: KEM basado en retículos

CRYSTALS-Kyber (cuyo nombre NIST cambió a ML-KEM en FIPS 203) es un mecanismo de encapsulación de claves (KEM) basado en Module-LWE. Sustituye a RSA y ECDH para el intercambio de claves y proporciona resistencia cuántica con un rendimiento práctico.

Un KEM encapsula un secreto compartido: el remitente genera una clave aleatoria K y la cifra con la clave pública del destinatario (encapsulación), lo que produce un texto cifrado C. El destinatario desencapsula C con su clave privada para recuperar K. No se necesita un intercambio interactivo de claves.

Kyber utiliza Module-LWE sobre el anillo R_q = Z_q[x]/(x^256+1), con q=3329. La dimensión es k=2 (Kyber-512), k=3 (Kyber-768) y k=4 (Kyber-1024). Los niveles de seguridad son de ~128, ~192 y ~256 bits, respectivamente. k=3 (Kyber-768) es la opción predeterminada recomendada.

Genere la matriz A ∈ R_q^{k×k} a partir de la semilla ρ (expandible). Muestree el secreto s y el ruido e a partir de una distribución binomial centrada (con coeficientes pequeños). Clave pública: (ρ, t=As+e). Clave privada: s. El ruido e es pequeño, pero impide recuperar s a partir de la clave pública.

Para enviar un secreto compartido al titular de la clave pública (ρ, t), muestree r, e1 y e2 a partir de la distribución de ruido. Calcule u = A^T r + e1, v = t^T r + e2 + round(q/2)*m, donde m es un mensaje aleatorio de 256 bits. Secreto compartido K = KDF(m). Texto cifrado = (u, v).

Con la clave privada s, calcule m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). Los términos de ruido se cancelan aproximadamente, dejando m'≈m. Calcule K = KDF(m'). Probabilidad de fallo de desencapsulación: < 2^{-139}.

Kyber-768: clave pública de 1184 bytes, clave privada de 2400 bytes, texto cifrado de 1088 bytes y secreto compartido de 32 bytes. Compárelo con ECDH-P256: clave pública de 65 bytes y texto cifrado de 32 bytes. Kyber es aproximadamente 15 veces más grande, pero ofrece seguridad poscuántica. Aun así, es rápido: encapsulación y desencapsulación tardan menos de 1 ms en CPU modernas.

La multiplicación de polinomios en R_q = Z_q[x]/(x^256+1) utiliza la transformada teórica de números (NTT), el análogo aritmético modular de la FFT. La NTT reduce la multiplicación de polinomios de O(n^2) a O(n log n). q=3329 se eligió por sus buenas propiedades para la NTT con n=256.

Durante la migración a PQC, utilice un intercambio híbrido de claves: combine ECDH y Kyber. Secreto compartido = KDF(ECDH_output || Kyber_output). La seguridad exige romper ambos: los adversarios clásicos no rompen ninguno; los adversarios cuánticos rompen ECDH, pero no Kyber. Los borradores de TLS 1.3 (IETF RFC 8446) admiten KEM híbridos.

La desencapsulación de Kyber no se ejecuta en tiempo constante en implementaciones ingenuas: el paso de muestreo por rechazo filtra información temporal. La implementación de referencia utiliza una NTT en tiempo constante y una comparación de textos cifrados comprimidos. Utilice el código de referencia de la propuesta de NIST o implementaciones de bibliotecas auditadas.

NIST publicó FIPS 203 (ML-KEM) en agosto de 2024. Chrome incorporó compatibilidad con Kyber en TLS 1.3 en 2023. Cloudflare, Google y AWS están implementando ECDH+Kyber híbrido. OpenSSL 3.x añadió compatibilidad con ML-KEM. Las implementaciones para LibSSH y WireGuard están en desarrollo.

¿Qué documento estándar de NIST estandariza CRYSTALS-Kyber?

Kyber (ML-KEM) es un KEM basado en Module-LWE que sustituye a ECDH. Sus claves ocupan aproximadamente 1 KB; utiliza aritmética NTT rápida y ofrece resistencia cuántica. Impleméntelo de forma híbrida con ECDH durante la migración. Está estandarizado como FIPS 203. Siguiente tema: los esquemas de firma CRYSTALS-Dilithium y Falcon.