2014 dxdy logo

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

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




 
 Шифр Цезаря
Сообщение07.11.2009, 15:03 
Аватара пользователя
Прошу помочь решить задачу. Давно не дает покоя.

"Некоторый русский текст, хранящийся в файле, зашифрован следующим образом: каждая буква текста циклически сдвигается на одно и тоже количество символов, а все остальные символы (знаки препинания и пробелы) остаются неизменными. При шифровке большие буквы переходят в большие, а маленькие в маленькие. Будем для простоты считать, что русский алфавит состоит из 32 букв (за буквой «е» следует буква «ж»). Требуется написать программу автоматической расшифровки текста."
Внимание: ключ не дан.

Интересны любые материалы по теме и метод решения.

 
 
 
 Re: Шифр Цезаря
Сообщение07.11.2009, 15:10 
Аватара пользователя
Можно использовать статистический анализ. А поскольку это шифр цезаря, то достаточно расшифровать только 1 букву, например "о" как самую распространенную в русских словах.

 
 
 
 Re: Шифр Цезаря
Сообщение07.11.2009, 15:24 
Еще можно использовать метод полосок. Правда, его реализация несколько сложнее, а также требует использования дополнительных материалов (т.е. необходим словарик часто употребляемых слов).

 
 
 
 Re: Шифр Цезаря
Сообщение07.11.2009, 15:54 
Аватара пользователя
Я был как-то наткнулся на статью в которой упоминалась частота встречаемости букв и диграм, но вот найти данные о частоте втречаемости у меня не получилось.
Попробую решить используя только "о".

 
 
 
 Re: Шифр Цезаря
Сообщение07.11.2009, 16:51 
Аватара пользователя
lucian в сообщении #259431 писал(а):
но вот найти данные о частоте втречаемости у меня не получилось.

плохо искали: http://www.google.ru/search?hl=ru&newwi ... 0%BA%D0%B5

 
 
 
 Re: Шифр Цезаря
Сообщение07.11.2009, 16:54 
Аватара пользователя
Сначала написал прогу основываясь на том что "о" всегда будет самой распространенной буквой.
Начал тестить и посмотрел что в примере к задаче в тексте самая распространенная буква "а".
Оригинальный текст : Я работаю, но я устал
Зашифрованный текст : А сбвпубя, оп а фтубм

Наверное надо искать по диграммам

 
 
 
 Re: Шифр Цезаря
Сообщение07.11.2009, 17:25 
lucian в сообщении #259455 писал(а):
Сначала написал прогу основываясь на том что "о" всегда будет самой распространенной буквой.Начал тестить и посмотрел что в примере к задаче в тексте самая распространенная буква "а".

По одной букве -- конечно, будет сбоить. Но если по всеиу алфавиту -- вероятность будет, наверное, достаточно высокой. Если, конечно, текст достаточно длинен.

 
 
 
 Re: Шифр Цезаря
Сообщение07.11.2009, 20:25 
Конечно же, при коротком тексте "сбоев" будет больше - вроятностный же алгоритм! При /поправил/ одной букве в тексте вообще не отгадать ничего. (А чем вам "О!" не текст?) :)

 
 
 
 Re: Шифр Цезаря
Сообщение13.11.2009, 09:05 
Аватара пользователя
В своё время написал программку, которая успешно справилась с фразой до 40 символов, меньше не пробовал. Программа очень простая: просматриваем текст, подсчитываем вероятность появления i-й буквы алфавита в тексте $F_T(i)$, также имеем эталонную вероятность появления буквы $F_{ideal}(i)$, а затем рассматриваем функцию $S(d) = \sum_{i=1}^{32}|F_T(i+d)-F_{ideal}(i+d)|$, в которой d - сдвиг букв. Сдвиг d, соответствующий минимуму функции $S(d)$, скорее всего и будет искомым сдвигом. Конечно, для коротких текстов, может и не сработает, и нужно будет искать несколько значений. Далее понятно, я думаю...

arseniiv в сообщении #259532 писал(а):
(А чем вам "О!" не текст?) :)
О может и текст, но крайне не информативный! :D

(Оффтоп)

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

 
 
 
 Re: Шифр Цезаря
Сообщение13.11.2009, 20:38 

(Оффтоп)

Kryptic в сообщении #261520 писал(а):
(Оффтоп)
Значит, ваша программа была с "толстовским уклоном" :) У авторов одного языка чуть-чуть тоже вероятности различаются.

 
 
 
 Re: Шифр Цезаря
Сообщение14.11.2009, 00:00 
Аватара пользователя

(Оффтоп)


 
 
 
 Re: Шифр Цезаря
Сообщение14.11.2009, 00:12 

(Оффтоп)

А почему, собственно, (Оффтоп)?
Вроде, всё - в тему.

 
 
 
 Re: Шифр Цезаря
Сообщение15.11.2009, 02:47 
Аватара пользователя
cepesh в сообщении #261791 писал(а):

(Оффтоп)


Я уже нашел таблицу "Вероятности биграмм в тексте"(Жельников Владимиp "Кpиптогpафия от папиpуса до компьютеpа"). И даже свою прогу написал, которая считает кол-во биграмм, но нет времени сейчас все это довести до конца. Понятно что надо брать коэффициенты встречаемости на не количество для Властелина Колец количество биграмм доходит до нескольких десятков тысяч. Но стоит ли брать всю таблицу. И может скормить программе всю электронную библиотеку, для увеличения точности.

/правка/
PS В задаче ограничения 255 символов.

 
 
 
 Re: Шифр Цезаря
Сообщение04.12.2009, 19:36 
Интересно конечно... Эта задача довольно проста - циклических сдвигов всего лишь мощность алфавита. Немного интереснее было бы решить задачу о вскрытии шифра простой замены, когда ключом является подстановка(или, как некоторым нравится, перестановка) на множестве $0, 1, ..., 31$.
Тогда количество ключей возросло бы до $32!$.
Ещё есть такой достаточно интересный термин, как запретные $m$-граммы. Например, запретными биграммами являются: ЪЬ ЬЪ ШЩ ЩШ ЖЫ ШЫ ЧЯ ЩЯ ЧЮ ЩЮ ЙА .....(текст без ошибок и Олбанского :D )
Так вот, хорошим критерием оценки правильности вскрытия шифр текста является крайне малое количество(или их полное отсутствие) запретных m - грамм. Можно часик подумать и выписать десяток - другой запретных биграмм, после чего искать их в тексте, который проверяется на близость к открытому.

Ещё интересный метод - использование генетичесих алгоритмов. Эта вообще отдельная тема, которую можно долго обсуждать. Программа, использующая генетические алгоритмы у меня работала минут 5, при этом ошибалась незначительно. Скажем, вместо самой частой буквы о ставила а, или вместо ъ ставила э

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group