Схема Ель-Гамаля
Схема Ель-Гамаля (ElGamal) — криптосистема з відкритим ключем, яку засновано на складності обчислення дискретних логарифмів у скінченному полі. Криптосистема включає у себе алгоритм шифрування і алгоритм цифрового підпису. Схема Ель-Гамаля лежить в основі колишніх стандартів електронного цифрового підпису в США (DSA) і Росії (ГОСТ Р 34.10-94[ru]).
Схему запропонував Тахер Ель-Гамаль 1985 року.[1] Ель-Гамаль розробив один з варіантів алгоритму Діффі-Геллмана. Він удосконалив систему Діффі-Геллмана й отримав два алгоритми, які призначено для шифрування та для автентифікації. На відміну від RSA, алгоритм Ель-Гамаля не запатентовано, і тому він став дешевшою альтернативою, оскільки оплата внесків за ліцензію не потрібна. Вважається, що алгоритм потрапляє під дію патенту Діффі-Геллмана.
Генерація ключів
ред.- Генерується випадкове просте число бітів.
- Обирається випадковий примітивний елемент поля .
- Обирається випадкове ціле число таке, що .
- Обчислюється .
- Відкритий ключ — це трійка , а приватний ключ — це число .
Робота в режимі шифрування
ред.- Шифросистема Ель-Гамаля — один зі способів створення відкритих ключів Діффі - Геллмана. Шифрування за схемою Ель-Гамаля не слід плутати з алгоритмом цифрового підпису за схемою Ель-Гамаля.
Шифрування
ред.Повідомлення шифрується так:
- Обирається сесійний ключ — випадкове ціле число таке, що
- Обчислюються числа і .
- Пара чисел є шифротекстом.
Неважко бачити, що довжина шифротексту в схемі Ель-Гамаля є довшою за повідомлення удвічі.
Розшифрування
ред.Знаючи приватний ключ , повідомлення можна обчислити з шифротексту за формулою:
При цьому неважко перевірити, що
і тому
- .
Для практичних обчислень більше підходить така формула:
Приклад
ред.- Шифрування
- Припустімо, що потрібно зашифрувати повідомлення .
- Згенеруймо ключі:
- Нехай . Оберімо — випадкове ціле число таке, що .
- Обчислімо .
- Отже, відкритий ключ — це трійка , а приватний ключ — це число .
- Оберімо випадкове ціле число таке, що 1 < k < (p − 1). Нехай .
- Обчислімо значення .
- Обчислімо значення .
- Отримана пара є шифротекстом.
- Розшифрування
- Необхідно отримати повідомлення за відомими шифротекстом та приватним ключем .
- Обчислімо за формулою:
- Отримали повідомлення .
Через те, що до схеми Ель-Гамаля вводиться випадкова величина , шифр Ель-Гамаля можна назвати шифром багатозначної заміни. Через випадковість вибору числа таку схему ще називають схемою імовірнісного шифрування. Імовірнісний характер шифрування — це перевага для схеми Ель-Гамаля, тому що у схем імовірнісного шифрування спостерігається більша стійкість у порівнянні зі схемами з певним процесом шифрування. Вадою схеми шифрування Ель-Гамаля можна назвати подвоєння довжини зашифрованого тексту в порівнянні з початковим текстом. Для схеми імовірнісного шифрування саме повідомлення і ключ не визначають шифротекст однозначно. У схемі Ель-Гамаля необхідно використовувати різні значення випадкової величини для шифрування різних повідомлень і . Якщо використовувати однакові , то для відповідних шифротекстів і виконується співвідношення . З цього виразу можна легко обчислити , якщо відоме .
Робота в режимі підпису
ред.Цифровий підпис підтверджує (або спростовує) недоторканності підписаних даних, а також те, що дані підписав їхній власник. Одержувач підписаного повідомлення може використовувати цифровий підпис для доказу третій стороні того, що підпис дійсно зробив їх відправник. При роботі в режимі підпису передбачається наявність фіксованої геш-функції , значення якої лежать в інтервалі .
Підпис повідомлень
ред.Для підпису повідомлення виконуються наступні операції:
- Обчислюється дайджест повідомлення :
- Обирається випадкове число взаємно просте з і обчислюється
- Обчислюється число .
- Підписом повідомлення вважається пара .
Перевірка підпису
ред.Знаючи відкритий ключ і підпис , повідомлення перевіряється так:
- Перевіряються дві умови: і . Якщо хоча б одна з них не виконується, то підпис вважається недійсним.
- Обчислюється дайджест
- Підпис вважається справжнім, якщо виконується рівність:
Приклад
ред.- Підпис повідомлення.
- Припустімо, що потрібно підписати повідомлення .
- Згенеруймо ключі:
- Нехай та змінні, які відомі у деякій спільноті. Секретний ключ — випадкове ціле число , таке, що .
- Обчислімо відкритий ключ : .
- Отже, відкритий ключ — це трійка .
- Тепер обчислімо геш-функцію: .
- Оберімо випадкове число таке, щоб виконувалася умова . Нехай .
- Обчислімо .
- Знайдімо число . Таке існує, тому що НСД ( k , p - 1) = 1. Отримуємо .
- Отже, ми підписали повідомлення: .
- Перевірка справжності отриманого повідомлення.
- Обчислімо геш-функцію: .
- Перевірмо рівність .
- Обчислімо ліву частину по модулю 23: .
- Обчислімо праву частину по модулю 23: .
- Оскільки права і ліва частини рівні, то підпис справжній.
- Головна перевага схеми цифрового підпису Ель-Гамаля — це можливість створювати цифрові підписи для великого числа повідомлень з використанням тільки одного секретного ключа. Для підробки підпису зловмиснику потрібно зробити складні математичні розрахунки з перебуванням логарифму в полі .
- Слід додати кілька коментарів:
- Випадкове число необхідно знищувати одразу після обчислення підпису, оскільки якщо зловмисник знає випадкове число і сам підпис, він легко може знайти секретний ключ за формулою: і повністю підробити підпис.
Число повинно бути випадковим і не повинно дублюватися для різних підписів, отриманих при однаковому значенні секретного ключа.
- Використання згортки пояснюється тим, що це захищає підпис від перебору повідомлень за відомими зловмисникові значеннями підпису. Приклад: якщо вибрати випадкові числа , що задовольняють умовам , НОД (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 | Сучасний напрямок. Його розробляють багато провідних математиків. |
Примітки
ред.- ↑ 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