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

Криптосистема Окамото–Утиямы — это криптосистема с открытым ключом, предложенная в 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 \Гамма}$${\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z})^{*}}$${\displaystyle |\Гамма |=p}$${\displaystyle \Гамма}$${\displaystyle 1,1+p,1+2p\точки 1+(p-1)p}$

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

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

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

Пусть такое, что и для . Тогда${\displaystyle x\in \Гамма}$${\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 д}$
2. Вычислить .${\displaystyle n=p^{2}q}$
3. Выберите случайное целое число, такое что .${\displaystyle g\in \{2\точки n-1\}}$${\displaystyle g^{p-1}\not \equiv 1\mod p^{2}}$
4. Вычислить .${\displaystyle h=g^{n}{\bmod {n}}}$

Тогда открытый ключ — это , а закрытый ключ — это .${\displaystyle (н,г,ч)}$${\displaystyle (п,д)}$

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

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

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

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

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

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

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

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

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

Теперь, чтобы зашифровать сообщение , мы выбираем случайное число и вычисляем .${\displaystyle м=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 м}$

${\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 м}$${\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.