Схемы цифровой подписи с использованием дискретных логарифмов

Схемы подписи ElGamal, Schnorr (см. раздел 21.3) и DSA очень похожи. По сути, все они являются тремя примерами общей схемы цифровой подписи, использующей проблему дискретных логарифмов. Вместе с тысячами других схем подписей они являются частью одного и того же семейства [740, 741, 699, 1184].

Выберем p, большое простое число, и q, равное либо p-1, либо большому простому множителю p-1. Затем выберем g, число между 1 и p, для которого g^qº 1 (mod p). Все эти числа открыты, и могут быть совместно использованы группой пользователей. Закрытым ключом является x, меньшее q. Открытым ключом служит y= g^x mod q.

Чтобы подписать сообщение m, сначала выберем случайное значение k, меньшее q и взаимно простое с ним. Если qтоже простое число, то будет работать любое k, меньшее q. Сначала вычислим

r= g^k mod p

Обобщенное уравнение подписи примет вид

ak= b+ cxmod q

Коэффициенты a, b и c могут принимать различные значения. Каждая строка Табл. 20-4 предоставляет шесть возможностей. Проверяя подпись, получатель должен убедиться, что

r^a= g^by^c mod p

Это уравнение называется уравнением проверки.

Табл. 20-4.
Возможные перестановки a, b и c (r'= r mod q)

± r'	± s	m
± r' m	± s
± r' m	± ms
± m r'	± r' s
± ms	± r' s

В Табл. 20-5 перечислены возможные варианты подписи и проверки, полученные только из первой строки возможных значений a, b и c без учета эффектов ±.

Табл. 20-5.
Схемы цифровой подписи с использованием дискретных логарифмов

Уравнение подписи	Уравнение проверки
(1) r'k=s+mx modq	rr'=gsym mod p
(2) r'k=m+sx modq	rr'=gmys mod p
(3) sk= r'+mx modq	rs=gr'ym mod p
(4) sk= m+ r'x modq	rs=gmyr' mod p
(5) mk= s+ r'x modq	rm=gsyr' mod p
(6) mk= r'+sx modq	rm=gr'ys mod p

Это шесть различных схем цифровых подписей. Добавление минуса увеличивает их количество до 24. При использовании всех возможных значения a, b и c число схем доходит 120.

EIGamal [518, 519] и DSA [1154] по существу основаны на уравнении (4). Другие схемы - на уравнении (2) [24, 1629]. Schnorr [1396, 1397], как и другая схема [1183], тесно связан с уравнением (5). А уравнение (1) можно изменить так, чтобы получить схему, предложенную в [1630]. Оставшиеся уравнения - новые.

Далее. Любую из этих схем можно сделать более DSA-подобной, определив r как

r= (g^k mod p)mod q

Используйте то же уравнение подписи и сделайте уравнением проверки

u₁ = a^-1bmod q

u₂ = a^-1cmod q

v= (() mod p) mod q

(r mod q )^a = g^by^cmod p

Существуют и две другие возможности подобных преобразований [740, 741]. Такие операции можно проделать с каждой из 120 схем, доведя общее число схем цифровой подписи, использующих дискретные логарифмы, до 480.

Но и это еще не все. Дополнительные обобщения и изменения приводят более, чем к 13000 вариантам (не все из них достаточно эффективны) [740, 741].

Одной из приятных сторон использования RSA для цифровой подписи является свойство, называемое восстановлением сообщения. Когда вы проверяете подпись RSA, вы вычисляете m. Затем вычисленное mсравнивается с сообщением и проверяется, правильна ли подпись сообщения. В предыдущих схемах восстановить m при вычислении подписи невозможно, вам потребуется вероятное m, которое и используется в уравнении проверки. Но, оказывается, можно построить вариант с восстановлением сообщения для всех вышеприведенных схем. Для подписи сначала вычислим

r= mg^k mod p

и заменим mединицейв уравнении подписи. Затем можно восстановит уравнение проверки так, чтобы mмогло быть вычислено непосредственно. То же самое можно предпринять для DSA-подобных схем:

r= (mg^k mod p) mod q

Безопасность всех вариантов одинакова, поэтому имеет смысл выбирать схему по сложности вычисления. Большинство схем замедляет необходимость вычислять обратные значения. Как оказывается, одна из этих схем позволяет вычислять и уравнение подписи, и уравнение проверки без использования обратных значений, при этом еще и восстанавливая сообщение. Она называется схемой p-NEW [1184].

r= mg^-k mod p

s= k- r 'x mod q

mвосстанавливается (и проверяется подпись) с помощью вычисления

m= g^sy^r'rmod p

В ряде вариантов одновременно подписывается по два-три блока сообщения [740], другие варианты можно использовать для слепых подписей [741].

Это значительная область для изучения. Все различные схемы цифровой подписи с использованием дискретных логарифмов были объединены логическим каркасом. Лично я считаю, что это окончательно положит конец спорам между Schnorr [1398] и DSA [897]: DSA не является ни производной Schnorr, равно как и EIGamal. Все три алгоритма являются частными случаями описанной общей схемы, и эта общая схема незапатентована.