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

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

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

5.2.7. Алгоритм цифровой подписи dsa

Рассмотрим данный алгоритм более подробно, так как на его основе построен стандарт цифровой подписи DSS. DSA – алгоритм подписи с дополнением, в котором собственно подпись состоит из двух 160-битовых целых чисел R и S. Число R является функцией 160-разрядного случайного числа k, которое называют эфемерным ключом, изменяемым с каждым новым сообщением. Число S – функция от сообщения, секретного ключа x, принадлежащего подписывающему лицу, числа R и эфемерного ключа k. Аналогично алгоритму Эль-Гамаля здесь есть несколько параметров домена. Для из задания сначала фиксируется 160-битовое простое число Q, а затем выбирается такое большое простое число P, лежащее между 2⁵¹² и 2²⁰⁴⁸, что P – 1 делится на Q. Наконец генерируется случайное число H < P и вычисляется

Если G = 1, то переходят к другому случайному H до тех пор, пока не получат G  1.

Этим обеспечивается выполнение следующего условия: G – порождающий элемент группы порядка Q, то есть

G^Q = 1 (mod P).

После выбора параметров домена (P, Q, G) каждый пользователь генерирует свой собственный закрытый подписывающий ключ x, удовлетворяющий неравенству 0 < x < Q. Соответствующим открытым ключом служит число Y, вычисляемое по правилу

Y = G^x (mod P).

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

Подписание сообщения осуществляется по следующему алгоритму:

- вычисляют значение хэш-функции H = H(M),

- выбирают случайный эфемерный ключ k, 0 < k < Q,

- определяют R = (G^k (mod P)) (mod Q),

- находят

Подписью сообщения M служит пара (R, S), имеющая в общей сложности 320 двоичных знаков.

Для проверки подписи (R, S) на сообщении M делают так:

- вычисляют значение хэш-функции H = H(M),

- определяют A = H/S (mod Q) и B = R/S (mod Q),

- находят

V = (G^AY^B (mod P))(mod Q),

где Y – открытый ключ автора сообщения.

- Подпись считается корректной только тогда, когда V = R.

Пример. Параметры домена Q = 13, P = 4Q + 1 = 53 и G = 16.

Предположим, что ключевая пара имеет вид x = 3 и Y = G^x (mod P) = 16³ (mod 53) = 15. Если мы хотим подписать сообщение с хэш-значением H = 5, то сначала нужно выбрать эфемерный ключ k = 2 и найти

R = (G^k (mod P)) (mod Q) = (16² (mod 53))(mod 13) = 44 mod 13 = 5,

S = (H + xR)/k (mod Q) = (5 + 3 · 5) · 2^-1 (mod 13) = (5 + 3 · 5) · 7 (mod 13) = 10.

Для проверки подписи получатель определяет

A = H/S (mod Q) = 5 · 10^-1 (mod 13) = 5 · 4 = 7,

B = R/S (mod Q) = 5 · 10^-1 (mod 13) = 7,

V = (G^AY^B (mod P))(mod Q) = (16⁷ · 15⁷ (mod 53)) (mod 13) = (49 · 42 (mod 53))(mod 13) = 5.

Ввиду равенства V = R = 5 делаем вывод о корректности подписи.