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

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

Схему запропонував Тахер Ель-Гамаль 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}}.

ГОСТ Р34.10-1994, який ухвалено 1994 року в Російській Федерації, що регламентував процедури формування та перевірки електронного цифрового підпису, засновано на схемі Ель-Гамаля. З 2001 року використовується новий ГОСТ Р 34.10-2001, що використовує арифметику еліптичних кривих, визначених над простими полями Галуа. Існує велика кількість алгоритмів, заснованих на схемі Ель-Гамаля: це алгоритми DSA, ECDSA, KCDSA, схема Шнорра.

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

Алгоритм	Ключ	Призначення	Крипостійкість, 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. IEEE Transactions on Information Theory 31 (4): 469–472. doi:10.1109/TIT.1985.1057074.

Література

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Taher ElGamal (1985). A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31 (4): 469–472. doi:10.1109/TIT.1985.1057074.