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

  1. 1. Метод перестановки

Шифри, засновані на методі підстановки, зберігають порядок символів, але підміняють їх. Шифри, що використовують метод перестановки, змінюють порядок слідування символів, але не змінюють самі символи.

На рис. 8-3 показаний простий шифр перестановки з колонковою перестановкою. Ключем до шифру служить слово або фраза, що не містить повторюваних букв. В даному прикладі в якості ключа використовується слово MEGABUCK. Мета ключа — пронумерувати колонки. Першою колонкою стає колонка під літерою, розташованою ближче всього до початку алфавіту і т. д. Відкритий текст записується горизонтально в рядках. Шифрований текст читається по колонках, починаючи з колонки з молодшою ключовою буквою.

table
Рисунок 8-3 Перестановочний шифр

Щоб зламати перестановочний шифр, криптоаналітик повинен спочатку зрозуміти, що він має справу саме з перестановочним шифром. Якщо поглянути на частоту символів E, T, A, O, I, N і т. д., легко помітити, що їх частоти відповідають нормальним частотам відкритого тексту. В такому разі, очевидно, що цей шифр є перестановочним, так як кожна буква в такому шифрі представляє сама себе.
Потім потрібно вгадати число колонок. У багатьох випадках за контекстом повідомлення можна вгадати слово або фразу. Наприклад, припустимо, що криптоаналітик підозрює, що десь у повідомленні має зустрітися словосполучення milliondollars. Зверніть увагу, що в результаті того, що ці слова присутні у вихідному тексті, в шифрованому тексті зустрічаються діграми MO, IL, LL, LA, IR, OS. Символ O слідує за символом M (тобто вони стоять поруч по вертикалі в колонці 4), так як вони розділені у припустимій фразі дистанцією, рівній довжині ключа. Якби використовувався ключ довжиною сім, тоді замість перерахованих вище діграм зустрічалися б наступні: MD, IO, LL, LL, IA, OR і NS. Таким чином, для кожної довжини ключа в шифрованому тексті утворюється різний набір діграм. Перебравши різні варіанти, криптоаналітик часто досить легко може визначити довжину ключа.
Залишається дізнатися тільки порядок колонок. Якщо кількість колонок k невелика, можна перебрати всі k(k – 1) можливих комбінацій пар сусідніх стовпчиків, порівнюючи частоти утворюваних діграм зі статистичними характеристиками англійської мови. Пара з кращою відповідністю вважається правильно позиційованою. Після того всі колонки по черзі перевіряються в поєднанні з вже знайденою парою. Колонка, в якій діграми і триграми дають максимальний збіг з статистикою, вважається правильною. Весь процес повторюється, поки не буде відновлений порядок всіх колонок. Є шанс, що на даному етапі текст вже буде розпізнаваним (наприклад, якщо замість слова million ми побачимо milloin, то відразу стане ясно, де зроблена помилка).

Деякі перестановочні шифри приймають блок фіксованої довжини на вході і видають блок фіксованої довжини на виході. Такі шифри повністю визначаються списком, що повідомляє порядок, в якому символи потрапляють у вихідний блок. Наприклад, шифр на рис. 8-3 можна розглядати у вигляді шифру з 64-символьним блоком. Його вихід описується послідовністю чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13, …, 62. Іншими словами, четверта вхідні літера, a, першою з’явиться на вихід, за нею послідує дванадцята, f, і т. д.

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

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

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