Схема цифровой подписи ElGamal

История: Схема была предложена Тахером Эль — Гамалем в 1984 году.

Эль — Гамаль разработал один из вариантов алгоритма Диффи — Хеллмана. Он усовершенствовал систему Диффи — Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличии от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию.

Схема Эль — Гамаля — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль — Гамаля лежит в основе стандартов электронной цифровой подписи в США и России.

Генерация ключей: Процедура генерации ключей здесь точно такая же, как та, которая используется в криптографической системе.

• 1. Генерируется случайное простое число P длины n битов.
• 2. Выбирается произвольное целое число g, являющееся первообразным корнем по модулю P.
• 3. Выбирается случайное целое число x такое, что 1 < x < P.
• 4. Вычисляется y = g^x mod p.
• 5. Открытым ключом является тройка (p, g, y), закрытым ключом — x.

Подписание:

• 1. Вычисляется хэш сообщения M: m = h (M).
• 2. Выбирается случайное число 1 < k < p — 1 взаимно простое с p — 1 и вычисляется r = g^k mod p.
• 3. С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению: m? xr + ks (mod p — 1).
• 4. Подписью сообщения M является пара (r, s).

Проверка: Зная открытый ключ (p, g, y), подпись (r, s) сообщения M проверяется следующим образом:

• 1. Проверяется выполнимость условий: 0 < r < p и 0 < s < p — 1. Если хотя бы одно из них не выполняется, то подпись считается неверной.
• 2. Вычисляется хэш m = h (M).
• 3. Подпись считается верной, если выполняется сравнение: g^r r^s mod p? g^m mod p.