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

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

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

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

Пусть n = p q {displaystyle {n=pq}} , где p {displaystyle p} , q {displaystyle q} — нечётные простые числа. Заметим, что мультипликативная группа Z n s + 1 ∗ {displaystyle {Z_{n^{s+1}}^{*}}} является декартовым произведением G × H {displaystyle {G imes H}} , где G {displaystyle G} — циклическая группа порядка n s {displaystyle {n^{s}}} , а H {displaystyle H} — изоморфна группе Z n ∗ {displaystyle {Z_{n}^{*}}} . Таким образом, факторгруппа G ¯ = Z n s + 1 ∗ / {displaystyle {{overline {G}}=Z_{n^{s+1}}^{*}/}} H {displaystyle H} тоже является циклической порядка n s {displaystyle {n^{s}}} . Каждому произвольному элементу a ∈ Z n s + 1 ∗ {displaystyle {ain Z_{n^{s+1}}^{*}}} мы ставим в соответствие элемент a ¯ = a H {displaystyle {{overline {a}}=aH}} из факторгруппы G ¯ {displaystyle {overline {G}}} .

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

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

Как только порядок H {displaystyle H} становится взаимно простым с n s {displaystyle {n^{s}}} , мы можем считать, что элемент 1 + n ¯ := ( 1 + n ) H ∈ G ¯ {displaystyle {{overline {1+n}}:=(1+n)Hin {overline {G}}}} является генератором группы G ¯ {displaystyle {overline {G}}} , кроме, возможно, s ⩾ p , q {displaystyle sgeqslant p,q} . Таким образом, смежными классами для H {displaystyle H} и Z n s + 1 ∗ {displaystyle {Z_{n^{s+1}}^{*}}} являются:

H , ( 1 + n ) H , ( 1 + n ) 2 H , … , ( 1 + n ) n s − 1 , {displaystyle {H,(1+n)H,(1+n)^{2}H,dots ,(1+n)^{n^{s}-1},}}

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

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

L ( ( 1 + n ) i mod n s + 1 ) = ( i + ( i 2 ) n + . . . + ( i s ) n s − 1 ) mod n s {displaystyle {L((1+n)^{i}{mod {n}}^{s+1})=(i+{dbinom {i}{2}}n+...+{dbinom {i}{s}}n^{s-1}){mod {n}}^{s}}}

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

i 1 = i mod n , i 2 = i mod n 2 , … {displaystyle {i_{1}=i{mod {n}},i_{2}=i{mod {n}}^{2},dots }}

Достаточно просто вычислить i 1 {displaystyle i_{1}} :

i 1 = L ( ( 1 + n ) i mod n 2 ) = i mod n {displaystyle {i_{1}=L((1+n)i{mod {n}}^{2})=i{mod {n}}}}

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

L ( ( 1 + n ) i mod n j + 1 ) = ( i j + ( i j 2 ) n + . . . + ( i j j ) n ( j − 1 ) ) mod n j {displaystyle {L((1+n)^{i}{mod {n}}^{j+1})=(i_{j}+{dbinom {i_{j}}{2}}n+...+{dbinom {i_{j}}{j}}n^{(j-1)}){mod {n}}^{j}}}

Заметим, что каждый член ( i j t + 1 ) n t {displaystyle {{dbinom {i_{j}}{t+1}}n^{t}}} для j > t > 0 {displaystyle {j>t>0}} удовлетворяет ( i j t + 1 ) n t = ( i j − 1 t + 1 ) n t mod n j {displaystyle {{dbinom {i_{j}}{t+1}}n^{t}={dbinom {i_{j-1}}{t+1}}n^{t}{mod {n}}^{j}}} . Следовательно:

L ( ( 1 + n ) i mod n j + 1 ) = ( i j − 1 + k n j − 1 + ( i j − 1 2 ) n + . . . + ( i j − 1 j ) n ( j − 1 ) ) mod n j {displaystyle {L((1+n)^{i}{mod {n}}^{j+1})=(i_{j-1}+kn^{j-1}+{dbinom {i_{j-1}}{2}}n+...+{dbinom {i_{j-1}}{j}}n^{(j-1)}){mod {n}}^{j}}}

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

i j = i j − 1 + k n j − 1 = i j − 1 + L ( ( 1 + n ) i mod n j + 1 ) − ( i j − 1 + ( i j − 1 2 ) n + ⋯ + ( i j − 1 j ) n ( j − 1 ) ) mod n j = {displaystyle {i_{j}=i_{j-1}+kn^{j-1}=i_{j-1}+L((1+n)^{i}{mod {n}}^{j+1})-(i_{j-1}+{dbinom {i_{j-1}}{2}}n+dots +{dbinom {i_{j-1}}{j}}n^{(j-1)}){mod {n}}^{j}=}}

= L ( ( 1 + n ) i mod n j + 1 ) − ( ( i j − 1 2 ) n + ⋯ + ( i j − 1 j ) n ( j − 1 ) ) mod n j {displaystyle {=L((1+n)^{i}{mod {n}}^{j+1})-({dbinom {i_{j-1}}{2}}n+dots +{dbinom {i_{j-1}}{j}}n^{(j-1)}){mod {n}}^{j}}}

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

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

Случайно и независимо друг от друга выбирается два больших простых числа p {displaystyle p} и q {displaystyle q} ;

Вычисляется n = p q {displaystyle n=pq} и λ {displaystyle lambda } как наименьшее общее кратное чисел p − 1 {displaystyle {p-1}} и q − 1 {displaystyle {q-1}} ;

Выбирается элемент g ∈ Z n s + 1 ∗ {displaystyle {gin {mathbb {Z} }_{n^{s+1}}^{*}}} такой, что g = ( 1 + n ) j x mod n s + 1 {displaystyle {g=(1+n)^{j}x{mod {n}}^{s+1}}} для заданного j {displaystyle j} является взаимно простым с n {displaystyle n} и x ∈ H {displaystyle {xin H}} .
Замечание:это можно сделать проще, если сначала случайно выбрать j {displaystyle j} и x {displaystyle x} , а затем по ним вычислить g {displaystyle g} .

Выбирается d {displaystyle d} такое, что d mod n ∈ Z n ∗ {displaystyle {d{mod {n}}in {mathbb {Z} }_{n}^{*}}} и d = 0 mod λ {displaystyle {d=0{mod {lambda }}}} (с использованием Китайской теоремы об остатках). Например, за d {displaystyle d} можно взять λ {displaystyle {lambda }} как и в схеме Пэйе.

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

Шифрование

Пусть m {displaystyle m} — шифруемое сообщение, причем m ∈ Z n s {displaystyle {min {mathbb {Z} }_{n^{s}}}} ;

Выбирается случайное r {displaystyle r} , такое, что r ∈ Z n s + 1 ∗ {displaystyle {rin {mathbb {Z} }_{n^{s+1}}^{*}}} ;

Вычисляется шифртекст: c = g m ⋅ r n s mod n s + 1 {displaystyle {c=g^{m}cdot r^{n^{s}}{mod {n}}^{s+1}}} .

Расшифровка

Пусть c {displaystyle c} — шифртекст, причем c ∈ Z n s + 1 ∗ {displaystyle {cin {mathbb {Z} }_{n^{s+1}}^{*}}} ;

Вычисляется c d b m o d n s + 1 {displaystyle {c^{d};bmod;n^{s+1}}} . Если c {displaystyle c} -действующий шифртекст, то c d = ( g m r n s ) d = ( ( 1 + n ) j m x m r n s ) d = ( 1 + n ) j m d mod n s ( x m r n s ) d mod λ = ( 1 + n ) j m d mod n s {displaystyle {c^{d}=(g^{m}r^{n^{s}})^{d}=((1+n)^{jm}x^{m}r^{n^{s}})^{d}=(1+n)^{jmd;{mod {;}}n^{s}}(x^{m}r^{n^{s}})^{d;{mod {;}}lambda }=(1+n)^{jmd;{mod {;}}n^{s}}}}

По указанному выше алгоритму вычисляется j i d mod n s {displaystyle {jid{mod {n}}^{s}}} . Поскольку произведение j d {displaystyle {jd}} уже известно, осталось вычислить m = ( j m d ) ⋅ ( j d ) − 1 mod n s {displaystyle {m=(jmd)cdot (jd)^{-1};{mod {;}}n^{s}}} .

Гомоморфизм

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

E ( x 1 ) ⋅ E ( x 2 ) = E ( x 1 + x 2 mod n s ) {displaystyle {{mathcal {E}}(x_{1})cdot {mathcal {E}}(x_{2})={mathcal {E}}(x_{1}+x_{2};{mod {;}}n^{s})}} .

Примечания

↑ Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) А.И.Трубей

↑ A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System (Ivan B. Damgard, Mads J. Jurik)

Литература

Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) (А.И.Трубей)

A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System (Ivan B. Damgard, Mads J. Jurik)