CRYSTALS-Kyber.

CRYSTALS-Kyber — это механизм инкапсуляции ключа (KEM), безопасность которого сводится к задаче Module Learning With Errors (MLWE) над структурированными решётками. NIST выбрал его основным постквантовым KEM в 2022 году и в августе 2024-го утвердил окончательным стандартом FIPS 203 (ML-KEM). Стандарт определяет три набора параметров — ML-KEM-512, ML-KEM-768 и ML-KEM-1024 — ориентированных на категории безопасности NIST 1, 3 и 5, с открытыми ключами размером примерно 800, 1184 и 1568 байт и шифртекстами сопоставимого размера.

Внутри IND-CPA-схема с открытым ключом усиливается до IND-CCA2-KEM с помощью преобразования Фуджисаки–Окамото: при декапсуляции восстановленное сообщение повторно шифруется, и любое несовпадение отклоняется, так что подделанный шифртекст даёт псевдослучайный ключ «неявного отклонения», а не раскрывает секреты. Поскольку противник, действующий по стратегии «сохрани сейчас — расшифруй потом», может архивировать сегодняшний трафик для будущего квантового компьютера, Kyber применяется в гибридном режиме (например, X25519MLKEM768), где злоумышленнику приходится взломать и классическую, и постквантовую половину.

Безопасность реализации важна не меньше самой математики. Раскрытие уязвимости KyberSlash (2024) показало, что зависящее от секрета целочисленное деление на модуль q = 3329 выполнялось за переменное время на многих CPU; измеряя время декапсуляции поддельных шифртекстов, можно было восстановить биты ключа. KyberSlash1 и KyberSlash2 были исправлены в эталонном коде (декабрь 2023 года) заменой делений на умножения, и исправления распространились на liboqs, PQClean, CIRCL, AWS-LC и Botan.

flowchart LR
  KG[Генерация ключей] --> PK[Открытый ключ pk]
  KG --> SK[Секретный ключ sk]
  PK --> ENC[Инкапсуляция: выбор m, вывод K и шифртекста c]
  ENC --> C[Шифртекст c]
  ENC --> KS1[Общий секрет K]
  C --> DEC[Декапсуляция ключом sk с проверкой повторного шифрования FO]
  SK --> DEC
  DEC -->|совпадение| KS2[Тот же общий секрет K]
  DEC -->|несовпадение| REJ[Неявное отклонение: псевдослучайный ключ]