Как улучшить взлом шифров подстановки программно? - PullRequest
10 голосов
/ 18 февраля 2010

Я написал (пишу) программу для анализа зашифрованного текста и попыток проанализировать и разбить его с помощью частотного анализа.

Зашифрованный текст принимает форму каждой буквы, заменяемой другой буквой, т.е. a-> m, b-> z, c-> t и т. д. все пробелы и не альфа-символы удаляются, а заглавные буквы делаются строчными.

Примером может быть:

Первоначальный вклад - это пример сообщения, которое содержит только буквы ниже
Зашифрованный вывод - ziololqlqdhstdtllqutozgfsnegfzqoflsgvtkeqltstzztkl
Попытка взлома - omieieaeanuhtnteeawtiorshylrsoaisehrctdlaethtootde

Здесь правильно указаны только I, A и Y.

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

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

1600 - правильные 10 букв
800 - правильные 7 букв
400 - правильные 2 буквы
200 - правильные 3 буквы
100 - 3 правильных буквы.

Я использую Ромео и Джульетту в качестве базы для получения частотных данных.

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

Ответы [ 10 ]

2 голосов
/ 18 февраля 2010
  • Однобуквенное слово является большой подсказкой (обычно только «A» и «I», редко «O». Случайный язык допускает «K»). Есть также конечный набор двух- и трехбуквенных слов. Не поможет, если пробелы были удалены.

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

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

Вы можете определить, когда вы приблизились, проверив Энтропию Шеннона .

2 голосов
/ 21 февраля 2010

Не полный ответ, но, возможно, полезный указатель: вы можете использовать словарь, чтобы определить, насколько хорош ваш кандидат в виде открытого текста. В системе UNIX с установленным aspell вы можете извлечь список английских слов с помощью команды

aspell -l en dump master
2 голосов
/ 18 февраля 2010

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

1) Картирование частоты недостаточно для решения головоломкитаким образом, многие частоты очень близки друг к другу, и если вы не используете один и тот же текст для источника частоты и открытого текста, вы почти гарантированно отключите несколько букв независимо от длины текста.Разные материалы будут иметь разные модели использования.

2) Не зачищайте пространства, если можете помочь.Это позволит вам проверить ваше потенциальное решение, проверив, что некоторый процент слов существует в словаре, к которому у вас есть доступ.

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

Редактировать: Сначала я бы посмотрел на большие графы и триграфы.Если вы достаточно уверены в одной или двух буквах, они могут помочь предсказать вероятных кандидатов на следующие буквы.Это в основном таблицы вероятностей, где AB будет вероятностью того, что за A следует буква B. Таким образом, при условии, что у вас есть заданная буква, которую можно использовать для решения букв рядом с ней, а не просто для предположения.Например, если у вас есть слово «y_u», для вас очевидно, что это слово для вас, но не для компьютера.Если у вас остались буквы N, C и O, биграфы скажут вам, что YN и YC очень необычны, где, как YO, гораздо более вероятно, даже если ваш текст имеет необычные частоты букв (что легко, когда он короткий) у вас еще есть достаточно точная система для решения неизвестных.Вы можете охотиться за скомпилированным набором данных или делать свой собственный анализ, но убедитесь, что используете много различного текста, много Шекспира - это не то же самое, что половина Шекспира и половина журнальных статей.

2 голосов
/ 18 февраля 2010

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

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

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

Многие предложения содержат слова «из» и «the». Если посмотреть на ваше предложение и предположить, что одно из двухбуквенных слов имеет значение, подразумевает дополнительные замены, которые могут позволить вам сделать выводы о других словах. Короче говоря, вам нужен словарь высокочастотных слов, чтобы вы могли делать дальнейшие выводы.

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

Удачи вам. Пожалуйста, поделитесь своими результатами, когда закончите.

2 голосов
/ 18 февраля 2010

Прежде всего, Ромео и Джульетта , вероятно, не очень хорошая основа для использования. Во-вторых, да, полезны орграфы (как и триграфы). Для заменительного шифра, на который вы смотрите, лучше всего начать с книг Military Cryptanalysis Уильяма Фридмана.

2 голосов
/ 18 февраля 2010

Просмотр пар символов имеет для меня большой смысл.

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

Например, нет способа получить qq, используя правильные английские слова, так как за каждым q должен следовать символ u. Если у вас повторяются одинаковые буквы в зашифрованном тексте, вы можете автоматически исключить возможность того, что они представляют q.

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

Кроме того, я хотел бы предположить, что Ромео и Джульетта являются лишь хорошей основой для статистических данных, если вы намерены проанализировать труды того периода. Произошли некоторые существенные изменения в правописании и использовании слов, которые могут исказить статистику.

1 голос
/ 23 февраля 2010

Что касается орграфов, диграмм и приближений слов, Джон Пирс (соавтор транзистора и РСМ) написал отличную книгу Введение в теорию информации , в которой содержится расширенный анализ расчета их характеристик, почему вы бы хотели и как их найти. Я нашел это полезным, когда сам написал код расшифровки частотного анализа.

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

1 голос
/ 23 февраля 2010

Частотный анализ

Частотный анализ - отличное место для начала. Тем не менее, Ромео и Джульетта - не очень хороший выбор, чтобы взять частоты символов для расшифровки текста «Гордость и предубеждение». Я бы предложил использовать частоты от этой страницы , потому что она использует 7 различных текстов, которые по возрасту ближе к Гордости и Предубеждению. В нем также перечислены вероятности для орграфов и триграфов. Однако орграфы и триграфы могут быть не столь полезны, когда из текста удаляются пробелы, потому что это создает шум от орграфов и триграфов, создаваемых словами, соединяемыми вместе.

Другой ресурс для символьных частот - этот сайт . Он утверждает, что использует «хорошее сочетание различных литературных жанров».

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

Хорошая вступительная книга

Если вы ищете хорошее введение в криптографию для неспециалистов, вы можете попробовать Кодовую книгу Саймона Сингха. Это очень читабельно и интересно. В книгах рассматривается развитие кодов и взлома кодов на протяжении всей истории. Он довольно рано рассматривает шифры замещения и описывает некоторые распространенные методы их взлома. Кроме того, в книге у него был Cipher Challenge (который уже был завершен), который состоял из нескольких различных кодов, которые нужно попытаться взломать, включая некоторые шифры замещения. Вы можете попробовать прочитать, как шведская команда взломала эти шифры на этом сайте . Тем не менее, я мог бы предложить прочитать хотя бы часть заменительного шифра книги, прежде чем читать эти решения.

Кстати, я никак не связан с публикацией этой книги. Мне просто очень понравилось.

1 голос
/ 18 февраля 2010

Вы можете попробовать смотреть на пары, а не на отдельные буквы.Например, at часто сопровождается h на английском языке, как и s.Марковское моделирование было бы здесь полезно.

0 голосов
/ 15 февраля 2011

интересный вопрос, я задаю похожий вопрос:)

Одна вещь, которую я пытаюсь выяснить и сделать, это: отсканировать более крупные слова с повторяющимися буквами ..

затем найдите соответствующее слово с шаблоном, аналогичным большему слову из шифра.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...