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

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

Все схемы подписи с восстановлением сообщения используют не однонаправленную хэш-функцию H, а открытую функцию избыточности F, которая является легко обратимой. В качестве простого примера можно взять F (M) = (M || M)₂.

Параметры системы совпадают с параметрами P, Q, G системы Эль-Гамаля.

Закрытый ключ x – целое число из интервала 1 < x < Q – 1. Открытый ключ определяется формулой Y = G^x (mod P).

Алгоритм подписи Ниберга-Руппеля состоит в следующем:

1. Берут случайное число k из промежутка 1 < k < Q – 1 и вычисляют R = G^k mod P.

2. Находят Е = F (M) · R (mod P).

3. Определяют S = x · E + k (mod Q).

Подпись представляет собой пару (E, S). Исходя из этой пары нам нужно:

- убедиться в том, что подпись принадлежит пользователю с открытым ключом Y;

- восстановить сообщение M.

В процедуре проверки подписи Ниберга-Руппеля по паре (E, S) и открытому ключу отправителя Y вычисляют:

U ₁ = G^SY^-E (mod P) = R.

U ₂ = E (U ₁)^-1 (mod P).

После этого убеждаются, что U ₂ является значением функции избыточности U ₂ = F (M). Если это равенство ложно, то подпись отклоняют. В противном случае восстанавливают сообщение по правилу M = f ^-1(U ₂) и принимают подпись.

Пример. Параметры домена Q = 101, P = 607 и G = 601.

Чтобы зафиксировать ключевую пару, положим x = 3 и

Y = G^x (mod P) = 601³ (mod 607) = 391.

Чтобы подписать сообщение M = 12 (в нашем примере M должно лежать на отрезке [0, 15]), выбираем эфемерный закрытый ключ k = 45 и вычисляем

R = G^k (mod P) = 601⁴⁵ (mod 607) = 143.

Допустим, F (M) = M + 2⁴ · 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).

Проверка подписи и восстановление сообщения. Вычисляется

U ₁ = G^SY^-E (mod P) = 601⁵² · (391³⁶)^-1 (mod 607) = 195 · 284 (mod 607) = 143 = R.

Далее находим

U ₂ = E (U ₁)^-1 (mod P) = 36 · (143)^-1 (mod 607) = 36 · 208 (mod 607) = 204.

Теперь необходимо убедиться, что найденное число U ₂ представимо в виде M + 2⁴ · M для некоторого целого числа M Î [0, 15]. U ₂ действительно так представимо, поэтому подпись корректна. Сообщение M = 12 восстанавливается из уравнения

M + 2⁴ · M = 204.