Расшифровка переставленных английских строк

Question

Недавно сотрудника спросили об этом при попытке получить (другую) исследовательскую работу:

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

Ему дали несколько дней, чтобы подумать, прежде чем ждать ответа. Как бы вы это сделали? Вы можете использовать любой компьютерный ресурс, включая языковые модели уровня символов / слов.

Answer 1

Это базовый шифр транспонирования .Мой вопрос выше состоял в том, чтобы просто определить, был ли это шифр транспонирования или шифр замещения.Криптоанализ таких систем довольно прост.Другие уже ссылались на основные методы.Оптимальные подходы будут пытаться размещать самые твердые и редкие буквы первыми, поскольку они будут стремиться однозначно идентифицировать буквы вокруг них, что значительно сокращает пространство для последующего поиска.Просто найти a место для размещения "a" (без каламбура) не сложно, но найти место для "q", "z" или "x" немного больше.

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

Поскольку вы можете использовать несколько строк одновременно, попытка создать слова из самых редких символов позволит вам параллельно тестировать атаки по словарю.Как можно более быстрое нахождение правильного размещения самых редких терминов в каждой строке расшифрует этот зашифрованный текст ПЛЮС всех остальных одновременно.

Если вы ищете криптоанализ шифров транспонирования, вы найдете группус генетическими алгоритмами.Они предназначены для повышения авторитета людей, работающих в ГА, поскольку на практике они не являются оптимальными.Вместо этого вам следует взглянуть на некоторые основные методы оптимизации, такие как ветвление и ограничение, A *, и различные статистические методы.(Насколько глубоко вы должны углубиться, зависит от вашего уровня знаний в области алгоритмов и статистики. :) Я бы несколько раз переключался между детерминистическими методами и методами статистической оптимизации.)

В любом случае, вычисления должны быть грязь дешевая и быстрая, потому что масштаб начальных догадок может быть довольно большим.Лучше всего сначала иметь дешевый способ отфильтровать МНОГО возможных мест размещения, а затем тратить больше процессорного времени на отбор лучших кандидатов.Для этого хорошо иметь способ описания этапов обработки и вычислительных усилий для каждого этапа.(По крайней мере, это то, что я ожидал бы, если бы дал это в качестве вопроса для интервью.)

Вы даже можете купить достаточно достоверный справочник по расшифровке шифров с двойной транспозицией.*

Обновление 1: посмотрите на эти слайды , чтобы получить больше идей по итерационным улучшениям.Это не отличный справочный набор слайдов, но он легко доступен.Более того, хотя слайды посвящены GA и имитированному отжигу (методы, которые часто встречаются в результатах поиска для криптоанализа шифрования с транспозицией), автор выступает против таких методов, когда можно использовать A * или другие методы.:)

Answer 2

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

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

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

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

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

Answer 3

Частотный анализ резко сократил бы пространство поиска.Наиболее распространенными буквами в английской прозе являются общеизвестные .

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

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

Answer 4

Во-первых, вам нужна функция оценки, которая увеличивается с увеличением вероятности правильной перестановки.Один из подходов состоит в том, чтобы предварительно рассчитать частоты триплетов в стандартном английском (получить некоторые данные из проекта Гутенбург) и сложить частоты всех триплетов во всех десяти строках.Вы можете обнаружить, что четверки дают лучший результат, чем триплеты.

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

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

Кстати, он «переставлен», а не «переставлен».