Для генерации ключевой пары выбираются большое простое число р и примитивный элемент g мультипликативной группы поля GF(p). Выбирается случайное число х такое, что x<p-1. Открытым ключом является y = g^x ( mod p), секретным ключем является x.

Подпись сообщения M

Для того, чтобы подписать сообщение M пользователю A необходимо выполнить следующие действия:

1. выбрать случайно и равновероятно число k из группы обратимых элементов кольца Z _p-1 ^*. То есть НОД(k,p-1) = 1,
2. вычислить a = g^k (mod q),
3. вычислить b = (M-xa)k^-1 (mod p-1),
4. подписью для сообщения M является пара (a,b).

Проверка подписи для сообщения M

Для проверки подписи (a,b) для сообщения M получатель B проверяет выполнение равенства
g^M = y^a a^b (mod p).

Надо заметить, что для ускорения процесса подписи вычисления на шагах 1,2 можно проводить заранее, вычислять значения k^-1 тоже. Как и в других похожих схемах подписи значение k должно оставаться в секрете и выбираться cлучайно.