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

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

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

Генерация ключейПравить

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

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

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

ШифрованиеПравить

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

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

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

РасшифрованиеПравить

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

$M=b(a^x{)}^{-<!--\; -\; -->1}modp.$$M=b(a^{x})^{-1}{\bmod {p}}.$ 

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

$(a^x{)}^{-<!--\; -\; -->1}=g^{-<!--\; -\; -->kx}modp$$(a^{x})^{-1}=g^{-kx}{\bmod {p}}$ 

и поэтому

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

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

$M=b(a^x{)}^{-<!--\; -\; -->1}=b{a}^{(p-<!--\; -\; -->1-<!--\; -\; -->x)}(\mathrm{mod}p)$$M=b(a^{x})^{-1}=ba^{(p-1-x)}{\pmod {p}}$ 

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

 

ПримерПравить

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

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

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

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

 

Подпись сообщенийПравить

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

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

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

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

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

   $y^r{r}^s\equiv <!--\; \equiv \; -->g^m(\mathrm{mod}p).$$y^{r}r^{s}\equiv g^{m}{\pmod {p}}.$ 

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

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

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

$m\equiv <!--\; \equiv \; -->xr+sk(\mathrm{mod}p-<!--\; -\; -->1).$$m\,\equiv \,xr+sk{\pmod {p-1}}.$ 

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

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

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

---

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

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

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

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

  $r=g^i\cdot <!--\; \cdot \; -->y^{-<!--\; -\; -->j}modp$$r=g^{i}\cdot y^{-j}{\bmod {p}}$ 

  $s=r\cdot <!--\; \cdot \; -->j^{-<!--\; -\; -->1}mod(p-<!--\; -\; -->1)$$s=r\cdot j^{-1}{\bmod {(}}p-1)$ 

  $m=r\cdot <!--\; \cdot \; -->i\cdot <!--\; \cdot \; -->j^{-<!--\; -\; -->1}mod(p-<!--\; -\; -->1)$$m=r\cdot i\cdot j^{-1}{\bmod {(}}p-1)$ 

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

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

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

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

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

ЛитератураПравить

• Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (англ.) // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1985. — Vol. 31, Iss. 4. — P. 469—472. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1985.1057074; doi:10.1007/3-540-39568-7_2
• Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии.^{[уточнить]}
• Б. А. Фороузан. Схема цифровой подписи Эль-Гамаля // Управление ключами шифрования и безопасность сети / Пер. А. Н. Берлин. — Курс лекций.
• Menezes A. J., Oorschot P. v., Vanstone S. A. 11.5.2 The ElGamal signature scheme // Handbook of Applied Cryptography (англ.) — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0