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

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

Например, если $p$ — большое простое число и ${\gamma }_p\subset Z_{{𝕡}^{\mathrm{𝟚}}}^{𝕟}$, такое, чтo ${\gamma }_p=x<p^2$ для $x=1modp$, то ${\gamma }_p$ имеет структуру группы по отношению к мультипликативному модулю $p^2$. Функция $\log :{\gamma }_p⟶Z_p$, связывающая $\frac{x-1}{p}$ с $x$, определена на $n=p^{2}q$ и обладает гомоморфными свойствами, а в частности:

$\mathrm{\forall }(x,y\in {\gamma }_p)\log (xy{modp}^2)=\log (x)+\log (y)modp$

,

или, более общо:

$\mathrm{\forall }(g\in {\gamma }_p,m\in Z_p)\log (g^m{modp}^2)=m\log (g)modp$

Алгоритмизация

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

1. Выбираются два больших различных простых числа $p$ и $q$ и вычисляется $n=p^{2}q$;
2. Выбирается число $g\in (\mathbb{Z}/n\mathbb{Z}{)}^{*}$ такое, что $g^{p-1}\ne 1mod{p}^2$;
3. Вычисляется $h=g^{n}modn$

Таким образом, $(n,g,h)$ — открытый ключ, $(p,q)$ — секретный ключ.

Шифрование

Чтобы зашифровать k-битное сообщение $m$, где $0<m<2^{k-1}$:

1. Выбирается случайное $r\in \mathbb{Z}/n\mathbb{Z}$;
2. Вычисляется шифртекст: $C=g^m{h}^{r}modn$

Расшифровка

Для $L(x)=\frac{x-1}{p}$ расшифровка сообщения $C$:

$m=\frac{L\left(C^{p-1}{modp}^2\right)}{L\left(g^{p-1}mod{p}^2\right)}modp$.

Свойства

Криптосистема является аддитивно гомоморфной, так как при $m_1+m_2<p$ выполняется:

$ℰ(m_1)\cdot ℰ(m_2)=(g^{m_1}{r}_1^c)(g^{m_2}{r}_2^c)modn=g^{m_1+m_2}(r_1{r}_2{)}^{c}mod=ℰ(m_1+m_2)$,

где $ℰ(m)$ является функцией шифрования от сообщения $m$.

Стойкость криптосистемы Окамото — Утиямы основана на сложности задачи факторизации числа $n$ и требует $O({\log }_{3}n)$ битовых операций.

Снижение сложности расшифровки

Возможно понизить сложность схемы до $O({\log }_{2}n)$, для этого выбирается $p$ через большой (160-битный) коэффициент $t$ следующим образом: $p-1=tu$ и модифицируется схему следующим образом:

1. Выбрать произвольное число $g<n$ такое, что $g_p=g^{(p-1)}{modp}^2$
2. Вычислить $G=g^{u}modn$
3. Выбрать произвольное число $g^{\prime }<n$ и вычислить $H={g^{\prime }}^{nu}modn$

Тогда тройка значений $(n,G,H)$ образует открытый ключ, а $(p,q)$ — секретный ключ.

Шифрование

1. Выбрать случайным образом число $r<n$
2. Расшифровать $(k-1)$-битное сообщение $m$ следующим образом: $c=G^m{H}^{r}modn$ .

Расшифровка

1. $c^{\prime }=c^t{modp}^2=g^{m(p-1)}{g}^{\prime nr(p-1)}=g_p^m{modp}^2$;
2. $m=\log (c^{\prime })\log (g_p{)}^{-1}modp$.

Литература

• Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). «A new public-key cryptosystem as secure as factoring». Advances in Cryptology — EUROCRYPT’98.
• Accelerating Okamoto-Uchiyama’s Public-Key Cryptosystem (Jean-S´ebastien Coron, David Naccache, Pascal Paillier)