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

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

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

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

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

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

Шифрование

Сообщение ${\displaystyle M}$ должно быть меньше числа ${\displaystyle p}$ . Сообщение шифруется следующим образом:

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

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

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

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

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

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

${\displaystyle (a^{x})^{-1}=g^{-kx}{\bmod {p}}}$

и поэтому

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

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

${\displaystyle M=b(a^{x})^{-1}=ba^{(p-1-x)}{\pmod {p}}}$

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

Пример

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

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

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

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

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

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

1. Вычисляется дайджест сообщения ${\displaystyle M}$ : ${\displaystyle m=h(M).}$ (Хеш функция может быть любая).
2. Выбирается случайное число ${\displaystyle 1<k<p-1}$ взаимно простое с ${\displaystyle p-1}$ и вычисляется ${\displaystyle r=g^{k}\,{\bmod {\,}}p.}$
3. Вычисляется число ${\displaystyle s\,=\,(m-xr)k^{-1}{\pmod {p-1}}}$ , где ${\displaystyle k^{-1}}$ это мультипликативное обратное ${\displaystyle k}$ по модулю ${\displaystyle p-1}$ , которое можно найти, например, с помощью расширенного алгоритма Евклида .
4. Подписью сообщения ${\displaystyle M}$ является пара ${\displaystyle \left(r,s\right)}$ .

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

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

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

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

Корректность проверки

Рассматриваемый алгоритм корректен в том смысле, что подпись, вычисленная по указанным выше правилам, будет принята при её проверке.

Преобразуя определение ${\displaystyle s}$ , имеем

${\displaystyle m\,\equiv \,xr+sk{\pmod {p-1}}.}$

Далее, из Малой теоремы Ферма следует, что

${\displaystyle {\begin{aligned}g^{m}&\equiv g^{xr}g^{ks}\\&\equiv (g^{x})^{r}(g^{k})^{s}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{aligned}}}$

Пример

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

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

---

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

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

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

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

  ${\displaystyle r=g^{i}\cdot y^{-j}{\bmod {p}}}$

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• Elgamal T. (англ.) // / — IEEE , 1985. — P. 10—18. — ISSN ; — ;
• Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. ^{[ уточнить ]}
• Б. А. Фороузан. // / Пер. А. Н. Берлин. — Курс лекций.
• Menezes A. J. , Oorschot P. v. , Vanstone S. A. // (англ.) — CRC Press , 1996. — 816 p. — ( ) — ISBN 978-0-8493-8523-0