Методи криптоаналізу асиметричних криптосистем

Міністерство освіти і науки України

Державний вищий навчальний заклад «Київський національний економічний університет імені Вадима Гетьмана»

кафедра комп’ютерної математики та інформаційної безпеки

Практична робота №4

з навчальної дисципліни

«Прикладної криптології»

Тема:

«Методи криптоаналізу асиметричних криптосистем»

Виконав  студент

гр. ІК-301

Арішин Б.І.

Перевірив

Викладач кафедри КМІБ:

Нагірна А. М.

Київ 2020

Вступ

Більшість використовуваних по цей час алгоритмів асиметричної криптографії засновані на задачах факторизації (наприклад, відома криптосистема RSA) і дискретного логарифмування в різних алгебраїчних структурах.

Незважаючи на те, що приналежність цих задач до класу NP-повних задач не доведена, на сьогоднішній день не знайдено поліноміальний алгоритм їх вирішення. Для криптоаналізу асиметричних криптосистем можна застосовувати універсальні методи - наприклад, метод "зустрічі посередині". Інший підхід полягає в рішенні математичної задачі, покладеної в основу асиметричного шифру.

З того моменту, як  Діффі і  Хеллман в 1976 р запропонували концепцію криптографії з відкритим ключем, проблеми факторизації цілих чисел і дискретного логарифмування стали об'єктом пильного вивчення математиків усього світу.

За останні роки в цій галузі спостерігався значний прогрес. Підтвердженням тому може служити наступний казус: в 1977 р Р. Ривест заявив, що розкладання на множники 125-розрядного числа потребує 40 квадрильйонів років, проте вже в 1994 році було факторізовано число, що складається з 129 двійкових розрядів.

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

Останні досягнення теорії обчислювальної складності показали, що загальна проблема логарифмування в кінцевих полях уже не є достатньо міцним фундаментом. Найбільш ефективні на сьогоднішній день алгоритми дискретного логарифмування мають вже не експоненціальну, а субекспоненціальну тимчасову складність. Це алгоритми "index-calculus", що використовують факторну базу.

Перший такий алгоритм для обчислення дискретного логарифму в простому полі  був запропонований Л. Адлеманом. На практиці алгоритм Адлемана виявився недостатньо ефективним; Д. Копперсміт, А. Одлижко і Р. Шреппель запропонували свою версію субекспоненціального алгоритму дискретного логарифмування – “cos”.[pic 1]

Алгоритм решета числового поля, запропонований О. Шірокауером, при  працює ефективніше різних модифікацій методу COS.[pic 2]

Ряд успішних атак на системи, засновані на складності дискретного логарифмування в кінцевих полях, привів до того, що стандарти ЕЦП Росії і США, які були прийняті в 1994 році і базувалися на схемі Ель-Гамаля, в 2001 році були оновлені: переведені на еліптичні криві.

Схеми ЕЦП при цьому залишилися колишніми, але в якості чисел, якими вони оперують, тепер використовуються не елементи кінцевого поля , а еліптичні числа - рішення рівняння еліптичних кривих над зазначеними кінцевими полями. Алгоритмів, що виконують дискретної логарифмування на еліптичних кривих в загальному випадку хоча б з субекспоненціальною складністю, на сьогоднішній день не існує, хоча роботи в цьому напрямку ведуться. Так, для еліптичних кривих спеціального виду наш співвітчизник І. Сема вказав спосіб відомості завдання логарифмування в групі точок еліптичної кривої до задачі логарифмування в деякому розширенні простого поля.[pic 3]