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 подвергалась серьёзной критике, поскольку ни в описании протокола, ни в другой литературе не было точного доказательства безопасности алгоритма.
PSEC-KEM относится к классу криптографических алгоритмов, использующих гибридную схему шифрования. Данная схема состоит их двух компонент: KEM (механизм инкапсуляции ключа), предназначенного для шифрования симметричного ключа, и DEM (механизм инкапсуляции данных), предназначенного для шифрования данных. Для совмещения этих двух механизмов необходимо, чтобы длина симметричного ключа на выходе KEM механизма была равно длине ключа, который используется для шифрования в DEM механизме. Начальные параметры следует выбирать так, чтобы данные механизмы были совместимы. Алгоритм генерации пары открытый/закрытый ключ ничем не отличается от стандартного алгоритма, который используется в KEM шифровании. Далее необходимо провести следующие действия. Во-первых, запускаем KEM алгоритм шифрования ключа, на выходе получаем шифротекст c0 и симметричный ключ k. Во-вторых, запускаем DEM алгоритм, который с помощью симметричного ключа k зашифровывает сообщение M. В-третьих, получаем итоговый шифротекст C = C 0 ∥ C 1 {displaystyle C=C_{0}parallel C_{1}} . Чтобы расшифровать шифротекст C необходимо последовательно произвести следующие действия. Во-первых, разделяем С на C 0 {displaystyle C_{0}} и C 1 {displaystyle C_{1}} с помощью специального префикса в сообщении. Во-вторых, используя KEM алгоритм дешифрования получаем симметричный ключ K из C 0 {displaystyle C_{0}} . В-третьих, используя симметричный ключ K расшифровываем сообщение M из C 1 {displaystyle C_{1}} .
Полученная гибридная схема шифрования является семантически безопасной от адаптивых атак на основе подобранного шифротекста (CCA).
Схема работает на трех функциях:
PSEC-KEM имеет следующие параметры:
Закрытый ключ:
s : неотрицательное число 0 ≤ s < p.
Открытый ключ:
W : точка на эллиптической кривой E.
В PSEC-KEM используется пять различных типов данных:
Функция преобразования принимает данные, представленные в одном из пяти типов и иногда некоторые дополнительные параметры, а затем выводит данные уже в другом типе. Названия всех функций построены по одному алгоритму. Пишется аббревиатура начального типа данных, затем цифра 2, и в конце пишется аббревиатура нового типа данных. Все преобразования имеют обратное преобразование. Например, FE2OSP(a), которое переводит строку байт в элемент группы a, имеет обратное преобразование OS2FEP(M), которое элементу группы ставит в соответствие строку байт. Некоторые из преобразований являются тривиальными и описаны только для формализации изложения. Функция преобразования всегда отвергает неправильные входные данные выводя спенциальную строку «INVALID».
Функция генерации ключей принимает на вход точку P {displaystyle P} эллиптической кривой E {displaystyle E} порядка p {displaystyle p} . На выходе получаем открытый ключ W {displaystyle W} и закрытый ключ s {displaystyle s} в диапазоне от 0 до p {displaystyle p} .
Функция кодирования ключа принимает на вход открытый ключ W {displaystyle W} , параметр R {displaystyle R} , который указывает на то, используется ли сжатие или нет, и точку P {displaystyle P} на эллиптической кривой E {displaystyle E} . На выходе получаем симметричный ключ k {displaystyle k} и шифротекст c 0 {displaystyle c_{0}} .
Функция декодирования ключа принимает на вход закрытый ключ s {displaystyle s} , шифротекст c 0 {displaystyle c_{0}} и точку P {displaystyle P} на эллиптической кривой E {displaystyle E} . На выходе получаем симметричный ключ k {displaystyle k} .
Для последней версии данной схемы шифрования допустимыми являются следующие хеш-функции: SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512. Все они описаны в стандарте ISO / IEC 10118-3.
Принимает на вход строку байт M {displaystyle M} произвольной длины и желаемую длину n {displaystyle n} выходной строки в битах. Алгоритм работы основан на работе хеш-функций. Функция параметризована собственно хеш-функцией H a s h {displaystyle Hash} и длиной сообщения в байтах на выходе хеш-функции h a s h L e n {displaystyle hashLen} . На выходе работы функции получаем строку байт желаемой длины n {displaystyle n} .
Безопасность PSEC-KEM основана на сложности вычислительной задачи Диффи-Хеллмана(ECDHP), которая состоит в следующем:
Даны (P, xP, yP), где P — точка эллиптической кривой E и x, y случайно выбранные числа из {0, … , p-1}. Необходимо вычислить точку xyP. Предполагается, что эта вычислительная задача является неразрешимой. В общем случае, даже невозможно сказать, является ли конкретное решение правильным.
Доказательство ШоупаАлгоритмы, которые возникают в попытках решить данную проблему, предполагают создание списка кандидатов на правильное решение. Обозначим:
Одно из доказательств безопасности PSEC-KEM состоит в том, чтобы показать, что:
A d v a n t a g e P S E C − K E M ( A ) ≤ A d v a n t a g e C D H ( A , l ) + ε {displaystyle Advantage_{PSEC-KEM}(A)leq Advantage_{CDH}(A,l)+varepsilon }Причем это должно быть верно для всех алгоритмов А, которые работают конечное время. Это доказательство было представлено Виктором Шоупом в 2001 году.
Работа Бонэ и ЛиптонаВесомое замечание представили в своей работе Дэн Бонех и Ричард Липтон. Они показали, что если ECDLP (задача дискретного логарифмирования) не может быть решена за субэкспоненциальное время, то ECDHP также не может быть решена за это время. Так как широко распространено мнение о том, что проблема дискретного логарифмирования не может быть решена за субэкспоненциальное время, то представленная работа является весомым, хотя и не полностью строгим доводом того, что решение задачи ECDHP весьма трудоемко.
20 февраля 2003 года PSEC-КЕМ был включён в список криптографических алгоритмов для использования японскими электронными системами государственного управления, а именно министерством общественного управления, внутренних дел почты и телекоммуникаций, и министерством экономики торговли и промышленности. 19 апреля 2005 года PSEC-КЕМ был сертифицирован в качестве стандартного шифра IETF для шифрования.