Схема Эль-Гамаля

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

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

Генерация ключей

1. Генерируется случайное простое число $~p$ длины $~n$ битов.
2. Выбирается произвольное целое число $~g$, являющееся первообразным корнем по модулю $~p$.
3. Выбирается случайное целое число $~x$ такое, что $~1 < x < p$.
4. Вычисляется $~y = g^x\,\bmod\,p$.
5. Открытым ключом является тройка $\left( p,g,y \right)$, закрытым ключом — число $~x$.

Работа в режиме шифрования

Шифрсистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Шифрование

Сообщение $~M$ шифруется следующим образом:

1. Выбирается сессионный ключ — случайное целое число $~k$ такое, что $~1 < k < p - 1$
2. Вычисляются числа $a = g^k\,\bmod\,p$ и $b = y^k M\,\bmod\,p$.
3. Пара чисел $\left( a, b \right)$ является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения $M$ вдвое.

Расшифрование

Зная закрытый ключ $~x$, исходное сообщение можно вычислить из шифротекста $\left( a, b \right)$ по формуле:

$M = b(a^x)^{-1}\,\bmod\,p.$

При этом нетрудно проверить, что

$~(a^x)^{-1}\equiv g^{-kx}\pmod{p}$

и поэтому

$~b(a^x)^{-1}\equiv (y^kM)g^{-xk}\equiv (g^{xk}M) g^{-xk}\equiv M \pmod{p}$.

Для практических вычислений больше подходит следующая формула:

$M = b(a^x)^{-1}\,\bmod\,p = b \cdot a^{(p-1-x)}\,\bmod\,p$

Схема шифрования

Пример

• Шифрование
  1. Допустим что нужно зашифровать сообщение $~M=5$.
  2. Произведем генерацию ключей :
     1. пусть $~p=11, g=2$. Выберем $~x=8$ - случайное целое число $~x$ такое,что $~1 < x < p$.
     2. Вычислим $~y= g^x\bmod{p}=2^8\bmod{11}=3$.
     3. Итак , открытым является тройка $~(p,g,y)=(11,2,3)$,а закрытым ключом является число $~x=8$.
  3. Выбираем случайное целое число $~k$ такое, что 1 < k < (p − 1). Пусть $~k=9$.
  4. Вычисляем число $~a=g^k\bmod{p}=2^9 \bmod{11}=512 \bmod{11}=6$.
  5. Вычисляем число $~b=y^k M\bmod{p}=3^9 5 \bmod{11}=19683 \cdot 5 \bmod{11}=9$.
  6. Полученная пара $~(a,b)=(6,9)$ является шифротекстом.
• Расшифрование
  1. Необходимо получить сообщение $~M=5$ по известному шифротексту $~(a,b)=(6,9)$ и закрытому ключу $~x=8$.
  2. Вычисляем M по формуле : $~M=b(a^x)^{-1}\bmod{p}=9(6^8)^{-1}\mod{11}=5$
  3. Получили исходное сообщение $~M=5$.

---

Так как в схему Эль-Гамаля вводится случайная величина $~k$,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа $~k$ такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение $~M$ и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины $~k$ для шифровки различных сообщений $~M$ и $~M^'$. Если использовать одинаковые $~k$, то для соответствующих шифротектов $~(a,b)$ и $~(a^',b^')$ выполняется соотношение $~b(b^')^{-1}=M(M^')^{-1}$. Из этого выражения можно легко вычислить $~M^'$, если известно $~M$.

Работа в режиме подписи

Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции $~h(\cdot)$, значения которой лежат в интервале $\left( 1, p - 1 \right)$.

Подпись сообщений

Для подписи сообщения $~M$ выполняются следующие операции:

1. Вычисляется дайджест сообщения $~M$: $~m = h(M).$
2. Выбирается случайное число $~1< k < p-1$ взаимно простое с $~p - 1$ и вычисляется $~r = g^k\,\bmod\,p.$
3. С помощью расширенного алгоритма Евклида вычисляется число $~s$, удовлетворяющее сравнению:

   $~m \equiv xr + ks\pmod{p-1}.$

4. Подписью сообщения $~M$ является пара $\left( r,s \right)$.

Проверка подписи

Зная открытый ключ $\left( p,g,y \right)$, подпись $\left( r,s \right)$ сообщения $~M$ проверяется следующим образом:

1. Проверяется выполнимость условий: $~0<r<p$ и $~0<s<p-1$. Если хотя бы одно из них не выполняется,то подпись считается неверной.
2. Вычисляется дайджест $~m = h(M).$
3. Подпись считается верной, если выполняется сравнение:

   $~y^r r^s \equiv g^m \pmod{p}.$

Пример

• Подпись сообщения.
  1. Допустим,что нужно подписать сообщение $~M=baaqab$.
  2. Произведем генерацию ключей:
     1. Пусть $~p=23$ $~g=5$ переменные, которые известны некоторому сообществу. Секретный ключ $~x=7$ — случайное целое число $~x$ такое, что $~1 < x < p$.
     2. Вычисляем открытый ключ $~y$: $~y=g^x\bmod p=5^7 \bmod 23=17$.
     3. Итак,открытым ключом является тройка $~(p,g,y)=(23,5,17)$.
  3. Теперь вычисляем хэш-функцию: $~h(M)=h(baaqab)=m=3$.
  4. Выберем случайное число $~k$ такое, что выполняется условие $1 < k < p-1$. Пусть $~k=5$.
  5. Вычисляем $~r=g^k modp=5^5 \bmod 23=20$.
  6. С помощью расширенного алгоритма Евклида находим число $~s$ из уравнения $~3=(7 \cdot 20+5 \cdot s) \bmod 22$. Такое $~s$ существует, так как НОД(k,p-1)=1. Получим что $~s=21$.
  7. Итак, мы подписали сообщение: $~<baaqab,20,21>$.

• Проверка подлинности полученного сообщения.
  1. Вычисляем хэш-функцию: $~h(M)=h(baaqab)=m=3$.
  2. Проверяем сравнение $~y^r \cdot r^s\equiv g^m \pmod{p}$.
  3. Вычислим левую часть по модулю 23: $~17^{20} \cdot 20^{21} \bmod 23=16 \cdot 15 \bmod 23=10$.
  4. Вычислим правую часть по модулю 23: $~5^3\bmod 23=10$.
  5. Так как правая и левая части равны, то это означает что подпись верна.

---

Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле $\mathbb{Z}_p$. Следует сделать несколько комментариев:

• Случайное число $~k$ должно сразу после вычисления подписи уничтожаться,так как если злоумышленник знает случайное число $~k$ и саму подпись, то он легко может найти секретный ключ по формуле: $~x=(m-ks)r^{-1} \bmod (p-1)$ и полностью подделать подпись.

Число $~k$ должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.

• Использование свертки $~m=h(M)$ объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа $~i,j$,удовлетворяющие условиям $~0<i<{p-1} , 0<j<{p-1}$, НОД(j,p-1)=1 и предположить что

  $~r=g^i \cdot y^j \bmod p$

  $~s=r \cdot j^{-1} \bmod (p-1)$

  $~m=r \cdot i \cdot j^{-1} \bmod (p-1)$

то легко удостовериться в том,что пара $~(r,s)$ является верной цифровой подписью для сообщения $~x=M$.

• Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: $~y^A \cdot r^B=g^C(modp)$, в котором тройка $~(A,B,C)$ принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при $~A=r$,$~B=s$, $~C=m$.На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения $~A=r$, $~B=-s$,$~C=m$, а в Российском стандарте: $~A=-x$, $~B=-m$, $~C=s$.
• Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел $~(s,m)$ на пару чисел $~(s \bmod q,m \bmod q$),где $~q$ является каким-то простым делителем числа $~(p-1)$. При этом сравнение для проверки подписи по модулю $~p$ нужно заменить на новое сравнение по модулю $~q$: $~(y^A \cdot r^B \bmod p) = g^C \pmod{q}$. Так сделано в американском стандарте DSS (Digital Signature Standard).

Криптостойкость и особенности

В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

$~y \equiv g^x\pmod{p}.$

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

Сравнение некоторых алгоритмов:

Алгоритм	Ключ	Назначение	Криптостойкость, MIPS	Примечания
RSA	До 4096 бит	Шифрование и подпись	2,7•1028 для ключа 1300 бит	Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты
ElGamal	До 4096 бит	Шифрование и подпись	При одинаковой длине ключа криптостойкость равная RSA, т.е. 2,7•1028 для ключа 1300 бит	Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS
DSA	До 1024 бит	Только подписание		Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.
ECDSA	До 4096 бит	Шифрование и подпись	Криптостойкость и скорость работы выше, чем у RSA	Современное направление. Разрабатывается многими ведущими математиками

Ссылки

• Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В Основы криптографии.
• Б. А. Фороузан Схема цифровой подписи Эль-Гамаля // Управление ключами шифрования и безопасность сети / Пер. А. Н. Берлин. — Курс лекций.
• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone 11.5.2 The ElGamal signature scheme // Handbook of applied cryptography.