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

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

Выберем 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 + cx mod q

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

r^a = g^by^c mod p

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

Возможные перестановки a, b и c (r'= r mod q)

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