 |
|
Цифровая подпись Эль-Гамаля.
Данная система электронно-цифровой подписи реализует схему с дополнением, поэтому существуют отличия от шифрования Эль-Гамаля, основное из которых – дополнительные требования, предъявляемые к эфемерному сеансовому ключу k. Как и при шифровании Эль-Гамаля, система позволяет использовать общие для всех абонентов параметры, аналогичные протоколу Диффи-Хеллмана – простое число P и примитивный элемент G.
Каждый абонент системы генерирует секретный ключ
Открытый ключ Y вычисляют как: 
Абонент, желающий подписать сообщение M, выбирает сеансовый ключ 
, последнее требование необходимо к выполнению для успешной проверки подписи.
Особенностью подписания является то, что сообщение при подписании удваивается по длине и представляет собой пару: 
- первая часть подписи, не зависящая от подписываемого сообщения. R служит для неявной передачи эфемерного ключа и, ввиду независимости от подписываемого сообщения, может быть выработано заранее в фоновом режиме.
- вторая часть подписи, связанная с сообщением M. Самой затратной операцией при формировании второй части является вычисление мультипликативного обратного при помощи обобщенного алгоритма Евклида, но оно может выполняться заранее вместе с генерацией k. Непосредственно же подписание сводится к выполнению двух операций сложения и одной вычитания.
Для проверки подписи, проверяют сравнение:
если оно выполняется, подпись считается правильной. Для проверки приходится выполнять три вычислительно затратных операции модульного экспоненцирования, что является несомненным недостатком схемы. Данный недостаток несколько компенсируется тем, что сервер обладает как правило большей вычислительной мощностью по сравнению с клиентом.
Ниже приведено краткое доказательство работоспособности, в котором для удобства опущены операции приведения по модулю:
Ввиду своих недостатков данная схема в чистом виде на практике применяется редко, но она послужила родоначальником целого семейства схем электронно-цифровой подписи на ее основе.
Задача 4.2. Для заданного простого числа P и открытого текста M, определить самостоятельно минимальный порождающий элемент G и остальные параметры схемы электронно-цифровой подписи Эль-Гамаля и осуществить подписание сообщения. Проверить правильность цифровой подписи.
Пример решения.
| Дано: P = 131 M = 92 | Решение:
|
| Найти: Gmin, x, Y, k, R, S Проверить подпись | |
Проверка: 
|