Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 12

В ідеалі, криптограф хотів би стверджувати, що алгоритм, кращий для злому спроектованого алгоритму шифрування, володіє експоненціального часовою складністю. На практиці, твердження, що можуть бути зроблені при поточному стані теорії обчислювальної складності, мають форму "усі відомі алгоритми розкриття даної криптосистеми володіють суперполіноміальною часовою складністю". Тобто, відомі нам алгоритми розкриття володіють суперполіноміальною часовою складністю, але поки неможливо довести, що не може бути відкритий алгоритм розкриття з поліноміальною часовою складністю. Розвиток теорії обчислювальної складності, можливо, коли-небудь дозволить створити алгоритми, для яких існування алгоритмів з поліноміальним часом розкриття може бути визначене з математичною точністю. [6]

З ростом п тимчасова складність алгоритмів може стати настільки величезною, що це вплине на практичну реалізацію алгоритму. У таблиці 1.2 показаний час виконання для різних класів алгоритмів при п рівному одному мільйонові. У таблиці ігноруються постійні величини, але показано, чому це можна зробити.

Табл. 2.1 Час виконання для різних класів алгоритмів [1]

За умови, що одиницею часу для нашого комп'ютера є мікросекунда, комп'ютер може виконати постійний алгоритм за мікросекунду, лінійний – за секунду, а квадратичний – за 11,6 дня. Виконання кубічного алгоритму потребує 32 тисяч років, що в принципі може бути реалізовано. Виконання експоненціального алгоритму неможливе, незалежно від екстраполяції росту потужності комп'ютерів або паралельної обробки даних.

Глянемо на проблему розкриття алгоритму шифрування грубою силою. Часова складність такого розкриття пропорційна кількості можливих ключів, що експоненціально залежить від довжини ключа. Якщо п – довжина ключа, то складність розкриття грубою силою дорівнює O(2ⁿ). [1]

1.2.2.  Складність проблем

Теорія складності також класифікує і складність самих проблем, а не тільки складність конкретних алгоритмів рішення проблеми. Теорія розглядає мінімальний час і обсяг пам'яті, необхідні для рішення найважчого варіанта проблеми на теоретичному комп'ютері, відомому як машина Тюрінга. Машина Тюрінга являє собою кінцевий автомат з нескінченною стрічкою пам'яті для читання-запису і є реалістичною моделлю обчислень. [10]

Проблеми, які можна вирішити за допомогою алгоритмів з поліноміальним часом, називаються розв'язуваними, якщо для розумних вхідних даних можуть бути вирішені за розумний час. (Точне визначення "розумності" залежить від конкретних обставин.) Проблеми, що неможливо вирішити за поліноміальний час, називаються нерозв'язаними, тому що обчислення їхніх рішень швидко стає неможливим. Нерозв'язані проблеми іноді називають важкими. Проблеми, що можуть бути вирішені тільки за допомогою суперполіноміальних алгоритмів, обчислювально нерозв'язувані, навіть при відносно малих значеннях n.

Що ще гірше, Алан Тюрінг довів, що деякі проблеми принципово нерозв'язні. Навіть відволікаючись від часової складності алгоритму, неможливо створити алгоритм рішення цих проблем.

Проблеми можна розбити на класи у відповідності зі складністю їхнього рішення. Найважливіші класи і їхні передбачувані співвідношення показані на малюнку 2.1. (Нажаль, лише мала частина цих тверджень може бути доведена математично) [6].

Клас Р складається з усіх проблем, які можливо вирішити за поліноміальний час. Клас NP – із усіх проблем, які можна вирішити за поліноміальний час тільки на недетермінованій машині Тюрінга: варіант звичайної машини Тюрінга, що може робити припущення. Машина припускає рішення проблеми – або "вдало угадуючи", або перебираючи всі припущення паралельно – і перевіряє своє припущення за поліноміальний час.

Важливість NP у криптографії полягає в наступному: багато симетричних алгоритмів і алгоритми з відкритими ключами можуть бути зламані за недетермінирований поліноміальний час. Для даного шифртексту С, криптоаналітик просто угадує відкритий текст, X, і ключ, k, і за поліноміальний час виконує алгоритм шифрування з входами X і k і перевіряє, чи рівний результат С. Це має важливе теоретичне значення, тому що установлює верхній кордон складності криптоаналізу цих алгоритмів. На практиці, звичайно ж, це виконуваний за поліноміальний час детермінирований алгоритм, що і шукає криптоаналітик. Більш того, цей аргумент не застосовний до всіх класів шифрів, конкретно, він не застосовний для одноразових блокнотів: для кожного С існує безліч пар X, k, щодають С при виконанні алгоритму шифрування, але більшість цих X являють собою безглузді, неприпустимі відкриті тексти.

Клас NP включає клас Р, тому що будь-яка проблема, розв'язувана за поліноміальний час на детермінованій машині Тюринга, буде також вирішена за поліноміальний час на недетермінованій машині Тюринга, просто пропускається етап припущення. [1]

Якщо всі NP проблеми вирішуються за поліноміальний час на детермінованій машині, то Р=NP. Хоча здається вірогідним, що деякі NP проблеми набагато складніші інших (розкриття алгоритму шифрування грубою силою проти шифрування довільного блоку шифротекста), ніколи не було доведено, що Р≠NP (або що Р=NP). Однак, більшість людей, що працюють над теорією складності, переконані, що ці класи нерівні [6].

Можна довести, що конкретні NP-проблеми настільки ж важкі, як і будь-яка проблема цього класу.

Питання, чи вірно Р=NP, є центральним невирішеним питанням теорії обчислювальної складності, і не очікується, що воно буде вирішено найближчим часом.