2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Шифры простой замены, наиболее выроятные ключи
Сообщение18.10.2013, 20:51 


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

 Профиль  
                  
 
 Re: Шифры простой замены, наиболее выроятные ключи
Сообщение19.10.2013, 00:01 


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

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

 Профиль  
                  
 
 Re: Шифры простой замены, наиболее выроятные ключи
Сообщение19.10.2013, 18:23 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group