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

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

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

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

,

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

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

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

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

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

Таким образом, $(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}{\bmod {n}}}$

Расшифровка

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

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

Свойства

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

${{\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})}$,

где ${{\mathcal {E}}(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)}{\bmod {p}}^{2}}$
2. Вычислить ${G=g^{u}{\bmod {n}}}$
3. Выбрать произвольное число $g^{\prime }<n$ и вычислить ${H={g^{\prime }}^{nu}{\bmod {n}}}$

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

Шифрование

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

Расшифровка

1. ${c^{\prime }=c^{t}{\bmod {p}}^{2}=g^{m(p-1)}g^{\prime nr(p-1)}=g_{p}^{m}{\bmod {p}}^{2}}$;
2. ${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)