Механизм инкапсуляции ключей¶

Механизм инкапсуляции ключей (англ. Key Encapsulation Mechanism, KEM) — это криптографический протокол, предназначенный для безопасной передачи симметричного ключа (сеансового ключа) между двумя сторонами по открытому каналу связи с использованием асимметричной криптографии. В отличие от традиционных схем шифрования ключей, KEM генерирует и инкапсулирует (упаковывает) ключ внутри одного зашифрованного сообщения, которое может быть расшифровано только владельцем соответствующего секретного ключа. KEM является фундаментальным строительным блоком в современных криптосистемах, особенно в протоколах гибридного шифрования и постквантовой криптографии.

¶История и развитие

Концепция инкапсуляции ключей возникла как развитие идей гибридного шифрования, где асимметричная криптография используется для защиты симметричного ключа. В 1990-х годах стандартные схемы, такие как RSA-OAEP (Optimal Asymmetric Encryption Padding), фактически выполняли функцию KEM, но не были формально описаны как отдельный механизм.

Формальное определение KEM было введено в 2003 году Виктором Шоупом (Victor Shoup) в рамках работы над стандартом ISO/IEC 18033-2. Шоуп предложил строгую математическую модель, отделяющую процесс генерации и инкапсуляции ключа от его расшифровки. Это позволило унифицировать подходы к гибридному шифрованию и упростить анализ безопасности.

В 2010-х годах, с развитием постквантовой криптографии, KEM стал центральным элементом многих схем, устойчивых к атакам с использованием квантовых компьютеров. В 2022 году Национальный институт стандартов и технологий США (NIST) выбрал алгоритм CRYSTALS-Kyber в качестве основного стандарта для постквантового KEM.

¶Принцип работы

Механизм инкапсуляции ключей состоит из трёх основных алгоритмов:

1. Генерация ключей (KeyGen): Сторона-получатель генерирует пару ключей — открытый ключ (pk) и секретный ключ (sk). Открытый ключ публикуется, секретный остаётся у получателя.
2. Инкапсуляция (Encaps): Сторона-отправитель, используя открытый ключ получателя, генерирует случайный сеансовый ключ K и его зашифрованную версию — шифротекст C. На выходе алгоритма получается пара (K, C).
3. Декапсуляция (Decaps): Получатель, используя свой секретный ключ и полученный шифротекст C, восстанавливает исходный сеансовый ключ K. Если шифротекст подделан или повреждён, алгоритм возвращает ошибку или случайный ключ.

Важное свойство KEM — детерминированность декапсуляции: для одного и того же шифротекста и секретного ключа всегда получается один и тот же ключ. Инкапсуляция, напротив, является вероятностной — каждый вызов алгоритма генерирует новый случайный ключ и новый шифротекст.

¶Отличие от традиционных схем

Традиционные схемы шифрования с открытым ключом (например, RSA-OAEP) могут использоваться для передачи ключа, но они имеют ряд недостатков:

• Избыточность: Симметричный ключ обычно имеет фиксированную длину (например, 256 бит), а асимметричное шифрование оперирует с блоками данных, размер которых может быть больше. Это требует дополнительного форматирования.
• Отсутствие гарантии случайности: При шифровании ключа с помощью детерминированного алгоритма (например, RSA без дополнения) злоумышленник может проверить догадки о значении ключа.
• Сложность анализа безопасности: Доказательство безопасности схемы гибридного шифрования, построенной на основе общего шифрования, требует более сложных математических выкладок.

KEM решает эти проблемы, предоставляя чётко определённый интерфейс, гарантирующий, что сгенерированный ключ является случайным и неотличимым от равномерно распределённого случайного значения для любого злоумышленника, не обладающего секретным ключом.

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

¶По математической основе

• На основе целочисленных решёток: KEM, построенные на задачах LWE (Learning With Errors) и Ring-LWE. Примеры: CRYSTALS-Kyber, FrodoKEM. Эти схемы считаются устойчивыми к квантовым атакам.
• На основе кодов, исправляющих ошибки: Например, Classic McEliece. Основаны на сложности декодирования случайного линейного кода.
• На основе хэш-функций: KEM, построенные на основе схемы Меркла — Дамгора. Пример: HQC (Hamming Quasi-Cyclic).
• На основе эллиптических кривых: Традиционные схемы, такие как ECDH (Elliptic Curve Diffie-Hellman), используемые в протоколах TLS 1.3. Однако ECDH не является полноценным KEM, так как не включает формальную инкапсуляцию.

¶По типу безопасности

• IND-CPA (Indistinguishability under Chosen Plaintext Attack): Схема устойчива к атакам с выбором открытого текста. Гарантирует, что шифротексты неотличимы для разных ключей.
• IND-CCA (Indistinguishability under Chosen Ciphertext Attack): Более сильное свойство, гарантирующее неотличимость даже при наличии доступа к оракулу декапсуляции. Большинство современных KEM, включая CRYSTALS-Kyber, обеспечивают IND-CCA2 — устойчивость к адаптивным атакам с выбором шифротекста.

¶Применение

¶Гибридное шифрование

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

1. Отправитель вызывает Encaps(pk) и получает (K, C).
2. Использует K как ключ для симметричного шифрования сообщения M, получая шифротекст CT.
3. Передаёт получателю пару (C, CT).

Получатель, в свою очередь, вызывает Decaps(sk, C) для восстановления K, а затем расшифровывает CT.

¶Протоколы TLS и HTTPS

В современных версиях протокола TLS (1.3) KEM используется для установления сеансового ключа. Например, схемы на основе эллиптических кривых (ECDHE) фактически реализуют KEM, хотя и не называются так явно. В постквантовых расширениях TLS (например, в проекте Open Quantum Safe) KEM, такие как Kyber, используются для защиты от квантовых атак.

¶Постквантовая криптография

KEM является ключевым компонентом большинства постквантовых криптосистем, проходящих стандартизацию NIST. В 2024 году NIST утвердил три алгоритма:

• CRYSTALS-Kyber (ML-KEM) — основной стандарт для общего шифрования.
• CRYSTALS-Dilithium (ML-DSA) — для цифровых подписей.
• FALCON и SPHINCS+ — дополнительные алгоритмы подписей.

Все эти схемы используют KEM как часть своей архитектуры.

¶Системы электронной почты и мессенджеры

В протоколах сквозного шифрования, таких как Signal Protocol и Matrix, KEM используется для обмена ключами между участниками. Например, в протоколе Signal применяется X3DH (Extended Triple Diffie-Hellman), который по сути является KEM, основанным на эллиптических кривых.

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

• Размер шифротекста в KEM обычно значительно меньше, чем в традиционных схемах шифрования. Например, для CRYSTALS-Kyber-512 шифротекст занимает 768 байт, а для RSA-2048 — 256 байт, но последний не обеспечивает постквантовой безопасности.
• В некоторых KEM, таких как Classic McEliece, размер открытого ключа может достигать нескольких мегабайт, что делает их непригодными для мобильных устройств, но безопасными для долговременного хранения.
• KEM может быть комбинирован с протоколами аутентификации, такими как HMQV (Hashed Menezes-Qu-Vanstone), для обеспечения взаимной аутентификации сторон.

¶Критика и ограничения

• Уязвимость к квантовым атакам: Традиционные KEM, основанные на RSA и эллиптических кривых, уязвимы к атакам с использованием квантовых компьютеров (алгоритм Шора). Это стимулировало разработку постквантовых схем.
• Сложность реализации: Постквантовые KEM, особенно на основе решёток, требуют сложных математических операций, что может приводить к ошибкам в реализации. Например, уязвимости в реализации CRYSTALS-Kyber были обнаружены в 2023 году.
• Проблемы с производительностью: Некоторые KEM, такие как Classic McEliece, имеют высокие требования к памяти и вычислительным ресурсам, что ограничивает их применение на встраиваемых устройствах.

¶Источники

• Shoup, V. (2003). A Proposal for an ISO Standard for Public Key Encryption. ISO/IEC 18033-2.
• National Institute of Standards and Technology (NIST). (2022). Post-Quantum Cryptography: Selected Algorithms 2022.
• Bernstein, D. J., & Lange, T. (2017). Post-Quantum Cryptography. Springer.
• Peikert, C. (2014). Lattice Cryptography for the Internet. In: Post-Quantum Cryptography.