ЕЦП Ель-Гамаля

Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,- задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

1. Обчислюється хеш-сума M:m = h (M)
2. Обирається випадкове число k, 1<k≤ p-1, взаємно просте з p-1
3. Обчислюється r=g^k mod p
4. За допомогою розширеного алгоритму Евкліда обчислюється число S, що задовольняє вимозі m ≡ xr+ ks mod (p -1)
5 Підписом повідомлення M є пара r,s

Знаючи відкритий ключ (p,g,y), підпис (r,s), повідомлення M, перевіряємо так:
6. Перевіряється виконання умов: 0 < r < 1 та 0 < S < p- 1
7. Обчислюємо хеш-суму (дайжест) m = h(M)
8. Підпис вважається вірним, якщо y^rr^S ≡ g^m mod р

• +: При завданому рівні стійкості алгоритму ЕЦП цілі числа, що беруть участь в обчислюваннях мають запис на 25% коротше, що зменшує складність обчислювань вдвічі.

• Під час обирання модуля Р достатньо перевірити, що це число є простим, і що у числа (Р-1) є великий простий множник (тобто лише дві умови, що легко перевіряються)

• Процедура формування підпису за схемою Ель Гамаля не дозволяє обчислити цифрові підписи під новими повідомленнями без знання таємного ключа (що можливо у RSA)

Недолік: Довжина цифрового підпису більше в півтори рази, що збільшує час на її обчислення

Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ Х отправителя.