WikiSort.ru - Не сортированное

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

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

Описываемая криптосистема использует расчётный модуль ${\displaystyle {n^{s+1}}}$ , где ${\displaystyle n}$  — модуль RSA, а ${\displaystyle s}$  — натуральное число. В случае, если ${\displaystyle s=1}$ , представляет собой схему криптосистемe Пэйе.

Пусть ${\displaystyle {n=pq}}$ , где ${\displaystyle p}$ , ${\displaystyle q}$  — нечётные простые числа. Заметим, что мультипликативная группа ${\displaystyle {Z_{n^{s+1}}^{*}}}$ является декартовым произведением ${\displaystyle {G\times H}}$ , где ${\displaystyle G}$  — циклическая группа порядка ${\displaystyle {n^{s}}}$ , а ${\displaystyle H}$  — изоморфна группе ${\displaystyle {Z_{n}^{*}}}$ . Таким образом, фактор-группа ${\displaystyle {{\overline {G}}=Z_{n^{s+1}}^{*}/}}$ ${\displaystyle H}$ тоже является циклической порядка ${\displaystyle {n^{s}}}$ . Каждому произвольному элементу ${\displaystyle {a\in Z_{n^{s+1}}^{*}}}$ мы ставим в соответствие элемент ${\displaystyle {{\overline {a}}=aH}}$ из фактор-группы ${\displaystyle {\overline {G}}}$ .

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

Лемма: Для любых ${\displaystyle s<p,q}$ , элемент ${\displaystyle N+1}$ имеет порядок ${\displaystyle {n^{s}}}$ в мультипликативной группе ${\displaystyle {Z_{n^{s+1}}^{*}}}$ .

Как только порядок ${\displaystyle H}$ становится взаимно простым с ${\displaystyle {n^{s}}}$ , мы можем считать, что элемент ${\displaystyle {{\overline {1+n}}:=(1+n)H\in {\overline {G}}}}$ является генератором группы ${\displaystyle {\overline {G}}}$ , кроме, возможно, ${\displaystyle s\geqslant p,q}$ . Таким образом, смежными классами для ${\displaystyle H}$ и ${\displaystyle {Z_{n^{s+1}}^{*}}}$ являются:

${\displaystyle {H,(1+n)H,(1+n)^{2}H,\dots ,(1+n)^{n^{s}-1},}}$

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

Ещё одним техническим приёмом, необходимым для обоснования дальнейших вычислений, является простой способ определения ${\displaystyle i}$ по ${\displaystyle {(1+n)^{i}{\bmod {n}}^{s+1}}}$ . Для его реализации, обозначим функцию ${\displaystyle {L(b)=(b-1)/}}$ ${\displaystyle n}$ , тогда

${\displaystyle {L((1+n)^{i}{\bmod {n}}^{s+1})=(i+{\dbinom {i}{2}}n+...+{\dbinom {i}{s}}n^{s-1}){\bmod {n}}^{s}}}$

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

${\displaystyle {i_{1}=i{\bmod {n}},i_{2}=i{\bmod {n}}^{2},\dots }}$

Достаточно просто вычислить ${\displaystyle i_{1}}$ :

${\displaystyle {i_{1}=L((1+n)i{\bmod {n}}^{2})=i{\bmod {n}}}}$

Дальнейшие вычисления проводим по индукции: на ${\displaystyle j}$ -ом шаге мы знаем ${\displaystyle i_{j-1}}$ . Тогда ${\displaystyle {i_{j}=i_{j-1}+kn^{j-1}}}$ для некоторого ${\displaystyle {0\leq k<n}}$ . Используем это соотношение:

${\displaystyle {L((1+n)^{i}{\bmod {n}}^{j+1})=(i_{j}+{\dbinom {i_{j}}{2}}n+...+{\dbinom {i_{j}}{j}}n^{(j-1)}){\bmod {n}}^{j}}}$

Заметим, что каждый член ${\displaystyle {{\dbinom {i_{j}}{t+1}}n^{t}}}$ для ${\displaystyle {j>t>0}}$ удовлетворяет ${\displaystyle {{\dbinom {i_{j}}{t+1}}n^{t}={\dbinom {i_{j-1}}{t+1}}n^{t}{\bmod {n}}^{j}}}$ . Следовательно:

${\displaystyle {L((1+n)^{i}{\bmod {n}}^{j+1})=(i_{j-1}+kn^{j-1}+{\dbinom {i_{j-1}}{2}}n+...+{\dbinom {i_{j-1}}{j}}n^{(j-1)}){\bmod {n}}^{j}}}$

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

${\displaystyle {i_{j}=i_{j-1}+kn^{j-1}=i_{j-1}+L((1+n)^{i}{\bmod {n}}^{j+1})-(i_{j-1}+{\dbinom {i_{j-1}}{2}}n+\dots +{\dbinom {i_{j-1}}{j}}n^{(j-1)}){\bmod {n}}^{j}=}}$

${\displaystyle {=L((1+n)^{i}{\bmod {n}}^{j+1})-({\dbinom {i_{j-1}}{2}}n+\dots +{\dbinom {i_{j-1}}{j}}n^{(j-1)}){\bmod {n}}^{j}}}$

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

Примечания

Литература

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