logo
Материалы для PDF / Информационная безопасность

Алгоритм Эль Гамаля

Другим известным методом является предложенный в 1985 г. Тахером Эль Гамалем (Taher El Gamal) алгоритм Эль Гамаля, положенный в основу стандарта NIST (National Institute of Standards and Technology)2 - MD 20899.

Алгоритм основан на возведении в степень по модулю большого простого числа. Для этого задается большое простое число P. Сообщения представляются целыми числами S из интервала (1, P). Оригинальный протокол передачи сообщения S выглядит в варианте А.Шамира так 2.2:

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

  2. А шифрует сообщение S1 = SX mod P и посылает В.

  3. В шифрует его своим ключом S2 = S1Y mod P и посылает S2 к А.

  4. А “снимает” свой ключ S3 = S2-X mod P и возвращает S3 к В.

  5. Получатель В расшифровывает сообщение

S = S3-Y mod P.

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

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

Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае системы, построенной с помощью алгоритма Эль Гамаля, угрозе раскрытия подвергнутся все абоненты криптографической сети.