Основніпоняття й означення теорії складності
У теоретичній криптографії існуєдва основних підходи до визначення стійкості криптографічних систем іпротоколів – теоретично-інформаційний та теоретично-складносний.
Теоретично-інформаційний підхідпередбачає, що супротивник, атакуючий криптографічну систему, не має навітьтеоретичної можливості отримати інформацію, достатню для досягнення своїхцілей. Класичний приклад – шифр Вернама з одноразовими ключами, абсолютностійкий проти пасивного супротивника. Цей шифр є абсолютно надійним.
Нагадаємо, що шифр Вернама(одноразового блокноту) був винайдений в 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 />-повних задач.Ось деякі з них:
– Задача комівояжера. Комівояжерповинен об’їхати /> різних міст, використовуючитільки один бак з пальним (задано максимальну відстань, яку він може проїхати).Чи існує такий маршрут, що дозволяє йому відвідати кожне місто лише один раз,використовуючи цей єдиний бак з пальним?
– Задача про трійні шлюби. У кімнаті/> чоловіків,/> жінок і /> священиків(жерців, равінів тощо). Окрім того існує список припустимих шлюбів, записи якихмістять одного чоловіка, одну жінку й одного священика, що згоден провестиобряд. Чи можливо, за умов цього списку, побудувати /> шлюбів так, щоб кожен чи вступаву шлюб тільки з однією людиною, чи реєстрував тільки один шлюб.
Наступним у ієрархії складностійде клас />.Задачі класу /> можна розв’язати вполіноміальному просторі. До класу /> входить клас />, але ряд задач /> вважають більшскладним ніж задачі />. Звісно, це поки що не може бутидоведено. Відомий клас т.з. />-повних задач, що мають такувластивість: якщо будь-яка з них є />-задачею, то /> і якщо будь-яка з них є/> — задачею,то />.
І, нарешті, існує клас />. Ці задачірозв’язуються за експоненційний час. На теперішній час можна довести, що />-повні задачінеможливо розв’язати за детермінований поліноміальний час. Крім того доведено,що />.
Дамо деякі визначення. Миговоритимемо про алгоритми.
Алгоритм – це чітко задана обчислювальна процедура, щоприймає змінні вхідні дані і зупиняється з видачею вихідних даних.
Звичайно, термін „чітко заданаобчислювальна процедура” є математично неточною. Вона може бути зроблена точноюза допомогою формальних обчислювальних моделей, таких як машини Тьюрінга,машини випадкового доступу чи булеві схеми. Однак, чим мати справу з технічнимискладностями таких моделей, краще розглядати алгоритм як комп’ютерну програму,записану на деякій конкретній мові програмування для конкретного комп’ютера,яка приймає змінні вхідні дані і зупиняється з видачею вихідних даних.
Зазвичай цікавим є знаходженнянайефективнішого (тобто, найшвидшого) алгоритму для вирішення даноїобчислювальної задачі. Час, який витрачає алгоритм до зупинки, залежить від”розміру” конкретної задачі. Крім того, одиниця часу, що використовується, маєбути точною, особливо при порівнянні ефективності двох алгоритмів.
Якщо ми маємо справу з алгоритмом,то вважають зафіксованими два алфавіти: вхідний – А і вихідний – В. Роботаалгоритму полягає у тому, що він отримує на вхід слово вхідного алфавіту, і якрезультат виконання послідовності елементарних операцій, подає на вихід слово увихідному алфавіті.
Залежно від типу алгоритмуговорять, що алгоритм обчислює функцію, розрізнює множину чи мову, знаходитьелемент з певними властивостями.
Час виконання алгоритму на конкретних вхідних данихвизначається як кількість елементарних операцій чи „кроків”, що виконуються.Часто крок використовується для визначення бітової операції. Для деякихалгоритмів буде більш зручним використовувати крок для маркування чогось ще, наприклад,порівняння, машинної команди, машинного тактового циклу, модулярного множеннятощо.
Якщо t (n) £cncдля деякої константи с, то алгоритм вирішуєзадачу за поліноміальний (від довжини входу) час.
Такий алгоритм називаютьполіноміальним, а задачу такою, що вирішується поліноміально.
Поняття поліноміального часу єцентральною концепцією теорії складності обчислень. У рамках цієї концепціївважається, що поліноміальні алгоритми відповідають швидким, ефективним напрактиці алгоритмам, а такі, що вирішуються поліноміально, відповідають легкимзадачам.
Алгоритм, що на безкінечнійпослідовності входів робить більш ніж />кроків, де n – довжинавходу, а с > 0 – деяка константа, називається експоненційним.
Про такий алгоритм говорять, щовін потребує експоненційного часу. Експоненційні алгоритми відповідаютьзагальним поняттям про неефективні на практиці алгоритми.
Так, наприклад, реалізація ідеїнесиметричного шифрування базується на понятті однобічної взаємно однозначноїфункції/>,такої, що при відомому /> порівняно просто обчислити />, однакзворотню функцію /> обчислити (за прийнятний час)неможливо. Цю властивість називають практичною незворотністю. Зазвичайобчислення прямої функції має поліноміальну складність, а зворотної – у кращомувипадку експоненційну. У криптосистемі RSA достатньо просто знайти добуток двохпростих чисел (поліноміальна складність), але задача розкладання великого числана прості співмножники є дуже складною (як мінімум експоненційної складності).Сьогодні не існує жодної однобічної функції, для якої математично була бдоведена її практична незворотність або експоненційна складність. Ті функції,що знайшли довгострокове застосування в криптографії, вважаються однобічними.При цьому можна лише стверджувати, що на сьогодні відомі алгоритми обчисленнязворотної функції зі складністю, що практично може бути реалізована (в рамкахзаданих параметрів).
Часто буває складно отримати часвиконання алгоритму. У таких випадках змушені погодитися на апроксимацію часувиконання, зазвичай можна отримати асимптотичний час виконання, тобтодосліджується, як збільшується час виконання алгоритму з безмежним збільшеннямрозміру вхідних даних. Розглядаються тільки ті функції, що задані на додатнихцілих числах і приймають дійсні значення.
Нехай f та g будутьдвома такими функціями.
Запис f(n)=O(g(n)) означає, що f асимптотично зростає не швидше, ніж g(n),з точністю до постійного кратного, у той час як f(n)=(g(n))означає, що f(n) зростає, принаймні, також асимптотично швидко,як зростає g(n), з точністю до постійного множника.
f(n) = O(g(n))означає, що функція f(n) стає несуттєвою відносно g(n)по мірі зростання n.
При цьому для будь-яких функцій f(n),g(n), h(n)іl(n) справедливітакі властивості і співвідношення:
f (n)=O(g(n)),у випадку. якщо g(n)= (f (n)).
f(n)= -(g(n)), у випадку. якщо f(n) = O(g(n))і(f)n=(g(n)).
Якщоf (n)=O(h(n))і (g)n =O(h(n)), то( f +g)(n)=O(h(n)).
Якщоf (n) =O(h(n))іg(n) =O(l(n)),то( f -g)(n) =O(h(n)l(n)).
Рефлексивність f(n) =O(f(n)).
Транзитивність. Якщо f(n)= O(g(n))іg(n)=O(h(n)), тоf(n) = O(h(n)).
Складність алгоритмів вимірюютькількістю арифметичних операцій (додавань, віднімань, множень і ділень іззалишком), необхідних для виконання всіх дій. Однак це визначення не бере доуваги величини чисел, що беруть участь в обчисленнях. Тому, часто беруть доуваги ще й величину чисел, зводячи обчислення до бітових операцій, тобтооцінюючи кількість необхідних операцій із цифрами 0 і 1, у двійковому записічисел. Це залежить від задачі, що розглядаються.
Даний підхід зручний з такихміркувань. По-перше, у комп’ютерах дані подаються і обробляються у двійковомувигляді, а інші подання в основному використовують під час введення даних і підчас виведення результатів. По-друге, перевід числа /> від однієї основи системиобчислень до іншої виконується швидко і потребує виконання /> арифметичних операцій(ділення з залишком, множення або додаваня чисел), де /> – довжина запису числа /> (основулогарифмам не вказуємо, оскільки воно не впливає на вид оцінки складності).Перехід до іншої основи є рідкісною операцією, затратами на її виконання можназнехтувати. Нарешті, бітова оцінка непогано відображує реальну складністьоперацій, оскільки, як правило, оцінки складності для інших основ системобчислень призводять лише до змін у константному множнику функції оцінкискладності. При оцінці складності обчислювальних задач, звичайно, застосовуютьметоди редукції і піднесення до інших задач з відомими оцінками складності.