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

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

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

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

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

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

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

Шифрування

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

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

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

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

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

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

При цьому неважко перевірити, що

${\displaystyle ~(a^{x})^{-1}\equiv g^{-kx}{\pmod {p}}}$

і тому

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

Для практичних обчислень більше підходить така формула:

${\displaystyle M=b(a^{x})^{-1}\,{\bmod {\,}}p=b\cdot a^{(p-1-x)}\,{\bmod {\,}}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. Обчислімо ${\displaystyle 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\,\equiv \,(m-xr)k^{-1}{\pmod {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. Обчислюється дайджест ${\displaystyle ~m=h(M).}$
3. Підпис вважається справжнім, якщо виконується рівність:

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

Приклад

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

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

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

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

Примітки

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.

Література

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