WikiSort.ru - Не сортированное

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

Криптосистемы, основанные на эллиптических кривых были впервые предложены Нилом Коблицем и Виктором Миллером^[en] в 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 на основе замечаний написанных Виктором Шоупом^[en][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 (механизм инкапсуляции ключа)^[en], предназначенного для шифрования симметричного ключа, и DEM (механизм инкапсуляции данных), предназначенного для шифрования данных. Для совмещения этих двух механизмов необходимо, чтобы длина симметричного ключа на выходе 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}}$ ^[7].

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

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

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

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

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

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

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

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

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

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

Типы данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle Advantage_{PSEC-KEM}(A)\leq Advantage_{CDH}(A,l)+\varepsilon }$ ^[15]

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

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

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

Статьи

• Alfred Menezes. Evaluation of Security Level of Cryptography: The Revised Version of PSEC-2 (PSEC-KEM) (англ.).
• 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 (англ.).