Криптосистема Эль-Гамаля
Система Эль-Гамаля – это криптосистема с открытым ключом, основанная на проблеме логарифма. Система включает как алгоритм шифрования, так и алгоритм цифровой подписи.
Множество параметров системы включает простое число p
и целое число g, степени которого по модулю p порождают большое число элементов Zp. У пользователя A есть секретный ключ a и открытый ключ y, где y = ga (mod
p). Предположим, что пользователь B желает послать сообщение m
пользователю A. Сначала B выбирает случайное число k, меньшее p. Затем он вычисляет
y1 = gk (mod p) и y2 = m Е (yk (mod p)),
где Е обозначает побитовое "исключающее ИЛИ". B посылает A пару (y1, y2).
После получения шифрованного текста пользователь A
вычисляет
m = (y1a mod
p) Е y2.
Известен вариант этой схемы, когда операция Е заменяется на умножение по модулю p. Это удобнее в том смысле, что в первом случае текст (или значение хэш-функции) необходимо разбивать на блоки той же длины, что и число yk (mod
p). Во втором случае этого не требуется и можно обрабатывать блоки текста заранее заданной фиксированной длины (меньшей, чем длина числа p).
