KEM/DEM-парадигма

KEM/DEM-парадигма — это концепция в области криптографии и теории сложности, описывающая два взаимодополняющих подхода к построению систем с открытым ключом: KEM (Key Encapsulation Mechanism — механизм инкапсуляции ключа) и DEM (Data Encapsulation Mechanism — механизм инкапсуляции данных). Парадигма была формализована в конце 1990-х — начале 2000-х годов как способ гибридного шифрования, сочетающего асимметричные и симметричные криптографические примитивы. Она лежит в основе многих современных стандартов, включая постквантовую криптографию, где KEM и DEM используются для обеспечения безопасности при передаче данных.

История и происхождение

Концепция гибридного шифрования, объединяющего асимметричные и симметричные алгоритмы, существовала и ранее, но её формализация в виде KEM/DEM-парадигмы была предложена в 1999 году криптографами Виктором Шоупом (Victor Shoup) и Рональдом Крамером (Ronald Cramer). В работе «Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack» они впервые чётко разделили задачи генерации сессионного ключа (KEM) и шифрования данных (DEM). Парадигма получила широкое признание после публикации в 2001 году статьи «A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack» (Cramer-Shoup), где была предложена схема, устойчивая к атакам на основе подобранного шифротекста (CCA2).

До появления KEM/DEM большинство гибридных схем строились ad hoc, что часто приводило к уязвимостям. Парадигма позволила формально доказывать безопасность гибридных конструкций, разделяя требования к асимметричной и симметричной частям. В 2002 году Коблиц и Менезес ввели термин «KEM/DEM» в контексте криптографии на эллиптических кривых. С 2010-х годов парадигма стала стандартом де-факто для многих протоколов, включая TLS 1.3 и постквантовые алгоритмы (например, Kyber — KEM, принятый NIST в 2022 году).

Основные понятия

KEM (Key Encapsulation Mechanism)

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

• Gen() — генерация пары ключей (открытый ключ pk, секретный ключ sk).
• Encaps(pk) — инкапсуляция: на вход подаётся открытый ключ, на выходе — шифротекст c (иногда называемый «капсулой») и сессионный ключ K.
• Decaps(sk, c) — декапсуляция: на вход подаётся секретный ключ и шифротекст, на выходе — сессионный ключ K (или символ ошибки ⊥).

KEM гарантирует, что ключ K является случайным и не может быть восстановлен из c без знания sk. Безопасность KEM обычно определяется как устойчивость к атакам на основе подобранного шифротекста (IND-CCA2).

DEM (Data Encapsulation Mechanism)

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

• Enc(K, m) — шифрование: на вход подаётся ключ K и открытый текст m, на выходе — шифротекст d.
• Dec(K, d) — расшифрование: на вход подаётся ключ K и шифротекст d, на выходе — открытый текст m (или символ ошибки ⊥).

DEM должен быть безопасным в модели IND-CCA2 (устойчивость к атакам на основе подобранного шифротекста) или, как минимум, IND-CPA (устойчивость к атакам на основе подобранного открытого текста). Обычно DEM реализуется с использованием блочных шифров (например, AES) в режиме аутентифицированного шифрования (AEAD), таком как GCM или CCM.

Принцип работы гибридной схемы

Гибридная схема на основе KEM/DEM работает следующим образом:

1. Генерация ключей: Получатель генерирует пару ключей (pk, sk) с помощью KEM.Gen() и публикует открытый ключ pk.
2. Шифрование (отправитель):

• Вызывает KEM.Encaps(pk), получает капсулу c и сессионный ключ K.
• Вызывает DEM.Enc(K, m), получает шифротекст данных d.
• Отправляет пару (c, d) получателю.

1. Расшифрование (получатель):

• Вызывает KEM.Decaps(sk, c), получает сессионный ключ K.
• Вызывает DEM.Dec(K, d), получает открытый текст m.

Ключевое преимущество — асимметричная часть (KEM) обрабатывает только короткий сессионный ключ (обычно 128–256 бит), а симметричная часть (DEM) — произвольные объёмы данных. Это значительно быстрее, чем чисто асимметричное шифрование, и безопаснее, чем чисто симметричное (из-за проблем с распределением ключей).

Классификация и виды

По типу KEM

• RSA-KEM: Основан на задаче RSA. Прост, но уязвим к квантовым атакам.
• EC-KEM: Использует эллиптические кривые (например, ECDH). Широко применяется в TLS.
• Постквантовые KEM: Например, Kyber (на основе решёток), Classic McEliece (на основе кодов), BIKE (на основе кодов). Разрабатываются для устойчивости к квантовым компьютерам.

По типу DEM

• Симметричные шифры: AES, ChaCha20.
• Режимы работы: GCM (аутентифицированное шифрование), CCM, OCB.
• Потоковые шифры: Salsa20, HC-128.

По уровню безопасности

• IND-CPA: Базовая безопасность против атак на основе открытого текста.
• IND-CCA1: Устойчивость к атакам на основе подобранного шифротекста (но не адаптивным).
• IND-CCA2: Наивысший уровень, устойчивость к адаптивным атакам.

Применение

Протоколы и стандарты

• TLS 1.3: Использует KEM/DEM-парадигму в виде гибридного шифрования на основе ECDHE (KEM) и AEAD (DEM). В версии 1.3 также поддерживаются постквантовые KEM (например, Kyber) в качестве экспериментальных расширений.
• IPsec: Применяет KEM/DEM в рамках протокола IKE (Internet Key Exchange).
• SSH: Использует аналогичные схемы для установления сессионных ключей.
• PGP/GnuPG: Гибридное шифрование на основе RSA или ElGamal (KEM) и AES (DEM).

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

В рамках конкурса NIST (Национальный институт стандартов и технологий США) по постквантовой криптографии (2016–2022) KEM/DEM-парадигма стала центральной. Победивший алгоритм Kyber (на основе решёток) является KEM, а для шифрования данных используется DEM (обычно AES-GCM). Аналогично, другие финалисты (Saber, NTRU) также основаны на KEM.

Криптовалюты и блокчейн

В некоторых криптовалютах (например, Monero) используются KEM-подобные схемы для обеспечения конфиденциальности транзакций (Stealth Addresses). Однако полная KEM/DEM-парадигма применяется редко из-за требований к децентрализации.

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

Сложность реализации

Хотя парадигма формально проста, на практике требуется аккуратная реализация, чтобы избежать уязвимостей. Например, ошибки в генерации случайных чисел в KEM могут привести к компрометации всех сессионных ключей. Также необходимо обеспечить аутентичность шифротекста DEM, иначе злоумышленник может подменить данные.

Квантовая угроза

Классические KEM (RSA, ECDH) уязвимы к атакам с использованием квантовых компьютеров (алгоритм Шора). Переход на постквантовые KEM (например, Kyber) требует значительных изменений в инфраструктуре. Кроме того, постквантовые KEM имеют большие размеры ключей и шифротекстов, что может быть проблемой для ограниченных устройств (IoT).

Проблемы с доказательством безопасности

Хотя для KEM/DEM существуют формальные доказательства безопасности (например, теорема Шоупа-Крамера), они часто требуют сильных предположений (например, о случайном оракуле). В реальных системах эти предположения могут не выполняться, что приводит к скрытым уязвимостям.

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

• Термин «капсула» (capsule) для шифротекста KEM был введён Шоупом в 1999 году и происходит от латинского «capsula» (коробочка).
• В 2019 году NIST выбрал Kyber как единственный KEM для постквантовой стандартизации, отклонив другие предложения (например, FrodoKEM) из-за производительности.
• В России KEM/DEM-парадигма используется в государственных стандартах криптографической защиты информации (ГОСТ Р 34.10-2012, ГОСТ Р 34.11-2012), хотя формально она не выделена как отдельная концепция.

Источники

• Shoup, V. (1999). «Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack».
• Cramer, R., Shoup, V. (2001). «A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack».
• NIST (2022). «Post-Quantum Cryptography: Selected Algorithms».
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography».
• Bernstein, D. J., Lange, T. (2017). «Post-Quantum Cryptography».