Главная | Обратная связь

Теоретичні відомості

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

Рис. 1 Приклад зашифрованого тексту

Відкритий текст: a b c d e f g h I j k l m n o p q r s t u v w y z

Шифрований текст: D E F G H I J K L M N O P Q R S T U W Y Z

Якщо в рядку "Шифрований текст" допустити використання кожної з перестановок 26 символів алфавіту, то ми одержимо 26!, або більш ніж 4 х 10²⁶ можливих ключів. Це на 10 порядків більше, ніж розмір простору ключів DES, і це здається достатнім для того, щоб унеможливити успішне застосування криптоаналізу на основі методу послідовного перебору.

Однак для криптоаналітика існує й інша лінія атаки. Якщо криптоаналітик має уявлення про природу відкритого тексту (наприклад, про те, що це зашифрований текст англійською мовою), можна використати відому інформацію про характерні ознаки, властиві текстам відповідною мовою. Щоб показати, як цей підхід застосовується на практиці, розглянемо невеликий приклад. Припустимо, нам потрібно розшифрувати наступний зашифрований текст.

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

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

Рис. 2. Відносна частота появи букв в англійському тексті

Порівнюючи ці результати з даними, показаними на рис. 2, можна припустити, що, швидше за все, букви Р и Z шифрованого тексту є еквівалентами букв е и t відкритого тексту, хоча важко сказати, якій саме букві - Р або Z - відповідає е, а який - t. Букви S, U, ПРО, М и Н, що володіють відносно високою частотою появи в тексті, швидше за все, відповідають буквам з множини {г, n, i, о, a, s}.. Букви з низькою частотою появи (а саме А, В, G, Y, I, J), очевидно, відповідають буквам множини {w,v,b,k,x,q,j,z}.

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

Один з дуже ефективних методів полягає в підрахунку частоти використання комбінацій, що складаються із двох букв. Такі комбінації називають біграмами. Для значень відносної частоти появи в тексті біграмм теж можна побудувати гістограму, подібну показаної на рис. 2. Відомо, що в англійській мові найпоширенішою є біграма th. У нашому шифрованому тексті найчастіше (три рази) зустрічається комбінація ZW. Тому можна припустити, що Z відповідає t, a W - h. Тоді з раніше сформованої гіпотези випливає, що Р відповідає е. Зауважимо, що в шифрованому тексті буквосполучення ZWP є, і тепер ми можемо представити його як the. В англійській мові the є найпоширенішою триграмою (тобто комбінацією із трьох букв), тому можна сподіватися, що ми рухаємося в правильному напрямку.

Тепер зверніть увагу на комбінацію ZWSW у першому рядку. Звичайно, ми не можемо сказати з повною впевненістю, що ці букви належать тому самому слову, але, якщо припустити, що це так, вони відповідають слову th?t. Звідси робимо висновок, що букві S відповідає а.

Тепер ми маємо наступний результат.

З'ясувавши значення всього лише чотирьох букв, ми розшифрували вже значну частину повідомлення. Продовжуючи аналіз частоти появи букв, а також застосовуючи метод «проб і помилок», залишається проробити зовсім небагато роботи, щоб отримати остаточну відповідь. Розшифрований вихідний текст (з доданими в нього пробілами) має такий вигляд.

Моноалфавітні шифри легко розкриваються, тому що вони успадковують частоту вживання букв оригінального алфавіту. Контрзаходом у цьому випадку є застосування для однієї букви не одного, а декількох замінників (називаних омофонами). Наприклад, букві е вихідного тексту може відповідати кілька різних символів шифру, (скажемо, 16, 74, 35 й 21), причому кожен такий символ може використовуватися або по черзі, або за випадковим законом. Якщо число символів-замінників, призначених букві, вибрати пропорційним частоті появи цієї букви, то підрахунок частковості вживання букв у шифрованому тексті стає безглуздим. Великий математик Карл Фрідріх Гаусс (Carl Friedrich Gauss) був упевнений, що з використанням омофонів він винайшов шифр, що неможливо зламати. Але навіть при вживанні омофонів кожному елементу відкритого тексту відповідає тільки один елемент шифрованого тексту, тому в останньому як і раніше повинні спостерігатися характерні показники частоти повторення комбінацій декількох букв (наприклад, біграм), і в результаті завдання криптоаналізу як і раніше залишається досить елементарним.

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

Завдання:

1. Отримати у викладача згідно з варіантом приклад текстового файлу, зашифрованого шифром Цезаря.

2. Створити програму, що реалізує метод крипто аналізу на основі частотного аналізу шифрованого тексту.

3. Підготувати і захистити звіт.