Схема шифрования Эль Гамаля

История

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

Алгоритм

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

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

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

Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < Р. Числа Р и G могут быть распространены среди группы пользователей.

Затем выбирают случайное целое число X, причем Х< Р. Число Х является секретным ключом и должно храниться в секрете.

Далее вычисляют Y = G^X mod P. Число Y является открытым ключом.

Для того чтобы зашифровать сообщение М, выбирают случайное целое число К, 1< К< Р -1, такое, что числа К и (Р-1) являются взаимно простыми.

Затем вычисляют числа

a=G^KmodP,

b = Y^K М mod P.

Пара чисел (а, Ь) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М.

Для того чтобы расшифровать шифртекст (а, b), вычисляют

М = b/a^Xmod Р. (*)

Поскольку

b/a^Xº Y^KM/a^X º G^KXM/G^KX º M(mod P),

то соотношение (*) справедливо.

Пример. Выберем Р = 11, G = 2, секретный ключ X = 8. Вычисляем

Y = G^XmodP = 2⁸ mod 11 =256 mod 11=3.

Итак, открытый ключ Y = 3.

Пусть сообщение М = 5. Выберем некоторое случайное число К = 9. Убедимся, что НОД (К, Р-1)=1. Действительно, НОД (9, 10)=1. Вычисляем пару чисел а и Ь:

a = G^XmodP = 2⁹ mod 11 =512 mod 11=6.

b = Y^XMmodP = 3⁹ mod 11 =19683 *5 mod 11=9.

Получим шифртекст (а, b) = (6, 9).

Выполним расшифрование этого шифртекста. Вычисляем сообщение М, используя секретный ключ X:

M=b/a^XmodP=9/б⁸mod11.

Выражение М = 9/б⁸mod11 можно представить в виде

6⁸*М º 9 mod 11

или

1679616 * M º 9 mod 11.

Решая данное сравнение, находим М = 5.

В реальных схемах шифрования необходимо использовать в качестве модуля Р большое целое простое число, имеющее в двоичном представлении длину 512... 1024 бит.

При программной реализации схемы Эль Гамаля скорость ее работы (на SPARC-II) в режимах шифрования и рас-шифрования при 160-битовом показателе степени для различных длин модуля Р определяется значениями, приведенными в табл.2.