Русская Википедия:Криптосистема Окамото — Утиямы

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

<math>{\forall (x, y \in\gamma_{p}}) {\log(xy \bmod p^{2}) = \log(x) + \log(y) \bmod p}</math>

,

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

<math>{\forall (g \in\gamma_{p}, m \in Z_{p}}) {\log(g^{m} \bmod p^{2}) = m\log(g)\bmod p}</math>

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

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

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

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

Шифрование

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

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

Расшифровка

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

<math>m={\frac {L\left(C^Шаблон:P-1\bmod p^{2}\right)}{L\left(g^Шаблон:P-1\mod p^{2}\right)}}\bmod p</math>.

Свойства

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

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

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

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

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

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

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

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

Шифрование

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

Расшифровка

1. <math>{c^\prime = c^{t} \bmod p^{2} = g^{m(p-1)}g^{\prime nr(p-1)} = g^{m}_{p} \bmod p^{2}}</math>;
2. <math>{m=\log(c^\prime) \log(g_{p})^{-1}\bmod p}</math>.

Литература

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