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

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

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

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

,

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

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

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

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

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

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

Шифрование

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

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

Расшифровка

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

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

Свойства

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

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

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

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

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

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

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

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

Шифрование

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

Расшифровка

1. [math]\displaystyle{ {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]\displaystyle{ {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)