У книзі «пазли для хакера» в самій першому розділі є завдання в якій читачеві пропонується декодувати текст зашифрований простим xor. При цьому ключ невідомий.
Як тексту пропонується якийсь маніфест «The Conscience of a Hacker.txt«.
Для початку нам потрібно визначити довжину ключа.
- циклічно зміщуємо текст на i (від 1 до len (text) / 2) символів вправо
- для кожної ітерації порівнюємо кількість збігів символів оригінального (не усунуте) і нового текстів)
- зміщення i при якому кількість збігів буде максимальним і є шукана довжина ключа
І до речі, чому len (text) / 2. Правильніше звичайно перевіряти всі зміщення аж до len (text) - 1. але експерименти показали, що відсоток збігів для зсуву i і n-i буде однаковий на великих текстах. Та й хто буде робити ключі завдовжки більше половини тексту?
На практиці це виглядає так:
- У нас є шифротекст «abcdea»
- циклічно зрушуємо його на i = 1 символів
- Отримуємо «aabcde»
- Шукаємо кількість збігів символів в рядках «abcdea» і «aabcde»
- У нас є один збіг в нульовому символі.
- Відсоток збігів для зсуву 1 дорівнює
Круто. Довжина ключа нам відома.
Тепер треба знайти сам ключ.
Для цього зробимо таким чином:
- Розбиваємо текст на групи символів
- Кількість груп дорівнює довжині ключа
- У кожну групу входять символи, які кодуються i-м символом ключа
- У кожній з груп КСОР символи з найбільш поширеним в алфавіті символом (для англійської мови це пробіл)
- Вважаємо частоти кожного отриманого символу серед групи
- Вибираємо в якості i-й літери ключа елемент з найбільшою частотою входження