O (n) - лінійна складність. Таку складність має, наприклад, алгоритм пошуку найбільшого елемента в невідсортованому масиві. Нам доведеться пройтися по всіх n елементах масиву, щоб зрозуміти, який з них максимальний.
O (log n) - логарифмічна складність. Найпростіший приклад - бінарний пошук. Якщо масив відсортований, ми можемо перевірити, чи є в ньому якесь конкретне значення, шляхом поділу навпіл. Перевіримо середній елемент,
якщо він більше шуканого, то відкинемо другу половину масиву - там його точно немає. Якщо ж менше, то навпаки - відкинемо початкову половину. І так будемо продовжувати ділити навпіл, в результаті перевіримо log n елементів.
O (n
2
) - квадратична складність. Таку складність має, наприклад, алгоритм сортування вставками. У канонічної реалізації він вдає із себе два вкладених циклу: один, щоб проходити по всьому масиву, а другий, щоб знаходити місце чергового елементу уже відсортованої частини. Таким чином, кількість операцій буде залежати від розміру масиву як n * n.
Для наочності наводимо час виконання алгоритму з певною складністю в залежності від розміру вхідних даних при швидкості виконання 10 6
операцій в секунду (Таблиця 3.1).
27
Таблиця 3.1. Час виконання алгоритму з певною складністю в залежності від розміру
вхідних даних при швидкості виконання 10
6
операцій в секунду
Множина задач, для вирішення яких існують алгоритми, схожі за обчислювальною складністю, утворює клас складності.
Розрізняють такі основні класи складності:
•
Клас P - вміщує всі ті проблеми, вирішення яких вважається
«швидким», тобто поліноміально залежать від розміру входу
(наприклад, сортування, пошук, з'ясування зв'язності графів і т.п.).
•
Клас NP - містить задачі, які не в змозі вирішити за поліноміальну кількість часу (наприклад, факторизація, дискретне логарифмування та
інші).
3.2. Межі застосування «грубої сили» до атак на шифри
Найбільш загальний вид атаки на шифр – метод повного перебору (або метод «грубої сили»).
Повний перебір (англ. brute force) - загальний метод вирішення завдань шляхом перебору всіх можливих потенційних рішень.
У криптографії на обчислювальній складності повного перебору
ґрунтується оцінка криптостойкости шифрів. Зокрема, шифр вважається крипостійким, якщо не існує методу «злому» істотно більш швидкого, ніж повний перебір всіх ключів. Криптографічні атаки, засновані на методі
повного перебору, є найбільш універсальними, але і найдовшими.
28
Стійкість до brute-force атаки визначає використовуваний в криптосистемі ключ шифрування. Так, зі збільшенням довжини ключа складність злому цим методом зростає експоненціально. У найпростішому випадку шифр довжиною в n бітів зламуються, в найгіршому випадку, за час О(2 n ). Взагалі будь-яка задача з класу NP може бути вирішена повним перебором, але це вимагатиме експоненціального часу роботи. Існують способи підвищення стійкості шифру до «brute force», наприклад заплутування (обфускація) шифрованих даних, що робить нетривіальним відмінність зашифрованих даних від незашифрованих. Виходячи з фізичних міркувань можна показати, що існує можливість вибрати таку довжину ключа, що таку атаку методом «грубої сили» неможливо буде виконати в принципі, безвідносно до потужностей наявної обчислювальної техніки. Доведення 1 (термодинамічний підхід).За законами термодинаміки поглинання енергії при здійсненні незворотного перетворення має порядок kT, де k=1.4*10 -23 Дж/K, T – температура зовнішнього середовища. Потужність сонячного випромінення Pc3.86 *10 26 Вт. Час існування Всесвіту t c 14 млд. років14*10 9 років 4*10 19 c. Температура Сонця T c 10 6 K. Тоді витрати на одну обчислювальну операцію kT=1.4*10 -23 *10 6 1.4*10 -17 (Дж). Вся енергія виділена Сонцем за час його існування Всесвіту E= Pc* t c 3.86 *10 26 *4*10 19 1.6* 10 46 (Дж). Тому можлива кількість виконаних операцій N=E/ kT1.6* 10 46 / 1.4*10 -17 10 63 А це означає, при довжині ключа шифрування L≥63 перебір всіх варіантів не можна здійснити за час існування Всесвіту. 29
Доведення 2 (гео-протонний підхід).
Маса Землі M6*10 24
кг, маса протону m1.6*10
-27
кг; тобто Земля містить
N=M/m 6*10 24
/
1.6*10 27
3.8*10 51
протонів.
Співставим кожному протону комп’ютер і вважатимемо, що на виконання однієї операції в ньому витрачається час t, за який світловий промінь
(швидкість c3*10 10
м/c) проходить відстань, рівну діаметру протона (d10
-15
м): t= d/c10
-15
/3*10 10
1/3*10
-25
(с).
Це означає, що швидкість роботи одного такого уявного комп’ютера v= t
-1
3*10 25
операцій/с.
Сумарна швидкодія всіх «протонних» комп’ютерів V=N*v 3.8*10 51
*
3*10 25
10 76
операцій/с. За весь час існування Всесвіту t c
4*10 19
c можна виконати не більше ніж M=V* t c
10 76
* 4*10 19
10 95
операцій.
Знову ж таки, це означає, при довжині ключа шифрування L≥95 перебір всіх варіантів не можна здійснити за час існування Всесвіту.
Резюмуючи, робимо наступний висновок: «хорошим» ключем шифрування
(тобто таким, який не можна підібрати методом «грубої сили») є ключ довжиною не менше L≥100.
3.3. Абсолютна криптостійкість шифрів
Абсолютна крипостійкість означає, що:
• результатом розшифрування може бути будь-який текст,
• не існує ніякого способу перевірки, що розшифрування виконане правильно.
Доведення існування абсолютно стійких алгоритмів шифрування було виконано Клодом Шенноном та опубліковано в роботі «Теорія зв'язку в секретних системах» (1946 рік). Там же визначені вимоги до такого роду систем:
1. Ключ генерується для кожного повідомлення (кожен ключ використовується один раз).
30
2. Ключ статистично надійний (тобто ймовірності появи кожного з можливих символів однакові, символи в ключовий послідовності незалежні і випадкові). 3. Довжина ключа дорівнює або більше довжини повідомлення. Стійкість цих систем не залежить від того, якими обчислювальними можливостями володіє криптоаналітик. Майже всі використовувані на практиці шифри характеризуються як умовно надійні, оскільки вони можуть бути розкриті в принципі при наявності необмежених обчислювальних можливостей. Абсолютно надійні шифри не можна зруйнувати навіть при наявності необмежених обчислювальних можливостей. Єдиним відомим шифром, який задовольняє вимогам абсолютної криптостійкості, є шифр Вернама. Шифр Вернама (інша назва: англ. One-time pad - схема одноразовихблокнотів) названий на честь телеграфіста AT & T Гільберта Вернама, який в 1917 році побудував телеграфний апарат, що виконував цю операцію автоматично - треба було тільки подати на нього стрічку з ключем. Для шифруівння відкритий текст «сумується» з ключем (який називається одноразовим блокнотом або шифроблокнотом) аналогічно розширеному шифру Цезаря. Але при цьому ключ повинен задовольняти трьом критично важливими умовам: 1. Бути істинно випадковим. 2. Співпадати за розміром з заданим відкритим текстом. 3. Застосовуватись тільки один раз. Будемо вважати, що число символів розширеного алфавіту, тобто сукупності літер, а також знаків пунктуації та пропусків між словами, дорівнює N. Занумерувавши всі символи розширеного алфавіту числами від 0 до N, текст, що передається, можна розглядати як послідовність {a n } чисел множини А = {0,1,2, ..., N}. 31
Маючи випадкову послідовність {k n
} з чисел множини А тієї ж довжини що
і ключ, складаємо по модулю N число a n
переданого текту з відповідним числом k n
ключа a n
+ k n
≡ c n
(mod N), 0 ≤ c n
≤ N, одержимо послідовність {c n
}
знаків шифрованого тексту.
Щоб отримати переданий текст, можна скористатися тим ж ключем: a n
≡ c n
- k
n
(mod N), 0 ≤ a n
≤ N.
У двох абонентів, що знаходяться в секретному листуванні, є два однакових блокнота, складених з відривних сторінок, на кожній з яких надрукована таблиця з випадковими числами або буквами, тобто випадкова послідовність чисел з множини А. Таблиця має тільки дві копії: одна використовується відправником, інша - одержувачем.
Приблизна сторінка шифроблокноту показана на Рис.3.1.
Рис.3.1. Приклад сторінки шифроблокноту
Відправник свій текст шифрує зазначеним вище способом за допомогою першої сторінки блокнота. Зашифрувавши повідомлення, він знищує
використувану сторінку і відправляє її іншому абоненту. Одержувач шифрованого тексту розшифровує його і також знищує використаний лист блокнота.
Неважко бачити, що одноразовий шифр не можна розкрити в принципі, так як символ у тексті може бути замінений будь-яким іншим символом і цей вибір абсолютно випадковий.
3.4. Основи квантової криптографії
Квантова криптографія́ – наука, що вивчає методи захисту систем зв’язку
і базується на принциповій непорушності закономірностей квантової фізики,
32
об’єкти якої забезпечують процеси безпечного передавання інформації між легітимними користувачами. Основними. засадами є: • постулат вимірювання (результат принципу невизначеності Гейзенберґа) та • теорема про заборону клонування. Принцип невизначеності – це фундаментальна нерівність (відношення невизначеностей), згідно з якою усі динамічні параметри поділяють на дві групи: перша – часові та просторові координати; друга – імпульс та енергія. При чому неможливо одночасно виміряти параметри з різних груп (напр., місцерозташування та енергію об’єкта). Теорема про заборону клонування стверджує неможливість створення точних (на 100 %) копій квантових об’єктів. Ці властивості не притаманні класичним системам зв’язку і забезпечують абсолютну й безумовну стійкість квантової криптографії. В останні роки значний інтерес викликають системи захисту інформації на базі методів квантової криптографії. Виокремлюють такі напрями, як квантовий розподіл ключів (КРК), квантовий прямий безпечний зв’язок (КПБЗ), квантове розділення секрету (КРС), квантовий цифровий підпис (КЦП) та кванттова стеганографія. Ідею використання квантових об’єктів для захисту інформації вперше запропонував С. Вайснер (1970 рік). В 1984 році Ч. Беннет (компанія IBM) та Ж. Брассар (Монреальський університет) розвинули її і запропонували перший протокол квантової криптографії ВВ84, що став альтернативним вирішенням проблеми розподілу ключів шифрування. У ньому для передачі даних використовуються фотони, поляризовані в чотирьох різних напрямках, в двох базисах - під кутом 0 і 90 градусів (позначається знаком +) або 45 і 135 градусів (позначається знаком x). Відправник повідомлення Аліса поляризує кожен фотон в випадково обраному базисі, а потім відправляє його одержувачу Бобу. Боб вимірює кожен 33 фотон, теж в випадково обраному базисі. Після цього Аліса по відкритому каналу повідомляє Бобу послідовність своїх базисів, і Боб відкидає неправильні (не співпали) базиси і повідомляє Алісі, які дані «не пройшли». При цьому самі значення, отримані в результаті вимірів, вони по відкритому каналу не обговорюють. Якщо шпигун Єва захоче перехопити секретний ключ, вона повинна буде вимірювати поляризацію фотонів. Оскільки вона не знає базису, то повинна буде визначати його випадковим чином. Якщо базис буде визначено неправильно, то Єва не отримає вірних даних, а крім того, змінить поляризацію фотона. Помилки, що з’являться, відразу виявлять і Аліса, і Боб. Описану схему можна проілюструвати наступним чином: Аліса надсилає фотони, що мають одну з чотирьох можливих поляризацій, яку вона обирає випадково. Для кожного фотона Боб обирає випадково тип вимірювання: прямолінійна поляризація (+), або діагональна (х). Боб записує та таємно зберігає отримані результати вимірювань. Боб відкрито оголошує типи вимірювань, які він обрав для кожного фотона, а Аліса повідомляє йому, які вимірювання були правильними. Аліса і Боб зберігають всі результати, що були отримані у тих випадках, коли Боб застосував правильний тип вимірювання. Ці результати переводять у біти (0 і 1), послідовність яких і є результатом квантового розподілу ключа. Протокол ВВ84 вважають основоположником протоколів квантової криптографії. Нині існують вже кілька десятків декілька подібних систем, які вийшли на світовий ринок і позиціонуються як надійні системи розподілу ключів та криптографічного захисту інформації. 34
Першим у світі комерційним рішенням була система QPN Security Gateway
(QPN-8505), запропонована американською компанією MagiQ. Вона пропонує
захист VPN за допомогою КРК (бл. 100 ключів 256 біт за секунду на відстань до 140 км) та інтегроване шифрування. За допомогою цієї системи можна організувати захищену квантову мережу.
Іншим ефективним рішенням є система КРК Clavis швейцарської компанії
ID Quantique. З її допомогою можна здійснювати захищений розподіл ключів шифрування між двома абонентами на відстань до 100 км. Крім того, компанія пропонує квант. систему Cerberis. Ця система може розподіляти ключі на відстань до 50 км.
На початку 21 ст. британською компанією Toshiba Research Europe Ltd представлено систему КРК Quantum Key Server, яка відрізняється простотою своєї архітектурири та забезпечує генерацію близько 100 ключів (довжиною
256 біт) за секунду та їхнє одностороннє передавання від передавача до приймача.
Інша британська компанія QinetiQ запропонувала першу у світі
комп’ютерну мережу, що використовує квантову криптографію, – Quantum Net
(Qnet). Максимальна довжина ліній зв’язку цієї мережі становить 120 км.
35
| 
Скачать 1.04 Mb.