PSEC-KEM

PSEC-KEM (Provably Secure Elliptic Curve Encryption — Key Encapsulation Mechanism) — асимметричная схема шифрования. Основана на схеме Эль-Гамаля и эллиптических кривых. Данная схема разработана японской компанией Nippon Telegraph and Telephone(NTT), а именно Эйчиро Фуджисаки и Тацуаки Окамото. Является модификацией механизма PSEC-2 и вместо него в сентябре 2001 года был включен в проект NESSIE, а также в стандарт ISO/IEC 18033-2.

Введение

Предпосылки создания

Криптосистемы, основанные на эллиптических кривых были впервые предложены Нилом Коблицем и Виктором Миллером в 1985 году. Технически, криптосистема, основанная на задаче дискретного логарифмирования, может быть реализована с использованием групп эллиптических кривых в качестве базовой алгебраической структуры. Схема Эль-Гамаля была первым алгоритмом, построенным на проблеме вычисления дискретного логарифма с открытым ключом шифрования. Однако данная схема не отвечает строгим требованиям безопасности против адаптивных атак на основе подобранного шифротекста (CCA). Это побудило криптографов предлагать новые варианты криптосистем, которые являются более надежными.

История создания

В начале 21-го века японская компания Nippon Telegraph and Telephone представила на первый этап проектов NESSIE и CRYPTREC 2000 три протокола шифрования на открытых ключах: PSEC-1, PSEC-2 и PSEC-3. PSEC-1 и PSEC-3 не выдержали конкуренции, а PSEC-2 смог пройти в следующий этап.

Многие из асимметричных алгоритмов были обновлены в начале второго этапа. Для асимметричных схем шифрования, эти изменения были произведены отчасти благодаря последним событиям в сфере криптографии, которые произошли после окончания срока представления работ на конкурсе NESSIE. Второй причиной этих изменений является прогресс стандартизации в ISO / IEC JTC1 / SC27. Стандарты развивались в направлении, определяющем гибридную схему шифрования. Поэтому разработчики модифицировали PSEC-2 на основе замечаний написанных Виктором Шоупом. Модифицированный протокол назвали PSEC-KEM.

Главное отличие PSEC-KEM от PSEC-2 заключается в том, что PSEC-KEM использует другой тип гибридной схемы шифрования. Симметричный ключ, который часто называют сеансовым, используется для шифрования данных, а асимметричный для шифрования самого симметричного ключа. К тому же схема PSEC-2 подвергалась серьёзной критике, поскольку ни в описании протокола, ни в другой литературе не было точного доказательства безопасности алгоритма.

Развитие алгоритма

• 17 апреля 2001 — объявление Royalty-Free лицензии для основных патентов компании NTT в области шифрования и цифровой подписи, в том числе и PSEC.
• 24 сентября 2001 — PSEC был выбран в качестве одного из алгоритмов шифрования на 2-го этапе проекта NESSIE.
• 27 февраля 2003 — проект NESSIE объявил окончательный выбор алгоритмов шифрования и PSEC-КЕМ был включен в портфель рекомендованных NESSIE криптографических примитивов.
• 10 июня 2004 — начался заключительный процесс для публикации предлагаемого стандарта RFC для добавления PSEC-KEM в качестве стандарта для шифрования XML.
• 16 марта 2006 — PSEC-KEM включается в международный стандарт шифрования ISO / IEC (ISO / IEC18033-2).
• 15 июня 2007 — в спецификацию PSEC-KEM была добавлена ISO версия алгоритма.
• 27 июня 2008 — последнее обновление спецификации PSEC-KEM.
• 7 июля 2008 — CRYPTREC одобрил изменение спецификации PSEC-KEM.

Описание

Краткое описание алгоритма

PSEC-KEM относится к классу криптографических алгоритмов, использующих гибридную схему шифрования. Данная схема состоит их двух компонент: KEM (механизм инкапсуляции ключа), предназначенного для шифрования симметричного ключа, и DEM (механизм инкапсуляции данных), предназначенного для шифрования данных. Для совмещения этих двух механизмов необходимо, чтобы длина симметричного ключа на выходе KEM механизма была равно длине ключа, который используется для шифрования в DEM механизме. Начальные параметры следует выбирать так, чтобы данные механизмы были совместимы. Алгоритм генерации пары открытый/закрытый ключ ничем не отличается от стандартного алгоритма, который используется в KEM шифровании. Далее необходимо провести следующие действия. Во-первых, запускаем KEM алгоритм шифрования ключа, на выходе получаем шифротекст c₀ и симметричный ключ k. Во-вторых, запускаем DEM алгоритм, который с помощью симметричного ключа k зашифровывает сообщение M. В-третьих, получаем итоговый шифротекст $C=C_{0}\parallel C_{1}$. Чтобы расшифровать шифротекст C необходимо последовательно произвести следующие действия. Во-первых, разделяем С на $C_{0}$ и $C_{1}$ с помощью специального префикса в сообщении. Во-вторых, используя KEM алгоритм дешифрования получаем симметричный ключ K из $C_{0}$. В-третьих, используя симметричный ключ K расшифровываем сообщение M из $C_{1}$.

Полученная гибридная схема шифрования является семантически безопасной от адаптивых атак на основе подобранного шифротекста (CCA).

Схема работает на трех функциях:

1. KGP-PSEC — алгоритм генерации открытого и закрытого ключей (W, s).
2. ES-PSEC-KEM-Encrypt — алгоритм получения симметричного ключа k и шифротекста c₀ на основе открытого ключа W и формата R.
3. ES-PSEC-KEM-Decrypt — алгоритм получения симметричного ключа k на основе закрытого ключа s и шифротекста c₀.

Параметризующие параметры, открытый и закрытый ключи

PSEC-KEM имеет следующие параметры:

• E — эллиптическая кривая,
• KDF — функция составления ключа,
• hLen — длина начальной строки, целое положительное число,
• keyLen — длина симметричного ключа, целое положительное число,
• p — порядок эллиптической кривой.

Закрытый ключ:

s : неотрицательное число 0 ≤ s < p.

Открытый ключ:

W : точка на эллиптической кривой E.

Типы данных

В PSEC-KEM используется пять различных типов данных:

1. I — целое неотрицательное число.
2. FE — элемент группы.
3. OC — строка байт.
4. BS — строка бит.
5. ECP — точки эллиптической кривой.

Преобразования

Преобразования между типами данных

Функция преобразования принимает данные, представленные в одном из пяти типов и иногда некоторые дополнительные параметры, а затем выводит данные уже в другом типе. Названия всех функций построены по одному алгоритму. Пишется аббревиатура начального типа данных, затем цифра 2, и в конце пишется аббревиатура нового типа данных. Все преобразования имеют обратное преобразование. Например, FE2OSP(a), которое переводит строку байт в элемент группы a, имеет обратное преобразование OS2FEP(M), которое элементу группы ставит в соответствие строку байт. Некоторые из преобразований являются тривиальными и описаны только для формализации изложения. Функция преобразования всегда отвергает неправильные входные данные выводя спенциальную строку «INVALID».

Генерация ключей (KGP-PSEC)

Функция генерации ключей принимает на вход точку $P$ эллиптической кривой $E$ порядка $p$. На выходе получаем открытый ключ $W$ и закрытый ключ $s$ в диапазоне от 0 до $p$.

Кодирование ключа (ES-PSEC-KEM-Encrypt)

Функция кодирования ключа принимает на вход открытый ключ $W$, параметр $R$, который указывает на то, используется ли сжатие или нет, и точку $P$ на эллиптической кривой $E$. На выходе получаем симметричный ключ $k$ и шифротекст $c_{0}$.

Декодирование ключа (ES-PSEC-KEM-Decrypt)

Функция декодирования ключа принимает на вход закрытый ключ $s$, шифротекст $c_{0}$ и точку $P$ на эллиптической кривой $E$. На выходе получаем симметричный ключ $k$.

Параметры системы

Для последней версии данной схемы шифрования допустимыми являются следующие хеш-функции: SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512. Все они описаны в стандарте ISO / IEC 10118-3.

Необходимые параметры

• pLen ≥ 20 (256 бит), $pLen=\lceil \log _{256}p\rceil$.
• hLen ≥ 16, hLen — длина строки байт, которая генерируется случайным образом в самом начале алгоритма кодирования ключа.

Рекомендуемые параметры

• KDF = MGF1(SHA-256, hashLen = 32), KDF(Key derivation function) — функция составления ключа.
• hLen = 32.
• R = Compressed, R — параметр который указывает, нужно ли использовать сжатие данных при кодировании. Этот параметр также должен быть передан получателю, что он смог правильно декодировать информацию.
• keyLen = 32 (256 бит), keyLen — длина симметричного ключа.

Функция составления ключа(MGF1)

Принимает на вход строку байт $M$ произвольной длины и желаемую длину $n$ выходной строки в битах. Алгоритм работы основан на работе хеш-функций. Функция параметризована собственно хеш-функцией $Hash$ и длиной сообщения в байтах на выходе хеш-функции $hashLen$. На выходе работы функции получаем строку байт желаемой длины $n$.

Безопасность

Безопасность PSEC-KEM основана на сложности вычислительной задачи Диффи-Хеллмана(ECDHP), которая состоит в следующем:

Даны (P, xP, yP), где P — точка эллиптической кривой E и x, y случайно выбранные числа из {0, … , p-1}. Необходимо вычислить точку xyP. Предполагается, что эта вычислительная задача является неразрешимой. В общем случае, даже невозможно сказать, является ли конкретное решение правильным.

Доказательство Шоупа

Алгоритмы, которые возникают в попытках решить данную проблему, предполагают создание списка кандидатов на правильное решение. Обозначим:

• A — алгоритм решения задачи Диффи-Хеллмана.
• l — список решений кандидатов для алгоритма А.
• Advantage_CDH(A, l) — вероятность того, что список l содержит правильное решение.

Одно из доказательств безопасности PSEC-KEM состоит в том, чтобы показать, что:

$Advantage_{PSEC-KEM}(A)\leq Advantage_{CDH}(A,l)+\varepsilon$

Причем это должно быть верно для всех алгоритмов А, которые работают конечное время. Это доказательство было представлено Виктором Шоупом в 2001 году.

Работа Бонэ и Липтона

Весомое замечание представили в своей работе Дэн Боне и Ричард Липтон. Они показали, что если ECDLP (задача дискретного логарифмирования) не может быть решена за субэкспоненциальное время, то ECDHP также не может быть решена за это время. Так как широко распространено мнение о том, что проблема дискретного логарифмирования не может быть решена за субэкспоненциальное время, то представленная работа является весомым, хотя и не полностью строгим доводом того, что решение задачи ECDHP весьма трудоемко.

Применение

20 февраля 2003 года PSEC-КЕМ был включён в список криптографических алгоритмов для использования японскими электронными системами государственного управления, а именно министерством общественного управления, внутренних дел почты и телекоммуникаций, и министерством экономики торговли и промышленности. 19 апреля 2005 года PSEC-КЕМ был сертифицирован в качестве стандартного шифра IETF для шифрования.

См. также

• NESSIE
• CRYPTREC
• Протокол Диффи-Хеллмана
• Эллиптическая кривая
• Хеш-функция
• Криптосистема с открытым ключом
• Симметричные криптосистемы
• Гибридная криптосистема

Литература

Статьи

• Alfred Menezes. Evaluation of Security Level of Cryptography: The Revised Version of PSEC-2 (PSEC-KEM) (англ.). Архивировано 8 августа 2017 года.
• Victor Shoup. DRAFT ISO/IEC 18033-2: Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric Ciphers (англ.).
• NTT Corporation. PSEC-KEM Specification version 2.2 (англ.).
• Dan Boneh, Richard J. Lipton. Algorithms for Black-Box Fields and their Application to Cryptography (англ.) // SpringerLink. — Springer Berlin Heidelberg. — ISBN 3540686975. — doi:10.1007/3-540-68697-5_22.
• Victor Shoup. A Proposal for an ISO Standard for Public Key Encryption (англ.).
• Rachel Shipsey. PSEC-KEM (англ.).

Сайты

• NTT Secure Platform Laboratories. Information Security problem (англ.).