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

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

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

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

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

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

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

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

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

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

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

$L((1+n{)}^i{modn}^{s+1})=(i+(\genfrac{}{}{0ex}{}{i}{2})n+\mathrm{...}+(\genfrac{}{}{0ex}{}{i}{s})n^{s-1}){modn}^s$

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

$i_1=imodn,i_2=i{modn}^2,\dots$

Достаточно просто вычислить $i_1$:

$i_1=L((1+n)i{modn}^2)=imodn$

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

$L((1+n{)}^i{modn}^{j+1})=(i_j+(\genfrac{}{}{0ex}{}{i_j}{2})n+\mathrm{...}+(\genfrac{}{}{0ex}{}{i_j}{j})n^{(j-1)}){modn}^j$

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

$L((1+n{)}^i{modn}^{j+1})=(i_{j-1}+k{n}^{j-1}+(\genfrac{}{}{0ex}{}{i_{j-1}}{2})n+\mathrm{...}+(\genfrac{}{}{0ex}{}{i_{j-1}}{j})n^{(j-1)}){modn}^j$

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

$i_j=i_{j-1}+k{n}^{j-1}=i_{j-1}+L((1+n{)}^i{modn}^{j+1})-(i_{j-1}+(\genfrac{}{}{0ex}{}{i_{j-1}}{2})n+\dots +(\genfrac{}{}{0ex}{}{i_{j-1}}{j})n^{(j-1)}){modn}^j=$

$=L((1+n{)}^i{modn}^{j+1})-((\genfrac{}{}{0ex}{}{i_{j-1}}{2})n+\dots +(\genfrac{}{}{0ex}{}{i_{j-1}}{j})n^{(j-1)}){modn}^j$

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

Генерация ключа

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

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

Шифрование

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

Расшифровка

1. Пусть $c$ — шифртекст, причем $c\in {\mathbb{Z}}_{n^{s+1}}^{\ast }$;
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{)}^{jmdmod{n}^s}(x^m{r}^{n^s}{)}^{dmod\lambda }=(1+n{)}^{jmdmod{n}^s}$
3. По указанному выше алгоритму вычисляется $jid{modn}^s$. Поскольку произведение $jd$ уже известно, осталось вычислить $m=(jmd)\cdot (jd{)}^{-1}mod{n}^s$.

Гомоморфизм

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

$ℰ(x_1)\cdot ℰ(x_2)=ℰ(x_1+x_{2}mod{n}^s)$.

Литература

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