Основні поняття й ознаки теорії складності
Основні поняття й означення теорії складності
У теоретичній криптографії існує два основних підходи до визначення стійкості криптографічних систем і протоколів – теоретично-інформаційний та теоретично-складносний.
Теоретично-інформаційний підхід передбачає, що супротивник, атакуючий криптографічну систему, не має навіть теоретичної можливості отримати інформацію, достатню для досягнення своїх цілей. Класичний приклад – шифр Вернама з одноразовими ключами, абсолютно стійкий проти пасивного супротивника. Цей шифр є абсолютно надійним.
Нагадаємо, що шифр Вернама (одноразового блокноту) був винайдений в 1917 році Гілбертом Вернамом. У ньому була використана операція побітового додавання за модулем 2. Перед шифруванням повідомлення подають у двійковій формі. Ключем є будь-яке двійкове слово, однакової з довжини. Криптотекст отримують таким шляхом: . Розшифрування в шифрі одноразового блокноту збігається із шифруванням . Це зрозуміло, оскільки
Якщо супротивник не знає ключа , то з підслуханого криптотексту він абсолютно нічого не дізнається про повідомлення . Для супротивника усі ключі є рівноймовірними. Двійкове слово може бути криптотекстом для будь-якого іншого повідомлення , якщо б шифрування відбувалось з використанням якогось іншого ключа , а саме . Наприклад, запишемо слово „БАНАН” у двійковій формі: 000001 000000 010001 000000 010001.
Нехай ключем буде двійкова послідовність
.
Отримуємо криптотекст
.
Але такий самий криптотекст ми отримаємо, якщо зашифруємо повідомлення „ГРУША” ключем
.
Теорія складності є методикою аналізу обчислювальної складності різних криптографічних методів і алгоритмів. Вона порівнює криптографічні методи та алгоритми і визначає їх надійність. Теорія інформації стверджує можливість злому всіх криптографічних алгоритмів (окрім одноразових блокнотів). Теорія складності повідомляє, чи можна їх зламати до того, як настане теплова загибель Всесвіту.
Складність алгоритму визначається обчислювальними потужностями, необхідними для його виконання. Обчислювальну складність алгоритму часто визначають двома параметрами: Т (часова складність) та S (просторова складність або вимоги до пам’яті). Як Т так і S звичайно відображуються як функції від , де – розмір вхідних даних (існують також інші міри складності: число випадкових бітів, наскільки широкий канал зв’язку, об’єм даних тощо).
Обчислювальну складність алгоритму звичайно виражають через символ „О велике”, що вказує порядок величини обчислювальної складності. Це просто член розкладення функції складності, що найшвидше зростає за умови зростання ; всі члени нищого порядку ігноруються. Наприклад, якщо часова складність порядку , то вона виражається як .
Часова складність, виміряна подібним чином, не залежить від реалізації.
Не потрібно знати ні точного часу виконання окремих інструкцій, ні числа бітів, які являють різні змінні, ні навіть швидкості процесора. Один комп’ютер може бути на 50% швидший від іншого, а в третього ширина шини даних може бути вдвічі більше, проте складність алгоритму, що оцінена порядком величини, не зміниться. І це не є хитрим трюком. Під час оцінки доволі складних алгоритмів усім іншим можна знехтувати (з точністю до постійного множника).
Оцінка обчислювальної складності наочно демонструє, як об’єм вхідних даних впливає на вимоги до часу та об’єму пам’яті.
Наприклад, якщо , подвоєння вхідних даних подвоїть і час виконання алгоритму. Якщо , додання лише одного біту до вхідних даних подвоїть час виконання алгоритму.
Головною ціллю теорії складності є забезпечення механізмів класифікації обчислювальних задач згідно з ресурсами, необхідних для їх розв’язання. Класифікація не має залежати від конкретної обчислювальної моделі, а скоріше оцінювати внутрішню складність задачі.
Ресурси, що оцінюються, як уже було зазначено раніше, можуть бути такими: час, простір пам’яті, випадкові біти, кількість процесорів, тощо, але зазвичай головним фактором є час, а іноді й простір.
Теорія розглядає мінімальний час і об’єм пам’яті для розв’язання найскладнішого варіанта задачі на теоретичному комп'ютері, відомому як машина Тьюринга. Машина Тьюрінга є кінцевим автоматом з безкінечною магнітною стрічкою пам’яті для читання/запису. Це означає, що машина Тьюрінга – реалістична обчислювальна модель.
Задачі, які можна розв’язати за допомогою алгоритмів з поліноміальним часом, називають такими, що можуть бути розв’язані, оскільки за умов нормальних вхідних даних вони можуть бути розв’язані за прийнятний час (точне визначення "прийнятності" залежить від конкретних умов).
Задачі, які можуть бути вирішені тільки за допомогою суперполіноміальних алгоритмів з поліноміальним часом, є обчислювально складними навіть за відносно малими значеннями .
Що ще гірше, Алан Тьюрінг доказав, що деякі задачі неможливо розв’язати. Навіть без урахування часової складності алгоритму, створити алгоритм для їх розв’язання неможливо.
Задачі можна розбити на класи у відповідності зі складністю їх розв'язання. Найважливіші класи й очікувані співвідношення між ними показані на рис. 1.
Клас , що є найнижчим, містить усі задачі, які можна розв’язати за поліноміальний час. До класу входять усі задачі, які можна розв’язати за поліноміальний час тільки на недетермінованій машині Тьюрінга (це варіант звичайної машини Тьюрінга, що може робити припущення). Така машина робить припущення щодо розв’язку задачі – чи „вдачно вгадуючи”, чи перебираючи усі припущення паралельно – та перевіряє своє припущення за поліноміальний час.
Рисунок 1 – Класи складності
Важливість – задач у криптографії визначається умовою, що за недетермінований поліноміальний час можна зламати багато симетричних алгоритмів та алгоритмів з відкритим ключем. Для даного шифротексту , криптоаналітик просто вгадує відкритий текст і ключ , потім поліноміальний час виконує алгоритм шифрування по входах і та перевіряє, чи рівний результат .
Приклад – криптосистема з відкритим ключем. Вам уже відомо, що вона визначається трьома алгоритмами: алгоритмом генерації ключів, алгоритмом шифрування та алгоритмом розшифрування. Алгоритм генерації є загальнодоступним. Хто завгодно може подати на вхід алгоритму рядок r належної довжини й отримати пару ключей (K1,K2). Відкритий ключ K1 - публікується, а секретний ключ K2 і випадковий рядок r – зберігаються в секреті. Нагадаємо, що криптосистема RSA запропонована в 1977 році, і є однією з найбільш популярних криптосистем з відкритим ключем. Назва системи утворена з перших букв прізвищ її творців – Рональда Райвеста, Аді Шаміра і Леонарда Адлемана.
Генерування ключів. Обирають два достатньо великих простих числа і .
Для їх добутку функція Ейлера буде дорівнювати (в теорії чисел використовують поняття функції Ойлера , під якою розуміють кількість чисел менших від і взаємопростих з ). Потім випадковим чином вибирають число е, яке не перевищує значення і буде взаємопростим з ним. Для цього числа е за алгоритмом Евкліда знаходять елемент d, зворотний до е, тобто такий, що і .
Цей запис у теорії чисел означає, що добуток при діленні на число дає залишок рівний 1 (читається порівнян з одиницею за модулем ).
У результаті:
Як відкритий ключ пара чисел та .
Як секретний ключ – число d.
Шифрування виконується блоками. Для цього повідомлення записують у цифровому вигляді та розбивають на блоки так, що кожний блок являє число, яке не перевищує . Скажімо, якщо блок М записаний у двійковому вигляді довжини , то має виконуватися .
Алгоритм шифрування Е в системі RSA полягає в піднесенні двійкового числа М до степеня . Запишемо це так
.
У результаті виходить шифроблок .
Дешифрування. Алгоритм дешифрування шифроблоку полягає у піднесенні двійкового числа С до степеня , тобто
.
Для простоти викладення припустимо, що відкритий текст і криптограма мають однакову довжину n. Крім того, вважаємо, що відкритий текст, криптограма й обидва ключі – рядки в двійковому алфавіті.
Припустимо, що супротивник атакує цю криптосистему. Йому відомий відкритий ключ K1. Він перехопив криптограму d і намагається знайти повідомлення М, де =. Оскільки алгоритм загальновідомий, супротивник може послідовно перебирати всі повідомлення довжини n, обчислювати для кожного такого повідомлення криптограму і порівнювати Dі з D. Якщо Dі = D, то Mі - шуканий текст. Якщо пощастить, то відкритий текст буде знайдений швидко. У найгіршому випадку перебір буде виконаний за час приблизно 2n T(n), де T(n) - час, потрібний на обчислення функції E1 від повідомлення довжини n. Якщо повідомлення мають довжину біля 1000 бітів, то такий перебіру є на практиці, навіть за допомогою найпотужніших комп’ютерів. Наведений алгоритм пошуку відкритого тексту називають алгоритмом повного перебору або „метод брутальної сили”.
Одним з інших найпростіших алгоритмів пошуку відкритого тексту – угадування. Цей алгоритм потребує малої кількості обчислень, але спрацьовує знехтовно низькою вірогідністю.
Насправді супротивник може намагатися атакувати криптосистему різними шляхами, використовувати різноманітні, більш складні алгоритми пошуку відкритого тексту.
Клас містить у собі клас , оскільки будь-яку задачу, що можна розв’язати за поліноміальний час на детермінованій машині Тьюрінга, можна розв’язати й на недетермінованій машині Тьюрінга за поліноміальний час, просто етап припущення опускається.
Якщо всі задачі класу розв’язуються за поліноміальний час і на детермінованій машині Тьюрінга, . Хоч здається очевидним, що деякі задачі набагато складніші від інших (лобове розкриття алгоритму шифрування проти шифрування випадкового блоку шифротексту), ніхто не доказав, що (чи ). Однак більшість спеціалістів, що займаються теорією складності, переконані, що ці класи нерівні. Можна навести приклади. Майкл Кері та Девід Джонсон склали перелік більш ніж 300 -повних задач. Ось деякі з них:
– Задача комівояжера. Комівояжер повинен об’їхати різних міст, використовуючи тільки один бак з пальним (задано максимальну відстань, яку він може проїхати). Чи існує такий маршрут, що дозволяє йому відвідати кожне місто лише один раз, використовуючи цей єдиний бак з пальним?
– Задача про трійні шлюби. У кімнаті чоловіків, жінок і священиків (жерців, равінів тощо). Окрім того існує список припустимих шлюбів, записи яких містять одного чоловіка, одну жінку й одного священика, що згоден провести обряд. Чи можливо, за умов цього списку, побудувати шлюбів так, щоб кожен чи вступав у шлюб тільки з однією людиною, чи реєстрував тільки один шлюб.
Наступним у ієрархії складності йде клас . Задачі класу можна розв’язати в поліноміальному просторі. До класу входить клас , але ряд задач вважають більш складним ніж задачі . Звісно, це поки що не може бути доведено. Відомий клас т.з. -повних задач, що мають таку властивість: якщо будь-яка з них є -задачею, то і якщо будь-яка з них є - задачею, то .
І, нарешті, існує клас . Ці задачі розв’язуються за експоненційний час. На теперішній час можна довести, що -повні задачі неможливо розв’язати за детермінований поліноміальний час. Крім того доведено, що .
Дамо деякі визначення. Ми говоритимемо про алгоритми.
Алгоритм – це чітко задана обчислювальна процедура, що приймає змінні вхідні дані і зупиняється з видачею вихідних даних.
Звичайно, термін „чітко задана обчислювальна процедура” є математично неточною. Вона може бути зроблена точною за допомогою формальних обчислювальних моделей, таких як машини Тьюрінга, машини випадкового доступу чи булеві схеми. Однак, чим мати справу з технічними складностями таких моделей, краще розглядати алгоритм як комп’ютерну програму, записану на деякій конкретній мові програмування для