Алгоритм Эль-Гамаля (ElGamal T., 1985).

Криптографы постоянно вели поиски эффективных систем открытого шифрования, и ЭльГамаль предложил следующую схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число Р. Сообщения представляются целыми числами S из интервала (1, Р). Оригинальный протокол передачи сообщения S выглядит в варианте Шамира, одного из авторов RSA, так:

1. Отправитель А и получатель В знают лишь Р. А генерирует случайное число Х из интервала (1, Р) и В тоже генерирует случайное число Y из того же интервала.

2. А шифрует сообщение: S₁ = S^X (mod Р) и посылает В.

3. В шифрует его своим ключом: S₂ = S₁^Y (mod Р) и посылает S₂ к А.

4. А "снимает" свой ключ: S₃ = S₂ ^(1/X) (mod Р) и возвращает S₃ к В.

5. Получатель В расшифровывает сообщение: S = S₃ ^(1/Y) (mod Р).

В системе ЭльГамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет почти на порядок увеличить скорость шифрования и расшифрования. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа, то есть произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предположить, что сложности вскрытия систем RSA и ЭльГамаля будут сходными. С точки зрения практической реализации как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет. Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае же системы, построенной с помощью алгоритма ЭльГамаля, угрозе раскрытия подвергнутся все абоненты криптографической сети. Кроме того, упомянутые выше Ленстра и Манасси не только поколебали стойкость RSA, разложив девятое число Ферма на простые множители за короткое время, но и, как было замечено некоторыми экспертами, указали "брешь" в способе ЭльГамаля. Дело в том, что подход, применявшийся при разложении на множители девятого числа Ферма, позволяет существенно усовершенствовать методы дискретного логарифмирования для отдельных специальных простых чисел. То есть тот, кто предлагает простое Р для алгоритма ЭльГамаля, имеет возможность выбрать специальное простое число, для которого задача дискретного логарифмирования будет вполне по силам обычным ЭВМ. Следует заметить, что этот недостаток алгоритма ЭльГамаля не фатален. Достаточно предусмотреть процедуру, гарантирующую случайность выбора простого Р в этой системе, и тогда только что высказанное возражение теряет силу. Стоит отметить, что чисел специального вида, ослабляющих метод ЭльГамаля, очень мало и случайным их выбором можно пренебречь.