Шифрование по алгоритму Эль-Гамаля

Пусть имеются абоненты А, В, С, ..., которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищен­ных каналов связи. Шифр, предло­женный Эль-Гамалем (Tahcr ElGamal), решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку со­общения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего со­общения секретный ключ вычисляется заново. Перейдем к точному описанию метода.

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

Затем каждый абонент группы выбирает свое секретное число c_i, 1 < с_i < р - 1 и вычисляет соответствующее ему открытое число d_i,

d_i=g^cimodp.(3.1)

Результат представлен в таблице 3.3.

Необходимо выбрать числа p и g так, чтобы они отвечали следующим требованиям:

g^q mod p 1, где p=2q+1.

Таблица 3.3- Ключи пользователей в системе Эль-Гамаля

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

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

r = g^k mod p,(3.2) e = m d_B^k mod p(3.3)