| Главная » Статьи » Задачи по программированию |
Куль хацкеры
Задача: Куль хацкеры. Расшифровать файл, зашифрованный шифром Цезаря, не имея ключа. Шифруются только большие русские буквы. Решение: Вспомнили задачу 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-алгоритм ;) | |
| Просмотров: 829 | Рейтинг: 0.0/0 |
| Всего комментариев: 0 | |