Криптосистема Дамгорда — Юрика

Криптосистема Дамгорда — Юрика — криптосистема с открытым ключом, предложенная Иваном Дамгордом и Мадсом Юриком в 2000 г. Является обобщением криптосистемы Пэйе для больших модулей с целью расширения области применения[1].

Предпосылки: Обобщение схемы Пэйе

править

Описываемая криптосистема использует расчётный модуль  , где   — модуль RSA, а   — натуральное число. В случае, если  , представляет собой схему криптосистемe Пэйе.

Пусть  , где  ,   — нечётные простые числа. Заметим, что мультипликативная группа   является декартовым произведением  , где   — циклическая группа порядка  , а   — изоморфна группе  . Таким образом, факторгруппа     тоже является циклической порядка  . Каждому произвольному элементу   мы ставим в соответствие элемент   из факторгруппы  .

Для объяснения дальнейших рассуждений, сформулируем следующую лемму[2]

Лемма: Для любых  , элемент   имеет порядок   в мультипликативной группе  .

Как только порядок   становится взаимно простым с  , мы можем считать, что элемент   является генератором группы  , кроме, возможно,  . Таким образом, смежными классами для   и   являются:

 

что приводит к естественной нумерации этих смежных классов.

Ещё одним техническим приёмом, необходимым для обоснования дальнейших вычислений, является простой способ определения   по  . Для его реализации, обозначим функцию   , тогда

 

Далее, последовательно вычисляем:

 

Достаточно просто вычислить  :

 

Дальнейшие вычисления проводим по индукции: на  -ом шаге мы знаем  . Тогда   для некоторого  . Используем это соотношение:

 

Заметим, что каждый член   для   удовлетворяет  . Следовательно:

 

Таким образом, получаем:

 

 

Описание схемы

править

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

править
  1. Случайно и независимо друг от друга выбирается два больших простых числа   и  ;
  2. Вычисляется   и   как наименьшее общее кратное чисел   и  ;
  3. Выбирается элемент   такой, что   для заданного   является взаимно простым с   и  .
    Замечание:это можно сделать проще, если сначала случайно выбрать   и  , а затем по ним вычислить  .
  4. Выбирается   такое, что   и   (с использованием Китайской теоремы об остатках). Например, за   можно взять   как и в схеме Пэйе.

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

Шифрование

править
  1. Пусть   — шифруемое сообщение, причем  ;
  2. Выбирается случайное  , такое, что  ;
  3. Вычисляется шифртекст:  .

Расшифровка

править
  1. Пусть   — шифртекст, причем  ;
  2. Вычисляется  . Если   -действующий шифртекст, то  
  3. По указанному выше алгоритму вычисляется  . Поскольку произведение   уже известно, осталось вычислить  .

Гомоморфизм

править

Система гомоморфна относительно сложения в  :

 .

Примечания

править
  1. Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) А.И.Трубей
  2. A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System (Ivan B. Damgard, Mads J. Jurik)

Литература

править
  1. Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) (А.И.Трубей)
  2. A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System (Ivan B. Damgard, Mads J. Jurik)