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. Вероятностная функция: это односторонняя, вероятностная функция . Пусть ${\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 ) .

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

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

Обзор

Схема шифрования с открытым ключом 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 .

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

Открытый ключ 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 закрытый ключ

Закрытый ключ 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}}}$ , неотрицательное целое число

EPOC-1

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

Ввод и вывод ${\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}$ . В противном случае выведем нулевую строку.

EPOC-2

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

Ввод и вывод ${\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. (англ.) . — 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 .