Криптосистема Окамото-Утиямы

Криптосистема Окамото-Утиямы — это криптосистема с открытым ключом, предложенная в 1998 году Тацуаки Окамото и Сигенори Утияма . Система работает в мультипликативной группе целых чисел по модулю n , $(\mathbb {Z} /n\mathbb {Z} )^{*}$, где n имеет вид p ² q и p и q — большие простые числа .

Фон

Позволять $p$ быть нечетным простым числом. Определять $\Gamma =\{x\in (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}|x\equiv 1{\bmod {p}}\}$. $\Gamma$ является подгруппой $(\mathbb {Z} /p^{2}\mathbb {Z} )^{*}$ с $|\Gamma |=p$ (элементы $\Gamma$ являются $1,1+p,1+2p\dots 1+(p-1)p$).

Определять $L:\Gamma \to \mathbb {Z} /p\mathbb {Z}$ к $L(x)={\frac {x-1}{p}}$

$L$ является гомоморфизмом между $\Gamma$ и аддитивная группа $\mathbb {Z} /p\mathbb {Z}$: то есть, $L(ab)=L(a)+L(b){\bmod {p}}$. С $L$ биективен, это изоморфизм.

В качестве следствия теперь можно показать следующее:

Позволять $x\in \Gamma$ такой, что $L(x)\neq 0{\bmod {p}}$ и $y=x^{m}{\bmod {p}}^{2}$ для $0\leq m<p$. Затем

$m={\frac {L(y)}{L(x)}}={\frac {y-1}{x-1}}{\bmod {p}}$

Следствие является прямым следствием $L(x^{m})=m\cdot L(x)$.

Операция

Как и многие криптосистемы с открытым ключом , эта схема работает в группе. $(\mathbb {Z} /n\mathbb {Z} )^{*}$. Эта схема гомоморфна и, следовательно, податлива .

Генерация ключей

Пара открытый/закрытый ключ генерируется следующим образом:

1. Создайте два больших простых числа $p$ и $q$.
2. Вычислить $n=p^{2}q$.
3. Выберите случайное целое число $g\in \{2\dots n-1\}$ такой, что $g^{p-1}\not \equiv 1\mod p^{2}$.
4. Вычислить $h=g^{n}{\bmod {n}}$.

Тогда открытый ключ $(n,g,h)$ и закрытый ключ $(p,q)$.

Шифрование

Сообщение $m<p$ можно зашифровать открытым ключом $(n,g,h)$ следующее.

1. Выберите случайное целое число $r\in \{1\dots n-1\}$.
2. Вычислить $c=g^{m}h^{r}{\bmod {n}}$.

Значение $c$ это шифрование $m$.

Расшифровка

Зашифрованное сообщение $c$ можно расшифровать приватным ключом $(p,q)$ следующее.

1. Вычислить $a=L(c^{p-1}{\bmod {p^{2}}})$.
2. Вычислить $b=L(g^{p-1}{\bmod {p^{2}}})$. $a$ и $b$ будут целыми числами.
3. Используя расширенный алгоритм Евклида , вычислите обратную величину $b$ модуль $p$:

   $b'=b^{-1}{\bmod {p}}$.

4. Вычислить $m=ab'{\bmod {p}}$.

Значение $m$ это расшифровка $c$.

Пример

Позволять $p=3$ и $q=5$. Затем $n=3^{2}\cdot 5=45$. Выбирать $g=22$. Затем $h=22^{45}{\bmod {4}}5=37$.

Теперь, чтобы зашифровать сообщение $m=2$, мы выбираем случайное $r=13$ и вычислить $c=g^{m}h^{r}{\bmod {n}}=22^{2}37^{13}{\bmod {4}}5=43$.

Чтобы расшифровать сообщение 43, мы вычисляем

$a={\frac {(43^{2}{\bmod {3}}^{2})-1}{3}}=1$.

$b={\frac {(22^{2}{\bmod {3}}^{2})-1}{3}}=2$.

$b'=2^{-1}{\bmod {3}}=2$.

И наконец $m=ab'=2$.

Доказательство правильности

Мы хотим доказать, что значение, вычисленное на последнем этапе расшифровки, $ab'{\bmod {p}}$, равно исходному сообщению $m$. У нас есть

$(g^{m}h^{r})^{p-1}\equiv (g^{m}g^{nr})^{p-1}\equiv (g^{p-1})^{m}g^{p(p-1)rpq}\equiv (g^{p-1})^{m}\mod p^{2}$

Итак, чтобы восстановиться $m$ нам нужно взять дискретный логарифм с основанием $g^{p-1}$. Это можно сделать, применив $L$, следующее.

По малой теореме Ферма , $g^{p-1}\equiv 1{\bmod {p}}$. С $g^{p-1}\not \equiv 1{\bmod {p}}^{2}$ можно написать $g^{p-1}=1+pr$ с $0<r<p$. Затем $L(g^{p-1})\not \equiv 0{\bmod {p}}$ и применяется следствие из предыдущего: $m={\frac {L((g^{p-1})^{m})}{L(g^{p-1})}}{\bmod {p}}$.

Безопасность

Можно показать, что инвертирование функции шифрования так же сложно, как факторизация n , а это означает, что если злоумышленник сможет восстановить все сообщение после шифрования сообщения, он сможет факторизовать n . Семантическая безопасность (то есть злоумышленники не могут восстановить какую-либо информацию о сообщении из шифрования) опирается на предположение о p -подгруппе, которое предполагает, что трудно определить, находится ли элемент x в $(\mathbb {Z} /n\mathbb {Z} )^{*}$ находится в подгруппе порядка p . Это очень похоже на проблему квадратичной невязки и проблему более высокой невязкости .

Ссылки

• Окамото, Тацуаки; Утияма, Сигенори (1998). «Новая криптосистема с открытым ключом, столь же безопасная, как факторинг». Достижения криптологии – EUROCRYPT'98 . Конспекты лекций по информатике . Том. 1403. Спрингер. стр. 308–318. дои : 10.1007/BFb0054135 . ISBN  978-3-540-64518-4 .