Шифры простой замены, наиболее выроятные ключи

[Euler7]

Доброго времени суток. Меня заинтересовал вопрос автоматической дешифровки шифров подстановки.
Мы имеем стандартные частоты для нашего алфавита и частоты шифротекста. Нужно сгенерировать список наиболее вероятных алфавитов. Т.е. найти алфавиты, для которых среднеквадратическое отклонение(или разность модулей) от стандартного будет минимальным. Какие есть варианты?

[_Ivana]

Вы будете смеяться, но тоже недавно думал над этой задачей Более того, мне кажется, что над ней задумались уже давно и существуют оптимальные методы ее решения. Но вместо того, чтобы поискать эти методы, я решил как обычно заняться кустарщиной и придумать их сам. Допустим, мы имеем алфавит из 33 символов. Общее количество возможных алфавитов прямой замены 33!. Можно отсортировать полученную из зашифрованного текста таблицу символов по частоте и сопоставить отсортированной таблице стандартных частот. Я проверял подобный метод на нескольких текстах, но результат плохой - если наиболее частые буквы "О" и "Е" зачастую угадывались правильно, то дальше уже начинался полный разброд, достаточно было вклиниться одному неверному символу или если получалась циклическая перестановка из трех символов (по сравнению с таблицей стандартных частот), и текст был неузнаваем. Но можно сделать следующее - взять в качестве стартового значения отклонение такого отсортированного алфавита от таблицы стандартных частот и попробовать посчитать рекурсивным методом отклонения всех 33! других алфавитов, прерывая анализ всей ветви графа, если на каком-то узле отклонение уже стало больше минимального. Но все равно 33! это очень много. Тогда можно поступить следующим образом: для каждого символа найти множество символов алфавита замены, частота которых в тексте отличается от стандартной частоты исходного символа не более чем на $x$%, например, не более чем 20%. К примеру, символ "О" у нас по частоте встречи в тексте может быть "С", "Н" или "У". И т.д. для каждого символа алфавита. То есть, типа как здесь во втором посте. Получаем количество вариантов, гораздо меньшее 33!, и их можем перебрать все полностью, причем так же отбрасывая ветви графа когда отклонение уже превышает найденное минимальное. И таким образом найти 10 (20, 30 - по желанию) вариантов алфавитов замены, которые дают минимальное отклонение, да еще и расположить их в порядке возрастания этого отклонения. Сам пока этот метод не реализовал, но мне кажется что проблем с этим не должно возникнуть.

ЗЫ кстати, когда игрался с этим, обнаружил в инете далеко не одну таблицу "стандартных частот" для букв русского языка.

[Euler7]

_Ivana, аналогичный вариант предлагает Бабаш в книге "Криптография"(2007) для ручной дешифровки, для автоматической предлагается генетический алгоритм, анализирующий буквосочетания(биграммы, триграммы, слова). Думаю я ошибся разделом, нужно ехать в программирование и на практике смотреть какой вариант лучше, а математика нам тут особо не поможет.

_Ivana писал(а):

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

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