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].
PSEC-KEM относится к классу криптографических алгоритмов, использующих гибридную схему шифрования. Данная схема состоит их двух компонент: KEM (механизм инкапсуляции ключа)[англ.], предназначенного для шифрования симметричного ключа, и DEM (механизм инкапсуляции данных), предназначенного для шифрования данных. Для совмещения этих двух механизмов необходимо, чтобы длина симметричного ключа на выходе KEM механизма была равно длине ключа, который используется для шифрования в DEM механизме. Начальные параметры следует выбирать так, чтобы данные механизмы были совместимы. Алгоритм генерации пары открытый/закрытый ключ ничем не отличается от стандартного алгоритма, который используется в KEM шифровании. Далее необходимо провести следующие действия. Во-первых, запускаем KEM алгоритм шифрования ключа, на выходе получаем шифротекст c0 и симметричный ключ k. Во-вторых, запускаем DEM алгоритм, который с помощью симметричного ключа k зашифровывает сообщение M. В-третьих, получаем итоговый шифротекст . Чтобы расшифровать шифротекст C необходимо последовательно произвести следующие действия. Во-первых, разделяем С на и с помощью специального префикса в сообщении. Во-вторых, используя KEM алгоритм дешифрования получаем симметричный ключ K из . В-третьих, используя симметричный ключ K расшифровываем сообщение M из [7].
Полученная гибридная схема шифрования является семантически безопасной от адаптивых атак на основе подобранного шифротекста (CCA)[8].
Схема работает на трех функциях:
PSEC-KEM имеет следующие параметры:
Закрытый ключ:
s : неотрицательное число 0 ≤ s < p.
Открытый ключ:
W : точка на эллиптической кривой E[10].
В PSEC-KEM используется пять различных типов данных:
Функция преобразования принимает данные, представленные в одном из пяти типов и иногда некоторые дополнительные параметры, а затем выводит данные уже в другом типе. Названия всех функций построены по одному алгоритму. Пишется аббревиатура начального типа данных, затем цифра 2, и в конце пишется аббревиатура нового типа данных. Все преобразования имеют обратное преобразование. Например, FE2OSP(a), которое переводит строку байт в элемент группы a, имеет обратное преобразование OS2FEP(M), которое элементу группы ставит в соответствие строку байт. Некоторые из преобразований являются тривиальными и описаны только для формализации изложения. Функция преобразования всегда отвергает неправильные входные данные выводя спенциальную строку «INVALID»[11].
Функция генерации ключей принимает на вход точку эллиптической кривой порядка . На выходе получаем открытый ключ и закрытый ключ в диапазоне от 0 до [12].
Функция кодирования ключа принимает на вход открытый ключ , параметр , который указывает на то, используется ли сжатие или нет, и точку на эллиптической кривой . На выходе получаем симметричный ключ и шифротекст [12].
Функция декодирования ключа принимает на вход закрытый ключ , шифротекст и точку на эллиптической кривой . На выходе получаем симметричный ключ [12].
Для последней версии данной схемы шифрования допустимыми являются следующие хеш-функции: SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512. Все они описаны в стандарте ISO / IEC 10118-3[12].
Принимает на вход строку байт произвольной длины и желаемую длину выходной строки в битах. Алгоритм работы основан на работе хеш-функций. Функция параметризована собственно хеш-функцией и длиной сообщения в байтах на выходе хеш-функции . На выходе работы функции получаем строку байт желаемой длины [12].
Безопасность PSEC-KEM основана на сложности вычислительной задачи Диффи-Хеллмана(ECDHP), которая состоит в следующем:
Даны (P, xP, yP), где P — точка эллиптической кривой E и x, y случайно выбранные числа из {0, … , p-1}. Необходимо вычислить точку xyP. Предполагается, что эта вычислительная задача является неразрешимой. В общем случае, даже невозможно сказать, является ли конкретное решение правильным[14].
Алгоритмы, которые возникают в попытках решить данную проблему, предполагают создание списка кандидатов на правильное решение. Обозначим:
Одно из доказательств безопасности PSEC-KEM состоит в том, чтобы показать, что:
Причем это должно быть верно для всех алгоритмов А, которые работают конечное время. Это доказательство было представлено Виктором Шоупом в 2001 году[16].
Весомое замечание представили в своей работе Дэн Боне и Ричард Липтон[17]. Они показали, что если ECDLP (задача дискретного логарифмирования) не может быть решена за субэкспоненциальное время, то ECDHP также не может быть решена за это время. Так как широко распространено мнение о том, что проблема дискретного логарифмирования не может быть решена за субэкспоненциальное время, то представленная работа является весомым, хотя и не полностью строгим доводом того, что решение задачи ECDHP весьма трудоемко[18].
20 февраля 2003 года PSEC-КЕМ был включён в список криптографических алгоритмов для использования японскими электронными системами государственного управления, а именно министерством общественного управления, внутренних дел почты и телекоммуникаций, и министерством экономики торговли и промышленности. 19 апреля 2005 года PSEC-КЕМ был сертифицирован в качестве стандартного шифра IETF для шифрования[3].