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

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

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

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

Шаг 2. получив (г,е), вычисляет

Утверждение (свойства шифра Эль-Гамаля).

1) Абонент В получал сообщение, т.е. m' = m;

2) противник, зная p, g, d_B, r и e, не может вычислить m

Доказательство.

По теореме Ферма

и. таким образом, мы получаем первую часть утверждения.

Для доказательства второй части заметим, что противник не может вычислить k, так как это задача дискретного логарифмирования. Следовательно, он не может вычислить m так как m было умножено на неизвестное ему число. Противник также не может воспроизвести действия законного получателя сообщения (абонента В), так как ему не известно секретное число c_B (вычисление c_B — также задача дискретного логарифмирования).

Пример

Передадим сообщение m = 15 от А к В. Выберем параметры аналогично тому, как это было сделано в примере.

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

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

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

Мы видим, что В смог расшифровать переданное сообщение.

Ясно, что но аналогичной схеме могут передавать сообщения все абоненты в сети. Заметим, что любой абонент, знающий открытый ключ абонента В, может посылать ему сообщения, зашифрованные с помощью открытого ключа d_B. Но только абонент J5, и никто другой, может расшифровать эти сообщения, используя известный только ему секретный ключ c_B. Отметим также, что объем шифра в два раза превышает объем сообщения, но требуется только одна передача данных (при условии, что таблица с открытыми ключами заранее известна всем абонентам).