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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Вычислить ${\displaystyle C}$:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Если выражение верно, то выведем ${\displaystyle 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.