CRYSTALS-Kyber: KEM на основе решёток

CRYSTALS-Kyber (переименованный NIST в ML-KEM в документе FIPS 203) — это механизм инкапсуляции ключа (KEM) на основе Module-LWE. Он заменяет RSA и ECDH при обмене ключами, обеспечивая постквантовую стойкость при практически применимой производительности.

KEM инкапсулирует общий секрет: отправитель генерирует случайный ключ K и шифрует его открытым ключом получателя (инкапсулирует), получая шифротекст C. Получатель декапсулирует C с помощью своего закрытого ключа, чтобы восстановить K. Интерактивный обмен ключами не требуется.

Kyber использует Module-LWE над кольцом R_q = Z_q[x]/(x^256+1), где q=3329. Размерность k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Уровень стойкости составляет соответственно около 128, 192 и 256 бит. Вариант k=3 (Kyber-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}.

Kyber-768: открытый ключ — 1184 байта, закрытый ключ — 2400 байт, шифротекст — 1088 байт, общий секрет — 32 байта. Для сравнения, ECDH-P256 использует открытый ключ размером 65 байт и шифротекст размером 32 байта. Kyber примерно в 15 раз больше, но устойчив к квантовым атакам. При этом он работает быстро: инкапсуляция и декапсуляция занимают менее 1 мс на современных процессорах.

Умножение многочленов в R_q = Z_q[x]/(x^256+1) выполняется с помощью теоретико-числового преобразования (NTT) — аналога FFT для модульной арифметики. NTT сокращает сложность умножения многочленов с O(n^2) до O(n log n). Значение q=3329 выбрано благодаря хорошим свойствам NTT для n=256.

Во время перехода на PQC используйте гибридный обмен ключами: сочетайте ECDH и Kyber. Общий секрет = KDF(ECDH_output || Kyber_output). Для нарушения безопасности необходимо взломать оба алгоритма: классические злоумышленники не взламывают ни один из них, а квантовые злоумышленники взламывают ECDH, но не Kyber. Черновики TLS 1.3 (IETF RFC 8446) поддерживают гибридные KEM.

В наивных реализациях декапсуляция Kyber не выполняется за постоянное время — этап выборки с отклонением раскрывает информацию по времени выполнения. Эталонная реализация использует NTT с постоянным временем выполнения и сравнение сжатого шифротекста за постоянное время. Используйте эталонный код из заявки NIST или проверенные реализации библиотек.

NIST опубликовал FIPS 203 (ML-KEM) в августе 2024 года. В 2023 году Chrome добавил поддержку Kyber в TLS 1.3. Cloudflare, Google и AWS внедряют гибридный ECDH+Kyber. В OpenSSL 3.x добавлена поддержка ML-KEM. Реализации для LibSSH и WireGuard находятся в разработке.

Какой нормативный документ NIST стандартизует CRYSTALS-Kyber?

Kyber (ML-KEM) — это KEM на основе Module-LWE, заменяющий ECDH. Размеры ключей — около 1 KB; быстрая арифметика NTT; устойчивость к квантовым атакам. На время перехода внедряйте его в гибриде с ECDH. Стандартизован в документе FIPS 203. Далее: схемы подписей CRYSTALS-Dilithium и Falcon.