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

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

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

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

Расшифровка

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

Упрощение

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

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

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

Смотрите также

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

Ссылки

1. Иван Дамгард , Мадс Юрик: Обобщение, упрощение и некоторые приложения вероятностной системы с открытым ключом Пайе. Криптография с открытым ключом 2001: 119-136