Методи підстановки (переклад за Таненбаумом)

Методи підстановки

У шифрах, заснованих на методі підстановок, кожен символ або група символів замінюється іншим символом або групою символів. Одним з найдавніших шифрів є, приписаний Юлію Цезарю, шифр Цезаря. Цей шифр замінює всі букви алфавіту на інші за допомогою циклічного зсуву на три позиції. Так літера a стає буквою D, b стає E, c перетворюється в F, … , а z – C. Наприклад, слово attack перетворюється в DWWDFN. У наших прикладах відкритий текст буде позначатися стрічковими буквами, а зашифрований текст з – прописними.


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

Наступне вдосконалення полягає у встановленні відповідності кожному зустрітому у відкритому тексті символу іншого символу. Наприклад,

відкритий текст: a b c d e f g h i j k l m n o p q r s t u v w x y z
зашифрований текст: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

Така система називається моноалфавітним підстановочним шифром, ключем до якого є 26-символьна стрічка відповідна повному алфавіту. У нашому прикладі слово attack буде виглядати, як QZZQEA.
На перший погляд, така система може здатися надійною, так як, навіть якщо криптоаналітику відома загальна система, він не знає, який з 26! ≈ 4 × 1026 можливих варіантів ключа застосувати. На відміну від шифру Цезаря застосування методу простого перебору в даному випадку дуже сумнівне. Навіть при витратах на 1 нс перевірку одного варіанту ключа, щоб перепробувати всі ключі, мільйону комп’ютерних чіпів, що працюють одночасно, знадобиться близько 10 000 років.

Тим не менше подібний шифр легко зламується навіть при наявності досить невеликих фрагментів зашифрованого тексту. Для атаки шифру може бути використана перевага статистичних характеристик природних мов. Наприклад, в англійській мові буква e зустрічається в тексті найчастіше. Слідом за нею по частоті використання йдуть букви t, o, a, n, i і т. д. Найбільш часто зустрічаються комбінації з двох символів, або діграми th, in, er, re і an. Найчастіше зустрічаються комбінації з трьох символів, або триграми the ing, and і ion.

Криптоаналітик, що намагається зламати моноалфавітний шифр, почне з того, що порахує відносні частоти всіх символів алфавіту в зашифрованому тексті. Потім він може спробувати замінити найбільш часті символ буквою e, а наступною за частотою — літерою t. Потім він подивиться на триграми і спробує знайти що-небудь схоже на tXe, після чого він зможе припустити, що X — h. Аналогічно, якщо послідовність thYt зустрічається досить часто, то, ймовірно, Y позначає символ a. Володіючи цією інформацією, криптоаналітик може пошукати часто часті триграми виду aZW, що, швидше за все, означає and. Продовжуючи у тому ж дусі, вгадуючи літери, діграми, триграми і знаючи, які послідовності символів є найбільш імовірними, криптоаналітик буквально відновлює вихідний текст.

Інший метод полягає у вгадуванні відразу цілого слова або фрази. Наприклад, розглянемо наступний зашифрований текст, отриманий від бухгалтерської фірми (розбитий на блоки по п’ять символів):

CTBMN BYCTC BTJDS QXBNS GSTJC BTSWX CTQTZ CQVUJ
QJSGS TJQZZ MNQJS VLNSX VSZJU JDSTS JQUUS JUBXJ
DSKSU JSNTK BGAQJ ZBGYQ TLCTZ BNYBN QJSW

У повідомленні бухгалтерської фірми, швидше за все, повинно зустрічатися слово «фінансовий» (financial). Використовуючи той факт, що в цьому слові літера i зустрічається двічі, розділена чотирма іншими буквами, ми будемо шукати в зашифрованому тексті повторювані символи, віддалені один від одного на відстань. В результаті ми знайдемо 12 таких місць у тексті у позиціях 6, 15, 27, 31, 42, 48, 56, 66, 70, 71, 76 і 82. Однак тільки у двох випадках, у позиціях 31 і 42, наступний символ (відповідний букві n у відкритому тексті) повторюється у відповідному місці. З цих двох варіантів символ a буде мати правильне розташування тільки для позиції 31. Таким чином, тепер нам відомо, що слово financial починається у позиції 30. Далі можна продовжувати, використовуючи лінгвістичну статистику англійської мови і вгадуючи цілі слова.

Оставить ответ

Обязательные поля помечены*

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.