В книге «Головоломки для хакера» в самой первой главе есть задача в которой читателю предлагается декодировать текст зашифрованный простым 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», а потом глазами искать что-то похожее на ключ…
Все в общем-то работает. Есть шифротекст, известна длина ключа по условию = 3, ключ я нашел. Но попробовал автоматизировать определение длины ключа и получил в 11 раз больше чем она есть на самом деле.
g 103
o 111
d 100
g 103
o 111
d 100
» 34
o 111
! 33
g 103
o 111
d 100
) 41
42
d 100
g 103
o 111
d 100
g 103
o 111
d 100
g 103
o 111
! 33
g 103
o 111
42
» 34
o 111
d 100
» 34
o 111
43
хотя истинный пароль god, ладно он дублирует но почему не верно?
Степан, к сожалению вы не указали ни шифротекст, ни ссылок на вашу реализацию. Если оно верно находит ключевое слово, то можно предположить, что при поиске повторяющейся подстроки допущена ошибка. В моем исходнике так же допущена ошибка поиска повторяющейся подстроки.
Конкретно это регулярка
Ее проблема в том, что ключ должен укладываться в строку целое число раз.
Бред какой-то, в чем интерес то, если шифруемая строка известна?
Как расшифровать не зная ни текст ни ключ?
Бинарные данные я так понимаю расшифровать невозможно не зная хотя бы примерную природу этих данных
Шифруемый текст нам может быть неизвестен. И здесь, равно как и в задании, он был дан просто для того, чтобы сравнить результат декодирования.
С бинарными данными этот метод так же будет работать.
Основа данного принципа — это свойство обратимости операции xor.
Если:
a xor c = A
b xor c = B
Тогда:
A xor B = c
Это свойство позволяет нам найти ключ шифруемого текста ксоря его с самим собой сдвигая каждый раз на один байт\бит\произвольную длину.
В полученный последовательностях мы ищем вероятный ключ. Да, существуют ограничения. Они касаются отношения длины ключа к шифротексту.
В решении есть одно упущение: реализация не позволит найти клч, который не укладывается целое число раз в шифруемое сообщение. Для поиска такого ключа стоит использовать алгоритмы нахождения повторяющейся последовательности наибольшей длины.
Хорошая догадка, но неверно!
А именно:
Если:
a xor c = A
b xor c = B
Тогда:
A xor B = c
Проверим: (a xor c) xor (b xor c) = (a xor b) xor (c xor c) = (a xor b)
Разве не так?
Да. В оригинальном комментарии опечатка.
upd: Перечитал статью. вроде бы в ней речь не про обратимость операции. а про попытку подобрать символы ключачастотным анализом. А про ксор вы правы.