Данный алгоритм также базируется на сложности дискретного логарифмирования и является примером схемы с восстановлением сообщения.
Все схемы подписи с восстановлением сообщения используют не однонаправленную хэш-функцию H, а открытую функцию избыточности F, которая является легко обратимой. В качестве простого примера можно взять F(M) = (M||M)2.
Параметры системы совпадают с параметрами P, Q, G системы Эль-Гамаля.
Закрытый ключ x – целое число из интервала 1 < x < Q – 1. Открытый ключ определяется формулой Y = Gx (mod P).
Алгоритм подписи Ниберга-Руппеля состоит в следующем:
1. Берут случайное число k из промежутка 1 < k < Q – 1 и вычисляют R = Gk mod P.
2. Находят Е = F(M) · R (mod P).
3. Определяют S = x · E + k (mod Q).
Подпись представляет собой пару (E, S). Исходя из этой пары нам нужно:
- убедиться в том, что подпись принадлежит пользователю с открытым ключом Y;
- восстановить сообщение M.
В процедуре проверки подписи Ниберга-Руппеля по паре (E, S) и открытому ключу отправителя Y вычисляют:
U1 = GSY-E (mod P) = R.
U2 = E(U1)-1 (mod P).
После этого убеждаются, что U2 является значением функции избыточности U2 = F(M). Если это равенство ложно, то подпись отклоняют. В противном случае восстанавливают сообщение по правилу M = f -1(U2) и принимают подпись.
Пример. Параметры домена Q = 101, P = 607 и G = 601.
Чтобы зафиксировать ключевую пару, положим x = 3 и
Y = Gx (mod P) = 6013 (mod 607) = 391.
Чтобы подписать сообщение M = 12 (в нашем примере M должно лежать на отрезке [0, 15]), выбираем эфемерный закрытый ключ k = 45 и вычисляем
R = Gk (mod P) = 60145 (mod 607) = 143.
Допустим, F(M) = M + 24 · M. Тогда F(M) = 204 и
E = F(M) · R (mod P) = 204 · 143 (mod 607) = 36,
S = x · E + k (mod Q) = 3 · 36 + 45 (mod 101) = 52.
Подписью является пара (E, S) = (36, 52).
Проверка подписи и восстановление сообщения. Вычисляется
U1 = GSY-E (mod P) = 60152 · (39136)-1 (mod 607) = 195 · 284 (mod 607) = 143 = R.
Далее находим
U2 = E(U1)-1 (mod P) = 36 · (143)-1 (mod 607) = 36 · 208 (mod 607) = 204.
Теперь необходимо убедиться, что найденное число U2 представимо в виде M + 24 · M для некоторого целого числа M Î [0, 15]. U2 действительно так представимо, поэтому подпись корректна. Сообщение M = 12 восстанавливается из уравнения
M + 24 · M = 204.