Цифровая подпись Эль-Гамаля

Этот протокол, опубликованный в 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 = g^x mod p =2⁸ mod 11 = 3.

Предположим, что исходное сообщение M характеризуется хэш-значением m = 5.

Для того чтобы вычислить цифровую подпись для сообщения M, имеющего хэш-значение m = 5, сначала выберем случайное целое число k = 9. Убедимся, что числа k и (p – 1) являются взаимно простыми. Действительно,

НОД (9, 10) = 1.

Далее вычисляем элементы a и b подписи:

a = g^k mod p = 2⁹ 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) y^aa^b (mod p) = 3⁶∙6³ (mod 11) =10 (mod 11);

2) g^m (mod p) = 2⁵ (mod 11) =10 (mod 11).

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

Следует отметить, что схема Эль–Гамаля является характерным примером подхода, который допускает пересылку сообщения M в открытой форме вместе с присоединенным аутентификатором (a,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.