Этот протокол, опубликованный в 1984 году, послужил прототипом стандартов США и России электронной цифровой подписи.
Зафиксируем конечное поле , где p — простое число. Пусть g — первообразный вычет по mod p. Вычет является секретным ключом отправителя А, а вычет является его открытым ключом. Обозначим через сообщение (хэш-значение сообщения), которое хочет подписать А. Протокол подписи и проверки.
1) А выбирает случайное секретное , вычисляет , .
2) Отправитель сообщения А, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа x целое число из уравнения m = x∙a + k b (mod (p —1)) и формирует подписанное сообщение (m,a,b) (пара, (a,b) есть подпись сообщения m).
3) Для проверки подписи получатель Б вычисляет и . Если вычисленные значения совпадают, то подпись принимается, в противном случае отвергается.
Нетрудно проверить, что если подпись правильная, то выполняется сравнение
. (*)
Следует отметить, что выполнение каждой подписи по методу Эль — Гамаля требует нового значения k, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение k, повторно используемое отправителем, то он сможет раскрыть секретный ключ x отправителя.
Пример.Выберем: числа p =11, g = 2 и секретный ключ x = 8. Вычисляем значение открытого ключа:
y = gx mod p =28 mod 11 = 3.
Предположим, что исходное сообщение M характеризуется хэш-значением m = 5.
Для того чтобы вычислить цифровую подпись для сообщения M, имеющего хэш-значение m = 5, сначала выберем случайное целое число k = 9. Убедимся, что числа k и (p — 1) являются взаимно простыми. Действительно,
НОД (9, 10) = 1.
Далее вычисляем элементы a и b подписи:
a = gk mod p = 29 mod 11 = 6,
элемент b определяем, используя расширенный алгоритм Евклида:
m = x∙a + k b (mod (p — 1)).
При m = 5, a = 6, x = 8, k = 9, p = 11 получаем 5 = (6∙8 + 9∙b)(mod 10)
Или 9∙b º — 43 (mod 10). Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3.
Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ y = 3, получатель вычисляет хэш-значение m = 5 для сообщения M, а затем вычисляет два числа:
1) yaab (mod p) = 36∙63 (mod 11) =10 (mod 11);
2) gm (mod p) = 25 (mod 11) =10 (mod 11).
Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.
Следует отметить, что схема Эль—Гамаля является характерным примером подхода, который допускает пересылку сообщения M в открытой форме вместе с присоединенным аутентификатором (a,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.
Источник