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

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

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

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

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

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

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

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

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

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

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