PSEC-KEM (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^[1]^[2]^[3].

Введение

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

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

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

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

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

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

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

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^[3].

Описание

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

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}$ ^[7].

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

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

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

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

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

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

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

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

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

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

Типы данных

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

I — целое неотрицательное число.
FE — элемент группы.
OC — строка байт.
BS — строка бит.
ECP — точки эллиптической кривой^[10].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^[15]

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

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

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

Применение

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

См. также

Примечания

↑ NTT Corporation, p. 4.
↑ R. Shipsey, p. 1.
↑ ¹ ² ³ ⁴ NTT Secure Platform.
↑ ¹ ² A. Menezes, p. 2.
↑ V. Shoup, pp. 32—39.
↑ V. Shoup, p. 34.
↑ V. Shoup, pp. 16—17.
↑ A. Menezes, p. 3.
↑ NTT Corporation, p. 14.
↑ ¹ ² NTT Corporation, p. 13.
↑ ¹ ² NTT Corporation, p. 5.
↑ ¹ ² ³ ⁴ ⁵ NTT Corporation, pp. 14—15.
↑ ¹ ² NTT Corporation, p. 17.
↑ R. Shipsey, pp. 4—5.
↑ R. Shipsey, p. 5.
↑ R. Shipsey, pp. 5—7.
↑ D. Boneh, R. J. Lipton, p. 283—297.
↑ A. Menezes, p. 8.

Литература

Статьи

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 (англ.).

[_b56a00051df224f5-1] NTT Corporation, p. 4.

[_95dcb6f758f52e01-2] R. Shipsey, p. 1.

[nttPlatform-3] ¹ ² ³ ⁴ NTT Secure Platform.

[menezes2-4] ¹ ² A. Menezes, p. 2.

[_98a1cf458dbab1af-5] V. Shoup, pp. 32—39.

[_ee930178b2d14751-6] V. Shoup, p. 34.

[_613b2a45df30567d-7] V. Shoup, pp. 16—17.

[menezes-8] A. Menezes, p. 3.

[_3542f8b1e274c3e4-9] NTT Corporation, p. 14.

[ntt13-10] ¹ ² NTT Corporation, p. 13.

[_b56a00051df224f4-11] ¹ ² NTT Corporation, p. 5.

[ntt1415-12] ¹ ² ³ ⁴ ⁵ NTT Corporation, pp. 14—15.

[ntt17-13] ¹ ² NTT Corporation, p. 17.

[_890db1c249bf6b8b-14] R. Shipsey, pp. 4—5.

[_95dcb6f758f52e05-15] R. Shipsey, p. 5.

[_8218d1ce37713b74-16] R. Shipsey, pp. 5—7.

[_33043922bf7540c8-17] D. Boneh, R. J. Lipton, p. 283—297.

[_dd676db7b3169817-18] A. Menezes, p. 8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]