Алгоритм цифровой подписи Ниберга-Руппеля

Данный алгоритм также базируется на сложности дискретного логарифмирования и является примером схемы с восстановлением сообщения.

Все схемы подписи с восстановлением сообщения используют не однонаправленную хэш-функцию 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.