2015-04-01
316
Схема Эль-Гамаля, предложенная в 1985 г., может быть использована как для шифрования, так и для цифровых подписей. Безопасность схемы Эль-Гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле.
Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое число 
и большое целое число 
, причем 
. Числа и могут быть распространены среди группы пользователей. Затем выбирают случайное целое число 
, причем 
. Число является секретным ключом и должно храниться в секрете. Далее вычисляют 
. Число Y является открытым ключом.
Для того чтобы зашифровать сообщение 
, выбирают случайное целое число 
такое, что числа 
и 
являются взаимно простыми. Затем вычисляют числа 
, 
. Пара чисел 
является шифротекстом. Заметим, что длина шифротекста вдвое больше длины исходного открытого текста М.
Для того чтобы расшифровать шифротекст , вычисляют 
. Справедливость этого равенства следует из: 
, 
.
