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

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

Фон

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

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

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

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

Пусть такое, что и для . Тогда ${\displaystyle x\in \Gamma }$ ${\displaystyle L(x)\neq 0{\bmod {p}}}$ ${\displaystyle y=x^{m}{\bmod {p}}^{2}}$ ${\displaystyle 0\leq m<p}$

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

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

Операция

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

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

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

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

Тогда открытый ключ — это , а закрытый ключ — это . ${\displaystyle (n,g,h)}$ ${\displaystyle (p,q)}$

Шифрование

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

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

Значение представляет собой шифрование . ${\displaystyle c}$ ${\displaystyle m}$

Расшифровка

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

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

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

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

Значение представляет собой расшифровку . ${\displaystyle m}$ ${\displaystyle c}$

Пример

Пусть и . Тогда . Выберите . Тогда . ${\displaystyle p=3}$ ${\displaystyle q=5}$ ${\displaystyle n=3^{2}\cdot 5=45}$ ${\displaystyle g=22}$ ${\displaystyle h=22^{45}{\bmod {4}}5=37}$

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

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

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

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

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

И наконец . ${\displaystyle m=ab'=2}$

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

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

${\displaystyle (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}}$

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

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

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

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

Ссылки

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