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

Криптосистема Окамото — Утиямы — вероятностная криптосистема, предложенная в 1998 году Тацуаки Окамото и Сигэнори Утиямой, построена на основе логарифмической функции , определённой над мультипликативной группой , где , а и являются большими простыми числами.

Например, если  — большое простое число и , такое, чтo для , то имеет структуру группы по отношению к мультипликативному модулю . Функция , связывающая с , определена на и обладает гомоморфными свойствами, а в частности:

,

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

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

Генерация ключа
  1. Выбираются два больших различных простых числа и и вычисляется ;
  2. Выбирается число такое, что ;
  3. Вычисляется

Таким образом,  — открытый ключ,  — секретный ключ.

Шифрование

Чтобы зашифровать k-битное сообщение , где :

  1. Выбирается случайное ;
  2. Вычисляется шифртекст:
Расшифровка

Для расшифровка сообщения :

.

Свойства

Криптосистема является аддитивно гомоморфной, так как при выполняется:

,

где является функцией шифрования от сообщения .

Стойкость криптосистемы Окамото — Утиямы основана на сложности задачи факторизации числа и требует битовых операций.

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

Возможно понизить сложность схемы до , для этого выбирается через большой (160-битный) коэффициент следующим образом[1]: и модифицируется схему следующим образом:

  1. Выбрать произвольное число такое, что
  2. Вычислить
  3. Выбрать произвольное число и вычислить

Тогда тройка значений образует открытый ключ, а  — секретный ключ.

Шифрование
  1. Выбрать случайным образом число
  2. Расшифровать -битное сообщение следующим образом: .
Расшифровка
  1. ;
  2. .

Примечания

  1. Accelerating Okamoto-Uchiyama’s Public-Key Cryptosystem (Jean-S´ebastien Coron, David Naccache, Pascal Paillier)

Литература

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

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!