Схема цифровой подписи Эль-Гамаля основана на сложности вычисления дискретных логарифмов в конечном поле.
Так же как и для шифрования Эль-Гамаля выбираются параметры системы:
P – большое простое число (порядка 1024-2048 бит).
Q – простой делитель числа P – 1 (порядка 160 бит).
G – порождающий элемент мультипликативной группы
Секретным ключом является:
x – целое случайное число в диапазоне 2 ≤ x ≤ P – 2.
Открытый ключ Y вычисляется по формуле:
Y = Gx (mod P).
Подпись для сообщения M вычисляется при помощи следующего алгоритма:
1. Выбрать случайный эфемерный сеансовый ключ k, 2 ≤ k ≤ P – 2, взаимно простой с P – 1, НОД(k, P – 1) = 1.
2. Вычислить R = Gk (mod P).
3. Вычислить S = (M - xR)k -1 (mod P – 1).
4. Подписью сообщения M служит пара (R, S).
Если сообщениe M большое, то при вычислении S используют его хэш-значение H(M).
Алгоритм проверки подписи заключается в проверке сравнения:
.
Основным достоинством данной схемы является возможность выработки цифровых подписей для большого числа сообщений с использованием одного секретного ключа.
Пример. Выберем P = 11 и G = 2, а закрытый ключ x = 8.
Вычислим:
Y = Gx mod P = 28 mod 11 = 3.
Открытым ключом являются Y = 3, G = 2, и P = 11. Чтобы подписать M = 5, сначала выберем случайное k = 9. Убеждаемся, что НОД(9, 10) = 1. Вычисляем:
R = Gk mod P = 29 mod 11 = 6.
Далее с помощью расширенного алгоритма Евклида находим k – 1 = 9 mod (11 – 1) и S:
S = (M - xR)k -1 (mod P – 1) = (5 – 8 · 6) 9 mod (11 – 1) = 3.
Подпись составит пару (6, 3).
Для проверки подписи убедимся, что:
36·63 mod 11 = 25 mod 11.
Схема Эль-Гамаля послужила образцом для построения большого семейства во многом сходных по своим свойствам схем подписи. В их основе лежит проверка сравнения вида:
в котором тройка (A, B, C) совпадает с одной из перестановок чисел ±M, ±S, ±R.
Например, исходная схема Эль-Гамаля получается при
A = M, B = – R и C = S.
Еще одно достоинство данного семейства является возможность уменьшения длины подписи путем замены пары чисел (R, S) на пару чисел (R mod Q, S mod Q). При этом проверочное равенство по модулю P следует заменить на модифицированное равенство по модулю Q:
.
На основе семейства данных схем построены стандарты цифровой подписи DSS и ГОСТ Р34.10-94.
Кроме того, данное семейство может быть модифицировано для работы с группой точек эллиптической кривой.