Какие печатные символы ASCII обычно появляются в английском тексте?

Question

Я некоторое время пытался решить Проект Эйлера # 59 , и у меня возникли проблемы, потому что некоторые из них кажутся несколько более двусмысленными, чем предыдущие проблемы.

В качестве фона проблема говорит о том, что данный текстовый файл является зашифрованным текстом с кодами ASCII, сохраненными в виде чисел. Метод шифрования состоит в том, чтобы XOR 3 строчные буквы циклически с открытым текстом (так что это обратимо). Проблема просит ключ, который расшифровывает файл в текст на английском языке. Как мне ограничить набор символов моего вывода, чтобы получить ответ, не пытаясь просеять все возможные открытые тексты (26 ^ 3)?

Я пытался ограничиться буквами, пробелами и пунктуацией, но это не сработало.

Чтобы уточнить: я хочу определить, из всех печатных символов ASCII, какие из них я могу отбросить, а какие можно ожидать в строке открытого текста.

Answer 1

Пробовали ли вы два самых «базовых» и распространенных инструмента для анализа используемого алгоритма?

1. Анализируйте частоту символов и пытайтесь сопоставить ее с частотой английских букв
2. Перебор, использующий ключи из списка слов, наиболее часто используемые слова используются в качестве ключей "тупыми" пользователями

Чтобы проанализировать частоту этой конкретной проблемы, вам придется разбивать строку на каждый третий элемент, посколькуключ имеет длину 3, теперь вы должны иметь возможность создать три столбца:

79  59  12
2   79  35
8   28  20
2   3   68
...

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

Хорошо, на самом деле я потратил свое время и построил 3 полных столбца, посчитал частоту для каждого из столбцов и получил два наиболее часто встречающихся элемента или каждого столбца:

Col1  Col2  Col3
71    79    68
2     1     1

Теперь, если вы проверите, например:1017 *http://en.wikipedia.org/wiki/Letter_frequency У вас самые частые буквы, и не забывайте, что у вас есть пробелы и другие символы, которых нет на этой странице,но я думаю, вы можете предположить, что пробел является наиболее частым символом.

Так что теперь это просто вопрос xor: наиболее часто встречающиеся символы в таблице, которые я предоставил, содержат наиболее часто встречающиеся символы на английском языке, ипосмотрим, есть ли строчные буквы, я нашел трехбуквенное слово, которое, я думаю, является ответом только с этими данными.

Удачи и, между прочим, это была хорошая проблема!

Answer 2

Возможное решение - просто предположить наличие заданной трехсимвольной последовательности в зашифрованном тексте. Вы можете использовать трехбуквенное слово или трехбуквенную последовательность, которая может появиться в английском тексте (например, " a ": буква «а» заключена между двумя пробелами). Затем просто попробуйте все возможные позиции этой последовательности в зашифрованном тексте. Каждая позиция позволяет вам просто пересчитать ключ, а затем расшифровать весь текст в файл.

Поскольку исходный текст имеет длину 1201, вы можете просмотреть 1199 файлов. На этом этапе это только вопрос терпения, но вы можете сделать это намного быстрее, используя простую утилиту текстового поиска на другой частой последовательности на английском языке (например, "are"), например, с помощью инструмента Unix grep. * 1006. *

Я так и сделал и получил расшифрованный текст менее чем за пять минут.

Answer 3

Признаюсь заранее, я не знаком с шифром XOR.

Однако, похоже, он очень похож на концепцию шифра Vigenere.Особенно в строке, где они упоминают о неразрушимом шифровании, длина ключа равна длине сообщения.Это крик Вернама Шифра.

Как уже упоминалось в другом ответе, стратегический подход к взлому шифровального шифра включает в себя вероятностный подход.Я не буду вдаваться в подробности, потому что большая часть теории, которую я выучил, была относительно сложной, но ее можно найти здесь , имея в виду, что vignere - это серия кесаревых шифров.

Проблема состоит в том, чтоэто легко для вас, потому что вы уже знаете длину ключа.Из-за этого, как вы упомянули, вы можете просто перебор, пробуя каждую трехбуквенную комбинацию.

Вот что я хотел бы сделать: взять кусок зашифрованного текста разумного размера, скажем, может быть, 10-20 символов, и попробовать на этом подход грубой силы.Отслеживайте все ключи, которые, кажется, создают понятные последовательности букв, а затем используйте их во всем зашифрованном тексте.Таким образом, мы можем использовать очевидный метод грубого принуждения, но без грубого решения всей проблемы, поэтому я не думаю, что вам придется беспокоиться об ограничении вывода.

Тем не менее, я согласен, что, когда вы создаете вывод, если вы когда-нибудь получите непечатаемый символ, вы, вероятно, можете разорвать ваш цикл и перейти к следующей клавише.Я не стал бы пытаться что-то более конкретное, чем это, потому что, кто знает, что может иметь исходное сообщение, никогда не делайте предположений относительно данных, с которыми вы имеете дело.Подобная логика короткого замыкания всегда является хорошей идеей, особенно при реализации решения методом перебора.

Answer 4

Я только что решил эту проблему несколько дней назад.Не портя это для вас, я хочу описать свой подход к этой проблеме.Часть из того, что я говорю, может быть избыточной к тому, что вы уже знали, но была частью моего подхода.

Сначала я предположил, что ключ в точности соответствует описанию, три строчные буквы ASCII.Поэтому я начал грубое принуждение в «ааа» и пошел в «zzz».При дешифровании, если какой-либо результирующий байт имел значение ниже 32 (значение ASCII пробела, самое низкое «печатаемое» значение ASCII) или больше 126 (значение ASCII тильды «~», которое является самым высоким печатаемым символом в ASCII), чем я предполагал, что ключ недействителен, потому что любое значение, кроме 32 и 126, будет недопустимым символом для простого текста на английском.Как только один байт выходит за пределы этого диапазона, я прекратил дешифрование и перешел к следующему возможному ключу.

Как только я расшифровал все сообщение с помощью определенного ключа (после прохождения первого теста всех байтов, пригодных для печатисимволов), мне нужен был способ проверить это как правильное дешифрование.Я ожидал, что результатом будет простой список слов без определенного порядка или значения.Благодаря другому опыту криптографии я вспомнил частоту букв, и самое простое, что ваше среднее английское слово в тексте имеет длину 5 символов.Файл содержит 1201 входных байтов.Так что это будет означать, что будет (в среднем) 240 слов.После расшифровки я посчитал, сколько пробелов было в результирующей выходной строке.Поскольку Project Euler совсем не средний, я сравнил количество пробелов с 200 с учетом более длинных, более неясных слов.Когда в выводе было более 200 пробелов, я распечатал ключ, с которым он был расшифрован, и выводимый текст.Ответ - единственный выход, имеющий более 200 пробелов.Позвольте мне сказать вам, что более чем очевидно, что у вас есть ответ, когда вы его видите.

Следует отметить, что ответ на вопрос НЕ является ключевым.Это сумма всех значений ASCII выходной строки.Этот подход также решит уравнение под отметкой в ​​одну минуту, фактически это время примерно за 3 или 4 секунды.

Answer 5

Разделить зашифрованный текст на 3.

Ciphertext1 содержит 1-е, 4-е, 7-е, 10-е ... числа Ciphertext2 содержит 2-е, 5-е, 8-е, 11-е ... числа Ciphertext3 содержит 3-е, 6-е,9-е, 12-е ... числа

Теперь вы знаете, что каждый шифротекст зашифрован одним и тем же ключом.Теперь сделайте стандартный анализ частоты на нем.Это должно дать вам достаточно подсказок относительно того, что это за письмо.