Класичний криптоаналіз

image
Протягом багатьох століть люди придумували хитромудрі способи приховування інформації — шифри, в той час як інші люди придумували ще більш хитромудрі способи розкриття інформації — методи злому.

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

Шифр Цезаря

Найлегший і один з найвідоміших класичних шифрів — шифр Цезаря відмінно підійде на роль аперитиву.
Шифр Цезаря відноситься до групи так званих одноалфавитных шифри підстановки. При використанні шифрів цієї групи «кожен символ відкритого тексту замінюється на певний, фіксований при цьому ключі символ того ж алфавіту» wiki.

Способи вибору ключів можуть бути різні. У шифрі Цезаря ключем служить довільне число k, вибране в інтервалі від 1 до 25. Кожна буква відкритого тексту замінюється буквою, що стоїть на k знаків далі неї в алфавіті. Наприклад, нехай ключем буде число 3. Тоді буква A англійського алфавіту буде замінена буквою D, літера B — літерою E і так далі.

Для наочності зашифруем слово HABRAHABR шифром Цезаря з ключем k=7. Побудуємо таблицю підстановки:
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
h i j k l m n o p q r s t u v w x y z a b c d e f g
І замінивши кожну літеру в тексті отримаємо: C('HABRAHABR', 7) = 'OHIYHOHIY'.

При розшифровці кожна літера замінюється буквою, що стоїть в алфавіті на k знаків раніше: D('OHIYHOHIY', 7) = 'HABRAHABR'.

Криптоаналіз шифру Цезаря

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

Аффиный шифр

Розглянемо трохи більш цікавий одноалфавитный шифр підстановки під назвою аффиный шифр. Він теж реалізує просту підстановку, але забезпечує трохи більший простір ключів порівняно з шифром Цезаря. У аффинном шифрі кожній букві алфавіту розміру m ставиться у відповідність число з діапазону 0… m-1. Потім за допомогою спеціальної формули, обчислюється нове число, яке замінить старе шифртексте.

Процес шифрування можна описати наступною формулою:

image,

де x — номер шифрованих букви в алфавіті; m — розмір алфавіту; a, b — ключ шифрування.

Для розшифровки обчислюється інша функція:

image,

де a-1 — число протилежне a по модулю m. Це означає, що для коректної розшифровки число a повинно бути взаємно простим з m.

З урахуванням цього обмеження обчислимо простір ключів аффиного шифру на прикладі англійського алфавіту. Так як англійський алфавіт містить 26 букв, то в якості a може бути обрано лише взаємно просте з 26 число. Таких чисел всього дванадцять: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 і 25. Число b в свою чергу може приймати будь-яке значення в інтервалі від 0 до 25, що в результаті дає нам 12*26 = 312 варіантів можливих ключів.

Криптоаналіз аффиного шифру

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

Давно відомо, що літери в природних мовах розподілені не рівномірно. Приміром, частоти появи літер англійської мови в текстах мають наступні значення:



Тобто, в англійському тексті найбільш зустрічаються літерами будуть E, T, A. У той час як найбільш рідкісними літерами є J, Q, Z. Отже, вважаючи частоту появи кожної букви в тексті ми можемо визначити наскільки частотна характеристика тексту відповідає англійській мові.

Для цього необхідно обчислити значення:

image,

де nі — частота i-ї літери алфавіту в природній мові. І fі — частота i-ї літери в шифртексте.

Чим більше значення χ, тим більше ймовірність того, що текст написаний на природній мові.

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

Зрозуміло, слід враховувати, що метод не завжди працює з короткими повідомленнями, в яких частотні характеристики можуть сильно відрізняться від характеристик природної мови.

Шифр простої заміни

Черговий шифр, що відноситься до групи одноалфавитных шифри підстановки. Ключем шифру служить перемішаний довільним чином алфавіт. Наприклад, ключем може бути наступна послідовність букв: XFQABOLYWJGPMRVIHUSDZKNTEC.

При шифруванні кожна буква в тексті замінюється за наступним правилом. Перша буква алфавіту заміщається першою літерою ключа, друга буква алфавіту — другою літерою ключа і так далі. У нашому прикладі літера A буде замінено на «X», літера B F.

При розшифровці буква спочатку шукається в ключі і потім замінюється буквою стоїть в алфавіті на тій же позиції.

Криптоаналіз шифру простої заміни

Простір ключів шифру простої заміни величезна і дорівнює кількості перестановок використовуваного алфавіту. Так для англійської мови це число становить 26! = 288. Зрозуміло наївний перебір всіх можливих ключів справа безнадійна і для злому потрібно більш витончена техніка, така як пошук сходженням до вершини:

  1. Вибирається випадкова послідовність букв — основний ключ. Шифртекст розшифровується за допомогою основного ключа. Для отриманого тексту обчислюється коефіцієнт, що характеризує ймовірність приналежності до природної мови.
  2. Основний ключ зазнає невеликих змін (перестановка двох довільно вибраних букв). Проводиться розшифровка і обчислюється коефіцієнт отриманого тексту.
  3. Якщо коефіцієнт вище збереженого значення, то основний ключ замінюється на модифікований варіант.
  4. 2-3 Кроки повторюються поки коефіцієнт не стане постійним.
Для обчислення коефіцієнта використовується ще одна характеристика природної мови — частота зустрічальності триграм.
Чим ближче текст до англійської мови тим частіше будуть зустрічатися такі триграми як THE, AND, ING. Підсумовуючи частоти появи у природній мові всіх триграм, зустрінутих в тексті отримаємо коефіцієнт, який з великою часткою ймовірності визначить текст, написаний на природній мові.

Шифр Полібія

Ще один шифр підстановки. Ключем шифру є квадрат розміром 5*5 (для англійської мови) містить всі букви алфавіту, крім J.



При шифруванні кожна буква вихідного тексту заміщається парою символів, що представляють номер рядка та номер стовпця, в яких розташована замещаемая літера. Буква a буде заміщена в шифртексте парою BB, літера b — парою EB і так далі. Так як ключ не містить літеру J, перед шифруванням у вихідному тексті J слід замінити на I.

Наприклад, зашифруем слово HABRAHABR. C('HABRAHABR') = 'AB BB EB DA BB AB BB EB DA'.

Криптоаналіз шифру Полібія

Шифр має великий простір ключів (25! = 283 для англійської мови). Однак єдина відмінність квадрата Полібія від попереднього шифру полягає в тому, що літера вихідного тексту замінюється двома символами.

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

Перестановочный шифр

Крім шифри підстановки, широке поширення також отримали перестановочные шифри. В якості прикладу опишемо Шифр вертикальної перестановки.

У процесі шифрування повідомлення записується у вигляді таблиці. Кількість колонок таблиці визначається розміром ключа. Наприклад, зашифруем повідомлення WE ARE DISCOVERED. FLEE AT ONCE з допомогою ключа 632415.

Так як ключ містить 6 цифр доповнимо повідомлення до довжини кратної 6 довільно вибраними літерами QKJEU і запишемо повідомлення в таблицю, що містить 6 колонок, зліва направо:



Для отримання шифртекста випишемо кожну колонку таблиці в порядку, що визначається ключем: EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE.

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

Криптоаналіз перестановочного шифру

Кращим способом атаки шифру вертикальної перестановки буде повний перебір всіх можливих ключів малої довжини (до 9 включно — близько 400 000 варіантів). У разі, якщо перебір не дав бажаних результатів, можна скористатися пошуком сходженням до вершини.

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

Шифр Плейфера

Шифр Плейфера — цей шифр реалізує заміну биграмм. Для шифрування необхідний ключ, який представляє собою таблицю букв розміром 5*5 (без букви J).

Процес шифрування зводиться до пошуку биграммы в таблиці і заміни її на пару букв, що утворюють з вихідної биграммой прямокутник.
Розглянемо, як приклад наступну таблицю, що утворить ключ шифру Плейфера:



Зашифруем пару 'WN'. Буква W розташована в першому рядку і першому стовпчику. А буква N знаходиться у другому рядку і третій колонці. Ці літери утворюють прямокутник з кутами W-E-S-N. Отже, при шифруванні біграм WN перетворюється в біграм ES.
У разі, якщо букви розташовані в одному рядку або стовпчику, результатом шифрування є біграм розташована на одну позицію праворуч/нижче. Наприклад, біграм NG перетворюється в біграм GP.

Криптоаналіз шифру Плейфера

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

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

Суть алгоритму зводиться до наступних дій:

  1. Вибирається випадкова послідовність букв — основний ключ. Шифртекст розшифровується за допомогою основного ключа. Для отриманого тексту обчислюється коефіцієнт, що характеризує ймовірність приналежності до природної мови.
  2. Основний ключ зазнає невеликих змін (перестановка двох довільно вибраних букв, перестановка рядків і стовпців). Проводиться розшифровка і обчислюється коефіцієнт отриманого тексту.
  3. Якщо коефіцієнт вище збереженого значення, то основний ключ замінюється на модифікований варіант.
  4. В іншому випадку заміна основного ключа на модифікований відбувається з ймовірністю, безпосередньо залежить від різниці коефіцієнтів основного та модифікованого ключів.
  5. Кроки 2-4 повторюються близько 50 000 разів.
Алгоритм періодично замінює основний ключ, ключем з гіршими характеристиками. При цьому ймовірність заміни залежить від різниці характеристик, що не дозволяє алгоритмом приймати погані варіанти занадто часто.

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

Шифр Віженер

Шифр Віженер відноситься до групи полиалфавитных шифри підстановки. Це означає, що в залежності від ключа одна і та ж буква відкритого тексту може бути зашифрована в різні символи. Така техніка шифрування приховує всі частотні характеристики тексту і ускладнює криптоаналіз.

Шифр Віженер являє собою послідовність кількох шифр Цезаря з різними ключами.

Продемонструємо, як приклад, шифрування слова HABRAHABR з допомогою ключа 123. Запишемо ключ під вихідним текстом, повторивши його необхідну кількість разів:



Цифри ключа визначають на скільки позицій необхідно зрушити букву в алфавіті для отримання шифртекста. Букву H необхідно змістити на одну позицію — в результаті виходить буква I, літеру A на 2 позиції — буква C, і так далі. Здійснивши всі підстановки отримаємо в результаті шифртекст: ICESCKBDU.

Криптоаналіз шифру Віженер

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

Для цього можна скористатися індексом збігів.

Індекс збігів — число, що характеризує ймовірність того, що дві довільно вибрані з тексту літери виявляться однакові.
Для будь-якого тексту індекс збігів обчислюється за формулою:

,

де fі — кількість появ i-ї літери алфавіту в тексті, а n — кількість літер у тексті.

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

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

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

p.s.

Исходники всіх вищеописаних шифрів і атак на них можна подивитися на GitHub.

Посилання

1. Криптоаналіз класичних шифрів на сайті practicalcryptography.com.
2. Частотні характеристики англійської мови на сайті practicalcryptography.com
3. Опис алгоритму імітації відпалу на wikipedia
4. Опис пошуку сходженням до вершини на вікіпедія

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.