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

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

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

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

Для объяснения дальнейших рассуждений, сформулируем следующую лемму^[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})=(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)

Литература

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