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

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

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

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

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

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

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

a = G^K mod P,

b = Y^K M mod P.

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

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

M = mod P. (*)

Поскольку

a^X º G^KX mod P,

ºY^K º G^KX º M (mod P),

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

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

Y = G^X mod P = 2⁸ mod 11 = 256 mod 11 = 3.

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

a = G^K mod P = 2⁹ mod 11 = 512 mod 11 = 6,

b =Y^K M mod P = 3⁹∙5 mod 11 = 19683∙5 mod 11 = 9.

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

M = b/a^X mod P = 9/6⁸ mod 11.

Выражение M = 9/6⁸ mod 11 можно представить в виде 6⁸ M 9 mod 11 или 1679616 * M 9 mod 11. Решая данное сравнение, находим М = 5.