Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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

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


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

  1. Генерується випадкове просте число ~ P довжини ~ Nбітів.
  2. Вибирається випадкове ціле число ~ G таке, що ~ 1 <g <p .
  3. Вибирається випадкове ціле число ~ X таке, що ~ 1 <x <p .
  4. Обчислюється ~ Y = g ^ x \, \ bmod \, p .
  5. Відкритим ключем є трійка \ Left (p, g, y \ right) , Закритим ключем - число ~ X .

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

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

2.1. Шифрування

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

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

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


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

Знаючи закритий ключ ~ X , Вихідне повідомлення можна обчислити з шіфротекста \ Left (a, b \ right) за формулою:

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

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

~ (A ^ x) ^ {-1} \ equiv g ^ {-kx} \ pmod {p}

і тому

~ B (a ^ x) ^ {-1} \ equiv (y ^ kM) g ^ {-xk} \ equiv (g ^ {xk} M) g ^ {-xk} \ equiv M \ pmod {p} .

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

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

2.3. Схема шифрування

Шифрування за схемою Ель-Гамаля

2.4. Приклад

  • Шифрування
    1. Припустимо що потрібно зашифрувати повідомлення ~ M = 5 .
    2. Зробимо генерацію ключів:
      1. нехай ~ P = 11, g = 2 . Виберемо ~ X = 8 - Випадкове ціле число ~ X таке, що ~ 1 <x <p .
      2. Обчислимо ~ Y = g ^ x \ bmod {p} = 2 ^ 8 \ bmod {11} = 3 .
      3. Отже, відкритим є трійка ~ (P, g, y) = (11,2,3) , А закритим ключем є число ~ X = 8 .
    3. Вибираємо випадкове ціле число ~ K таке, що 1 .
    4. Обчислюємо число ~ A = g ^ k \ bmod {p} = 2 ^ 9 \ bmod {11} = 512 \ bmod {11} = 6 .
    5. Обчислюємо число ~ B = y ^ k M \ bmod {p} = 3 ^ 9 5 \ bmod {11} = 19683 \ cdot 5 \ bmod {11} = 9 .
    6. Отримана пара ~ (A, b) = (6,9) є шіфротекста.
  • Розшифрування
    1. Необхідно отримати повідомлення ~ M = 5 за відомим шіфротекста ~ (A, b) = (6,9) і закритому ключу ~ X = 8 .
    2. Обчислюємо M за формулою: ~ M = b (a ^ x) ^ {-1} \ bmod {p} = 9 (6 ^ 8) ^ {-1} \ mod {11} = 5
    3. Отримали вихідне повідомлення ~ M = 5 .


Так як в схему Ель-Гамаля вводиться випадкова величина ~ K , То шифр Ель-Гамаля можна назвати шифром багатозначної заміни. Через випадковості вибору числа ~ K таку схему ще називають схемою імовірнісного шифрування. Імовірнісний характер шифрування є перевагою для схеми Ель-Гамаля, так як у схем імовірнісного шифрування спостерігається більша стійкість в порівнянні зі схемами з певним процесом шифрування. Недоліком схеми шифрування Ель-Гамаля є подвоєння довжини зашифрованого тексту в порівнянні з початковим текстом. Для схеми імовірнісного шифрування саме повідомлення ~ M і ключ не визначають шіфротекст однозначно. У схемі Ель-Гамаля необхідно використовувати різні значення випадкової величини ~ K для шифровки різних повідомлень ~ M і ~ M ^ ' . Якщо використовувати однакові ~ K , То для відповідних шіфротектов ~ (A, b) і ~ (A ^ ', b ^') виконується співвідношення ~ B (b ^ ') ^ {-1} = M (M ^') ^ {-1} . З цього виразу можна легко обчислити ~ M ^ ' , Якщо відомо ~ M .


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

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

Цифровий підпис за схемою Ель-Гамаля

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

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

  1. Обчислюється дайджест повідомлення ~ M : ~ M = h (M).
  2. Вибирається випадкове число ~ 1 <k <p-1 взаємно просте з ~ P - 1 і обчислюється ~ R = g ^ k \, \ bmod \, p.
  3. Обчислюється число s \, \ equiv \, (m-x r) k ^ {-1} \ pmod {p-1} .
  4. Підписом повідомлення ~ M є пара \ Left (r, s \ right) .

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

Знаючи відкритий ключ \ Left (p, g, y \ right) , Підпис \ Left (r, s \ right) повідомлення ~ M перевіряється наступним чином:

  1. Перевіряється здійснимість умов: ~ 0 <r <p і ~ 0 <s <p-1 . Якщо хоча б одне з них не виконується, то підпис вважається невірною.
  2. Обчислюється дайджест ~ M = h (M).
  3. Підпис вважається вірною, якщо виконується порівняння:
    ~ Y ^ r r ^ s \ equiv g ^ m \ pmod {p}.

3.3. Приклад

  • Підпис повідомлення.
    1. Припустимо, що потрібно підписати повідомлення ~ M = baaqab .
    2. Зробимо генерацію ключів:
      1. Нехай ~ P = 23~ G = 5 змінні, які відомі деякого спільноті. Секретний ключ ~ X = 7 - Випадкове ціле число ~ X таке, що ~ 1 <x <p .
      2. Обчислюємо відкритий ключ ~ Y : ~ Y = g ^ x \ bmod p = 5 ^ 7 \ bmod 23 = 17 .
      3. Отже, відкритим ключем є трійка ~ (P, g, y) = (23,5,17) .
    3. Тепер обчислюємо хеш-функцію: ~ H (M) = h (baaqab) = m = 3 .
    4. Виберемо випадкове число ~ K таке, що виконується умова 1 <k <p-1 . Нехай ~ K = 5 .
    5. Обчислюємо ~ R = g ^ k modp = 5 ^ 5 \ bmod 23 = 20 .
    6. Знаходимо число s \, \ equiv \, (m-x r) k ^ {-1} \ pmod {p-1} . Таке ~ S існує, так як НОД (k, p -1) = 1. Отримаємо що ~ S = 21 .
    7. Отже, ми підписали повідомлення: ~ <baaqab,20,21> .
  • Перевірка справжності отриманого повідомлення.
    1. Обчислюємо хеш-функцію: ~ H (M) = h (baaqab) = m = 3 .
    2. Перевіряємо порівняння ~ Y ^ r \ cdot r ^ s \ equiv g ^ m \ pmod {p} .
    3. Обчислимо ліву частину по модулю 23: ~ 17 ^ {20} \ cdot 20 ^ {21} \ bmod 23 = 16 \ cdot 15 \ bmod 23 = 10 .
    4. Обчислимо праву частину по модулю 23: ~ 5 ^ 3 \ bmod 23 = 10 .
    5. Так як права і ліва частини рівні, то це означає що підпис вірна.


Головною перевагою схеми цифрового підпису Ель-Гамаля є можливість виробляти цифрові підписи для великого числа повідомлень з використанням тільки одного секретного ключа. Щоб зловмисникові підробити підпис, йому потрібно вирішити складні математичні завдання із знаходженням логарифма в поле \ Mathbb {Z} _p . Слід зробити кілька коментарів:
  • Випадкове число ~ K повинно відразу після обчислення підпису знищуватися, оскільки якщо зловмисник знає випадкове число ~ K і саму підпис, то він легко може знайти секретний ключ за формулою: ~ X = (m-ks) r ^ {-1} \ bmod (p-1) і повністю підробити підпис.

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

  • Використання згортки ~ M = h (M) пояснюється тим, що це захищає підпис від перебору повідомлень по відомим зловмисникові значенням підпису. Приклад: якщо вибрати випадкові числа ~ I, j , Що задовольняють умовам ~ 0 <i <{p-1}, 0 <j <{p-1} , НОД (j, p-1) = 1 і припустити що
    ~ R = g ^ i \ cdot y ^ j \ bmod p
    ~ S = r \ cdot j ^ {-1} \ bmod (p-1)
    ~ M = r \ cdot i \ cdot j ^ {-1} \ bmod (p-1)

то легко переконатися в тому, що пара ~ (R, s) є вірною цифровим підписом для повідомлення ~ X = M .

  • Цифровий підпис Ель-Гамаля стала прикладом побудови інших підписів, схожих за своїми властивостями. В їх основі лежить виконання порівняння: ~ Y ^ A \ cdot r ^ B = g ^ C (modp) , В якому трійка ~ (A, B, C) приймає значення однієї з перестановок r, s і m при якомусь виборі знаків. Наприклад, вихідна схема Ель-Гамаля виходить при ~ A = r , ~ B = s , ~ C = m . На такому принципі побудови підписи зроблені стандарти цифрового підпису США і Росії. В американському стандарті DSS (Digital Signature Standard), використовується значення ~ A = r , ~ B =-s , ~ C = m , А в Російському стандарті: ~ A =-x , ~ B =-m , ~ C = s .
  • Ще однією з переваг є можливість зменшення довжини підпису за допомогою заміни пари чисел ~ (S, m) на пару чисел ~ (S \ bmod q, m \ bmod q ), Де ~ Q є якимось простим дільником числа ~ (P-1) . При цьому порівняння для перевірки підпису по модулю ~ P потрібно замінити на нове порівняння по модулю ~ Q : ~ (Y ^ A \ cdot r ^ B \ bmod p) = g ^ C \ pmod {q} . Так зроблено в американському стандарті DSS (Digital Signature Standard).

math> ~


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

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

~ Y \ equiv g ^ x \ pmod {p}.

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

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

Алгоритм Ключ Призначення Криптостійкість, 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 - caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf ". IEEE Transactions on Information Theory 31 (4): 469 - 472. DOI : 10.1109/TIT.1985.1057074 - dx.doi.org/10.1109/TIT.1985.1057074.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Ель-Аюн-Буждур-Сегієт-ель-Хамра
Ель-Джебал-Ель-Ахдар
Схема
Блок-схема
Схема Горнера
Різницева схема
Схема Шнорр
Схема перетворення
Схема виділення
© Усі права захищені
написати до нас
Рейтинг@Mail.ru