Подпись Нюберга — Руэппеля
Подпись Нюберга — Руэппеля (англ. Nyberg-Rueppel Signature Scheme) — схема электронной подписи с использованием открытого ключа, основанная на задаче дискретного логарифмирования в конечном поле. Алгоритм не может использоваться для шифрования (в отличие от RSA и схемы Эль-Гамаля). Подпись создается секретно, но может быть публично проверена. Это значит, что только один субъект может создать подпись сообщения, но любой может проверить её корректность. Схема была предложена Кайсой Нюберг и Райнером Руэппелем в 1993 году на первой конференции ACM (англ. 1st ACM conference on Computer and communications security)[1] как модификация DSA[2][3].
Использование алгоритма
Схема подписи с восстановлением сообщения подразумевает собой процедуру, когда сообщение восстанавливается после проверки подписи. Иными словами, пусть имеются два пользователя, Алиса и Боб, и незащищенный канал связи между ними. Пользователь Алиса подписывает открытое сообщение секретным ключом, а полученную подпись пересылает пользователю Бобу, который в свою очередь с помощью открытого ключа проверяет подлинность подписи и восстанавливает сообщение. При положительном результате проверки, Боб убеждается в целостности сообщения, в его оригинальности (то есть в том, что сообщение было послано именно пользователем Алисой), а также лишается возможности утверждать, что Алиса не посылала это сообщение. Важно, что только Алиса способна подписать своё сообщение, потому что только она знает свой секретный ключ, и то, что её подпись может быть проверена любым пользователем, так как для этого нужен лишь открытый ключ[4].
Параметры схемы цифровой подписи
Для построения системы цифровой подписи и генерации ключей необходимо[2][5][6]:
- Выбрать открытую функцию избыточности , которая преобразует фактическое сообщение в данные, которые затем подписываются. Это похоже на хеш-функцию в схемах подписи с приложением, но в отличие от них, функция избыточности должны быть легко обратима.
- Выбрать большое простое число .
- Выбрать большое простое число , такое, что делится на .
- Сгенерировать случайное число и вычислить . Если , то искать другое случайное , пока будет не равным , что обеспечит выполнение условия
Открытый и секретный ключи
- Секретный ключ представляет собой число
- Открытый ключ вычисляется по формуле
Открытыми параметрами являются . Закрытый параметр — . Ключевая пара [2][5][6].
Подпись сообщения
Подпись сообщения выполняется по следующему алгоритму[2][5][6]:
- Выбрать случайное число и найти .
- Найти .
- Определить .
Подписью является пара .
Проверка подписи и восстановление сообщения
Исходя из пары и целого числа по модулю необходимо убедиться в том, что подпись принадлежит пользователю с открытым ключом и восстановить сообщение . Проверка подписи выполняется по алгоритму:
- Вычислить .
- Вычислить .
Теперь нужно убедиться в том, что является значением функции избыточности, то есть . Если равенство не выполняется, то подпись ложная и отклоняется. В ином случае восстанавливается сообщение и принимается подпись[2][5][6].
Схема алгоритма
Достоинства и недостатки схемы
Схема подписи на тех же принципах, что и DSA, главное отличие заключается в том, что в схеме реализовано восстановление сообщения из подписи. В отличие от RSA, подпись и восстановление не коммутируют, следовательно, алгоритм не может быть использован для шифрования. Преимущества восстановления сообщения заключаются в том, что применение схемы осуществляется без использования хеш-функций, более короткая подпись на коротких сообщениях, возможность прямого применения в схемах на основе идентификационной системы с открытым ключом, где пользователь после регистрации в центре ключей может аутентифицировать себя любому другому пользователю без дальнейшего обращения в центр ключей, или в протоколах согласования ключа, которые устанавливают общий ключ между двумя сторонами на основе взаимной аутентификации[2][7][8].
Пример
- Подпись сообщения[9]
- Выберем параметры схемы:
- Ключевая пара пусть выглядит как .
- Чтобы подписать сообщение , вычисляем временный ключ и .
- Пусть , тогда и
, .
Итого, пара чисел , то есть — это подпись.
- Проверка подписи и восстановление сообщения[9]
- Вычисляем . Следует заметить, что значение совпадает со значением .
- Вычисляем .
- Теперь нужно проверить, что представляется в виде для некоторого целого числа , и убедившись в этом, делаем заключение в корректности подписи.
- Восстанавливаем сообщение как решение уравнения .
См. также
Примечания
- ACM Conference on Computer and Communications Security (CCS)
- Nyberg, K., Rueppel, R. A., 1993.
- Elgamal, 1985.
- Смарт, 2005, p. 261.
- Nyberg, K., Rueppel, R. A., 1996.
- Смарт, 2005, с. 278.
- Смарт, 2005, с. 271.
- Бауер, 2007, с. 228.
- Смарт, 2005, с. 279.
Литература
- Бауер Ф. Расшифрованные секреты. Методы и принципы криптологии. — Мир, 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.