Как я могу улучшить алгоритмы замещения замещения?

Ответ 1

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

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

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

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

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

Ответ 2

Взгляд на пары персонажей имеет для меня большой смысл.

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

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

Ответ 5

• Однобуквенное слово - большой намек (как правило, только "A" и "I", редко "O". Случайный язык позволяет "K" ). Существует также конечный набор двух и трех буквенных слов. Никакой помощи, если пробелы были разделены.

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

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

Возможно, вы сможете определить, когда вы закрылись, проверив Shannon Entropy.

Ответ 6

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

aspell -l en dump master

Ответ 7

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

Ответ 8

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

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

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

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

Хорошая вводная книга

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

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

Ответ 9

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

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

Ответ 10

Интересный вопрос, задаю аналогичный вопрос:)

одно, что я пытаюсь выяснить и сделать: для сканирования больших слов, которые повторяют буквы в них.

затем найдите соответствующее слово с похожим шаблоном для большего слова из шифрования..

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