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

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

Описываемая криптосистема использует расчётный модуль ${\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}}}$ .

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

Лемма: Для любых ${\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. Случайно и независимо друг от друга выбирается два больших простых числа ${\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})}}$ .

Примечания

Литература

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