Подпись Нюберг — Руэппеля

Подпись Нюберг — Руэппеля (англ. Nyberg-Rueppel Signature Scheme) — схема электронной подписи с использованием открытого ключа, основанная на задаче дискретного логарифмирования в конечном поле. Алгоритм не может использоваться для шифрования (в отличие от RSA и схемы Эль-Гамаля). Подпись создается секретно, но может быть публично проверена. Это значит, что только один субъект может создать подпись сообщения, но любой может проверить её корректность. Схема была предложена Кайсой Нюберг и Райнером Руэппелем в 1993 году на первой конференции ACM (англ. 1st ACM conference on Computer and communications security) как модификация DSA.

История

В 1993 году Кайса Нюберг и Райнер Руэппель представили новую схему подписи, основанную на тех же принципах, что и DSA. Основное отличие заключается в том, что новая схема обеспечивает восстановление сообщений. Но в отличие от RSA, преобразования подписи и восстановления не коммутируют. Следовательно, новая схема не может быть использована для шифрования. Преимуществами восстановления сообщений являются: приложения без хэш-функции, меньшая пропускная способность для подписей небольших сообщений, прямое использование в других схемах, таких как системы открытого ключа на основе идентификации или протоколы согласования ключей.

Авторы представили два приложения новой схемы. Во-первых, в системе открытых ключей на основе идентификации, которая позволяет избежать требования полного доверия Центру ключей. Во-вторых, в протоколе соглашения о ключах, который устанавливает общий секретный ключ между двумя сторонами взаимно аутентифицированным способом. Несомненно, за этим последует ещё больше применений новой системы подписи.

Использование алгоритма

Схема подписи с восстановлением сообщения подразумевает собой процедуру, когда сообщение восстанавливается после проверки подписи. Иными словами, пусть имеются два пользователя, Алиса и Боб, и незащищенный канал связи между ними. Пользователь Алиса подписывает открытое сообщение секретным ключом, а полученную подпись пересылает пользователю Бобу, который в свою очередь с помощью открытого ключа проверяет подлинность подписи и восстанавливает сообщение. При положительном результате проверки, Боб убеждается в целостности сообщения, в его оригинальности (то есть в том, что сообщение было послано именно пользователем Алисой), а также лишается возможности утверждать, что Алиса не посылала это сообщение. Важно, что только Алиса способна подписать своё сообщение, потому что только она знает свой секретный ключ, и то, что её подпись может быть проверена любым пользователем, так как для этого нужен лишь открытый ключ.

Параметры схемы цифровой подписи

Для построения системы цифровой подписи и генерации ключей необходимо:

1. Выбрать открытую функцию избыточности $f$, которая преобразует фактическое сообщение в данные, которые затем подписываются. Это похоже на хеш-функцию в схемах подписи с приложением, но в отличие от них, функция избыточности должны быть легко обратима.
2. Выбрать большое простое число $Q$.
3. Выбрать большое простое число $P$, такое, что $(P-1)$ делится на $Q$.
4. Сгенерировать случайное число $H<P$ и вычислить $G=H^{(P-1)/Q}\mod P$. Если $G=1$, то искать другое случайное $H$, пока $G$ будет не равным $1$, что обеспечит выполнение условия $G^{Q}=1\mod P$

Открытый и секретный ключи

1. Секретный ключ представляет собой число $x\in (0,Q)$
2. Открытый ключ вычисляется по формуле $Y=G^{x}\mod p$

Открытыми параметрами являются $(P,Q,G,Y)$. Закрытый параметр — $x$. Ключевая пара $(Y,x)$.

Вычисление ключей

Каждый пользователь создает свой открытый ключ и ему соответствующий секретный ключ. Каждый пользователь должен выполнить следующее:

1. Выбрать простые числа $P$ и $Q$, для которых $Q$ делит $P-1$.
2. Выбрать генератора $G\in \mathrm {Z} _{p}^{*}$ для циклической подгруппы порядка $Q$ в группе.

Для этого пользователь должен выполнить следующее:

1. Выбрать элемент ${\displaystyle H\in \mathrm {Z} _{p}^{*}}$, и найти $G=H^{(p-1)/q}{\pmod {p}}$.
2. Если $G=1$, то перейти к шагу 1 с другим $H$.

Продолжить действия в соответствии с шагами:

1. Выбрать произвольное число $H$, $1\leq G\leq Q-1$
2. Вычислить $Y=G^{Q}{\pmod {p}}$
3. Открытый ключ адресата есть (Р, Q, G, Y). Секретный ключ пользователя есть число H.

Вычисление подписи

Пользуясь своим секретным ключом, пользователь Алиса подписывает бинарное сообщение m. Пользователь Алиса должна выполнить следующее:

1. Вычислить $m=R(m)$.
2. Выбрать случайное секретное целое $k$, $1\leq k\leq Q-1$ и вычислить $r=G-k{\pmod {p}}$
3. Вычислить $e=m\prime r{\pmod {p}}$.
4. Вычислить $s=ae+k{\pmod {Q}}$.
5. Подпись А под $m$ есть пара ($e$, $s$).

Проверка подписи и вычисление сообщения

Пользуясь открытым ключом пользователя Алиса, адресат Боб может проверить подпись (e, s) пользователя Алиса и извлечь из подписи сообщение от Алисы. Пользователь Боб должен выполнить следующее:

1. Получить открытый ключ (Р, Q, G, Y) пользователя Алиса.
2. Проверить, что $e\in [1,P-1]$. Если нет, то отклонить подпись.
3. Проверить, что ${\displaystyle s\in [1,Q-1]}$. Если нет, то отклонить подпись.
4. Вычислить $v=G^{s}*Y^{-e}{\pmod {P}}$ и $m\prime =Ve{\pmod {P}}$.
5. Проверить, что $m\prime \in M_{R}$. Если нет, то отклонить подпись.
6. Вычислить $m=R^{-1}(m\prime )$.

Схема алгоритма

Схема подписи Нюберга — Руэппеля

Пример

Подпись сообщения

1. Выберем параметры схемы: $Q=101,P=607,G=601.$
2. Ключевая пара пусть выглядит как $(391,3)$.
3. Чтобы подписать сообщение $M=12$ , вычисляем временный ключ $k=45$ и $R=G^{k}(modP)=143$.
4. Пусть $f(M)=M+2^{4}\cdot M$, тогда $f(M)=204$ и

$E=f(M)\cdot R(modP)=36$, $S=x\cdot E+k(modQ)=52$.

Итого, пара чисел $(E,S)$, то есть $(36,52)$ — это подпись.

Проверка подписи и восстановление сообщения

1. Вычисляем $U_{1}=G^{S}\cdot Y^{-E}=143$. Следует заметить, что значение $U_{1}$ совпадает со значением $R$.
2. Вычисляем $U_{2}={E \over U_{1}}(modP)=204$.
3. Теперь нужно проверить, что $U_{2}=204$ представляется в виде $M+2^{4}\cdot M$ для некоторого целого числа $M$, и убедившись в этом, делаем заключение в корректности подписи.
4. Восстанавливаем сообщение $M=12$ как решение уравнения $M+2^{4}\cdot M=204$.

Достоинства и недостатки

Схема подписи на тех же принципах, что и DSA, главное отличие заключается в том, что в схеме реализовано восстановление сообщения из подписи. В отличие от RSA, подпись и восстановление не коммутируют, следовательно, алгоритм не может быть использован для шифрования. Преимущества восстановления сообщения заключаются в том, что применение схемы осуществляется без использования хеш-функций, более короткая подпись на коротких сообщениях, возможность прямого применения в схемах на основе идентификационной системы с открытым ключом, где пользователь после регистрации в центре ключей может аутентифицировать себя любому другому пользователю без дальнейшего обращения в центр ключей, или в протоколах согласования ключа, которые устанавливают общий ключ между двумя сторонами на основе взаимной аутентификации.

Модифицированная подпись Нюберга-Руэппеля

Модификация сигнатуры Нюберга-Руэппеля позволяет избежать трудностей проектирования функции избыточности за счет отказа от свойства восстановления сообщений. Её производительность немного хуже, чем у Elgamal, который аналогично не обеспечивает восстановление сообщений, но более эффективен, чем двойные подписи Нюберга-Руэппеля, которые доказуемо безопасны в той же модели. Хотя двойная подпись Нюберга-Руэппеля действительно обеспечивает восстановление сообщений, для этого по-прежнему требуется передача четырёх значений подписи, в то время как для модифицированной версии подписи требуется только три значения (включая сообщение). Поскольку смысл восстановления сообщений заключается в экономии полосы пропускания, эта схема достигает цели с помощью других средств.

Модифицированная подпись Нюберга-Руэппеля заменяет функцию избыточности дискретным возведением в степень. Более явно, пусть $g1$ — другой генератор той же группы порядка $q$, такой, что дискретные логарифмы $g1$ по отношению как к $g$, так и к y неизвестны. Пространство сообщений $M_{S}$ − это целочисленный интервал $I$, то есть равный $[1,q-1]$ в случае известного порядка или $[-2^{n},2^{n}-1]$ в случае неизвестного порядка. Если ($r$, $s$) является подписью в сообщении $m$, модифицированное уравнение проверки выглядит следующим образом:

$g_{1}^{m}=ry^{p(r)}g^{s}$

Процедура подписания работает как и прежде, поскольку сообщение m в I сначала изменяется на $m'=g_{1}^{m}$ как сообщение в $G$, а затем подписывается, как в предыдущем алгоритме.

Безопасность

В своей простой форме подпись Нюберга-Руэппеля уязвима для атак экзистенциальной подделки. А именно, можно произвольно выбрать $r\in [1,p-1]$ и $s\in [1,q-1]$, и эти значения подписывают уникальное сообщение, которое получается путем применения алгоритма восстановления к ($r$, $s$). Хотя это сообщение не может быть выбрано злоумышленником заранее, это все равно означает, что схема подписи небезопасна.

Типичным решением проблемы такого типа является использование функции резервирования. Пусть $R$ — эффективно вычислимая взаимно однозначная функция от {${0,1}$} до $[1,p-1]$, которая является разреженной, то есть набор изображений R соответствует небольшой доле всех значений в диапазоне. При заданном $Z$ в изображении $R$ существует эффективный алгоритм вычисления $R-1(Z)$.

Модифицированная версия схемы подписи при заданном m вычисляет $m\prime =R(m)$, а затем подписывает m' в соответствии с простой схемой Нюберга-Руэппеля. Чтобы восстановить подписанное сообщение, верификатор сначала восстанавливает $m\prime$ в соответствии с механизмом восстановления простой подписи Нюберга-Руэппеля, а затем фактическое сообщение $m$ как $R-1(m\prime )$. Безопасность модифицированной версии зависит от сложности выбора значений $r$ и $s$ таким образом, чтобы выходные данные алгоритма восстановления были в виде $R$. На практике разработка функций резервирования, обеспечивающих надлежащую безопасность, является деликатной задачей.

Кольцевая подпись версии Нюберга-Руэппеля

См. также: Кольцевая подпись

Для подписи сообщения $m$ при наличии секретного ключа $S_{S}$, и открытых ключах всех участников кольца — $P_{1},P_{2},...,P_{r}$, подпись вычисляется следующим образом:

1. Вычислить $h(m)$ как симметричный ключ $k$: $k=h(m)$.
2. Выбрать значение инициализации $v$ равномерно случайным образом из ${(0,1)}^{b}$.
3. Выбирать случайное ($e_{i},y_{i}$) равномерно и независимо от $Z_{p}*Z_{q}(1\leq i\leq r,i\neq s)$ и вычислить: $x_{i}=f_{i}(e_{i},y_{i})$.
4. Решить следующее кольцевое уравнение для $x_{s}$: $C_{k,v}(x_{1},x_{2},...,x_{r})=v.$
5. Использовать секретный ключ $S_{i}$, чтобы инвертировать $f_{s}$ на $x_{s}$ для получения ($e_{s},y_{s}$).
6. Подпись в сообщении m определяется как $(2r+1)$-запись: $(P_{1},P_{2},...,P_{r};v;(e_{1},y_{1}),...,(e_{r},y_{r}))$.
7. Проверить подпись $(P_{1},P_{2},...,P_{r};v;(e_{1},y_{1}),...,(e_{r},y_{r}))$.
8. В сообщении $m$ подпись будет принята верификатором тогда и только тогда, когда $C_{H(m)},v(f_{1}(e_{1},y_{1}),f_{2}(e_{2},y_{2}),...,f_{r}(e_{r},y_{r}))=v$.

См. также

• Электронная цифровая подпись
• Схема Эль-Гамаля
• RSA
• DSA
• ECDSA
• ГОСТ Р 34.10-2001
• Случайное простое число

Литература

• Авдошин С. М. Дискретная математика. Модулярная алгебра, криптография, кодирование. — М.: ДМК Пресс, 2017. — 352 с.
• Бауер Ф. Расшифрованные секреты. Методы и принципы криптологии. — Мир, 2007. — 550 с.
• Смарт, Н. Криптография. — Техносфера, 2005. — 528 с.
• Ateniese, G and Breno de Medeiros. «A Provably Secure Nyberg-Rueppel Signature Variant with Applications.» IACR Cryptol. ePrint Arch. 2004 (2004): 93.
• Elgamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms // Advances in Cryptology : книга. — 1985.
• Gao, Cz., Yao, Za., Li, L. (2003). A Ring Signature Scheme Based on the Nyberg-Rueppel Signature Scheme. In: Zhou, J., Yung, M., Han, Y. (eds) Applied Cryptography and Network Security. ACNS 2003. Lecture Notes in Computer Science, vol 2846. Springer, Berlin, Heidelberg.
• Nyberg, K., Rueppel, R. A. A new signature scheme based on the DSA giving message recovery // 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia (Nov. 3–5, 1993). — 1993.
• Nyberg, K., Rueppel, R. A. Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem // Designs, Codes and Cryptography : журнал. — 1996. — № Volume 7, Issue 1-2. — С. 61—81.