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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Использование алгоритма[править | править код]

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

Параметры схемы цифровой подписи[править | править код]

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

  1. Выбрать открытую функцию избыточности , которая преобразует фактическое сообщение в данные, которые затем подписываются. Это похоже на хеш-функцию в схемах подписи с приложением, но в отличие от них, функция избыточности должны быть легко обратима.
  2. Выбрать большое простое число .
  3. Выбрать большое простое число , такое, что делится на .
  4. Сгенерировать случайное число и вычислить . Если , то искать другое случайное , пока будет не равным , что обеспечит выполнение условия

Открытый и секретный ключи[править | править код]

  1. Секретный ключ представляет собой число
  2. Открытый ключ вычисляется по формуле

Открытыми параметрами являются . Закрытый параметр — . Ключевая пара [2][5][6].

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

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

  1. Выбрать случайное число и найти .
  2. Найти .
  3. Определить .

Подписью является пара .

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

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

  1. Вычислить .
  2. Вычислить .

Теперь нужно убедиться в том, что является значением функции избыточности, то есть . Если равенство не выполняется, то подпись ложная и отклоняется. В ином случае восстанавливается сообщение и принимается подпись[2][5][6].

Схема алгоритма[править | править код]

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

Достоинства и недостатки схемы[править | править код]

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

Пример[править | править код]

Подпись сообщения[9]
  1. Выберем параметры схемы:
  2. Ключевая пара пусть выглядит как .
  3. Чтобы подписать сообщение , вычисляем временный ключ и .
  4. Пусть , тогда и

, .

Итого, пара чисел , то есть  — это подпись.

Проверка подписи и восстановление сообщения[9]
  1. Вычисляем . Следует заметить, что значение совпадает со значением .
  2. Вычисляем .
  3. Теперь нужно проверить, что представляется в виде для некоторого целого числа , и убедившись в этом, делаем заключение в корректности подписи.
  4. Восстанавливаем сообщение как решение уравнения .

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

  • Бауер Ф. Расшифрованные секреты. Методы и принципы криптологии. — Мир, 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.