Русская Википедия:Криптосистема Дамгорда — Юрика

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

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

<math>{H,(1 + n)H,(1 + n)^{2}H,\dots,(1 + n)^{n^{s}-1},}</math>

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

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

<math>{L((1 + n)^{i}\bmod n^{s+1})=(i +{\dbinom i 2} n + ... +{\dbinom i s}n^{s-1})\bmod n^{s}}</math>

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

<math>{i_{1} = i\bmod n, i_{2} = i\bmod n^{2},\dots}</math>

Достаточно просто вычислить <math>i_{1}</math>:

<math>{i_{1} = L((1+n)i \bmod n^{2}) = i \bmod n}</math>

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

<math>{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}}</math>

Заметим, что каждый член <math>{{\dbinom {i_{j}} {t+1}}n^{t}}</math> для <math>{j>t> 0}</math> удовлетворяет <math>{{\dbinom {i_{j}} {t+1}}n^{t} = {\dbinom {i_{j-1}} {t+1}}n^{t}\bmod n^{j}}</math>. Следовательно:

<math>{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}}</math>

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

<math>{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} =}</math>

<math>{=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}}</math>

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

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

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

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

Шифрование

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

Расшифровка

1. Пусть <math>c</math> — шифртекст, причем <math>{c\in {\mathbb Z}_{{n^Шаблон:S+1}}^Шаблон:*}</math>;
2. Вычисляется <math>{c^{d}\;bmod\;n^Шаблон:S+1}</math>. Если <math>c</math> -действующий шифртекст, то <math>{c^{d}=(g^{m}r^{{n^{s}}})^{d}=((1+n)^Шаблон:Jmx^{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}}}}</math>

1. По указанному выше алгоритму вычисляется <math>{jid \bmod n^{s}}</math>. Поскольку произведение <math>{jd}</math> уже известно, осталось вычислить <math>{m=(jmd)\cdot (jd)^Шаблон:-1\;\bmod\;n^{s}}</math>.

Гомоморфизм

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

<math>{{\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}n^{s})}</math>.

Литература

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