Дискретных логарифмов

Уравнение подписи Уравнение проверки

(1) r'k=s+mx mod q

(2) r'k=m+sx mod q

(3) sk= r'+mx mod q

/-gy-mod p /-gy mod p /=g^ry^m mod p

(4) sk= m+ r'x mod q /-gY' mod p

(5) mk= s+ r'x mod q i>"=fffmod p

(6) mk= r'+sx mod q /"=//mod p

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

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

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

r ={g^k mod p) mod q

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

щ =а^лЪ mod q

и₂ = а^лс mod q

v = ((g". *y"2) mod p) mod q

(r mod q)^a = g»y^c mod p

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

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

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

r = mg^k mod p

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

г = (mg^k mod p) mod q

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

r = mg^k mod p

s = k - r'x mod q

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

m = gYr mod p

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

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