Шифр Цезаря

[lucian]

Прошу помочь решить задачу. Давно не дает покоя.

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

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

[meduza]

Можно использовать статистический анализ. А поскольку это шифр цезаря, то достаточно расшифровать только 1 букву, например "о" как самую распространенную в русских словах.

[EtCetera]

Еще можно использовать метод полосок. Правда, его реализация несколько сложнее, а также требует использования дополнительных материалов (т.е. необходим словарик часто употребляемых слов).

[lucian]

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

[meduza]

lucian в сообщении #259431 писал(а):

но вот найти данные о частоте втречаемости у меня не получилось.

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

[lucian]

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

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

[ewert]

lucian в сообщении #259455 писал(а):

Сначала написал прогу основываясь на том что "о" всегда будет самой распространенной буквой.Начал тестить и посмотрел что в примере к задаче в тексте самая распространенная буква "а".

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

[arseniiv]

Конечно же, при коротком тексте "сбоев" будет больше - вроятностный же алгоритм! При /поправил/ одной букве в тексте вообще не отгадать ничего. (А чем вам "О!" не текст?)

[Kryptic]

В своё время написал программку, которая успешно справилась с фразой до 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 писал(а):

(А чем вам "О!" не текст?)

О может и текст, но крайне не информативный!

(Оффтоп)

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

[arseniiv]

(Оффтоп)

Kryptic в сообщении #261520 писал(а):

(Оффтоп)

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

[cepesh]

(Оффтоп)

Вот вам в тему )) http://cepesh.mexmat.ru/scripts/lexic_calc.php

[venco]

(Оффтоп)

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

[lucian]

cepesh в сообщении #261791 писал(а):

(Оффтоп)

Вот вам в тему )) http://cepesh.mexmat.ru/scripts/lexic_calc.php

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

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

[malin]

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

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