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

Схема Ель-Гамаля (ElGamal) — криптосистема з відкритим ключем, яку засновано на складності обчислення дискретних логарифмів у скінченному полі. Криптосистема включає у себе алгоритм шифрування і алгоритм цифрового підпису. Схема Ель-Гамаля лежить в основі колишніх стандартів електронного цифрового підпису в США (DSA) і Росії (ГОСТ Р 34.10-94^[ru]).

Схему запропонував Тахер Ель-Гамаль 1985 року.^[1] Ель-Гамаль розробив один з варіантів алгоритму Діффі-Геллмана. Він удосконалив систему Діффі-Геллмана й отримав два алгоритми, які призначено для шифрування та для автентифікації. На відміну від RSA, алгоритм Ель-Гамаля не запатентовано, і тому він став дешевшою альтернативою, оскільки оплата внесків за ліцензію не потрібна. Вважається, що алгоритм потрапляє під дію патенту Діффі-Геллмана.

Генерація ключів

Генерується випадкове просте число $~p$ бітів.
Обирається випадковий примітивний елемент $~g$ поля $\mathbb {Z} _{p}$ .
Обирається випадкове ціле число $~x$ таке, що $~1<x<p-1$ .
Обчислюється $~y=g^{x}\,{\bmod {\,}}p$ .
Відкритий ключ — це трійка $\left(p,g,y\right)$ , а приватний ключ — це число $~x$ .

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

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

Шифрування

Повідомлення $~M$ шифрується так:

Обирається сесійний ключ — випадкове ціле число $~k$ таке, що $~1<k<p-1$
Обчислюються числа $a=g^{k}\,{\bmod {\,}}p$ і $b=y^{k}M\,{\bmod {\,}}p$ .
Пара чисел $\left(a,b\right)$ є шифротекстом.

Неважко бачити, що довжина шифротексту в схемі Ель-Гамаля є довшою за повідомлення $M$ удвічі.

Розшифрування

Знаючи приватний ключ $~x$ , повідомлення $M$ можна обчислити з шифротексту $\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^{k}M)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$ виконуються наступні операції:

Обчислюється дайджест повідомлення $~M$ : $~m=h(M).$
Обирається випадкове число $~1<k<p-1$ взаємно просте з $~p-1$ і обчислюється $~r=g^{k}\,{\bmod {\,}}p.$
Обчислюється число $s\,\equiv \,(m-xr)k^{-1}{\pmod {p-1}}$ .
Підписом повідомлення $~M$ вважається пара $\left(r,s\right)$ .

Перевірка підпису

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

Перевіряються дві умови: $~0<r<p$ і $~0<s<p-1$ . Якщо хоча б одна з них не виконується, то підпис вважається недійсним.
Обчислюється дайджест $~m=h(M).$
Підпис вважається справжнім, якщо виконується рівність:
$~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 {2}}3=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 {2}}3=20$ .
6. Знайдімо число $s\,\equiv \,(m-xr)k^{-1}{\pmod {p-1}}$ . Таке $~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 {2}}3=16\cdot 15{\bmod {2}}3=10$ .
4. Обчислімо праву частину по модулю 23: $~5^{3}{\bmod {2}}3=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}}.

Існує велика кількість алгоритмів, заснованих на схемі Ель-Гамаля: це алгоритми DSA, ECDSA, KCDSA, схема Шнорра^[ru].

Порівняння деяких алгоритмів:

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

Примітки

↑ Taher ElGamal (1985). A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (PDF). IEEE Transactions on Information Theory. 31 (4): 469—472. doi:10.1109/TIT.1985.1057074. Архів оригіналу (PDF) за 13 серпня 2011. Процитовано 9 грудня 2014.

Література

Алфьоров А.П., Зубов А.Ю., Кузьмін А.С., Черьомушкін А.В
Б. А. Фороузан
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone

Портал «Програмування» Портал «Інформаційні технології»

[1] Taher ElGamal (1985). A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (PDF). IEEE Transactions on Information Theory. 31 (4): 469—472. doi:10.1109/TIT.1985.1057074. Архів оригіналу (PDF) за 13 серпня 2011. Процитовано 9 грудня 2014.

[1]

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

Зміст

Генерація ключів