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

Криптосистема Дамгорда -Юрика. является обобщением криптосистемы Пайе . Он использует вычисления по модулю $n^{s+1}$ где $n$ представляет собой модуль RSA и $s$ (положительное) натуральное число . Схема Пайе представляет собой частный случай $s=1$. Порядок $\varphi (n^{s+1})$ ( общая функция Эйлера ) $Z_{n^{s+1}}^{*}$ можно разделить на $n^{s}$. Более того, $Z_{n^{s+1}}^{*}$ можно записать как прямое произведение $G\times H$. $G$ является циклическим и упорядоченным $n^{s}$, пока $H$ изоморфен $Z_{n}^{*}$. Для шифрования сообщение преобразуется в соответствующий смежный класс факторной группы. $G\times H/H$ а безопасность схемы зависит от сложности различения случайных элементов в разных смежных классах $H$. , Семантически безопасно если трудно определить, находятся ли два заданных элемента в одном смежном классе. Как и Пайе, безопасность Дамгорда-Юрика может быть доказана в рамках предположения о составной невязкости принятия решений .

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

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

• Открытый ключ (шифрования) — это $(n,g)$.
• Закрытый ключ (дешифрования) $d$.

Шифрование

1. Позволять $m$ быть сообщением, которое нужно зашифровать, где $m\in \mathbb {Z} _{n^{s}}$.
2. Выбрать случайный $r$ где $r\in \mathbb {Z} _{n}^{*}$.
3. Вычислите зашифрованный текст как: $c=g^{m}\cdot r^{n^{s}}\mod n^{s+1}$.

Расшифровка

1. Зашифрованный текст $c\in \mathbb {Z} _{n^{s+1}}^{*}$
2. Вычислить $c^{d}\;mod\;n^{s+1}$. Если c является действительным зашифрованным текстом, то $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}}$.
3. Примените рекурсивную версию механизма дешифрования Пайе, чтобы получить $jmd$. Как $jd$ известно, можно вычислить $m=(jmd)\cdot (jd)^{-1}\;mod\;n^{s}$.

Упрощение

За счет того, что классическая криптосистема Пайе больше не будет содержаться в качестве примера, Дамгорд-Юрик может быть упрощен следующим образом:

• Основание g фиксировано как $g=n+1$.
• Показатель дешифрования d вычисляется так, что $d=1\;mod\;n^{s}$ и $d=0\;mod\;\lambda$.

В этом случае расшифровка дает $c^{d}=(1+n)^{m}\;mod\;n^{s+1}$. Используя рекурсивное дешифрование Пайе, мы получаем непосредственно открытый текст m .

См. также

• Интерактивный симулятор криптосистемы Дамгорда -Юрика демонстрирует приложение для голосования.