Interested Article - EPOC (схема шифрования)

EPOC ( англ. Efficient Probabilistic Public Key Encryption ; эффективное вероятностное шифрование с открытым ключом) — это схема шифрования с открытым ключом .

EPOC был разработан в ноябре 1998 г. Т. Окамото (англ. T. Okamoto), С. Учияма (англ. S. Uchiyama) и Э. Фудзисаки (англ. E. Fujisaki) из NTT Laboratories в Японии . Он основан на модели случайного оракула , в которой функция шифрования с открытым ключом преобразуется в безопасную схему шифрования с использованием (действительно) случайной хеш-функции; результирующая схема разработана так, чтобы быть семантически защищённой от атак на основе подобранного шифротекста .

Виды схем

Функция шифрования EPOC — это функция OU (англ. Okamoto-Uchiyama), которую инвертировать так же сложно, как факторизировать составной целочисленный открытый ключ. Существует три версии EPOC :

  • EPOC-1, использующий одностороннюю функцию (англ. trapdoor function) и случайную функцию (хеш-функцию) .;
  • EPOC-2, использующий одностороннюю функцию , две случайные функции (хеш-функции) и шифрование с симметричным ключом (например, одноразовый блокнот и блочные шифры) ;
  • EPOC-3 использует одностороннюю функцию OU (англ. Okamoto-Uchiyama) и две случайные функции (хеш-функции), а также любую симметричную схему шифрования, такую как одноразовые блокноты (англ. one-time pad) или блочный шифр .

Свойства

EPOC обладает следующими свойствами:

  1. EPOC-1 семантически безопасен , устойчив к атакам на основе подобранного шифротекста ( IND-CCA2 или NM-CCA2 ) в модели случайного оракула в предположении p-подгруппы , которое вычислительно сопоставимо с предположениями квадратичного вычета и вычетов более высокой степени.
  2. EPOC-2 с одноразовым блокнотом семантически безопасен , устойчив к атакам на основе подобранного шифротекста ( IND-CCA2 или NM-CCA2 ) в модели случайного оракула в предположении факторизации.
  3. EPOC-2 с симметричным шифрованием семантически безопасен , устойчив к атакам на основе подобранного шифротекста ( IND-CCA2 или NM-CCA2 ) в модели случайного оракула в рамках предположения факторизации, если базовое симметричное шифрование является безопасным против пассивных атак (атак вида, когда криптоаналитик имеет возможность только видеть предаваемые шифротексты и генерировать собственные, используя открытый ключ .).

Предыстория

Диффи и Хеллман предложили концепцию криптосистемы с открытым ключом (или односторонней функции ) в 1976 году. Хотя многое криптографы и математики провели обширные исследования, чтобы реализовать концепцию криптосистем с открытым ключом в течение более чем 20 лет, было найдено очень мало конкретных методов, которые являются безопасными .

Типичным классом методов является RSA-Rabin , представляющий собой комбинацию полиномиального алгоритма нахождения корня многочлена в кольце вычетов по модулю составного числа конечном поле )и неразрешимой задачи факторизации(по вычислительной сложности ). Другим типичным классом методов является метод Диффи-Хеллмана, Эль-Гамаля , который представляет собой комбинацию коммутативного свойства логарифма в конечной Абелевой группе и неразрешимой задачи дискретного логарифма .

Среди методов RSA-Rabin и Diffie-Hellman-ElGamal для реализации односторонней функции ни одна функция, кроме функции Рабина и её вариантов, таких как её версии эллиптической кривой и Уильямса, не была доказана такой же надёжной, как примитивные задачи (например, задачи факторизации и дискретного логарифма ).

Окамото и Учияма, предложили одностороннюю функцию , названную OU (англ. Okamoto-Uchiyama), которая практична, доказуемо безопасна и обладает некоторыми другими интересными свойствами .

Свойства функции OU

  1. Вероятностная функция: это односторонняя, вероятностная функция . Пусть — зашифрованный текст открытого текста со случайным .
  2. Односторонность функции: Доказано, что инвертирование функции так же трудно, как факторизация .
  3. Семантическая стойкость: Функция семантически безопасна , если верно следующее предположение (предположение p-подгруппы ): и вычислительно неразличимы, где и равномерно и независимо выбраны из . Это предположение о неразличимости шифротекста для атак на основе подобранного открытого текста вычислительно сравнимо с поиском квадратичного вычета и вычета более высокой степени.
  4. Эффективность: В среде использования криптосистем с открытым ключом , где криптосистема с открытым ключом используется только для распространения секретного ключа (например, длиной 112 и 128 бит) криптосистемы с секретным ключом (например, Triple DES и IDEA ), скорость шифрования и дешифрования функции OU сравнима (в несколько раз медленнее) со скоростью криптосистем с эллиптической кривой .
  5. Свойство гомоморфного шифрования: Функция обладает свойством гомоморфного шифрования: (Такое свойство используется для электронного голосования и других криптографических протоколов ).
  6. Неразличимость шифротекста : Даже тот, кто не знает секретного ключа, может изменить зашифрованный текст, , на другой зашифрованный текст, , сохраняя при этом открытый текст m (то есть ), и связь между и может быть скрыта (то есть и неразличимы). Такое свойство полезно для протоколов защиты конфиденциальности).

Доказательство безопасности схемы шифрования

Одним из важнейших свойств шифрования с открытым ключом является доказуемая безопасность . Самое сильное понятие безопасности в шифровании с открытым ключом — это понятие семантической защиты от атак на основе подобранного шифротекста .

Доказано, что семантическая защита от атак на основе адаптивно подобранного шифротекста ( IND-CCA2 ) эквивалентна (или достаточна) самому сильному понятию безопасности ( NM-CCA2 ) .

Фудзисаки и Окамото реализовали две общие и эффективные меры для преобразования вероятностной односторонней функции в защищённую схему IND-CCA2 в модели случайного оракула . Одна из них — это преобразование семантически безопасной ( IND-CPA ) односторонней функции в защищённую схему IND-CCA2 . Другая, от односторонней функции (OW-CPA) и шифрования с симметричным ключом (включая одноразовый блокнот) до защищённой схемы IND-CCA2 . Последнее преобразование может гарантировать полную безопасность системы шифрования с открытым ключом в сочетании со схемой шифрования с симметричным ключом .

Схема шифрования EPOC

Обзор

Схема шифрования с открытым ключом EPOC, которая задаётся триплетом , где -операция генерации ключа, -операция шифрования и -операция дешифрования.

Схемы EPOC: EPOC-1 и EPOC-2.

EPOC-1 предназначен для распределения ключей, а EPOC-2 предназначен для распределения ключей и передачи зашифрованных данных, а также распределения более длинного ключа при ограниченном размере открытого ключа.

Типы ключей

Существует два типа ключей: открытый ключ OU и закрытый ключ OU, оба из которых используются в криптографических схемах шифрования EPOC-1, EPOC-2 .

OU открытый ключ

Открытый ключ OU — это набор , компоненты которого имеют следующие значения:

  • — неотрицательное целое число
  • — неотрицательное целое число
  • — неотрицательное целое число
  • — секретный параметр, неотрицательное целое число

На практике в открытом ключе OU модуль принимает вид , где и — два различных нечётных простых числа, а битовая длина и равна . -элемент в такой, что порядок в равен , где . -элемент в .

OU закрытый ключ

Закрытый ключ OU — это набор , компоненты которого имеют следующие значения:

  • — первый фактор, неотрицательное целое число
  • — второй фактор, неотрицательное целое число
  • — секретный параметр, неотрицательное целое число
  • — значение , где , неотрицательное целое число

EPOC-1

Создание Ключа: G

Ввод и вывод следующие:

[Входные данные]: Секретный параметр ( ) — положительное целое число.

[Выходные данные]: Пара открытого ключа и секретного ключа .

Операция со входом выглядит следующим образом:

  • Выберем два простых числа , ( ) и вычислим . Здесь и такое, что и — простые числа, а и такие, что .
  • Выберем случайным образом так, чтобы порядок был равен (Заметим, что НОД( , ) и НОД( , ) ).
  • Установить . Установите и такими, что .
  • Выберем хеш-функцию .

Примечание: является дополнительным параметром, повышающим эффективность дешифрования, и может быть вычислен из и . , когда ( -константа ). может быть зафиксирован системой и совместно использован многими пользователями.

Шифрование: E

Ввод и вывод следующие:

[Входные данные]: Открытый текст вместе с открытым ключом .

[Выходные данные]: Шифротекст С.

Операция со входами , выглядит следующим образом:

  • Выберем и вычислим . Здесь обозначает конкатенацию и .
  • Вычислить :

Дешифрование: D

Ввод и вывод следующие:

[Входные данные]: Шифротекст наряду с открытым ключом и секретным ключом .

[Выходные данные]: Открытый текст или нулевая строка.

Операция со входами , и выглядит следующим образом:

  • Вычислим , а , где .
  • Проверим, верно ли следующее уравнение: .
  • Если выражение верно, то выведем как расшифрованный открытый текст, где обозначает наиболее значимые биты в . В противном случае выведем нулевую строку.

EPOC-2

Создание Ключа: G

Ввод и вывод следующие:

[Входные данные]: Секретный параметр ( ).

[Выходные данные]: Пара открытого ключа и секретного ключа .

Операция со входом выглядит следующим образом:

  • Выберем два простых числа , ( ) и вычислим . Здесь и такое, что и — простые числа, а и такие, что .
  • Установить . Установите и такими, что .
  • Выберем хеш-функции и .

Примечание: является дополнительным параметром, повышающим эффективность дешифрования, и может быть вычислено из и . , когда ( -константа ). и могут быть зафиксированы системой и совместно использованы многими пользователями.

Шифрование: E

Пусть — пара алгоритмов шифрования и дешифрования с симметричным ключом , где длина равна . Алгоритм шифрования принимает ключ и открытый текст и возвращает зашифрованный текст . Алгоритм расшифровки принимает ключ и зашифрованный текст и возвращает открытый текст .

Ввод и вывод следующие:

[Входные данные]: Открытый текст вместе с открытым ключом и .

[Выходные данные]: Зашифрованный текст .

Операция со входами , и выглядит следующим образом:

  • Выберем и вычислим .
  • Вычислим . Здесь обозначает конкатенацию и .
  • ;

Примечание: типичный способ реализации — это одноразовый блокнот. То есть, , и , где обозначает операцию побитового исключающего ИЛИ .

Дешифрование: D

Ввод и вывод следующие:

[Входные данные]: Шифротекст наряду с открытым ключом , секретным ключом и .

[Выходные данные]: Открытый текст или нулевая строка.

Операция со входами , , и выглядит следующим образом:

  • Вычислим , а , где .
  • Вычислим
  • Проверим, верно ли следующее уравнение: .
  • Если выражение верно, то выведем как расшифрованный открытый текст. В противном случае выведем нулевую строку.

Примечания

  1. , с. 1.
  2. .
  3. , с. 2—3.
  4. , с. 3—4.
  5. , с. 8—11.
  6. .
  7. .
  8. .
  9. , с. 5.
  10. , с. 4.
  11. , с. 3—4.
  12. , с. 53.
  13. .
  14. , с. 5.
  15. , с. 7.
  16. , с. 9—10.

Литература

  • Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. (англ.) . — 1999.
  • W. DIFFIE AND M.E. HELLMAN. (англ.) . — 1976.
  • Maxwell Krohn. (англ.) . — 1999.
  • T. Elgamal. (англ.) . — 1985.
  • NTT Information Sharing Platform Laboratories, NTT Corporation. (англ.) . — 2001. — P. 7—10 .
  • Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. (англ.) . — 1998. — P. 1—12 .
  • Evaluator: Prof. Jean-Jacques Quisquater, Math RiZK, consulting; Scientific Support: Dr. Fran ̧cois Koeune, K2Crypt. (англ.) . — 2002.
  • E.Brickell, D.Pointcheval, S.Vaudenay, M.Yung. (англ.) . — 2000. — P. 276—292 .
  • Bellare, M., Desai, A., Pointcheval, D., and Rogaway, P. Relations Among Notions of Security for Public-Key Encryption Schemes, Proc. of Crypto’98, LNCS 1462, Springer- Verlag, (англ.) . — 1998. — P. 26–45 .
  • Katja Schmidt-Samoa. (англ.) . — 2006. — P. 86–88 .
Источник —

Same as EPOC (схема шифрования)