Доказательство корректности, использование для шифрования и электронной подписи
Имеются две стороны 
и 
и незащищенный канал связи между ними. Стороне требуется передать открытое сообщение 
стороне и подписать его для того, чтобы сторона смогла аутентифицировать сторону .
имеет секретный ключ 
, открытый ключ 
, полученные так же, как и в системе шифрования Эль-Гамаля, и хочет подписать открытое сообщение. Обозначим подпись 
.
Для создания сторона выполняется следующие операции:
- вычисляет значение криптографической хэш - функциии
![h(m)\in[0,p-2]](7_infosafe/33/13.png)
, от своего открытого сообщения ;
- выбирает случайное число
, 
;
- используя открытый ключ, вычисляет
;- создает подпись в виде двух чисел
и посылает сообщение с подписью 
.
Получив сообщение, сторона осуществляет проверку подписи, выполняя операции:
- по известному соообщению вычисляет хэш-функцию
;
- вычисляет
,
- сравнивает значения
и 
, если
,то подптсь подлинная, в противном случае - фальсификация.
Проверка подписи корректна, так как по малой теореме Ферма
;