Задача 21: Куль
хацкеры.
Расшифровать файл, зашифрованный шифром Цезаря, не имея ключа.
Шифруются только большие русские буквы.
Решение:
Вспомнили задачу 3?
Теперь мы попытаемся сделать расшифровку не имея ключа. Для этого
нам придется немного коснуться основ криптографии. Каждый текст
имеет свою специфику - некоторые символы встречаются в нем часто,
другие реже, но в среднем частота символов примерно одинакова. Этим
мы можем воспользоваться в нашем нелегком труде - написании
взламывающей программы.
Для начала нам понадобиться таблица-эталон с частотой встречи букв в
стандартном русском тексте. Она выглядит примерно так:
А := 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:
Недавно узнал еще один способ решения этой задачи, заключающийся в
оценивании редко и часто встречающихся сочетаний букв. Например:
четыре согласные подряд - плохое сочетание, а окончание "-ий", "-ой"
или "-ый" - хорошее. Для каждого сдвига считается разность хороших и
плохих сочетаний - в каком сдвиге эта разность наибольшая - тот и
лучший.
Далее
ð
