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

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

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

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

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

Открытыми параметрами являются ${\displaystyle (P,Q,G,Y)}$. Закрытый параметр — ${\displaystyle x}$. Ключевая пара ${\displaystyle (Y,x)}$[2][5][6].

Подпись сообщения выполняется по следующему алгоритму[2][5][6]:

1. Выбрать случайное число ${\displaystyle k\in \mathbb {Z} /Q\mathbb {Z} }$ и найти ${\displaystyle R=G^{k}(modP)}$.
2. Найти ${\displaystyle E=f(M)\cdot R(modP)}$.
3. Определить ${\displaystyle S=x\cdot E+k(modQ)}$.

Подписью является пара ${\displaystyle (E,S)}$.

Исходя из пары ${\displaystyle (E,S)}$ и целого числа по модулю ${\displaystyle Q}$ необходимо убедиться в том, что подпись принадлежит пользователю с открытым ключом ${\displaystyle Y}$ и восстановить сообщение ${\displaystyle M}$. Проверка подписи выполняется по алгоритму:

1. Вычислить ${\displaystyle U_{1}=G^{S}\cdot Y^{-E}=G^{S-Ex}=G^{k}(modP)}$.
2. Вычислить ${\displaystyle U_{2}={E \over U_{1}}(modP)}$.

Теперь нужно убедиться в том, что ${\displaystyle U_{2}}$ является значением функции избыточности, то есть ${\displaystyle U_{2}=f(M)}$. Если равенство не выполняется, то подпись ложная и отклоняется. В ином случае восстанавливается сообщение ${\displaystyle M=f^{-1}(U_{2})}$ и принимается подпись[2][5][6].

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

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

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

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

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

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

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

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

• Бауер Ф. Расшифрованные секреты. Методы и принципы криптологии. — Мир, 2007. — 550 с.
• Смарт, Н. Криптография. — Техносфера, 2005. — 528 с.
• Elgamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms // Advances in Cryptology : книга. — 1985.
• 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.
• 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.