Принадлежит семейству цифровых подписей на дискретных логарифмах и интересна с точки зрения практического применения в смарт-картах для реализации процедуры аутентификации. Алгоритм также может быть обобщен на эллиптические кривые.
Параметры системы совпадают с параметрами P, Q, G системы Эль-Гамаля.
Закрытый ключ x – целое число из и
нтервала 1 < x < Q – 1. Открытый ключ определяется формулой Y = Gx (mod P). Чтобы подписать сообщение в алгоритме Шнорра поступают следующим образом:
- Выбирают эфемерный ключ k из промежутка 1 < k < Q – 1.
- Вычисляют соответствующий открытый ключ R = Gk mod P.
- Находят E = H(M||R). Значение функции зависит как от сообщения, так и от эфемерного ключа.
- Вычисляют S = k + x · E (mod Q).
Полученная таким образом пара (E, S) является искомой подписью.
Для проверки подписи вычисляют:
R’ = GSY-E (mod P) и H(M||R’).
Подпись корректна, если верно равенство E = H(M||R’).
(Возможен вариант, в котором закрытый ключ вычисляется по формуле Y = G-x (mod P) и тогда проверочное уравнение принимает форму R’ ≡ GSYE (mod P).)
Пример. Параметры домена Q = 101, P = 607 и G = 601.
Чтобы зафиксировать ключевую пару, положим x = 3 и
Y = Gx (mod P) = 6013 (mod 607) = 391.
Затем генерируем эфемерный ключ k = 65 и вычисляем.
R = Gk (mod P) = 60165 (mod 607) = 223.
Теперь находим хэш-значение E = H(M||R). Допустим, что при этом получилось E = 93. Тогда вторая компонента подписи выглядит как
S = k + x · E (mod Q) = 65 + 3 · 93 (mod 101) = 41.
При проверке подписи (E, S) теоретически можно вычислить
R’ YE (mod P) = 223 · 39193 (mod 607) = 172.
GS (mod P) = 60141(mod 607) = 172.
Но так как R’ не передается напрямую, а только в виде свертки E = H(M||R), придется вычислять:
R’ = GSY-E (mod P) = 60141 · (39193)-1 (mod 607) = 172 · (537)-1 (mod 607) = 223.
Соответственно совпадут и хэш-значения H(M||R) = H(M||R’) = 93.