ГОСТ 3410.94.

Пусть р – простое число размера 509512 бит, q простое число такое, что q|(p-1). Число g<p-1 имеет мультипликативный порядок q, то есть 
g= 1(modp). p, q, g открыты. Число х, х <q, –секретный ключ, открытым ключом является у= g(modp). Алгоритм подписи [ГОСТ 94] сообщения М выглядит следующим образом.
1.	Выбирается случайное число k. 
2.	Вычисляется 
r = [g(modp)](modq).
3. Вычисляется
s = 
Подписью сообщения М является пара (r,s).
Проверка подписи осуществляется следующим образом. Вычисляются 
v = М(modq),
z = (sv)(modq),
z = ((q-r)v)(modq),
u = [(g y)(modp)](modq).
Если выполняется равенство u = r, то подпись подтверждена.
Д о к а з а т е л ь с т в о. 
u = [(g y)(modp)](modq) = 
=  [(g)(modp)](modq) =
=  [(g)(modp)](modq) =
=  [g(modp)](modq)= r.