Метод ель-Гамаля. Розшифровування криптограм ель-Гамаля.

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

Загальнодоступними ключами є y, g і p, а секретним ключем є х. Для підпису повідомлення M вибирається випадкове число k, яке є простим по відношенню до p-1. Після цього обчислюється a= g^k mod p.

Далі з рівняння M = (xa + kb) mod (p-1) знаходимо b. Електронним підписом для повідомлення M буде служити пара a і b. Випадкове число k слід зберігати в секреті. Для верифікації підпису необхідно перевірити рівність:

y^aa^b mod p = g^M mod p.

Пара a і b представляють собою зашифрований текст. Слід зауважити, що зашифрований текст має розмір у два рази більше вихідного. Для дешифрування виробляється обчислення:

M = b/a^x mod p

Проблема дискретного логарифма полягає в тому, що, знаючи підставу степені і отриманий після зведення результат по модулю простого числа, неможливо за поліноміальний час визначити, в яку саме степінь було зведено основу. У схемі Ель Гамаля потенційний зловмисник може отримати значення a, р, (a^хmodp) і (а^уmodp). Однак через складності визначення чисел х і у "в чистому вигляді" у нього не виявляється можливості обчислити значення

k= (a^хуmodp), яке йому так необхідно для прочитання шифровки.

Щодо числа р криптоаналіз висуває таку вимогу. Число (р-1) має містити в розкладанні на множники великий простий дільник. У деяких протоколах з участю схеми Ель Гамаля р вибирається як (qх2+1), де q-просте число (число р в цьому випадку називається простим). При виборі хіуполучателем і відправником відповідно, природно, має виконуватися вимога до їх інформаційної ємності. Для генерації цих чисел повинен використовуватися або ГВЧ-генератор "дійсно" випадкових чисел (не ГПСЧ), або криптостійкий генератор псевдовипадкових чисел (КПТСЧ). В іншому випадку зловмисник просто визначить х або у повним перебором.

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

За криптостійкість у схемі Ель Гамаля 512-бітове число р прирівнюється до 56-бітного симетричного ключа, про який вже склалося однозначну думку. Тому на практиці застосовуються р довжиною в 768, 1024 і 1536 біт.