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

Схема Эль-Гамаля — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (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)$$

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

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

Покажем теперь, как А передает сообщение $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тметим также, что объем шифра в два раза превышает объем сообщения, но требуется только одна передача данных (при условии, что таблица с открытыми ключами заранее известна всем абонентам).