Схема Эль Гамаля, предложенная в 1985 г., может быть использована как для шифрования, так и для цифровых подписей. Безопасность схемы эль гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле.
Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < P. Числа Р и G могут быть распространены среди группы пользователей.
Затем выбирают случайное целое число X, причем X<P. Число X является секретным ключом и должно храниться в секрете.
Далее вычисляют Y = GX mod P. Число Y является открытым ключом.
Для того чтобы зашифровать сообщение M, выбирают случайное целое число k, 1< k< p –1, такое, что числа к и (P –1) являются взаимно простыми.
Затем вычисляют числа
a = GK mod P,
b = YK M mod P.
Пара чисел (a,b) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М.
Для того чтобы расшифровать шифртекст (a,b), вычисляют
M = b/aX mod P. (*)
Поскольку
aX º GKX mod P,
b/aX ºYKM/aX º GKXM/GKX º M (mod P),
то соотношение (*) справедливо.
В реальных схемах шифрования необходимо использовать в качестве модуля P большое целое простое число, имеющее в двоичном представлении длину 512…1024 бит.
При программной реализации схемы Эль Гамаля [123] скорость ее работы (на SPARC-II) в режимах шифрования и расшифрования при 160-битовом показателе степени для различных длин модуля P определяется значениями, приведенными в табл.4.2.
Таблица 4.2
Скорости работы схемы Эль Гамаля
Режим работы | Длина модуля, бит | ||
Шифрование | 0,33 с | 0,80 с | 1,09 с |
Расшифрование | 0,24 с | 0,58 с | 0,77 с |