EPOC (; эффективное вероятностное шифрование с открытым ключом) — это вероятностная схема шифрования с открытым ключом.
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 обладает следующими свойствами: EPOC-1 семантически безопасен, устойчив к атакам на основе подобранного шифротекста (IND-CCA2 или NM-CCA2) в модели случайного оракула в предположении p-подгруппы, которое вычислительно сопоставимо с предположениями квадратичного вычета и вычетов более высокой степени. EPOC-2 с одноразовым блокнотом семантически безопасен, устойчив к атакам на основе подобранного шифротекста (IND-CCA2 или NM-CCA2) в модели случайного оракула в предположении факторизации. EPOC-2 с симметричным шифрованием семантически безопасен, устойчив к атакам на основе подобранного шифротекста (IND-CCA2 или NM-CCA2) в модели случайного оракула в рамках предположения факторизации, если базовое симметричное шифрование является безопасным против пассивных атак (атак вида, когда криптоаналитик имеет возможность только видеть предаваемые шифротексты и генерировать собственные, используя открытый ключ.).
Предыстория Диффи и Хеллман предложили концепцию криптосистемы с открытым ключом (или односторонней функции) в 1976 году. Хотя многое криптографы и математики провели обширные исследования, чтобы реализовать концепцию криптосистем с открытым ключом в течение более чем 20 лет, было найдено очень мало конкретных методов, которые являются безопасными.
Типичным классом методов является RSA-Rabin, представляющий собой комбинацию полиномиального алгоритма нахождения корня многочлена в кольце вычетов по модулю составного числа (в конечном поле)и неразрешимой задачи факторизации(по вычислительной сложности). Другим типичным классом методов является метод Диффи-Хеллмана, Эль-Гамаля, который представляет собой комбинацию коммутативного свойства логарифма в конечной Абелевой группе и неразрешимой задачи дискретного логарифма.
Среди методов RSA-Rabin и Diffie-Hellman-ElGamal для реализации односторонней функции ни одна функция, кроме функции Рабина и её вариантов, таких как её версии эллиптической кривой и Уильямса, не была доказана такой же надёжной, как примитивные задачи(например, задачи факторизации и дискретного логарифма).
Окамото и Учияма, предложили одностороннюю функцию, названную OU (англ. Okamoto-Uchiyama), которая практична, доказуемо безопасна и обладает некоторыми другими интересными свойствами.
Свойства функции OU Вероятностная функция: это односторонняя, вероятностная функция. Пусть — зашифрованный текст открытого текста со случайным . Односторонность функции: Доказано, что инвертирование функции так же трудно, как факторизация . Семантическая стойкость: Функция семантически безопасна, если верно следующее предположение (предположение p-подгруппы): и вычислительно неразличимы, где и равномерно и независимо выбраны из . Это предположение о неразличимости шифротекста для атак на основе подобранного открытого текста вычислительно сравнимо с поиском квадратичного вычета и вычета более высокой степени. Эффективность: В среде использования криптосистем с открытым ключом, где криптосистема с открытым ключом используется только для распространения секретного ключа(например, длиной 112 и 128 бит) криптосистемы с секретным ключом(например, Triple DES и IDEA), скорость шифрования и дешифрования функции OU сравнима (в несколько раз медленнее) со скоростью криптосистем с эллиптической кривой. Свойство гомоморфного шифрования: Функция обладает свойством гомоморфного шифрования: (Такое свойство используется для электронного голосования и других криптографических протоколов). Неразличимость шифротекста: Даже тот, кто не знает секретного ключа, может изменить зашифрованный текст, , на другой зашифрованный текст, , сохраняя при этом открытый текст 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
Ввод и вывод следующие:
[Входные данные]: Шифротекст наряду с открытым ключом , секретным ключом и .
[Выходные данные]: Открытый текст или нулевая строка.
Операция со входами , , и выглядит следующим образом:
Вычислим , а , где .
Вычислим
Проверим, верно ли следующее уравнение: .
Если выражение верно, то выведем как расшифрованный открытый текст. В противном случае выведем нулевую строку.
Примечания
Литература
Категория:Криптография Категория:Шифры Категория:Криптография с открытым ключом