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

криптосистема публічних ключів

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

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

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

ред.
  1. Генерується випадкове просте число   бітів.
  2. Обирається випадковий примітивний елемент   поля  .
  3. Обирається випадкове ціле число   таке, що  .
  4. Обчислюється  .
  5. Відкритий ключ — це трійка  , а приватний ключ — це число  .

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

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

Шифрування

ред.

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

  1. Обирається сесійний ключ — випадкове ціле число   таке, що  
  2. Обчислюються числа   і  .
  3. Пара чисел   є шифротекстом.

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

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

ред.

Знаючи приватний ключ  , повідомлення   можна обчислити з шифротексту   за формулою:

 

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

 

і тому

 .

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

 

Приклад

ред.
  • Шифрування
    1. Припустімо, що потрібно зашифрувати повідомлення  .
    2. Згенеруймо ключі:
      1. Нехай  . Оберімо   — випадкове ціле число   таке, що  .
      2. Обчислімо  .
      3. Отже, відкритий ключ — це трійка  , а приватний ключ — це число  .
    3. Оберімо випадкове ціле число   таке, що 1 < k < (p − 1). Нехай  .
    4. Обчислімо значення  .
    5. Обчислімо значення  .
    6. Отримана пара   є шифротекстом.
  • Розшифрування
    1. Необхідно отримати повідомлення   за відомими шифротекстом  та приватним ключем  .
    2. Обчислімо   за формулою:  
    3. Отримали повідомлення  .

Через те, що до схеми Ель-Гамаля вводиться випадкова величина  , шифр Ель-Гамаля можна назвати шифром багатозначної заміни. Через випадковість вибору числа   таку схему ще називають схемою імовірнісного шифрування. Імовірнісний характер шифрування — це перевага для схеми Ель-Гамаля, тому що у схем імовірнісного шифрування спостерігається більша стійкість у порівнянні зі схемами з певним процесом шифрування. Вадою схеми шифрування Ель-Гамаля можна назвати подвоєння довжини зашифрованого тексту в порівнянні з початковим текстом. Для схеми імовірнісного шифрування саме повідомлення   і ключ не визначають шифротекст однозначно. У схемі Ель-Гамаля необхідно використовувати різні значення випадкової величини   для шифрування різних повідомлень   і  . Якщо використовувати однакові  , то для відповідних шифротекстів   і   виконується співвідношення  . З цього виразу можна легко обчислити  , якщо відоме  .

Робота в режимі підпису

ред.

Цифровий підпис підтверджує (або спростовує) недоторканності підписаних даних, а також те, що дані підписав їхній власник. Одержувач підписаного повідомлення може використовувати цифровий підпис для доказу третій стороні того, що підпис дійсно зробив їх відправник. При роботі в режимі підпису передбачається наявність фіксованої геш-функції  , значення якої лежать в інтервалі  .

Підпис повідомлень

ред.

Для підпису повідомлення   виконуються наступні операції:

  1. Обчислюється дайджест повідомлення  :  
  2. Обирається випадкове число   взаємно просте з   і обчислюється  
  3. Обчислюється число  .
  4. Підписом повідомлення   вважається пара  .

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

ред.

Знаючи відкритий ключ   і підпис  , повідомлення   перевіряється так:

  1. Перевіряються дві умови:   і  . Якщо хоча б одна з них не виконується, то підпис вважається недійсним.
  2. Обчислюється дайджест  
  3. Підпис вважається справжнім, якщо виконується рівність:
     

Приклад

ред.
  • Підпис повідомлення.
    1. Припустімо, що потрібно підписати повідомлення  .
    2. Згенеруймо ключі:
      1. Нехай   та   змінні, які відомі у деякій спільноті. Секретний ключ   — випадкове ціле число  , таке, що  .
      2. Обчислімо відкритий ключ  :  .
      3. Отже, відкритий ключ — це трійка  .
    3. Тепер обчислімо геш-функцію:  .
    4. Оберімо випадкове число   таке, щоб виконувалася умова  . Нехай  .
    5. Обчислімо  .
    6. Знайдімо число  . Таке   існує, тому що НСД ( k , p - 1) = 1. Отримуємо  .
    7. Отже, ми підписали повідомлення:  .
  • Перевірка справжності отриманого повідомлення.
    1. Обчислімо геш-функцію:  .
    2. Перевірмо рівність  .
    3. Обчислімо ліву частину по модулю 23:  .
    4. Обчислімо праву частину по модулю 23:  .
    5. Оскільки права і ліва частини рівні, то підпис справжній.
Головна перевага схеми цифрового підпису Ель-Гамаля — це можливість створювати цифрові підписи для великого числа повідомлень з використанням тільки одного секретного ключа. Для підробки підпису зловмиснику потрібно зробити складні математичні розрахунки з перебуванням логарифму в полі  .
Слід додати кілька коментарів:
  • Випадкове число   необхідно знищувати одразу після обчислення підпису, оскільки якщо зловмисник знає випадкове число   і сам підпис, він легко може знайти секретний ключ за формулою:   і повністю підробити підпис.

Число   повинно бути випадковим і не повинно дублюватися для різних підписів, отриманих при однаковому значенні секретного ключа.

  • Використання згортки   пояснюється тим, що це захищає підпис від перебору повідомлень за відомими зловмисникові значеннями підпису. Приклад: якщо вибрати випадкові числа  , що задовольняють умовам  , НОД (j,p-1)=1 і припустити що
     
     
     ,

то легко переконатися в тому, що пара   — це справжній цифровий підпис повідомлення  .

  • Цифровий підпис Ель-Гамаля став прикладом для побудови інших підписів, схожих за своїми властивостями. В їхній основі лежить рівність  , в якій трійка   набуває значення однієї з перестановок ± r, ± s і ± m при якомусь виборі знаків. Наприклад, вихідна схема Ель-Гамаля утворюється за  , ,  . На такому принципі побудови підпису зроблено стандарти цифрового підпису США та Російської Федерації. В американському стандарті DSS (Digital Signature Standard) використовуються значення  ,  , , а в російському —  ,  ,  .
  • Наступна перевага — це можливість зменшити довжину підпису за допомогою заміни пари чисел   на пару чисел  ), де   — якийсь простий дільник числа  . При цьому рівняння для перевірки підпису по модулю   потрібно замінити на нове рівняння по модулю  :  . Так зроблено в американському стандарті DSS (Digital Signature Standard).

Криптостійкість і особливості

ред.

Нині криптосистеми з відкритим ключем вважаються найперспективнішими. До них належить і схема Ель-Гамаля, криптостійкість якої засновано на обчислювальній складності проблеми дискретного логарифмування, де за відомими p , g та y потрібно обчислити x , що задовольняє рівнянню:

 

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

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

Алгоритм Ключ Призначення Крипостійкість, MIPS Примітки
RSA До 4096 біт Шифрування і підпис 2,7•1028 для ключа завдовжки 1300 біт Засновано на складності розв'язання проблеми факторизації великих чисел; один із перших асиметричних алгоритмів. Включено до багатьох стандартів.
ElGamal До 4096 біт Шифрування і підпис За однакової довжини ключа криптостійкість дорівнює RSA, тобто 2,7•1028 для ключа завдовжки 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