Обработка текста, JFF

Шифр XOR: практика взлома.

В книге «Головоломки для хакера» в самой первой главе есть задача в которой читателю предлагается декодировать текст зашифрованный простым 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 равен ~16,7%
  • Повторяем для всех сдвигов и выбираем тот, у которого процент наибольший

Круто. Длина ключа нам известна.

Теперь надо найти сам ключ.

Для этого поступим таким образом:

  • Разбиваем текст на группы символов
  • Количество групп равно длине ключа
    Если у нас шифротекст "ciphertext" и ключ длиной 3 символа, то в первую группу попадут буквы c,h,t,t; во вторую: i, e, e; а в третью - p, r, x
  • В каждую группу входят символы, которые кодируются i-м символом ключа
  • В каждой из групп ксорим символы с наиболее распространенным в алфавите символом (для английского языка это пробел)
  • Считаем частоты каждого полученного символа среди группы
  • Выбираем в качестве i-й буквы ключа элемент с наибольшей частотой вхождения

Отлично. Потому что этот алгоритм успешно нашел ключ к шифротексту из задачи. Правда автор в решениях рекомендовал поксорить текст с фразой «The Conscience of a Hacker», а потом глазами искать что-то похожее на ключ…

Исходники на гитхабе. Вместе с исходником загадки.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s