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

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

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

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

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

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

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

Шифрование

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

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

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

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

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

$M=b(a^x{)}^{-1}modp.$

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

$(a^x{)}^{-1}=g^{-kx}modp$

и поэтому

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

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

$M=b(a^x{)}^{-1}=b{a}^{(p-1-x)}(\mathrm{mod}p)$

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

Шифрование по схеме Эль-Гамаля

Пример

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

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

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

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

Цифровая подпись по схеме Эль-Гамаля

Цифровая подпись по схеме Эль-Гамаля

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

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

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

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

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

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

   $y^r{r}^s\equiv g^m(\mathrm{mod}p).$

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

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

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

$m\equiv xr+sk(\mathrm{mod}p-1).$

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

$\begin{array}{cc}{g}^m& \equiv g^{xr}{g}^{ks}\\ & \equiv (g^x{)}^r(g^k{)}^s\\ & \equiv (y{)}^r(r{)}^s(\mathrm{mod}p).\\ \end{array}$

Пример

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

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

---

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

• Случайное число $k$ должно сразу после вычисления подписи уничтожаться, так как если злоумышленник знает случайное число $k$ и саму подпись, то он легко может найти секретный ключ по формуле: $x=(m-ks)r^{-1}mod(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}modp$

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

  $m=r\cdot i\cdot j^{-1}mod(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)$ на пару чисел $(smodq,mmodq$), где $q$ является каким-то простым делителем числа $(p-1)$. При этом сравнение для проверки подписи по модулю $p$ нужно заменить на новое сравнение по модулю $q$: $(y^A\cdot r^B)modp=g^C(\mathrm{mod}q)$. Так сделано в американском стандарте DSS (Digital Signature Standard).

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

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

$y\equiv g^x(\mathrm{mod}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	Современное направление. Разрабатывается многими ведущими математиками

Литература

• Шаблон:Source
• Шаблон:КнигаШаблон:Уточнить
• Шаблон:Книга
• Шаблон:Source