А выбирает простое число и число – образующая поля по mod p. А выбирает x, 1<x<p-1, которое держит в секрете. Это его секретный ключ.
Затем вычисляет y=gx mod p
Открытым ключом являются: y, g и p.
Закрытым ключом: x.
Допустим, А хочет подписать сообщение m=m1…mn.
Вначале А вычисляет значение хеш-функции y=h(m1…mn), которое должно удовлетворять неравенству 1<h<p.
Затем А выбирает случайное число k (1<k<p-1), взаимно простое с p-1, вычисляет число r=gk mod p.
Далее А вычисляет числа
u=(h-x∙r) mod (p-1),
s=k-1∙u mod (p-1).
Под k-1 подразумевается число, удовлетворяющее уравнению k ∙k-1mod (p-1)=1.
k-1 можно найти по обобщенному алгоритму Евклида.
Подписанное сообщение <m;r,s>.
Получатель сообщения заново вычисляет значение хеш-функции y=h(m1…mn). Затем проверяет подпись, используя равенство
yr∙rs=gh mod p.
Если подпись верна, то равенство yr∙rs=gh mod p верное.