Криптосистема Дамгорда — Юрика — криптосистема с открытым ключом, предложенная и Мадсом Юриком в 2000 году. Является обобщением криптосистемы Пэйе для больших модулей с целью расширения области применения.
Предпосылки: обобщение схемы Пэйе Описываемая криптосистема использует расчётный модуль , где — модуль RSA, а — натуральное число. В случае представляет собой схему криптосистемы Пэйе.
Пусть , где и — нечётные простые числа. является декартовым произведением , где — циклическая группа порядка , а изоморфна группе . Таким образом, факторгруппа тоже является циклической порядка . Каждому произвольному элементу ставится в соответствие элемент из факторгруппы .
Имеет место следующая полезная лемма: для любых , элемент имеет порядок в мультипликативной группе .
Как только порядок становится взаимно простым с , можно считать, что элемент является генератором группы , кроме, возможно, . Таким образом, смежными классами для и являются
что приводит к естественной нумерации этих смежных классов.
Ещё одним техническим приёмом, необходимым для обоснования дальнейших вычислений, является простой способ определения по . Пусть , тогда
Далее последовательно вычисляются
Достаточно вычислить лишь :
Дальнейшие вычисления проводятся по индукции: на -ом шаге известно . Тогда для некоторого . Тогда:
Каждый член для удовлетворяет . Следовательно
Таким образом,
Описание схемы
Генерация ключа Случайно и независимо друг от друга выбирается два больших простых числа и ; Вычисляется и как наименьшее общее кратное чисел и ; Выбирается элемент такой, что для заданного является взаимно простым с и . Этот шаг можно упростить, если сначала случайно выбрать и , а затем по ним вычислить . Выбирается такое, что и (с использованием китайской теоремы об остатках). Например, за можно взять , как и в схеме Пэйе.
Таким образом, открытым ключом будет пара , а секретным — .
Шифрование Пусть — шифруемое сообщение, причем ; Выбирается случайное , такое, что ; Вычисляется шифртекст: .
Расшифровка Пусть — шифртекст, причем ; Вычисляется . Если — действующий шифртекст, то По указанному выше алгоритму вычисляется . Поскольку произведение уже известно, осталось вычислить .
Гомоморфизм Система гомоморфна относительно сложения в : .
Примечания
Категория:Криптография с открытым ключом