Просмотр кода страницы PSEC-KEM

[[Файл:Start page for Provably Secure Elliptic Curve Key Encapsulation Mechanism.jpg|мини|320x320px]]
'''PSEC-KEM''' (Provably Secure Elliptic Curve Encryption — Key Encapsulation Mechanism) — [[Криптосистема с открытым ключом|асимметричная схема шифрования]]. Основана на [[Схема Эль-Гамаля|схеме Эль-Гамаля]] и [[Эллиптическая криптография|эллиптических кривых]]. Данная схема разработана японской компанией [[Nippon Telegraph and Telephone|Nippon Telegraph and Telephone(NTT)]], а именно [[Эйчиро Фуджисаки]] и [[Окамото, Тацуаки|Тацуаки Окамото]]. Является модификацией механизма [[PSEC-2]] и вместо него в сентябре 2001 года был включен в проект [[NESSIE]], а также в стандарт [[ISO/IEC 18033|ISO/IEC 18033-2]]{{sfn|NTT Corporation|p=4}}{{sfn|R. Shipsey|p=1}}{{sfn|NTT Secure Platform|name = nttPlatform}}.

== Введение ==

=== Предпосылки создания ===
Криптосистемы, основанные на эллиптических кривых были впервые предложены [[Нил Коблиц|Нилом Коблицем]] и {{iw|Миллер, Виктор (криптограф)|Виктором Миллером|en|Victor S. Miller}} в [[1985 год]]у. Технически, криптосистема, основанная на [[ECDLP|задаче дискретного логарифмирования]], может быть реализована с использованием групп эллиптических кривых в качестве базовой алгебраической структуры. Схема Эль-Гамаля была первым алгоритмом, построенным на проблеме вычисления дискретного логарифма с [[Открытый ключ|открытым ключом шифрования]]. Однако данная схема не отвечает строгим требованиям безопасности против [[Атака на основе подобранного шифротекста|адаптивных атак на основе подобранного шифротекста (CCA)]]. Это побудило криптографов предлагать новые варианты криптосистем, которые являются более надежными{{sfn|A. Menezes|p=2|name=menezes2}}.

=== История создания ===
В начале 21-го века японская компания Nippon Telegraph and Telephone представила на первый этап проектов [[NESSIE]] и CRYPTREC 2000 три протокола шифрования на [[Открытый ключ|открытых ключах]]: [[PSEC-1]], PSEC-2 и [[PSEC-3]]. PSEC-1 и PSEC-3 не выдержали конкуренции, а PSEC-2 смог пройти в следующий этап<ref name="menezes2" /><ref name="nttPlatform" />.

Многие из асимметричных алгоритмов были обновлены в начале второго этапа. Для [[Криптосистема с открытым ключом|асимметричных схем шифрования]], эти изменения были произведены отчасти благодаря последним событиям в сфере криптографии, которые произошли после окончания срока представления работ на конкурсе NESSIE. Второй причиной этих изменений является прогресс стандартизации в [[ISO/IEC JTC1|ISO / IEC JTC1 / SC27]]. Стандарты развивались в направлении, определяющем [[Гибридная криптосистема|гибридную схему шифрования]]. Поэтому разработчики модифицировали PSEC-2 на основе замечаний написанных {{iw|Виктор Шоуп|Виктором Шоупом|en|Victor Shoup}}{{sfn|V. Shoup|pp=32—39}}. Модифицированный протокол назвали PSEC-KEM.

Главное отличие PSEC-KEM от PSEC-2 заключается в том, что PSEC-KEM использует другой тип гибридной схемы шифрования. [[Симметричные криптосистемы|Симметричный ключ]], который часто называют сеансовым, используется для шифрования данных, а асимметричный для шифрования самого симметричного ключа. К тому же схема PSEC-2 подвергалась серьёзной критике, поскольку ни в описании протокола, ни в другой литературе не было точного доказательства безопасности алгоритма{{sfn|V. Shoup|p=34}}.

=== Развитие алгоритма ===
* 17 апреля 2001 — объявление [[Royalty-free|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<ref name="nttPlatform" />.

== Описание ==

=== Краткое описание алгоритма ===
PSEC-KEM относится к классу криптографических алгоритмов, использующих гибридную схему шифрования. Данная схема состоит их двух компонент: {{Не переведено 5|Механизм инкапсуляции ключа|KEM (механизм инкапсуляции ключа)|en|Key encapsulation}}, предназначенного для шифрования симметричного ключа, и [[Механизм инкапсуляции данных|DEM (механизм инкапсуляции данных)]], предназначенного для шифрования данных. Для совмещения этих двух механизмов необходимо, чтобы длина симметричного ключа на выходе KEM механизма была равно длине ключа, который используется для шифрования в DEM механизме. Начальные параметры следует выбирать так, чтобы данные механизмы были совместимы. Алгоритм генерации пары открытый/закрытый ключ ничем не отличается от стандартного алгоритма, который используется в KEM шифровании. Далее необходимо провести следующие действия. Во-первых, запускаем KEM алгоритм шифрования ключа, на выходе получаем шифротекст c<sub>0</sub> и симметричный ключ k. Во-вторых, запускаем DEM алгоритм, который с помощью симметричного ключа k зашифровывает сообщение M. В-третьих, получаем итоговый шифротекст <math>C = C_0 \parallel C_1</math>. Чтобы расшифровать шифротекст C необходимо последовательно произвести следующие действия. Во-первых, разделяем С на <math>C_0</math> и <math>C_1</math> с помощью специального префикса в сообщении. Во-вторых, используя KEM алгоритм дешифрования получаем симметричный ключ K из <math>C_0</math>. В-третьих, используя симметричный ключ K расшифровываем сообщение M из <math>C_1</math>{{sfn|V. Shoup|pp=16—17}}.

Полученная гибридная схема шифрования является семантически безопасной от адаптивых атак на основе подобранного шифротекста (CCA){{sfn|A. Menezes|p=3|name=menezes}}.

Схема работает на трех функциях:
# KGP-PSEC — алгоритм генерации открытого и закрытого ключей (W, s).
# ES-PSEC-KEM-Encrypt — алгоритм получения симметричного ключа k и шифротекста c<sub>0</sub> на основе открытого ключа W и формата R.
# ES-PSEC-KEM-Decrypt — алгоритм получения симметричного ключа k на основе закрытого ключа s и шифротекста c<sub>0</sub>{{sfn|NTT Corporation|p=14}}.

=== Параметризующие параметры, открытый и закрытый ключи ===
PSEC-KEM имеет следующие параметры:
* E — [[эллиптическая кривая]],
* KDF — функция составления ключа,
* hLen — длина начальной строки, целое положительное число,
* keyLen — длина симметричного ключа, целое положительное число,
* p — порядок эллиптической кривой.
''<u>Закрытый ключ:</u>''

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

''<u>Открытый ключ:</u>''

W : точка на эллиптической кривой E{{sfn|NTT Corporation|p=13|name=ntt13}}.

=== Типы данных ===
В PSEC-KEM используется пять различных типов данных:
# I — целое неотрицательное число.
# FE — элемент [[Группа (математика)|группы]].
# OC — строка байт.
# BS — строка бит.
# ECP — точки эллиптической кривой<ref name="ntt13" />.

=== Преобразования ===
[[Файл:Преобразования между типами данных.jpg|альт=Преобразования между типами данных|мини|629x629px|Преобразования между типами данных]]
Функция преобразования принимает данные, представленные в одном из пяти типов и иногда некоторые дополнительные параметры, а затем выводит данные уже в другом типе. Названия всех функций построены по одному алгоритму. Пишется аббревиатура начального типа данных, затем цифра 2, и в конце пишется аббревиатура нового типа данных. Все преобразования имеют обратное преобразование. Например, FE2OSP(a), которое переводит строку байт в элемент группы a, имеет обратное преобразование OS2FEP(M), которое элементу группы ставит в соответствие строку байт. Некоторые из преобразований являются тривиальными и описаны только для формализации изложения. Функция преобразования всегда отвергает неправильные входные данные выводя спенциальную строку «INVALID»{{sfn|NTT Corporation|p=5}}.

=== Генерация ключей (KGP-PSEC) ===
Функция генерации ключей принимает на вход точку <math>P</math> эллиптической кривой <math>E</math> порядка <math>p</math>. На выходе получаем открытый ключ <math>W</math> и закрытый ключ <math>s</math> в диапазоне от 0 до <math>p</math>{{sfn|NTT Corporation|pp=14—15|name=ntt1415}}.

=== Кодирование ключа (ES-PSEC-KEM-Encrypt) ===
Функция кодирования ключа принимает на вход открытый ключ <math>W</math>, параметр <math>R</math>, который указывает на то, используется ли сжатие или нет, и точку <math>P</math> на эллиптической кривой <math>E</math>. На выходе получаем симметричный ключ <math>k</math> и шифротекст <math>c_0</math><ref name="ntt1415" />.

=== Декодирование ключа (ES-PSEC-KEM-Decrypt) ===
Функция декодирования ключа принимает на вход закрытый ключ <math>s</math>, шифротекст <math>c_0</math> и точку <math>P</math> на эллиптической кривой <math>E</math>. На выходе получаем симметричный ключ <math>k</math>{{sfn|NTT Corporation|pp=14—15|name=ntt1415}}.

== Параметры системы ==
Для последней версии данной схемы шифрования допустимыми являются следующие [[Хеш-функция|хеш-функции]]: [[SHA-1]], [[SHA-2|SHA-224]], [[SHA-2|SHA-256]], [[SHA-384]] и [[SHA-2|SHA-512]]. Все они описаны в стандарте [[ISO / IEC 10118-3]]<ref name="ntt1415" />.

=== Необходимые параметры ===
* pLen ≥ 20 (256 бит), <math>pLen = \lceil \log_{256}p\rceil</math>{{sfn|NTT Corporation|p=5}}.
* hLen ≥ 16, hLen — длина строки байт, которая генерируется случайным образом в самом начале алгоритма кодирования ключа{{sfn|NTT Corporation|p=17|name=ntt17}}.

=== Рекомендуемые параметры ===
* KDF = MGF1([[SHA-2|SHA-256]], hashLen = 32), KDF(Key derivation function) — функция составления ключа.
* hLen = 32.
* R = Compressed, R — параметр который указывает, нужно ли использовать сжатие данных при кодировании. Этот параметр также должен быть передан получателю, что он смог правильно декодировать информацию.
* keyLen = 32 (256 бит), keyLen — длина симметричного ключа<ref name="ntt17" />.

=== Функция составления ключа(MGF1) ===
Принимает на вход строку байт <math>M</math> произвольной длины и желаемую длину <math>n</math> выходной строки в битах. Алгоритм работы основан на работе хеш-функций. Функция параметризована собственно хеш-функцией <math>Hash</math> и длиной сообщения в байтах на выходе хеш-функции <math>hashLen</math>. На выходе работы функции получаем строку байт желаемой длины <math>n</math><ref name="ntt1415" />.

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

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

====== Доказательство Шоупа ======
Алгоритмы, которые возникают в попытках решить данную проблему, предполагают создание списка кандидатов на правильное решение. Обозначим:
* A — алгоритм решения задачи Диффи-Хеллмана.
* l — список решений кандидатов для алгоритма А.
* Advantage<sub>CDH</sub>(A, l) — вероятность того, что список l содержит правильное решение.
Одно из доказательств безопасности PSEC-KEM состоит в том, чтобы показать, что:

<center><math>Advantage_{PSEC-KEM}(A) \leq Advantage_{CDH}(A, l) + \varepsilon</math>{{sfn|R. Shipsey|p=5}}</center>
Причем это должно быть верно для всех алгоритмов А, которые работают конечное время. Это доказательство было представлено Виктором Шоупом в 2001 году{{sfn|R. Shipsey|pp=5—7}}.

====== Работа Бонэ и Липтона ======
Весомое замечание представили в своей работе [[Дэн Боне]] и [[Ричард Липтон]]{{sfn|D. Boneh, R. J. Lipton|p=283—297}}. Они показали, что если [[ECDLP|ECDLP (задача дискретного логарифмирования)]] не может быть решена за [[Временная сложность алгоритма|субэкспоненциальное время]], то ECDHP также не может быть решена за это время. Так как широко распространено мнение о том, что проблема дискретного логарифмирования не может быть решена за субэкспоненциальное время, то представленная работа является весомым, хотя и не полностью строгим доводом того, что решение задачи ECDHP весьма трудоемко{{sfn|A. Menezes|p=8}}.

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

== См. также ==
* [[NESSIE]]
* [[CRYPTREC]]
* [[Протокол Диффи — Хеллмана на эллиптических кривых|Протокол Диффи-Хеллмана]]
* [[Эллиптическая кривая]]
* [[Хеш-функция]]
* [[Криптосистема с открытым ключом]]
* [[Симметричные криптосистемы]]
* [[Гибридная криптосистема]]

== Примечания ==
{{примечания}}

== Литература ==

=== Статьи ===
* {{статья|автор = Alfred Menezes|заглавие = Evaluation of Security Level of Cryptography: The Revised Version of PSEC-2 (PSEC-KEM)|ссылка = https://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1020_psec.pdf|язык = en|ref = A. Menezes|издание = |archiveurl = https://web.archive.org/web/20170808083417/http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1020_psec.pdf|archivedate = 2017-08-08}}
* {{статья|автор = Victor Shoup|заглавие = DRAFT ISO/IEC 18033-2: Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric Ciphers|ссылка = http://www.shoup.net/iso/std4.pdf|язык = en|ref = V. Shoup DRAFT}}
* {{статья|автор = NTT Corporation|заглавие = PSEC-KEM Specification version 2.2|ссылка = https://info.isl.ntt.co.jp/crypt/eng/psec/dl/iso/psec-kem_v2.2_20080414e.pdf|язык = en|ref = NTT Corporation}}
* {{Статья|автор=Dan Boneh, Richard J. Lipton|заглавие=Algorithms for Black-Box Fields and their Application to Cryptography|ссылка=https://link.springer.com/chapter/10.1007/3-540-68697-5_22|язык=en|ref = D. Boneh, R. J. Lipton |издание=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|ссылка=http://www.shoup.net/papers/iso-2_1.pdf|язык=en|ref = V. Shoup}}
* {{Статья|автор=Rachel Shipsey|заглавие=PSEC-KEM|ссылка=https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/psec-kem.pdf|язык=en|ref = R. Shipsey}}

=== Сайты ===
* {{Статья|автор=NTT Secure Platform Laboratories|заглавие=Information Security problem|ссылка=https://info.isl.ntt.co.jp/crypt/index.html|язык=en|ref = NTT Secure Platform}}

[[Категория:Криптографические протоколы]]
[[Категория:Шифры]]