19. Дискретне логарифмування.

Стійкість широко розповсюджених у даний час схем ЕЦП (електронний цифровий підпис) заснована на складності рішення приватної завдання дискретного логарифмування в простому полі GF (p). Завдання це формулюється наступним чином:

• задані прості числа p, q і натуральне число g <p порядку q, тобто

g^q 1 (modp);

• знаючи значення y = g^x (mod p), необхідно знайти x  Z.

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

O(exp((c+O(1))(ln (p))^1/3(ln (ln (p)))^2/3 операцій в полі GF(p), де c (64/9)^1/3.

Методами рішення приватної завдання дискретного логарифмування є також -метод и -метод Полларда і деякі близькі методи, що вимагають для її вирішення виконання порядку

q/4 операцій множення в полі GF (p). (1.2)

«При 1024-бітовому p і 256-бітовому q ми отримуємо приблизно 1.3E +26 для методу решета числового поля і 3.0E +38 для - і - методів Полларда».

Національні стандарти DigitalSignatureStandard (прийнятий NIST в 1991 р. з наступними змінами в 1993, 1996 р.), російський стандарт цифрового підпису ГОСТ Р 34.10-94 реалізовують ЕЦП в простому полі.

Прогрес в галузі вирішення задачі дискретного логарифмування привів до того, що стала можлива реальна компрометація схем ЕЦП, заснованих на складності обчислень у мультиплікативної групи поля, з боку порушника, який володіє досить невисокими обчислювальними і фінансовими ресурсами. Тому на рубежі XX і XXI століття в багатьох країнах світу стали використовуватися схеми формування ЕЦП, засновані на складності розв'язання задачі дискретного логарифмування в групі точок еліптичної кривої. Це завдання формулюється наступним чином:

• задана еліптична крива E над полем GF (p), де p - просте число;

• обрана точка G, що має простий порядок q в групі точок кривої E;

• знаючи точку kG необхідно відновити натуральне число k.

Алгоритми створення і перевірки ЕЦП, що базуються на математичному апараті еліптичних кривих, є стійкішими в порівнянні зі схемами, що базуються на складнощі вирішення задачі дискретного логарифмування в простому полі.

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

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

Алгоритм Ель-Гамаля може використовуватися для формування електронного підпису або для шифрування даних. Він базується на трудності обчислення дискретного логарифма. Для генерації пари ключів спочатку береться просте число 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 біт.