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

Схема Эль Гамаля, предложенная в 1985г, может быть использована как для шифрования, так и для цифровых подписей. Безопасность схемы Эль Гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле. Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < Р. Числа Р и G могут быть распространены среди группы пользователей. Затем выбирают случайное целое число X, причем X < Р. Число X является секретным ключом и должно храниться в секрете. Далее вычисляют Y= G^X mod P. Число Y является открытым ключом.

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

Затем вычисляют числа а = G^K mod P и b=Y^X M mod P.

Пара чисел (а, Ь) является шифртекстом. Длина шифртекста вдвое больше длины исходного открытого текста М. Для того чтобы расшифровать шифртекст (а, Ь), вычисляют М = b/a^x mod Р. (*) Поскольку , , то соотношение (*) справедливо.