Криптосистема Окамото – Учияма - Okamoto–Uchiyama cryptosystem

В Криптосистема Окамото – Учияма это криптосистема с открытым ключом предложенный в 1998 г. Тацуаки Окамото и Сигенори Учияма. Система работает в мультипликативная группа целых чисел по модулю n, ${displaystyle (mathbb {Z} /nmathbb {Z} )^{*}}$, где п имеет форму п²q и п и q большие простые числа.

Операция

Как и многие криптосистемы с открытым ключом, эта схема работает в группе ${displaystyle (mathbb {Z} /nmathbb {Z} )^{*}}$. Эта схема гомоморфный и, следовательно податливый.

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

Пара открытый / закрытый ключ создается следующим образом:

1. Создайте два больших простых числа ${displaystyle p}$ и ${displaystyle q}$.
2. Вычислить ${displaystyle n=p^{2}q}$.
3. Выберите случайное целое число ${displaystyle gin {2dots n-1}}$ такой, что ${displaystyle g^{p-1}ot equiv 1mod p^{2}}$.
4. Вычислить ${displaystyle h=g^{n}{mod {n}}}$.

Тогда открытый ключ ${displaystyle (n,g,h)}$ а закрытый ключ ${displaystyle (p,q)}$.

Шифрование

Сообщение ${displaystyle m<p}$ может быть зашифрован открытым ключом ${displaystyle (n,g,h)}$ следующим образом.

1. Выберите случайное целое число ${displaystyle rin {1dots n-1}}$.
2. Вычислить ${displaystyle c=g^{m}h^{r}{mod {n}}}$.

Значение ${displaystyle c}$ это шифрование ${displaystyle m}$.

Расшифровка

Зашифрованное сообщение ${displaystyle c}$ можно расшифровать с помощью закрытого ключа ${displaystyle (p,q)}$ следующим образом.

1. Вычислить ${displaystyle a={frac {(c^{p-1}{mod {p^{2}}})-1}{p}}}$.
2. Вычислить ${displaystyle b={frac {(g^{p-1}{mod {p^{2}}})-1}{p}}}$. ${displaystyle a}$ и ${displaystyle b}$ будут целыми числами.
3. С использованием Расширенный евклидов алгоритм, вычислить обратное ${displaystyle b}$ по модулю ${displaystyle p}$:

   ${displaystyle b'=b^{-1}{mod {p}}}$.

4. Вычислить ${displaystyle m=ab'{mod {p}}}$.

Значение ${displaystyle m}$ это расшифровка ${displaystyle c}$.

пример

Позволять ${displaystyle p=3}$ и ${displaystyle q=5}$. потом ${displaystyle n=3^{2}cdot 5=45}$. Выбрать ${displaystyle g=22}$. потом ${displaystyle h=22^{45}{mod {4}}5=37}$.

Теперь зашифруем сообщение ${displaystyle m=2}$, мы выбираем случайный ${displaystyle r=13}$ и вычислить ${displaystyle c=g^{m}h^{r}{mod {n}}=22^{2}37^{13}{mod {4}}5=43}$.

Чтобы расшифровать сообщение 43, мы вычисляем

${displaystyle a={frac {(43^{2}{mod {3}}^{2})-1}{3}}=1}$.

${displaystyle b={frac {(22^{2}{mod {3}}^{2})-1}{3}}=2}$.

${displaystyle b'=2^{-1}{mod {3}}=2}$.

И наконец ${displaystyle m=ab'=2}$.

Доказательство правильности

Мы хотим доказать, что значение, вычисленное на последнем шаге дешифрования, ${displaystyle ab'{mod {p}}}$, равно исходному сообщению ${displaystyle m}$. У нас есть

${displaystyle (g^{m}h^{r})^{p-1}equiv (g^{m}g^{nr})^{p-1}equiv (g^{p-1})^{m}g^{p(p-1)rpq}equiv (g^{p-1})^{m}mod p^{2}}$

Итак, чтобы восстановить ${displaystyle m}$ нам нужно взять дискретный логарифм с базой ${displaystyle g^{p-1}}$.

Группа

${displaystyle (mathbb {Z} /nmathbb {Z} )^{*}simeq (mathbb {Z} /p^{2}mathbb {Z} )^{*} imes (mathbb {Z} /qmathbb {Z} )^{*}}$.

Мы определяем ЧАС которая является подгруппой ${displaystyle mathbb {Z} /p^{2}mathbb {Z} ^{*}}$ и его мощность п-1

${displaystyle H={x:x^{p-1}mod p^{2}=1+rp,0<r<p}}$.

Для любого элемента Икс в ${displaystyle (mathbb {Z} /p^{2}mathbb {Z} )^{*}}$, у нас есть Икс^п−1 модп² в ЧАС, поскольку п разделяет Икс^п−1 − 1.

Карта ${displaystyle L(x)={frac {x-1}{p}}}$ следует рассматривать как логарифм от циклической группы ЧАС в аддитивную группу ${displaystyle mathbb {Z} /pmathbb {Z} }$, и легко проверить, что L(ab) = L(а) + L(б), и что L является изоморфизмом между этими двумя группами. Как и в случае с обычным логарифмом, L(Икс)/L(г) в некотором смысле является логарифмом Икс с базойг.

что достигается

${displaystyle {frac {Lleft((g^{p-1})^{m}ight)}{L(g^{p-1})}}=mmod p.}$^{[требуется дальнейшее объяснение ]}

Безопасность

Безопасность весь сообщение можно показать как эквивалент факторинга п.^{[требуется разъяснение ]} В семантическая безопасность опирается на п-подгрупповое допущение, которое предполагает, что трудно определить, является ли элемент Икс в ${displaystyle (mathbb {Z} /nmathbb {Z} )^{*}}$ находится в подгруппе порядка п. Это очень похоже на квадратичная проблема остаточности и проблема более высокой остаточности.

использованная литература

• Окамото, Тацуаки; Учияма, Сигенори (1998). «Новая криптосистема с открытым ключом, столь же безопасная, как факторинг». Достижения в криптологии - EUROCRYPT'98. Конспект лекций по информатике. 1403. Springer. С. 308–318. Дои:10.1007 / BFb0054135.