DSA.

В основе DSA(DSS) (Digital Signature Algorithm (Digital Signature Standard )) [DSS 94] лежит подпись El Gamal. Пусть p – простое число, q – простое число, такое, что q|(p-1) и g имеет мультипликативный порядок q, то есть g= 1(modp). 
Лемма.  Мультипликативные вычисления степеней g по модулю p эквивалентны арифметическим вычислениям в показателе g по модулю q.
Д о к а з а т е л ь с т в о.  
gg (modp) = g (modp)= g (modp)=
= gg (modp) =  g (modp).
Аналогично
(g)(modp)= g (modp),
что и требовалось доказать.
В  DSS выбирают р~ 512 бит,  q~ 160 бит. Пусть х  случайное число, 
x< p-1. Тогда х – секретный ключ, а
у = g(modp) – 
открытый ключ. Алгоритм подписи сообщения М выглядит следующим образом.
1.	Выбирается случайное число k<q. Так как НОД(k,q) = 1, то 
 
2.	Вычисляется 
r = [g(modp)](modq).
3.	Вычисляется
s = 
Подписью сообщения М является пара (r,s).
Проверка подписи осуществляется следующим образом. Вычисляется 
w = 
Это можно сделать, так как q простое число.
u = (Mw)(modq),
u = (rw)(modq),
v = [(g y)(modp)](modq).
Если выполняется равенство v = r, то подпись подтверждена.
Д о к а з а т е л ь с т в о. 
v = [(g y)(modp)](modq).
Тогда по лемме
v = [(g g)(modp)](modq) =
= [(g)(modp)](modq) =
=  [g(modp)](modq)= r.