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

Якби ця інформація була представлена відповідними рядками ASCII символів, вона зайняла б більше місця в пам'яті, але не містила б більше інформації. Аналогічно, поле бази даних "стать" містить тільки один біт інформації, хоча ця інформація може зберігатися як одне з двох 7-байтових ASCII рядків: "ЧОЛОВІК" або "ЖІНКА".

Формально, кількість інформації в повідомленні М вимірюється ентропією повідомлення, що позначається як Н(М). Ентропія повідомлення, що визначає стать, складає 1 біт, а ентропія повідомлення, що визначає день тижня, небагато менше, ніж 3 біти. У загальному випадку ентропія повідомлення, вимірювана в бітах, дорівнює log2п, де п – це кількість можливих значень.[1, 8] При цьому передбачається, що всі значення рівноімовірні. Наприклад, ентропія для рівноімовірної послідовності українських символів дорівнює Н(М)=log232=5 бітів.

Ентропія повідомлення також є мірою його невизначеності. Це кількість бітів відкритого тексту, які потрібно розкрити в шифрі тексту повідомлення, щоб розкрити весь відкритий текст. Наприклад, якщо блок шифртексту "QHP*5M " означає або "ЧОЛОВІК", або "ЖІНКА", то невизначеність повідомлення дорівнює 1. Криптоаналітику потрібно довідатися тільки один правильно обраний біт, щоб розкрити повідомлення. [1]

1.1.3.  Норма мови

Для кожної конкретної мови норма мови у відповідності з [8]дорівнює

де N – це довжина повідомлення. При великих N норма звичайної української мови приймає різні значення від 1,0 біт/літеру до 1,7 біт/літеру. Абсолютна норма мови дорівнює максимальній кількості бітів, що може бути передано кожним символом за умови, що всі послідовності символів рівноімовірні. Якщо в мові L символів, то абсолютна норма в відповідності з [8] дорівнює:

R=log2L

Це максимум ентропії окремих символів.

Для української мови з 32 буквами абсолютна норма дорівнює log232, або 5 біт/букву. Як бачимо абсолютна норма української мови набагато більше її дійсної норми. Це відбувається через те, що природні мови мають високу надмірність. [2]

1.1.4.  Безпека криптосистеми.

Шенон визначив точну математичну модель поняття безпеки криптосистеми. Зміст роботи криптоаналітика складається у визначенні ключа (К), відкритого тексту (Р) або і того, і іншого. Однак, його може улаштувати і деяка вірогідна інформація про Р. [2]

У реальному криптоаналізі в криптоаналітика є деяка вірогідна інформація про Р ще до початку роботи. Він, швидше за все, знає мову відкритого тексту. Ця мова володіє визначеною, зв'язаною з ним надмірністю. Метою криптоаналітика є зміна імовірностей, зв'язаних з кожним можливим відкритим текстом. При такому підході до криптоаналізу кінцевим результатом для криптоаналітика можна вважати єдино можливий або декілька найбільш ймовірних відкритих текстів.

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

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

Криптоаналітики використовують природну надмірність мови для зменшення числа можливих відкритих текстів. Чим багатша мова, тим легше її аналізувати. З цієї причини багато криптографічних реалізацій перед шифруванням використовують програми стиску для зменшення розміру тексту. Стиск зменшує надмірність повідомлення разом з обсягом роботи, необхідним для його шифрування і дешифрування.

Ентропія криптосистеми є мірою розміру простору ключів (К). Вона приблизно дорівнює логарифму числа ключів по основі 2:

Н(К)=log2К

Ентропія криптосистеми з 64-бітовим ключем дорівнює 64 бітам, ентропія криптосистеми з 56-бітовим ключем дорівнює 56 бітам. У загальному випадку, чим більше ентропія, тим важче зламати криптосистему.

1.1.5.  Відстань унікальності.

Для повідомлення довжиною п число різних ключів, що можуть розшифрувати шифртекст повідомлення в якийсь осмислений відкритий текст, визначається наступною формулою [3]:

2H(K)-nD-1

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

Для більшості симетричних криптосистем відстань унікальності визначається як ентропія криптосистеми поділена на надмірність мови.

U=H(K)/D

Наприклад, якщо ми шифруємо український текст алгоритмом DES (фактична довжина ключа – 56 біт, довжина одного блоку повідомлення – 64 біт), то при надмірності мови, прийнятої 3,6 біт, відстань унікальності буде дорівнювати 68 біт. Результат показує, що при довжині блоку менш 68 біт, шифртекст ймовірно розшифровується декількома способами.

Відстань унікальності є не точним, а вірогідним значенням. Вона дозволяє оцінити мінімальну кількість шифротексту, при розкритті якого грубою силою є, імовірно, тільки один розумний спосіб дешифрування. Звичайно чим більше відстань унікальності, тим краще криптосистема.