История: Схема была предложена Тахером Эль — Гамалем в 1984 году.
Эль — Гамаль разработал один из вариантов алгоритма Диффи — Хеллмана. Он усовершенствовал систему Диффи — Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличии от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию.
Схема Эль — Гамаля — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль — Гамаля лежит в основе стандартов электронной цифровой подписи в США и России.
Генерация ключей: Процедура генерации ключей здесь точно такая же, как та, которая используется в криптографической системе.
- 1. Генерируется случайное простое число P длины n битов.
- 2. Выбирается произвольное целое число g, являющееся первообразным корнем по модулю P.
- 3. Выбирается случайное целое число x такое, что 1 < x < P.
- 4. Вычисляется y = gx mod p.
- 5. Открытым ключом является тройка (p, g, y), закрытым ключом — x.
Подписание:
- 1. Вычисляется хэш сообщения M: m = h (M).
- 2. Выбирается случайное число 1 < k < p — 1 взаимно простое с p — 1 и вычисляется r = gk 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. Подпись считается верной, если выполняется сравнение: gr rs mod p? gm mod p.
