Шифр Эль-Гамаля

Схема Эль-Гамаля — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1984 году.Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

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

Перейдем к точному описанию метода. Для всей группы абонентов выбираются некоторое большое простое число р и число g, такие, что различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети). Затем каждый абонент группы выбирает свое секретное число %%c_i%%, %%1 < c_i < p — 1%%, и вычисляет соответствующее ему открытое число %%d_i%%, $$d_i = g^{с_i} mod \,p. ~~~~~(1) $$

В результате получаем таблицу:

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

Абонент	Секретный ключ	Открытый ключ
А	%%c_A%%	%% d_A%%
В	%%c_B%%	%%d_B%%
C	%%c_C%%	%%d_C%%

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

Шаг 1. А формирует случайное число %%k%%, %%1 < k < p — 2%%, вычисляет числа $$r = g^k mod\, p ~~~ (2)$$ $$e = m \cdot d_B^k mod \, p~~~(3)$$ и передает пару чисел %%(r,e)%% абоненту В.

Шаг 2. В, получив %%(r,e)%%, вычисляет %%m' = e \cdot r^{p-1-C_B} mod\,p. (4)%%

Cвойства шифра Эль-Гамаля:

1. Абонент В получил сообщение, т.е. %%m' = m%%;
2. противник, зная %%p%%, %%g%%, %%d_B%%, %%r%% и %%e%%, не может вычислить %%m%%.

Пример. Передадим сообщение %%m = 15%% от А к В. Выберем параметры: %%p = 23%%, %%g = 5%%. Пусть абонент В выбрал для себя секретное число %%c_B = 13%% и вычислил по (1) $$d_B = 5^{13} mod\, 23 = 21.$$

Абонент А выбирает случайно число %%k%%, например %%k = 7%%, и вычисляет по (2), (3): $$r = 5^7 mod \,23 = 17,$$ $$e = 15 \cdot 21^7 mod\, 23 = 15 \cdot 10\, mod \,23 = 12. $$

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

$$m' = 12 \cdot 17^{23-1-13} mod \,23 =\\ 12 \cdot 17^9 mod\, 23 = 12 \cdot 7\, mod \,23 = 15. $$ Мы видим, что В смог расшифровать переданное сообщение.

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

Oтметим также, что объем шифра в два раза превышает объем сообщения, но требуется только одна передача данных (при условии, что таблица с открытыми ключами заранее известна всем абонентам).