Задача g6_1007: Куль хацкеры.

Расшифровать файл, зашифрованный шифром Цезаря, не имея ключа. Шифруются только большие русские буквы.

Решение g6_1007:
Вспомнили задачу 1003? Сначала я хотел разобрать задачу расшифровки шифра с ключом, но потом мне это показалось неинтересным, т.к. расшифровка - та же самая расшифровка с ключом (32 - n)!
Теперь мы попытаемся сделать расшифровку не имея ключа. Для этого нам придется немного коснуться основ криптографии. Каждый текст имеет свою специфику - некоторые символы встречаются в нем часто, другие реже, но в среднем частота символов примерно одинакова. Этим мы можем воспользоваться в нашем нелегком труде - написании взламывающей программы.
Для начала нам понадобиться таблица-эталон с частотой встречи букв в стандартном русском тексте. Она выглядит примерно так:

А := 0.074438;
Б := 0.016189;
В := 0.050396;
Г := 0.019352;
Д := 0.028179;
Е := 0.089613;
Ж := 0.010010;
З := 0.016637;
И := 0.074109;
Й := 0.014743;
К := 0.032171;
Л := 0.037507;
М := 0.031160;
Н := 0.067640;
О := 0.113329;
П := 0.026275;
Р := 0.049378;
С := 0.056569;
Т := 0.063209;
У := 0.023785;
Ф := 0.001466;
Х := 0.009276;
Ц := 0.004299;
Ч := 0.014236;
Ш := 0.006525;
Щ := 0.004035;
Ъ := 0.000240;
Ы := 0.017820;
Ь := 0.016222;
Э := 0.004256;
Ю := 0.007210;
Я := 0.019724;

Уфф... Сгенерировать эту таблицу - иногда тоже проблема.
А теперь собственно к задаче. Мы имеем две таблицы - таблицу-эталон и таблицу для взламываемого файла. как же определить какой сдвиг был использован.
Первая моя реализация (которую я придумал сам) была туповатой и работала только на больших файлах. Она выбирала самую часто встречающуюся букву и считала ее буквой "О". Исходя из этого производилась расшифровка. Однако, в некоторых текстах самая частая - вовсе не буква "О" и, следовательно, программа работала неверно.
Следующая реализация вплотную пододвинула меня к истине(она вполне рабочая, но есть вариант чуть-чуть лучше, но о нем позже):
Я производил циклический сдвиг таблицы для взламываемого файла и считал сумму модулей разницы частот появления символов в таблице-эталоне и передвинутой таблицы. Например:

Пусть алфавит состоит из трех букв: {А, Б, В} с частотами:
А := 0.1;
Б := 0.3;
В := 0.6;

На вход мы получаем сообщение состоящее из того же алфавита, но с частотами:
А := 0.35;
Б := 0.55;
В := 0.1;

Теперь посчитаем нашу хитрую функцию для всех возможных сдвигов: {0, 1, 2}
[0] := |0.1 - 0.35| + |0.3 - 0.55| + |0.6 - 0.1| = 1; - очень скверно
[1] := |0.1 - 0.55| + |0.3 - 0.1| + |0.6 - 0.35| = 0.9; - скверно
[2] := |0.1 - 0.1| + |0.3 - 0.35| + |0.6 - 0.55| = 0.1; - скверно, но верно

Минимальная сумма получилась для сдвига 2, следовательно он и является ключом!
Другой способ решения состоит в том чтобы считать не сумму модулей, а сумму квадратов (он несколько более правильный, т.к. мелкие погрешности в нем почти исчезают), но и мой алгоритм расшифровывает практически все.
Пожалуй, в следующий раз надо сломать RSA-алгоритм ;)

ДОПОЛНЕНИЕ ОТ 18.02.02:
Недавно узнал еще один способ решения этой задачи, заключающийся в оценивании редко и часто встречающихся сочетаний букв. Например: четыре согласные подряд - плохое сочетание, а окончание "-ий", "-ой" или "-ый" - хорошее. Для каждого сдвига считается разность хороших и плохих сочетаний - в каком сдвиге эта разность наибольшая - тот и лучший.