Криптосистема Окамото и Утиямы — вероятностная криптосистема, предложенная в 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}\mid x=1{\bmod {p}}}}$}, то ${\displaystyle \gamma _{p}}$ имеет структуру группы по отношению к мультипликативному модулю ${\displaystyle p^{2}}$. Функция ${\displaystyle \log(.):\gamma _{p}\longrightarrow Z_{p}}$ , связывающая ${\displaystyle {\frac {x-1}{p}}}$ с ${\displaystyle x}$, определена на ${\displaystyle n=p^{2}q}$ и обладает гомоморфными свойствами, а в частности:

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

Или, обобщая:

${\displaystyle {\forall g\in \gamma _{p},m\in Z_{p}}}$    ${\displaystyle {\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. Pасшифровать ${\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)