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

Например, если ${\displaystyle p}$ — большое простое число и ${\displaystyle \gamma _{p}\subset \mathbb {Z_{p^{2}}^{n}} }$, такое, чтo ${\displaystyle \gamma _{p}=x<p^{2}}$ для ${\displaystyle x=1{\bmod {p}}}$, то ${\displaystyle \gamma _{p}}$ имеет структуру группы по отношению к мультипликативному модулю ${\displaystyle p^{2}}$. Функция ${\displaystyle \log \colon \gamma _{p}\longrightarrow Z_{p}}$, связывающая ${\displaystyle {\frac {x-1}{p}}}$ с ${\displaystyle x}$, определена на ${\displaystyle n=p^{2}q}$ и обладает гомоморфными свойствами, а в частности:

${\displaystyle {\forall (x,y\in \gamma _{p}}){\log(xy{\bmod {p}}^{2})=\log(x)+\log(y){\bmod {p}}}}$

,

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

${\displaystyle {\forall (g\in \gamma _{p},m\in Z_{p}}){\log(g^{m}{\bmod {p}}^{2})=m\log(g){\bmod {p}}}}$

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

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

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

Шифрование

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

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

Расшифровка

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

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

Криптосистема является аддитивно гомоморфной, так как при ${\displaystyle {m_{1}+m_{2}<p}}$ выполняется:

${\displaystyle {{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})=(g^{m_{1}}r_{1}^{c})(g^{m_{2}}r_{2}^{c}){\bmod {n}}=g^{m_{1}+m_{2}}(r_{1}r_{2})^{c}{\bmod {=}}{\mathcal {E}}(m_{1}+m_{2})}}$,

где ${\displaystyle {{\mathcal {E}}(m)}}$ является функцией шифрования от сообщения ${\displaystyle m}$.

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

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

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

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

Шифрование

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

Расшифровка

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

• 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)