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

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

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

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

r = (g^k mod p) mod q

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

u₁ = a^-1b mod q

u₂ = a^-1c mod q

v = (( ) mod p) mod q

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

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

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

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

r = mg^k mod p

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

r = (mg^k mod p) mod q

Безопасность всех вариантов одинакова, поэтому имеет смысл выбирать схему по сложности вычисления. Большинство схем замедляет необходимость вычислять обратные значения.