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

Введение

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

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

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

В начале 21-го века японская компания Nippon Telegraph and Telephone представила на первый этап проектов NESSIE и CRYPTREC 2000 три протокола шифрования на открытых ключах : , PSEC-2 и . 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 шифровании. Далее необходимо провести следующие действия. Во-первых, запускаем KEM алгоритм шифрования ключа, на выходе получаем шифротекст c ₀ и симметричный ключ k. Во-вторых, запускаем DEM алгоритм, который с помощью симметричного ключа k зашифровывает сообщение M. В-третьих, получаем итоговый шифротекст ${\displaystyle C=C_{0}\parallel C_{1}}$ . Чтобы расшифровать шифротекст C необходимо последовательно произвести следующие действия. Во-первых, разделяем С на ${\displaystyle C_{0}}$ и ${\displaystyle C_{1}}$ с помощью специального префикса в сообщении. Во-вторых, используя KEM алгоритм дешифрования получаем симметричный ключ K из ${\displaystyle C_{0}}$ . В-третьих, используя симметричный ключ K расшифровываем сообщение M из ${\displaystyle 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)

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

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

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

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

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

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

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

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

• pLen ≥ 20 (256 бит), ${\displaystyle 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)

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

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

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

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

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

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

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

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

${\displaystyle 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. (англ.) . 8 августа 2017 года.
• Victor Shoup. (англ.) .
• NTT Corporation. (англ.) .
• Dan Boneh, Richard J. Lipton. (англ.) // SpringerLink. — Springer Berlin Heidelberg. — ISBN 3540686975 . — doi : .
• Victor Shoup. (англ.) .
• Rachel Shipsey. (англ.) .

Сайты

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