Шифр Цезаря: объяснение
Шифр Цезаря — самый древний шифр, носящий знаменитое имя, и первый, с которым знакомится большинство людей. Он достаточно прост, чтобы применять его в уме, и достаточно слаб, чтобы взломать его за минуты, и именно это сочетание делает его идеальным местом, чтобы увидеть в действии две основные идеи криптографии: секретный ключ, превращающий сообщение в бессмыслицу, и закономерности, которые всё равно позволяют злоумышленнику его прочесть.
Шифр Цезаря
Римский историк Светоний писал, что Юлий Цезарь, когда ему нужно было сообщить что-то секретное, писал так, чтобы порядок букв нельзя было разобрать: он заменял каждую букву той, что стоит на три места дальше, D вместо A и так далее. Его преемник Август, как говорят, пользовался сдвигом на одну букву. Любой фиксированный сдвиг от 1 до 25 работает так же, и сдвиг — это ключ. На шифровальном диске из двух колец букв ключ — это просто то, насколько повёрнуто внутреннее кольцо.
Арифметика сдвига
Пронумеруйте буквы от A = 0 до Z = 25. Шифрование с ключом k превращает букву x в (x + k) mod 26, а расшифровка возвращает её в (x − k) mod 26: это арифметика часов с 26 делениями. Поскольку в алфавите 26 букв, сдвиг на 13 обратен сам себе, и поэтому ROT13 может и спрятать, и раскрыть концовку шутки. Сдвиг на 26 или на 0 ничего не меняет, поэтому полезных ключей 25.
Взлом полным перебором
Шифр надёжен лишь настолько, насколько трудно перебрать его ключи. При 25 ключах злоумышленник может выписать все возможные расшифровки и посмотреть, какая из них имеет смысл; на компьютере это занимает меньше миллисекунды. У современных шифров, таких как AES, 2¹²⁸ или больше ключей — так много, что перебрать их все невозможно ни на одном компьютере, который вообще можно построить. Большое пространство ключей — первое требование к надёжному шифру.
Частотный анализ
В IX веке арабский философ и учёный аль-Кинди описал метод, при котором не нужно угадывать ключи: подсчитайте, как часто каждая буква встречается в шифртексте, и сравните с тем, как часто буквы встречаются в языке. В английском примерно каждая восьмая буква — E, а J, Q, X и Z редки. Шифр Цезаря лишь сдвигает эту картину, поэтому самый высокий пик в шифртексте — скорее всего, E, и сдвиг сразу становится ясен. Метод также взламывает любой шифр, который всегда заменяет букву одним и тем же символом, как бы ни был перемешан алфавит.
Оценка с помощью хи-квадрат
Чтобы компьютер мог судить, какая расшифровка больше всего похожа на язык, сравните количество букв в ней с тем количеством, которого можно ожидать для этого языка. Статистика хи-квадрат суммирует по всем буквам квадрат разности между наблюдаемым и ожидаемым количеством, делённый на ожидаемое количество. Текст, близко соответствующий языку, получает низкую оценку; бессмыслица — высокую. Ранжирование всех 26 сдвигов по этой оценке почти всегда ставит верный сдвиг на первое место, как только в тексте набирается несколько десятков букв.
Шифры, которые дали отпор
Частотный анализ заставил создателей шифров скрывать частоты. Омофонические шифры давали частым буквам по несколько символов. Шифр Виженера XVI века с помощью ключевого слова применял к каждой букве по очереди свой сдвиг Цезаря и триста лет считался неразгадываемым шифром, пока Чарльз Бэббидж и Фридрих Касиски не показали, как найти длину ключевого слова, а затем взломать каждый сдвиг отдельно — снова частотным анализом. Роторные машины, такие как «Энигма», пошли ещё дальше, а современная криптография и вовсе заменила буквы математикой.
Шифры Цезаря в истории
При всей своей слабости шифр сдвига использовался для настоящих секретов гораздо дольше, чем того заслуживал. Марию Стюарт, королеву Шотландии, осудили в 1586 году на основании писем, написанных более сложным шифром замены, который был взломан частотным анализом. Ещё в начале XX века армии отправляли сообщения простыми шифрами сдвига, а в 2006 году босса сицилийской мафии Бернардо Провенцано поймали отчасти благодаря запискам, в которых каждая буква записывалась числом на три больше её места в алфавите.
Попробуйте сами
Откройте взлом шифра Цезаря, чтобы шифровать и расшифровывать собственные сообщения, вращать шифровальный диск и взламывать сообщения без ключа. Диаграмма показывает буквы результата на фоне частот выбранного вами языка, так что можно увидеть, как пики совмещаются, когда сдвиг становится верным, а таблица ранжирует все 26 сдвигов по оценке хи-квадрат. Попробуйте пример с панграммой, чтобы увидеть, как частотный анализ буксует на тексте, в котором каждая буква встречается один раз.
Часто задаваемые вопросы
Используется ли шифр Цезаря до сих пор?
Не для секретов. ROT13 по-прежнему прячет спойлеры и ответы к головоломкам, шифр используют для обучения криптографии и модульной арифметике, а ещё он встречается в головоломках, квестах и геокэшинге. Всё, что должно оставаться тайным, защищают современными шифрами с огромным числом ключей.
Чем шифр Цезаря отличается от шифра простой замены?
Шифр Цезаря — это частный случай шифра замены, в котором алфавит замены — обычный алфавит со сдвигом. Общий шифр замены может использовать любую перестановку алфавита, что даёт около 4 × 10²⁶ ключей — слишком много, чтобы их перебрать. Тем не менее он поддаётся частотному анализу, потому что каждая буква всегда заменяется одним и тем же символом.
Какой длины должен быть текст, чтобы его надёжно взломать?
С оценкой хи-квадрат для английского обычно хватает нескольких десятков букв, а пары предложений — почти всегда. Очень короткие тексты или тексты с необычным набором букв могут привести к тому, что лучшую оценку получит неверный сдвиг, поэтому приложение показывает весь рейтинг и то, насколько явно выделяется победитель.
Почему частоты букв различаются в разных языках?
Каждый язык использует буквы по-своему: E — самая частая буква в английском, немецком, французском и нидерландском, но в португальском самая частая — A, в испанском и итальянском она почти наравне с E, а K, W и Y в романских языках редки. Выбор языка сообщения делает оценку надёжнее.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть взлом шифра Цезаря