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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Схема була запропонована Тахера Ель-Гамаль в 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. Обчислюємо M за формулою:
    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 , що задовольняє порівнянню:

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

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

Алгоритм Ключ Призначення Крипостійкість, 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. 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