Криптосистема Окамото — Утиямы — вероятностная криптосистема, предложенная в 1998 году Тацуаки Окамото и Сигэнори Утиямой, построена на основе логарифмической функции , определённой над мультипликативной группой , где , а и являются большими простыми числами.
Например, если — большое простое число и , такое, чтo для , то имеет структуру группы по отношению к мультипликативному модулю . Функция , связывающая с , определена на и обладает гомоморфными свойствами, а в частности: </p>,
или, более общо: </p>
Алгоритмизация Генерация ключа Выбираются два больших различных простых числа и и вычисляется ; Выбирается число такое, что ; Вычисляется
Таким образом, — открытый ключ, — секретный ключ.
Шифрование Чтобы зашифровать k-битное сообщение , где : Выбирается случайное ; Вычисляется шифртекст:
Расшифровка Для расшифровка сообщения :
.
Свойства Криптосистема является аддитивно гомоморфной, так как при выполняется:
, где является функцией шифрования от сообщения .
Стойкость криптосистемы Окамото — Утиямы основана на сложности задачи факторизации числа и требует битовых операций.
Снижение сложности расшифровки Возможно понизить сложность схемы до , для этого выбирается через большой (160-битный) коэффициент следующим образом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)
Категория:Криптография с открытым ключом