Методи криптоаналізу асиметричних криптосистем
Автор: Boris Arishyn • Апрель 23, 2020 • Практическая работа • 1,352 Слов (6 Страниц) • 378 Просмотры
Міністерство освіти і науки України
Державний вищий навчальний заклад «Київський національний економічний університет імені Вадима Гетьмана»
кафедра комп’ютерної математики та інформаційної безпеки
Практична робота №4
з навчальної дисципліни
«Прикладної криптології»
Тема:
«Методи криптоаналізу асиметричних криптосистем»
Виконав студент
гр. ІК-301
Арішин Б.І.
Перевірив
Викладач кафедри КМІБ:
Нагірна А. М.
Київ 2020
Вступ
Більшість використовуваних по цей час алгоритмів асиметричної криптографії засновані на задачах факторизації (наприклад, відома криптосистема RSA) і дискретного логарифмування в різних алгебраїчних структурах.
Незважаючи на те, що приналежність цих задач до класу NP-повних задач не доведена, на сьогоднішній день не знайдено поліноміальний алгоритм їх вирішення. Для криптоаналізу асиметричних криптосистем можна застосовувати універсальні методи - наприклад, метод "зустрічі посередині". Інший підхід полягає в рішенні математичної задачі, покладеної в основу асиметричного шифру.
З того моменту, як Діффі і Хеллман в 1976 р запропонували концепцію криптографії з відкритим ключем, проблеми факторизації цілих чисел і дискретного логарифмування стали об'єктом пильного вивчення математиків усього світу.
За останні роки в цій галузі спостерігався значний прогрес. Підтвердженням тому може служити наступний казус: в 1977 р Р. Ривест заявив, що розкладання на множники 125-розрядного числа потребує 40 квадрильйонів років, проте вже в 1994 році було факторізовано число, що складається з 129 двійкових розрядів.
Задача дискретного логарифмування вважається більш складною, ніж завдання факторизації. Якщо буде знайдений поліноміальний алгоритм її вирішення, стане можливим і розкладання на множники (протилежне не доведено).
Останні досягнення теорії обчислювальної складності показали, що загальна проблема логарифмування в кінцевих полях уже не є достатньо міцним фундаментом. Найбільш ефективні на сьогоднішній день алгоритми дискретного логарифмування мають вже не експоненціальну, а субекспоненціальну тимчасову складність. Це алгоритми "index-calculus", що використовують факторну базу.
Перший такий алгоритм для обчислення дискретного логарифму в простому полі був запропонований Л. Адлеманом. На практиці алгоритм Адлемана виявився недостатньо ефективним; Д. Копперсміт, А. Одлижко і Р. Шреппель запропонували свою версію субекспоненціального алгоритму дискретного логарифмування – “cos”.[pic 1]
Алгоритм решета числового поля, запропонований О. Шірокауером, при працює ефективніше різних модифікацій методу COS.[pic 2]
Ряд успішних атак на системи, засновані на складності дискретного логарифмування в кінцевих полях, привів до того, що стандарти ЕЦП Росії і США, які були прийняті в 1994 році і базувалися на схемі Ель-Гамаля, в 2001 році були оновлені: переведені на еліптичні криві.
Схеми ЕЦП при цьому залишилися колишніми, але в якості чисел, якими вони оперують, тепер використовуються не елементи кінцевого поля , а еліптичні числа - рішення рівняння еліптичних кривих над зазначеними кінцевими полями. Алгоритмів, що виконують дискретної логарифмування на еліптичних кривих в загальному випадку хоча б з субекспоненціальною складністю, на сьогоднішній день не існує, хоча роботи в цьому напрямку ведуться. Так, для еліптичних кривих спеціального виду наш співвітчизник І. Сема вказав спосіб відомості завдання логарифмування в групі точок еліптичної кривої до задачі логарифмування в деякому розширенні простого поля.[pic 3]
...