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

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

Схему запропонував Тахер Ель-Гамаль 1985 року.^[1] Ель-Гамаль розробив один з варіантів алгоритму Діффі-Геллмана. Він удосконалив систему Діффі-Геллмана й отримав два алгоритми, які призначено для шифрування та для автентифікації. На відміну від 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].

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

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

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено. (липень 2017)