Криптосистема Эль-Гамаля

Автор шифра – Эль-Гамаль (Taher ElGamal). (Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость).

В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.

Пусть имеются абоненты А, В, С, ..., которые хотят передавать друг другу зашифрованные сообщения.

Для всей группы абонентов выбираются некоторое большое про­стое число р и целое число g. Числа р и g передаются абонентам в открытом виде.

Затем каждый j-й абонент выбирает свое секретное число с_j , 1 < с_j < р-1, и вычисляет соответствующее ему открытое число d_j,

d_j = g^Cj mod p.

В результате получаем пары ключей: c_A d_A , c_B d_B , c_C d_C , …

Покажем теперь, как А передает сообщение т абоненту В. Бу­дем предполагать, что сообщение представлено в виде чисел m_i < р .

1. А формирует случайное число k , 1 < k < р-2 , вычисляет числа

r_i = g^k mod p,

е_i = m _i • d_B ^k mod p

и передает пару чисел (r_i, е_i) абоненту В.

2. В,получив (r_i, е_i), вычисляет

т_i = е_i • r_i ^р-1-СB mod p.

Пример. Передадим сообщение т = 15 от А к В. Возьмем р = 23, g= 5. Пусть абонент В выбрал для себя секретное число c_b =13 и вычислил

d_B = 5¹³ mod 23 = 21.

Абонент А выбирает случайно число k, например k = 7, и вы­числяет:

r = 5⁷ mod 23 = 17, е = 15 • 21⁷ mod 23 = 15 • 10 mod 23 = 12.

Теперь А посылает к В зашифрованное сообщение в виде пары чисел (17,12). В вычисляет

т = 12 • 17^23-1-13 mod 23 = 12 • 17⁹ mod 23 = 12 • 7 mod 23 = 15.

Заметим, что объем шифра в два раза пре­вышает объем сообщения.

Есть и другой вариант зашифрования и расшифрования, где вместо умножения используется побитовое сложение по модулю 2 (Е):

e_i = m_i Е d^k,

m_i = (r_i ^{C j} mod p) Е e_i.

Пример.

е = 15Е(21⁷ mod 23) = 15 Е 10 = 5,

т = (17¹³ mod 23) Е 5 = 10 Е 5 = 15.