Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом,основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России^{[уточнить]} (ГОСТ Р 34.11-94).

Схема была предложена Тахером Эль-Гамалем в 1984 году.^[1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Генерация ключей

1. Генерируется случайное простое число длины битов.
2. Выбирается произвольное целое число , являющееся первообразным корнем по модулю .
3. Выбирается случайное целое число такое, что .
4. Вычисляется .
5. Открытым ключом является тройка , закрытым ключом — число .

Работа в режиме шифрования

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

Шифрование

Сообщение шифруется следующим образом:

1. Выбирается сессионный ключ — случайное целое число такое, что
2. Вычисляются числа и .
3. Пара чисел является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.

Расшифрование

Зная закрытый ключ , исходное сообщение можно вычислить из шифротекста по формуле:

При этом нетрудно проверить, что

и поэтому

.

Схема шифрования

Пример

• Шифрование
  1. Допустим что нужно зашифровать сообщение .
  2. Произведем генерацию ключей :
     1. пусть . Выберем - случайное целое число такое,что .
     2. Вычислим .
     3. Итак , открытым является тройка ,а закрытым ключом является число .
  3. Выбираем случайное целое число такое, что 1 < k < (p − 1). Пусть .
  4. Вычисляем число .
  5. Вычисляем число .
  6. Полученная пара является шифротекстом.
• Расшифрование
  1. Необходимо получить сообщение по известному шифротексту и закрытому ключу .
  2. Вычисляем M по формуле :
  3. Получили исходное сообщение .

Так как в схему Эль-Гамаля вводится случайная величина ,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины для шифровки различных сообщений и . Если использовать одинаковые , то для соответствующих шифротектов и выполняется соотношение . Из этого выражения можно легко вычислить , если известно .

Работа в режиме подписи

Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции , значения которой лежат в интервале .

Подпись сообщений

Для подписи сообщения выполняются следующие операции:

1. Вычисляется дайджест сообщения :
2. Выбирается случайное число взаимно простое с и вычисляется
3. С помощью расширенного алгоритма Евклида вычисляется число , удовлетворяющее сравнению:

4. Подписью сообщения является пара .

Проверка подписи

Зная открытый ключ , подпись сообщения проверяется следующим образом:

1. Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется,то подпись считается неверной.
2. Вычисляется дайджест
3. Подпись считается верной, если выполняется сравнение:

Пример

• Подпись сообщения.
  1. Допустим,что нужно подписать сообщение .
  2. Произведем генерацию ключей:
     1. Пусть переменные, которые известны некоторому сообществу. Секретный ключ — случайное целое число такое, что .
     2. Вычисляем открытый ключ : .
     3. Итак,открытым ключом является тройка .
  3. Теперь вычисляем хэш-функцию: .
  4. Выберем случайное число такое, что выполняется условие . Пусть .
  5. Вычисляем .
  6. С помощью расширенного алгоритма Евклида находим число из уравнения . Такое существует, так как НОД(k,p-1)=1. Получим что .
  7. Итак, мы подписали сообщение: .

• Проверка подлинности полученного сообщения.
  1. Вычисляем хэш-функцию: .
  2. Проверяем сравнение .
  3. Вычислим левую часть по модулю 23: .
  4. Вычислим правую часть по модулю 23: .
  5. Так как правая и левая части равны, то это означает что подпись верна.

Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле . Следует сделать несколько комментариев:

• Случайное число должно сразу после вычисления подписи уничтожаться,так как если злоумышленник знает случайное число и саму подпись, то он легко может найти секретный ключ по формуле: и полностью подделать подпись.

Число должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.

• Использование свертки объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа ,удовлетворяющие условиям , НОД(j,p-1)=1 и предположить что

то легко удостовериться в том,что пара является верной цифровой подписью для сообщения .

• Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: , в котором тройка принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при ,, .На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения , ,, а в Российском стандарте: , , .
• Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел на пару чисел ),где является каким-то простым делителем числа . При этом сравнение для проверки подписи по модулю нужно заменить на новое сравнение по модулю : . Так сделано в американском стандарте DSS (Digital Signature Standard).

Криптостойкость и особенности

В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

Сравнение некоторых алгоритмов:

Примечания