2015-01-07
1017
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом,основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе стандартовэлектронной цифровой подписи в США и России (ГОСТ Р 34.11-94).
Схема была предложена Тахером Эль-Гамалем в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.
Генерация ключей
1. Генерируется случайное простое число длины битов.
2. Выбирается произвольное целое число, являющееся первообразным корнем по модулю.
3. Выбирается случайное целое число такое, что.
4. Вычисляется.
5. Открытым ключом является тройка, закрытым ключом — число.
Шифрование
Сообщение шифруется следующим образом:
1. Выбирается сессионный ключ — случайное целое число такое, что
2. Вычисляются числа и.
3. Пара чисел является шифротекстом.
Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.
