Захист інформації (стр. 9 из 15)

(2.7)

Із графа, який представлено на мал.2.3. і який показує можливості шифрування при рівноймовірних символах ключа слідчить, що

, .

Звідси р(Е) =р(М=0) р(Е|М=0) +р(М=1) р(Е|М=1) =0.5(р(М=0) +р(М=1)) = 0.5 і отимаємо

(2.8)

Останнє рівняння і є умовою теоретичної недешифруємості.

Відзначимо, що дана система має суттєвий недолік, який полягає у тому, що потрібна довжина ключа N повинна дорівнювати довжині повідомлення, тому необхідна генерація, передача у секреті, зберігання великого числа біт ключа, що робить розглядаєму систему дорогою та непридатною для масового використання, доступною лише для привілейованих користувачів. Але поки на доведено, що умова n=N є необхідною для побудови ТНДШ.

Доведемо: необхідна умова ТНДШ складається з того, що число можливих кодів, використовуємих у ТНДШ повинно бути не менш, ніж число повідомлень, які засекречуються на цих ключах. Дійсно, нехай є L можливих повідомлень

. Виберемо фіксований ключ . При одному й тому ж ключі різні повідомлення переходять у різні кріптограми з ймовірністю (граф такої системи

шифрування - на мал.2.5.

Мал.2.5. Граф шифрування одним ключом.

Мал.2.6. Граф шифрування в одну криптограму.

Оскільки передбачається, що система є ідеальною, то по визначенню для будь-якого повідомлення

та кріптограми повинна виконуватися умова: , з якого, враховуючи, що

(2.9)

і виходить, що

. Тоді для будь-якої обраної кріптограми (наприклад ) існують нульові ймовірності переходу у неї з будь-якого повідомлення , але оскільки різні повідомлення можуть переходити в одну й ту ж саму кріптограму тільки на різних ключах, то кожному такому переходу можуть відповідати різні ключі .

Відповідний граф для отримання кріптограми

представлений на мал.2.6. Тоді ми отримаємо стільки ж ключів, скільки є повідомлень, тобто R.

Нехай ключ представляє собою послідовність довжиною N із алфавіта К об’ємом

. Тоді загальне число ключів буде дорівнювати . Порівнюючи це число ключів з числом повідомлень , де m - об’єм алфавіта джерела, n - довжина повідомлення, отримаємо, що необхідна умова ТНДШ приймає вигляд

, або (2.10)

У частному випадку, коли L=m, отримаємо, що N=n, що співпадає з достатньою умовою, яку отримали вище для прикладу двоїчного кодування по модулю два.

Але нема необхідності шифрувати усі послідовності, які можна скласти із символів джерела повідомлень. У дійсності можна шифрувати тільки так звані "типічні" послідовності, які з’являються з ненульовою ймовірністю.

Із теорії інформації бачимо, що при

число типових послідовностей ~ , де H(M) - ентропія джерела повідомлення. Типові послідовності приблизно рівноймовірні, їх сумарна ймовірність збігається до одиниці. На підставі раніше доведеного твердження, шифруючи тільки типові послідовності, отримаємо необхідну умову ТНДШ:

, або (2.11)

Оскільки для будь-яких джерел Н(М) <logm, то (7) дає меньш жорсткі умови, ніж (6). Чим більше надлишок джерела, тим менше його ентропія. Таким чином для забезпечення найбільш економного з точки зору ключа ідеального шифра, необхідно попередньо стиснути повідомлення, а потім провести додавання по модулю два з ключовою послідовністю.

Таким чином, необхідною умовою ТНДШ є пропорційність довжини ключа довжині послідовності. Тільки коефіцієнт цієї пропорційності для надлишкових джерел може бути декілька зменшений в порівнянні з одиницею.

Приклад: нехай задані такі параметри джерела повідомлень та ключа: L=2, m=32, ентропія джерела Н(М) =0.5 біта на букву. Тоді при шифруванні усіх послідовностей джерела довжина ключа повинна бути N=5n, тоді як після стиснення повідомлення такого джерела вони можуть бути зменшені вдвічи.

2.4. Поняття про відстань єдиності

Розглянемо декілька інший підхід до поняття стійкості кріптосистеми, яка не залежить від розрахункової потужності опонента, який зв’язан з невизначеністю дешифрування при відомому ключі.

Будемо вважати, що опоненту відома кріптограма Е та опис системи шифрування-дешифрування симетричної кріптосистеми, тобто функції f(M,K) та g(E,K), але невідомий ключ К. Використовуючи до прийнятої кріптограми Е усі можливі ключі К, можна спробувати відновити повідомлення, коли серед численності ключів тільки один є вірним, тоді як інші - помилкові. Відбраковку ключів можна виконувати, використовуючи крітерій, який полягає у отриманні осмисленного текста. Однак може статися, що одній кріптограмі будуть відповідати декілька осмисленних розшифровок. У цьому випадку навіть при необмеженій розрахунковій потужності опонента немає засобу, щоб знайти істиний ключ та відновити дійсно зашифроване повідомлення.

- осмислених "типічних" повідомлень. - безглуздих повідомлень.

Мал.2.7. Розшифровка кріптограми тотальним перебором ключів.

Нехай одній кріптограмі відповідає S осмислених розшифровок (мал.2.7). З них

очевидно будуть помилкові, та одна істинна. Передбачемо також, що алфавіти повідомлень та кріптограм, а також довжини послідовностей повідомлень та кріптограм співпадають.

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

у випадку використання кріптосистеми з ключом довжини N, з об’ємом алфавіта ключових даних L, при шифруванні джерела повідомлення з ентропією Н(М) визначається теоремою Шеннона-Хелмна:

(2.15)

де m - об’єм алфавіта, n - довжина повідомлення (кріптограма). Із даного відношення видно, що якщо показник степені більше нуля та достатньо великий, то середнє число помилкових розшифровок буде дуже великим і систему шифрування можна вважати стійкою.

Але з ростом довжини прийнятої кріптограми та при фіксованому числі ключів, показник степені буде падати і коли він наблизиться до нуля, то можна важати, що помилкових розшифровок не буде, тобто нульове значення показника степені є критичним: при довжині кріптограми

, де - довжина кріптограми, яка обертає в нуль показник степені, кожна кріптограма може бути розсекречена єдиним чином, а прі це не так. Величина дає ту мінімальну довжину кріптограми, починаючи з якої помилкові розшифровки будуть відсутні, отже, при переборі всіх ключів кожній кріптограмі буде відповідати єдине повідомлення, яке дійсно передавалося. Така довжина кріптограми називається відстанью єдиності . Знайдемо цю відстань, прирівнюючи до нуля показник степені у (2.15). Розв’язуючи отримане рівняння, знаходимо формулу Шеннона для відстані єдиності.

(2.16)