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

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

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

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

Пусть ${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})=\left(i+{\dbinom {i}{2}}n+...+{\dbinom {i}{s}}n^{s-1}\right){\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})=\left(i_{j}+{\dbinom {i_{j}}{2}}n+...+{\dbinom {i_{j}}{j}}n^{(j-1)}\right){\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})=\left(i_{j-1}+kn^{j-1}+{\dbinom {i_{j-1}}{2}}n+...+{\dbinom {i_{j-1}}{j}}n^{(j-1)}\right){\bmod {n}}^{j}}$

Таким образом,

${i_{j}=i_{j-1}+kn^{j-1}=i_{j-1}+L((1+n)^{i}{\bmod {n}}^{j+1})-\left(i_{j-1}+{\dbinom {i_{j-1}}{2}}n+\dots +{\dbinom {i_{j-1}}{j}}n^{(j-1)}\right){\bmod {n}}^{j}=L((1+n)^{i}{\bmod {n}}^{j+1})-\left({\dbinom {i_{j-1}}{2}}n+\dots +{\dbinom {i_{j-1}}{j}}n^{(j-1)}\right){\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})}$.