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

Question

Я пытался решить Project Euler's problem #59 какое-то время, и у меня проблемы, потому что некоторые из них кажутся несколько более неоднозначными, чем предыдущие проблемы.

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

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

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

Answer 1

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

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

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

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

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

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

Col1 Col2 Col3 
71 79 68 
2  1  1 

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

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

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

Answer 2

Я буду признателен заранее. Я не знаком с шифром XOR.

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

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

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

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

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

Answer 3

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

Ciphertext1 включает 1-й, 4-й, 7-й, 10-й ... номер Ciphertext2 включает в себя 2-е, 5-й, 8-й, 11-й ... номер Ciphertext3 включает 3-й, 6-й , 9-й, 12-й ... номера

Теперь вы знаете, что каждый cyphertext зашифрован одной буквой. Теперь сделайте стандартный анализ частоты на нем. Это должно дать вам достаточно информации о том, что такое письмо.

Answer 4

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

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

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

Answer 5

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

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

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

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