WikiSort.ru - Не сортированное

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

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}}}}$ .