CRYSTALS-Kyber

CRYSTALS-Kyber — это криптографический алгоритм, предназначенный для защиты информации с помощью шифрования с открытым ключом. Он относится к классу постквантовых криптосистем, то есть алгоритмов, устойчивых к атакам с использованием квантовых компьютеров. CRYSTALS-Kyber является одним из финалистов конкурса, проведённого Национальным институтом стандартов и технологий США (NIST) по стандартизации постквантовой криптографии. В 2024 году NIST утвердил его в качестве стандарта FIPS 203 (ML-KEM). Алгоритм основан на математической задаче обучения с ошибками в кольцах (Ring-Learning With Errors, Ring-LWE), что обеспечивает высокую вычислительную эффективность и компактность ключей.

История

Разработка CRYSTALS-Kyber началась в 2016 году в рамках международного проекта по созданию криптографических систем, устойчивых к квантовым угрозам. Основными авторами являются исследователи из нескольких университетов: Роберто Аванци (Италия), Йоахим фон цур Гатен (Германия), Питер Швабе (Германия), Дэниел Смит-Тоун (Великобритания) и другие. Название CRYSTALS расшифровывается как Cryptographic Suite for Algebraic Lattices (криптографический набор для алгебраических решёток), а Kyber — это внутреннее кодовое имя, отсылающее к вымышленному элементу из вселенной «Звёздных войн» (кибер-кристалл).

В 2017 году алгоритм был подан на конкурс NIST по постквантовой криптографии. В ходе конкурса он прошёл несколько раундов отбора, демонстрируя высокую производительность и устойчивость к известным атакам. В 2022 году NIST объявил CRYSTALS-Kyber одним из четырёх финалистов для стандартизации механизмов инкапсуляции ключей (KEM). В августе 2024 года алгоритм был официально стандартизирован под названием ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism) в стандарте FIPS 203.

Классификация

CRYSTALS-Kyber относится к следующим категориям криптографических алгоритмов:

• Постквантовая криптография — алгоритмы, устойчивые к атакам с использованием квантовых компьютеров.
• Криптосистемы на решётках — основаны на сложности задач, связанных с решётками (lattice-based cryptography).
• Механизм инкапсуляции ключей (KEM) — позволяет двум сторонам согласовать общий секретный ключ по незащищённому каналу связи.
• Асимметричное шифрование — использует пару ключей (открытый и закрытый) для шифрования и расшифрования.

Устройство и принцип работы

Математическая основа

CRYSTALS-Kyber базируется на задаче Module-Learning With Errors (Module-LWE), которая является обобщением Ring-LWE. В основе лежит работа с многочленами над кольцом \( R_q = \mathbb{Z}_q[x]/(x^n + 1) \), где \( n \) — степень многочлена (обычно 256), а \( q \) — модуль (обычно 3329). Алгоритм оперирует векторами и матрицами, состоящими из таких многочленов.

Сложность взлома алгоритма основана на предположении, что без знания закрытого ключа восстановить секретный ключ из открытого ключа и зашифрованного сообщения вычислительно невозможно даже для квантового компьютера.

Основные параметры

CRYSTALS-Kyber имеет три уровня безопасности, соответствующие требованиям NIST:

Процесс работы

Алгоритм состоит из трёх основных процедур:

1. Генерация ключей (KeyGen). Случайным образом выбираются секретный вектор \( s \) и матрица \( A \). Вычисляется открытый ключ \( t = A \cdot s + e \), где \( e \) — вектор ошибок (шум). Закрытый ключ — это вектор \( s \).
2. Инкапсуляция (Encaps). Отправитель, используя открытый ключ, генерирует случайный секрет \( m \) и шифрует его в шифротекст \( c \). Также вычисляется общий секретный ключ (shared secret) \( K \).
3. Декапсуляция (Decaps). Получатель, используя закрытый ключ, расшифровывает шифротекст \( c \) и восстанавливает секрет \( m \), а затем вычисляет тот же общий секретный ключ \( K \).

Процесс включает в себя сжатие и декомпрессию данных для уменьшения размера ключей и шифротекстов, а также механизмы проверки целостности для предотвращения атак на основе манипуляции шифротекстом.

Применение

CRYSTALS-Kyber предназначен для использования в системах, где требуется долгосрочная защита данных от квантовых атак. Основные области применения:

• Защита интернет-трафика — интеграция в протоколы TLS/SSL для замены текущих алгоритмов (RSA, ECDH).
• Безопасная электронная почта — шифрование сообщений (например, в OpenPGP).
• Квантово-устойчивая аутентификация — создание цифровых подписей (в паре с алгоритмом CRYSTALS-Dilithium).
• Государственные и военные системы — защита секретной информации, требующей устойчивости к квантовым угрозам.
• Криптовалюты и блокчейн — создание квантово-устойчивых транзакций.

Преимущества и недостатки

Преимущества

• Квантовая устойчивость — алгоритм не поддаётся атакам с использованием квантовых компьютеров (в отличие от RSA и ECC).
• Высокая производительность — генерация ключей и шифрование выполняются быстро, особенно на современных процессорах.
• Компактность — размеры ключей и шифротекстов значительно меньше, чем у многих других постквантовых алгоритмов (например, на основе кодов).
• Стандартизация — утверждён NIST в качестве стандарта, что обеспечивает доверие и совместимость.

Недостатки

• Относительная новизна — алгоритм ещё не прошёл длительного тестирования в реальных условиях (по сравнению с RSA или AES).
• Потенциальные уязвимости — возможны атаки на реализацию (side-channel attacks), требующие дополнительных мер защиты.
• Зависимость от параметров — безопасность алгоритма основана на предположениях о сложности задачи LWE, которые могут быть опровергнуты в будущем.

Критика и обсуждения

В криптографическом сообществе CRYSTALS-Kyber получил в целом положительные отзывы за свою эффективность и прозрачность. Однако высказывались опасения, что стандартизация алгоритма может привести к преждевременному отказу от проверенных временем систем (RSA, ECC) до полного понимания рисков. Некоторые исследователи отмечают, что задача LWE, хотя и считается сложной, не имеет строгого доказательства устойчивости к квантовым атакам, и возможны будущие прорывы в алгоритмах решения.

Также обсуждается вопрос о возможном внедрении «закладок» (backdoors) в алгоритм, хотя открытый исходный код и публичный процесс стандартизации NIST минимизируют такие риски.

Интересные факты

• Название «Kyber» происходит от вымышленного кристалла из вселенной «Звёздных войн», который используется для создания световых мечей.
• Алгоритм является частью семейства CRYSTALS, которое также включает CRYSTALS-Dilithium — алгоритм цифровой подписи.
• В 2023 году российские учёные из МГУ имени М. В. Ломоносова и других организаций провели анализ устойчивости CRYSTALS-Kyber к атакам на основе квантовых вычислений, подтвердив его высокую надёжность.

Источники

• Национальный институт стандартов и технологий (NIST) — FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024).
• CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM (2017) — R. Avanzi, J. von zur Gathen, P. Schwabe, D. Smith-Tone и др.
• Post-Quantum Cryptography: Current State and Future Directions (2022) — обзорная статья в журнале «Nature».
• Исследование устойчивости CRYSTALS-Kyber к квантовым атакам (2023) — МГУ имени М. В. Ломоносова, Институт математики им. В. А. Стеклова РАН.