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

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

Таблиця 1.3. Відстані унікальності українського тексту, зашифрованого алгоритмами з різною довжиною ключа [4].

Шенон визначив криптосистему з нескінченною відстанню унікальності, що має ідеальну таємницю. [3] Ідеальна криптосистема не обов'язково є повністю безпечною, хоча повністю безпечна криптосистема обов'язково буде й ідеальною. Якщо криптосистема має ідеальну таємницю, то навіть при успішному криптоаналізі залишиться деяка невизначеність, чи є відновлений відкритий текст реальним відкритим текстом. [6]

1.1.6.  Плутанина і дифузія

Двома основними методами маскування надмірності відкритого тексту повідомлення, згідно Шенону, служать плутанина і дифузія [3].

Плутанина маскує зв'язок між відкритим текстом і шифртекстом. Вона запобігає спробам знайти в шифртексті надмірність і статистичні закономірності. Найпростішим шляхом створити плутанину є підстановка. У простому підстановочному шифрі, наприклад, шифрі Цезаря, всі однакові букви відкритого тексту заміняються іншими однаковими буквами шифртексту. Сучасні підстановочні шифри є більш складними: довгий блок відкритого тексту заміняється блоком шифртексту, і спосіб заміни міняється з кожним бітом відкритого тексту або ключа. Такого типу підстановки звичайно недостатньо – складний алгоритм німецької Енігми був зламаний у ході другої світової війни. [9]

Дифузія розсіює надмірність відкритого тексту, поширюючи її по всьому шифртексту. Найпростішим способом створити дифузію є транспозиція (також називана перестановкою). Простий шифр перестановки тільки переставляє букви відкритого тексту. Сучасні шифри також виконують таку перестановку, але вони також використовують інші форми дифузії, що дозволяє розкидати частини повідомлення по всьому повідомленню.

Потокові шифри використовують тільки плутанину, хоча ряд схем зі зворотним зв'язком додають дифузію. Блокові алгоритми застосовують і плутанину, і дифузію. Як правило, дифузію саму по собі нескладно зламати, хоча шифри з подвійною перестановкою виявляються стійкіші, ніж інші некомп'ютерні системи. [1]

1.2  Теорія складності

В даному розділі автори викладають початкові відомості з теорії складності. Більш докладно це питання викладено у [1, 6, 10]

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

1.2.1.  Складність алгоритмів

Складність алгоритму визначається обчислювальними потужностями, необхідними для його виконання. Обчислювальна складність алгоритму часто виміряється двома параметрами: Т (часова складність) і S (просторова складність, або вимоги до пам'яті). І Т, і S звичайно представляються у вигляді функцій від п, де п – це розмір вхідних даних. (Існують й інші способи виміру складності: кількість випадкових біт, ширина каналу зв'язку, обсяг даних і т.п.) [6]

Звичайно обчислювальна складність алгоритму виражається за допомогою нотації O(n) і описується порядком величини обчислювальної складності. Це просто член розкладання функції складності, швидше всього зростаючий з ростом n, усі члени нижчого порядку ігноруються. Наприклад, якщо тимчасова складність даного алгоритму дорівнює 4n²+7n+12, то обчислювальна складність порядку n², записується як O(n²). [10]

Часова складність, вимірювана таким чином, не залежить від реалізації. Не потрібно знати ні точний час виконання різних інструкцій, ні число бітів, використовуваних для представлення різних перемінних, ні навіть швидкість процесора. Один комп'ютер може бути на 50 відсотків швидше іншого, а в третього шина даних може бути в два рази ширше, але складність алгоритму, оцінена по порядку величини, не зміниться. Ця нотація дозволяє побачити, як обсяг вхідних даних впливає на вимоги до часу й обсягу пам'яті. Наприклад, якщо Т=O(n), то подвоєння вхідних даних подвоїть і час виконання алгоритму. Якщо T=O(2ⁿ), то додавання одного біта до вхідних даних подвоїть час виконання алгоритму. [1]

Звичайно алгоритми класифікуються відповідно до їх часової або просторової складності. Алгоритм називають постійним, якщо його складність не залежить від n: О(1). Алгоритм є лінійним, якщо його часова складність O(n). Алгоритми можуть бути квадратичними, кубічними і т.д. Усі ці алгоритми – поліноміальні, їхня складність – O(n^m), де m – константа. Алгоритми з поліноміальною часовою складністю називаються алгоритмами з поліноміальним часом.

Алгоритми, складність яких дорівнює , де t – константа, більша, ніж 1, a f(n) – деяка поліноміальна функція від n, називаються експоненціальними. Підмножина експоненціальних алгоритмів, складність яких дорівнює , де с – константа, a f(n) зростає швидше, ніж постійна, але повільніше, ніж лінійна функція, називається суперполіноміальним.