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. Вероятностная функция: это односторонняя, вероятностная функция. Пусть $E(m,r)$ — зашифрованный текст открытого текста $m$ со случайным $r$.
2. Односторонность функции: Доказано, что инвертирование функции так же трудно, как факторизация $n:=p^{2}q$.
3. Семантическая стойкость: Функция семантически безопасна, если верно следующее предположение (предположение p-подгруппы): $E(0,r)=h^{r}{\text{ mod }}n$ и $E(1,r')=gh^{r'}{\text{ mod }}n$ вычислительно неразличимы, где $r$ и $r'$ равномерно и независимо выбраны из $\mathbf {Z} /n\mathbf {Z}$. Это предположение о неразличимости шифротекста для атак на основе подобранного открытого текста вычислительно сравнимо с поиском квадратичного вычета и вычета более высокой степени.
4. Эффективность: В среде использования криптосистем с открытым ключом, где криптосистема с открытым ключом используется только для распространения секретного ключа(например, длиной 112 и 128 бит) криптосистемы с секретным ключом(например, Triple DES и IDEA), скорость шифрования и дешифрования функции OU сравнима (в несколько раз медленнее) со скоростью криптосистем с эллиптической кривой.
5. Свойство гомоморфного шифрования: Функция обладает свойством гомоморфного шифрования: $E(m_{0},r_{0})E(m_{1},r_{1}){\text{ mod }}n=E(m_{0}+m_{1},r_{3}),{\text{ if }}m_{0}+m_{1}<p$(Такое свойство используется для электронного голосования и других криптографических протоколов).
6. Неразличимость шифротекста: Даже тот, кто не знает секретного ключа, может изменить зашифрованный текст, $C=E(m,r)$, на другой зашифрованный текст, $C'=Ch^{r'}{\text{ mod }}n$, сохраняя при этом открытый текст m (то есть $C'=E(m,r'')$), и связь между $C$ и $C'$ может быть скрыта (то есть $(C,C')$ и $(C,E(m',t)$ неразличимы). Такое свойство полезно для протоколов защиты конфиденциальности).

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

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

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

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

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

Обзор

Схема шифрования с открытым ключом EPOC, которая задаётся триплетом $({\mathcal {G}},{\mathcal {E}},{\mathcal {D}})$, где ${\mathcal {G}}$-операция генерации ключа, ${\mathcal {E}}$-операция шифрования и ${\mathcal {D}}$-операция дешифрования.

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

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

Типы ключей

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

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

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

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

На практике в открытом ключе OU модуль $n$ принимает вид $n:=p^{2}q$, где $p$ и $q$ — два различных нечётных простых числа, а битовая длина $p$ и $q$ равна $pLen$. $g$-элемент в $(\mathbf {Z} /n\mathbf {Z} )^{*}$ такой, что порядок $g_{p}$ в $(\mathbf {Z} /p^{2}\mathbf {Z} )^{*}$ равен $p$, где $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$. $h$-элемент в $(\mathbf {Z} /n\mathbf {Z} )^{*}$.

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

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

• $p$ — первый фактор, неотрицательное целое число
• $h$ — второй фактор, неотрицательное целое число
• $pLen$ — секретный параметр, неотрицательное целое число
• $w$ — значение $L(g_{p})$, где $L(x)={\frac {x-1}{p}}$, неотрицательное целое число

EPOC-1

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

Ввод и вывод ${\mathcal {G}}$ следующие:

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

[Выходные данные]: Пара открытого ключа $(n,g,h,H,pLen,mLen,hLen,rLen)$ и секретного ключа $(p,g_{p})$.

Операция ${\mathcal {G}}$ со входом $k$ выглядит следующим образом:

• Выберем два простых числа $p$, $q$ ($|p|=|q|=k$) и вычислим $n:=p^{2}q$. Здесь $p-1=p'u$ и $q-1=q'v$ такое, что $p'$ и $q'$ — простые числа, а $|u|$ и $|v|$ такие, что $O(\log k)$.

• Выберем $g\in (\mathbf {Z} /n\mathbf {Z} )^{*}$ случайным образом так, чтобы порядок $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ был равен $p$ (Заметим, что НОД($p$, $q-1$)$=1$ и НОД($q$, $p-1$)$=1$).

• Выберем $h_{0}$ из $(\mathbf {Z} /n\mathbf {Z} )^{*}$ случайным образом и независимо от $g$. Вычислим $h:=h_{n}^{0}{\text{ mod }}n$.

• Установить $pLen:=k$. Установите $mLen$ и $rLen$ такими, что $mLen+rLen\leq pLen-1$.

• Выберем хеш-функцию $H:\{0,1\}^{*}\rightarrow \{0,1\}^{hLen}$.

Примечание: $g_{p}$ является дополнительным параметром, повышающим эффективность дешифрования, и может быть вычислен из $p$ и $g$. $h=g^{n}{\text{ mod }}n$, когда $hLen=(2+c_{0})k$ ($c_{0}$-константа $>0$). $H$ может быть зафиксирован системой и совместно использован многими пользователями.

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

Ввод и вывод ${\mathcal {E}}$ следующие:

[Входные данные]: Открытый текст $M\in \{0,1\}^{mLen}$ вместе с открытым ключом $(n,g,h,H,pLen,mLen,hLen,rLen)$.

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

Операция ${\mathcal {E}}$ со входами $M$, $(n,g,h,H,mLen,rLen)$ выглядит следующим образом:

• Выберем $R\in \{0,1\}^{rLen}$ и вычислим $r:=H(M\parallel R)$. Здесь $M\parallel R$ обозначает конкатенацию $M$ и $R$.

• Вычислить $C$:

$C:=g^{(M\parallel R)}h^{r}{\text{ mod }}n.$

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

Ввод и вывод ${\mathcal {D}}$ следующие:

[Входные данные]: Шифротекст $C$ наряду с открытым ключом $(n,g,h,H,pLen,mLen,hLen)$ и секретным ключом $(p,g_{p})$.

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

Операция ${\mathcal {D}}$ со входами $C$, $(n,g,h,H,pLen,mLen,hLen)$ и $(p,g_{p})$ выглядит следующим образом:

• Вычислим $C_{p}:=C^{p-1}{\text{ mod }}p^{2}$, а $X:={\frac {L(C_{p})}{L(g_{p})}}{\text{ mod }}p$, где $L(x):={\frac {x-1}{p}}$.

• Проверим, верно ли следующее уравнение: $C=g^{X}h^{H(X)}{\text{ mod }}n$.

• Если выражение верно, то выведем $[X]^{mLen}$ как расшифрованный открытый текст, где $[X]^{mLen}$ обозначает наиболее значимые $mLen$ биты в $X$. В противном случае выведем нулевую строку.

EPOC-2

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

Ввод и вывод ${\mathcal {G}}$ следующие:

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

[Выходные данные]: Пара открытого ключа $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ и секретного ключа $(p,g_{p})$.

Операция ${\mathcal {G}}$ со входом $k$ выглядит следующим образом:

• Выберем два простых числа $p$, $q$ ($|p|=|q|=k$) и вычислим $n:=p^{2}q$. Здесь $p-1=p'u$ и $q-1=q'v$ такое, что $p'$ и $q'$ — простые числа, а $|u|$ и $|v|$ такие, что $O(\log k)$.

• Выберем $g\in (\mathbf {Z} /n\mathbf {Z} )^{*}$ случайным образом так, чтобы порядок $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ был равен $p$.

• Выберем $h_{0}$ из $(\mathbf {Z} /n\mathbf {Z} )^{*}$ случайным образом и независимо от $g$. Вычислим $h:=h_{n}^{0}{\text{ mod }}n$.

• Установить $pLen:=k$. Установите $mLen$ и $rLen$ такими, что $mLen+rLen\leq pLen-1$.

• Выберем хеш-функции $H:\{0,1\}^{*}\rightarrow \{0,1\}^{hLen}$ и $G:{0,1}^{*}\rightarrow \{0,1\}^{hLen}$.

Примечание: $g_{p}$ является дополнительным параметром, повышающим эффективность дешифрования, и может быть вычислено из $p$ и $g$. $h=g^{n}{\text{ mod }}n$, когда $hLen=(2+c_{0})k$ ($c_{0}$-константа $>0$). $H$ и $G$ могут быть зафиксированы системой и совместно использованы многими пользователями.

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

Пусть $SymE=(SymEnc,SymDec)$ — пара алгоритмов шифрования и дешифрования с симметричным ключом $K$, где длина $K$ равна $gLen$. Алгоритм шифрования $SymEnc$ принимает ключ $K$ и открытый текст $X$ и возвращает зашифрованный текст $SymEnc(K,X)$. Алгоритм расшифровки $SymDec$ принимает ключ $K$ и зашифрованный текст $Y$ и возвращает открытый текст $SymDec(K,Y)$.

Ввод и вывод ${\mathcal {E}}$ следующие:

[Входные данные]: Открытый текст $M\in \{0,1\}^{mLen}$ вместе с открытым ключом $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ и $SymEnc$.

[Выходные данные]: Зашифрованный текст $C=(C_{1},C_{2})$.

Операция ${\mathcal {E}}$ со входами $M$, $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ и $SymEnc$ выглядит следующим образом:

• Выберем $r\in \{0,1\}^{rLen}$ и вычислим $G(R)$.

• Вычислим $H(M\parallel R)$. Здесь $M\parallel R$ обозначает конкатенацию $M$ и $R$.

• $C_{1}:=g^{R}h^{H(M\parallel R)}{\text{ mod }}n$; $C_{2}:=SymEnc(G(R),M)$

Примечание: типичный способ реализации $SymE$ — это одноразовый блокнот. То есть, $SymEnc(K,X):=K\oplus X$, и $SymDec(X,Y):=X\oplus Y$ , где $\oplus$ обозначает операцию побитового исключающего ИЛИ.

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

Ввод и вывод ${\mathcal {D}}$ следующие:

[Входные данные]: Шифротекст $C=(C_{1},C_{2})$ наряду с открытым ключом $(n,g,h,H,G,pLen,hLen,gLen,rLen)$, секретным ключом $(p,g_{p})$ и $SymDec$.

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

Операция ${\mathcal {D}}$ со входами $C=(C_{1},C_{2})$, $(n,g,h,H,G,pLen,hLen,gLen)$, $(p,g_{p})$ и $SymDec$ выглядит следующим образом:

• Вычислим $C_{p}:=C^{p-1}{\text{ mod }}p^{2}$, а $R':={\frac {L(C_{p})}{L(g_{p})}}{\text{ mod }}p$, где $L(x):={\frac {x-1}{p}}$.

• Вычислим $M':=SymDec(G(R'),C_{2}).$

• Проверим, верно ли следующее уравнение: $C=g^{R'}h^{H(M'\parallel R')}{\text{ mod }}n$.

• Если выражение верно, то выведем $M'$ как расшифрованный открытый текст. В противном случае выведем нулевую строку.

Литература

• Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. Secure integration of asymmetric and symmetric encryption schemes (англ.). — 1999.
• W. DIFFIE AND M.E. HELLMAN. New Directions in Cryptography (англ.). — 1976.
• Maxwell Krohn. On the Definitions of Cryptographic Security: Chosen-Ciphertext Attack Revisited (англ.). — 1999.
• T. Elgamal. A public key cryptosystem and a signature scheme based on discrete logarithms (англ.). — 1985.
• NTT Information Sharing Platform Laboratories, NTT Corporation. EPOC-2 Specification (англ.). — 2001. — P. 7—10.
• Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. EPOC: Efficient Probabilistic Public-Key Encryption (англ.). — 1998. — P. 1—12.
• Evaluator: Prof. Jean-Jacques Quisquater, Math RiZK, consulting; Scientific Support: Dr. Fran ̧cois Koeune, K2Crypt. Security Evaluation of the Encryption Scheme (англ.). — 2002.
• E.Brickell, D.Pointcheval, S.Vaudenay, M.Yung. Design Validations for Discrete Logarithm Based Signature Schemes (англ.). — 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. A New Rabin-type Trapdoor Permutation Equivalent to Factoring (англ.). — 2006. — P. 86–88.