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

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

Схема Ель-Гамаля (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