Русская Википедия:PSEC-KEM

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Start page for Provably Secure Elliptic Curve Key Encapsulation Mechanism.jpg

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

Введение

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

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

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

В начале 21-го века японская компания Nippon Telegraph and Telephone представила на первый этап проектов NESSIE и CRYPTREC 2000 три протокола шифрования на открытых ключах: PSEC-1, PSEC-2 и PSEC-3. PSEC-1 и PSEC-3 не выдержали конкуренции, а PSEC-2 смог пройти в следующий этап[1][2].

Многие из асимметричных алгоритмов были обновлены в начале второго этапа. Для асимметричных схем шифрования, эти изменения были произведены отчасти благодаря последним событиям в сфере криптографии, которые произошли после окончания срока представления работ на конкурсе NESSIE. Второй причиной этих изменений является прогресс стандартизации в ISO / IEC JTC1 / SC27. Стандарты развивались в направлении, определяющем гибридную схему шифрования. Поэтому разработчики модифицировали PSEC-2 на основе замечаний написанных Шаблон:IwШаблон:Sfn. Модифицированный протокол назвали PSEC-KEM.

Главное отличие PSEC-KEM от PSEC-2 заключается в том, что PSEC-KEM использует другой тип гибридной схемы шифрования. Симметричный ключ, который часто называют сеансовым, используется для шифрования данных, а асимметричный для шифрования самого симметричного ключа. К тому же схема PSEC-2 подвергалась серьёзной критике, поскольку ни в описании протокола, ни в другой литературе не было точного доказательства безопасности алгоритмаШаблон:Sfn.

Развитие алгоритма

  • 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[2].

Описание

Краткое описание алгоритма

PSEC-KEM относится к классу криптографических алгоритмов, использующих гибридную схему шифрования. Данная схема состоит их двух компонент: Шаблон:Не переведено 5, предназначенного для шифрования симметричного ключа, и DEM (механизм инкапсуляции данных), предназначенного для шифрования данных. Для совмещения этих двух механизмов необходимо, чтобы длина симметричного ключа на выходе KEM механизма была равно длине ключа, который используется для шифрования в DEM механизме. Начальные параметры следует выбирать так, чтобы данные механизмы были совместимы. Алгоритм генерации пары открытый/закрытый ключ ничем не отличается от стандартного алгоритма, который используется в KEM шифровании. Далее необходимо провести следующие действия. Во-первых, запускаем KEM алгоритм шифрования ключа, на выходе получаем шифротекст c0 и симметричный ключ 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.

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

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

  1. KGP-PSEC — алгоритм генерации открытого и закрытого ключей (W, s).
  2. ES-PSEC-KEM-Encrypt — алгоритм получения симметричного ключа k и шифротекста c0 на основе открытого ключа W и формата R.
  3. ES-PSEC-KEM-Decrypt — алгоритм получения симметричного ключа k на основе закрытого ключа s и шифротекста c0Шаблон:Sfn.

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

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

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

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

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

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

W : точка на эллиптической кривой EШаблон:Sfn.

Типы данных

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

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

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

Преобразования между типами данных
Преобразования между типами данных

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

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

Функция генерации ключей принимает на вход точку <math>P</math> эллиптической кривой <math>E</math> порядка <math>p</math>. На выходе получаем открытый ключ <math>W</math> и закрытый ключ <math>s</math> в диапазоне от 0 до <math>p</math>Шаблон:Sfn.

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

Функция кодирования ключа принимает на вход открытый ключ <math>W</math>, параметр <math>R</math>, который указывает на то, используется ли сжатие или нет, и точку <math>P</math> на эллиптической кривой <math>E</math>. На выходе получаем симметричный ключ <math>k</math> и шифротекст <math>c_0</math>[4].

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

Функция декодирования ключа принимает на вход закрытый ключ <math>s</math>, шифротекст <math>c_0</math> и точку <math>P</math> на эллиптической кривой <math>E</math>. На выходе получаем симметричный ключ <math>k</math>Шаблон:Sfn.

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

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

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

  • pLen ≥ 20 (256 бит), <math>pLen = \lceil \log_{256}p\rceil</math>Шаблон:Sfn.
  • hLen ≥ 16, hLen — длина строки байт, которая генерируется случайным образом в самом начале алгоритма кодирования ключаШаблон:Sfn.

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

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

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

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

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

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

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

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

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

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

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

<math>Advantage_{PSEC-KEM}(A) \leq Advantage_{CDH}(A, l) + \varepsilon</math>Шаблон:Sfn

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

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

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

Применение

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

См. также

Примечания

Шаблон:Примечания

Литература

Статьи

Сайты

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Ошибка цитирования Неверный тег <ref>; для сносок menezes2 не указан текст
  2. ↑ 2,0 2,1 2,2 Ошибка цитирования Неверный тег <ref>; для сносок nttPlatform не указан текст
  3. ↑ Ошибка цитирования Неверный тег <ref>; для сносок ntt13 не указан текст
  4. ↑ 4,0 4,1 4,2 Ошибка цитирования Неверный тег <ref>; для сносок ntt1415 не указан текст
  5. ↑ Ошибка цитирования Неверный тег <ref>; для сносок ntt17 не указан текст
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:PSEC-KEM&oldid=8766382