CRYSTALS-Kyber: 격자 기반 KEM

CRYSTALS-카이버(NIST가 FIPS 203에서 ML-KEM으로 이름을 변경)는 Module-LWE에 기반한 키 캡슐화 메커니즘(KEM)입니다. 키 교환에서 RSA와 ECDH를 대체하며, 실용적인 성능 수준에서 양자 내성을 제공합니다.

KEM은 공유 비밀을 캡슐화합니다. 송신자가 무작위 키 K를 생성하고 수신자의 공개키로 암호화하여 캡슐화하면 암호문 C가 생성됩니다. 수신자는 자신의 개인키로 C를 디캡슐화하여 K를 복원합니다. 상호작용 방식의 키 교환이 필요하지 않습니다.

카이버는 환 R_q = Z_q[x]/(x^256+1)에서 q=3329인 Module-LWE를 사용합니다. 차원 k는 카이버-512에서 2, 카이버-768에서 3, 카이버-1024에서 4입니다. 보안 수준은 각각 약 128비트, 192비트, 256비트입니다. k=3인 카이버-768이 권장되는 기본값입니다.

시드 ρ에서 행렬 A ∈ R_q^{k×k}를 확장하여 생성합니다. 비밀 s와 잡음 e는 중심 이항 분포에서 샘플링합니다(계수가 작음). 공개키는 (ρ, t=As+e)이고 개인키는 s입니다. 잡음 e는 작지만 공개키에서 s를 복원하지 못하도록 합니다.

공개키 (ρ, t)의 보유자에게 공유 비밀을 보내려면 잡음 분포에서 r, e1, e2를 샘플링합니다. u = A^T r + e1, v = t^T r + e2 + round(q/2)*m을 계산합니다. 여기서 m은 무작위 256비트 메시지입니다. 공유 비밀 K = KDF(m)이고 암호문은 (u, v)입니다.

개인키 s를 사용하여 m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1))를 계산합니다. 잡음 항들이 근사적으로 상쇄되어 m'≈m이 됩니다. K = KDF(m')을 계산합니다. 디캡슐화 실패 확률은 < 2^{-139}입니다.

카이버-768의 공개키는 1184바이트, 개인키는 2400바이트, 암호문은 1088바이트, 공유 비밀은 32바이트입니다. ECDH-P256과 비교하면 공개키는 65바이트이고 암호문은 32바이트입니다. 카이버는 약 15배 더 크지만 양자 컴퓨터에 안전합니다. 그래도 최신 CPU에서 캡슐화와 디캡슐화를 합쳐 1ms 미만으로 빠르게 처리됩니다.

R_q = Z_q[x]/(x^256+1)에서 다항식 곱셈은 FFT의 모듈러 연산 아날로그인 수론적 변환(NTT)을 사용합니다. NTT는 다항식 곱셈의 복잡도를 O(n^2)에서 O(n log n)으로 낮춥니다. q=3329는 n=256에서 좋은 NTT 특성을 갖도록 선택되었습니다.

PQC로 전환하는 동안 하이브리드 키 교환을 사용합니다. ECDH와 카이버를 결합하여 공유 비밀을 KDF(ECDH_output || Kyber_output)으로 계산합니다. 보안을 유지하려면 두 방식 모두를 해독해야 합니다. 고전 공격자는 어느 쪽도 해독하지 못하고, 양자 공격자는 ECDH를 해독하지만 카이버는 해독하지 못합니다. TLS 1.3 초안(IETF RFC 8446)은 하이브리드 KEM을 지원합니다.

단순한 구현에서 카이버 디캡슐화는 상수 시간이 아닙니다. 거부 샘플링 단계에서 실행 시간이 유출되기 때문입니다. 참조 구현은 상수 시간 NTT와 압축된 암호문 비교를 사용합니다. NIST 제출본의 참조 코드나 보안 감사를 거친 라이브러리 구현을 사용해야 합니다.

NIST는 2024년 8월에 FIPS 203(ML-KEM)을 발표했습니다. 크롬은 2023년에 TLS 1.3에서 카이버 지원을 추가했습니다. 클라우드플레어, 구글, AWS는 하이브리드 ECDH+카이버를 배포하고 있습니다. OpenSSL 3.x는 ML-KEM 지원을 추가했습니다. LibSSH와 WireGuard 구현은 진행 중입니다.

CRYSTALS-카이버를 표준화한 NIST 표준 문서는 무엇인가요?

카이버(ML-KEM)는 ECDH를 대체하는 Module-LWE 기반 KEM입니다. 키 크기는 약 1KB이고 NTT 연산은 빠르며 양자 내성을 제공합니다. 전환 중에는 ECDH와 하이브리드 방식으로 배포합니다. FIPS 203으로 표준화되었습니다. 다음으로 CRYSTALS-딜리시움과 팔콘 서명 방식을 살펴봅니다.