15. Электронная подпись Эль Гамаля

Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной.

Чтобы подписать сообщение М, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычисляется a=(g в степени k) mod p. И с помощью расширенного алгоритма Эвклида находится b в следующем уравнении:

M=(xa+kb)mod(p-1) Подписью является пара чисел a и b. Случайное значение k должно храниться в секрете. Для проверки подписи нужно убедиться, что (y в степени a)*(a в степени b)mod p =(g в стемени M)mod p.

Каждая подпись или шифрование требует нового значения k, и это значение должно быть выбрано случайным образом.

P – простое число (открытый ключ)

G - <p (открытый ключ)

Y = (g в степени x) mod p

Закрытый ключ:

X<p

Подпись

K – выбирается случайным образом, взаимно простое с p-1

A (подпись)= (g в степени k) mod p

B (подпись) такое что M=(xa+kb)maod (p-1)

ПРОверка

Подпись читается правильной, если y в степени a)*(a в степени b)mod p =(g в стемени M)mod p