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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${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}}$

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

${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}}$

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

${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}=}$

${=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. Случайно и независимо друг от друга выбирается два больших простых числа $p$ и $q$;
2. Вычисляется $n=pq$ и $\lambda$ как наименьшее общее кратное чисел ${p-1}$ и ${q-1}$;
3. Выбирается элемент ${g\in {\mathbb {Z} }_{n^{s+1}}^{*}}$ такой, что ${g=(1+n)^{j}x{\bmod {n}}^{s+1}}$ для заданного $j$ является взаимно простым с $n$ и ${x\in H}$.
   Замечание:это можно сделать проще, если сначала случайно выбрать $j$ и $x$, а затем по ним вычислить $g$.
4. Выбирается $d$ такое, что ${d{\bmod {n}}\in {\mathbb {Z} }_{n}^{*}}$ и ${d=0{\bmod {\lambda }}}$ (с использованием Китайской теоремы об остатках). Например, за $d$ можно взять ${\lambda }$ как и в схеме Пэйе.

Таким образом, открытым ключом будет пара $(n,g)$, а секретным — $d$.

Шифрование

1. Пусть $m$ — шифруемое сообщение, причем ${m\in {\mathbb {Z} }_{n^{s}}}$;
2. Выбирается случайное $r$, такое, что ${r\in {\mathbb {Z} }_{n^{s+1}}^{*}}$;
3. Вычисляется шифртекст: ${c=g^{m}\cdot r^{n^{s}}{\bmod {n}}^{s+1}}$.

Расшифровка

1. Пусть $c$ — шифртекст, причем ${c\in {\mathbb {Z} }_{n^{s+1}}^{*}}$;
2. Вычисляется ${c^{d}\;bmod\;n^{s+1}}$. Если $c$ -действующий шифртекст, то ${c^{d}=(g^{m}r^{n^{s}})^{d}=((1+n)^{jm}x^{m}r^{n^{s}})^{d}=(1+n)^{jmd\;{\bmod {\;}}n^{s}}(x^{m}r^{n^{s}})^{d\;{\bmod {\;}}\lambda }=(1+n)^{jmd\;{\bmod {\;}}n^{s}}}$
3. По указанному выше алгоритму вычисляется ${jid{\bmod {n}}^{s}}$. Поскольку произведение ${jd}$ уже известно, осталось вычислить ${m=(jmd)\cdot (jd)^{-1}\;{\bmod {\;}}n^{s}}$.

Гомоморфизм

Система гомоморфна относительно сложения в ${Z_{n^{s}}}$:

${{\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}n^{s})}$.

Литература

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