Электронная подпись на базе шифра Эль-Гамаля

А выбирает простое число и число – образующая поля по mod p. А выбирает x, 1<x<p-1, которое держит в секрете. Это его секретный ключ.

Затем вычисляет y=g^x mod p

Открытым ключом являются: y, g и p.

Закрытым ключом: x.

Допустим, А хочет подписать сообщение m=m₁…m_n.

Вначале А вычисляет значение хеш-функции y=h(m₁…m_n), которое должно удовлетворять неравенству 1<h<p.

Затем А выбирает случайное число k (1<k<p-1), взаимно простое с p-1, вычисляет число r=g^k 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(m₁…m_n). Затем проверяет подпись, используя равенство

y^r∙r^s=g^h mod p.

Если подпись верна, то равенство y^r∙r^s=g^h mod p верное.