CRYSTALS-Kyber: KEM baseado em reticulados

CRYSTALS-Kyber, renomeado como ML-KEM pelo NIST no FIPS 203, é um mecanismo de encapsulamento de chaves (KEM) baseado em Module-LWE. Ele substitui RSA e ECDH na troca de chaves, oferecendo resistência quântica com níveis práticos de desempenho.

Um KEM encapsula um segredo compartilhado: o remetente gera uma chave aleatória K e a criptografa com a chave pública do destinatário (encapsulamento), produzindo um texto cifrado C. O destinatário desencapsula C com sua chave privada para recuperar K. Não é necessária uma troca interativa de chaves.

Kyber usa Module-LWE sobre o anel R_q = Z_q[x]/(x^256+1), com q=3329. Dimensão k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Nível de segurança: aproximadamente 128, 192 e 256 bits, respectivamente. k=3 (Kyber-768) é o padrão recomendado.

Gere a matriz A ∈ R_q^{k×k} a partir da semente ρ (expansível). Extraia o segredo s e o ruído e de uma distribuição binomial centrada, com coeficientes pequenos. Chave pública: (ρ, t=As+e). Chave privada: s. O ruído e é pequeno, mas impede a recuperação de s a partir da chave pública.

Para enviar um segredo compartilhado ao titular da chave pública (ρ, t): extraia r, e1, e2 da distribuição de ruído. Calcule u = A^T r + e1, v = t^T r + e2 + round(q/2)*m, em que m é uma mensagem aleatória de 256 bits. Segredo compartilhado K = KDF(m). Texto cifrado = (u, v).

Com a chave privada s: calcule m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). Os termos de ruído se cancelam aproximadamente, deixando m'≈m. Calcule K = KDF(m'). Probabilidade de falha do desencapsulamento: < 2^{-139}.

Kyber-768: chave pública de 1184 bytes, chave privada de 2400 bytes, texto cifrado de 1088 bytes e segredo compartilhado de 32 bytes. Compare com ECDH-P256: chave pública de 65 bytes e texto cifrado de 32 bytes. Kyber é aproximadamente 15 vezes maior, mas é seguro contra ataques quânticos. Ainda assim, é rápido: encapsulamento e desencapsulamento levam menos de 1 ms em CPUs modernas.

A multiplicação de polinômios em R_q = Z_q[x]/(x^256+1) usa a Transformada Teórica dos Números (NTT) — o análogo da FFT para a aritmética modular. A NTT reduz a multiplicação de polinômios de O(n^2) para O(n log n). q=3329 foi escolhido por oferecer boas propriedades de NTT para n=256.

Durante a migração para PQC, use uma troca híbrida de chaves: combine ECDH e Kyber. Segredo compartilhado = KDF(ECDH_output || Kyber_output). A segurança exige quebrar ambos: adversários clássicos não quebram nenhum dos dois; adversários quânticos quebram ECDH, mas não Kyber. Os rascunhos do TLS 1.3 (IETF RFC 8446) oferecem suporte a KEMs híbridos.

O desencapsulamento de Kyber não executa em tempo constante em implementações ingênuas — a etapa de amostragem por rejeição vaza informações de temporização. A implementação de referência usa NTT em tempo constante e comparação de textos cifrados comprimidos. Use o código de referência da submissão do NIST ou implementações de bibliotecas auditadas.

O NIST publicou o FIPS 203 (ML-KEM) em agosto de 2024. O Chrome adicionou suporte a Kyber no TLS 1.3 em 2023. Cloudflare, Google e AWS estão implantando ECDH+Kyber híbrido. O OpenSSL 3.x adicionou suporte a ML-KEM. As implementações de LibSSH e WireGuard estão em andamento.

Kyber (ML-KEM) é um KEM baseado em Module-LWE que substitui ECDH. Tamanhos de chave de aproximadamente 1 KB; aritmética NTT rápida; resistente a ataques quânticos. Durante a migração, implante-o em modo híbrido com ECDH. Padronizado como FIPS 203. A seguir: os esquemas de assinatura CRYSTALS-Dilithium e Falcon.