Частотный анализ: объяснение

Веками лучшим способом скрыть сообщение была замена каждой буквы алфавита другой. Число возможных ключей астрономическое, поэтому шифр казался невзламываемым. Однако ещё в IX веке учёный из Багдада нашёл его слабое место: язык использует одни буквы гораздо чаще других, и никакие перестановки этого не скроют. Частотный анализ превратил взлом шифров из гадания в метод, и до сих пор это первое, что пробуют на любом новом шифре.

Столбчатая диаграмма букв шифра от самой частой к самой редкой в сравнении с частотами английского языка, над шифртекстом, в котором разгаданы первые буквы
Столбчатая диаграмма букв шифра от самой частой к самой редкой в сравнении с частотами английского языка, над шифртекстом, в котором разгаданы первые буквы

Шифр простой замены

Шифр простой замены заменяет каждую букву алфавита другой по фиксированной таблице: например, A становится Q, B становится W и так далее, причём каждая буква используется один раз. Таблица — это ключ. В отличие от шифра Цезаря, который лишь сдвигает алфавит и имеет 25 ключей, шифр простой замены может использовать любой порядок букв: 26! ключей, около 4 × 10²⁶. Даже компьютеру, проверяющему миллиард ключей в секунду, понадобилось бы больше десяти миллиардов лет, чтобы перебрать их все.

Открытие аль-Кинди

Около 850 года арабский философ Абу Юсуф аль-Кинди написал трактат о расшифровке тайных сообщений — самое древнее из известных описаний частотного анализа. Он советовал взять длинный текст на том же языке, подсчитать, как часто встречается каждая буква, затем подсчитать буквы тайного сообщения и сопоставить их: самую частую с самой частой, следующую со следующей. Учёные, изучавшие Коран, поколениями подсчитывали буквы и слова, и, возможно, именно так возникла эта идея.

Буквы, пары и слова

В английском около 12,7% букв — E, 9% — T и 8% — A, а Z встречается реже чем раз на тысячу букв. Сами по себе подсчёты лишь указывают верное направление, особенно в коротких текстах, поэтому взломщики шифров используют любую закономерность, какую удаётся найти. Однобуквенное слово в английском — A или I. Самые частые пары — TH, HE, IN и ER, а самые частые удвоенные буквы — LL, EE, SS и OO. За Q почти всегда следует U. Частое трёхбуквенное слово — скорее всего, THE, а когда T, H и E известны, на свои места встают такие слова, как THAT и THERE. У каждого языка свой отпечаток: в немецком и нидерландском E преобладает ещё сильнее, а в португальском лидирует A.

Роковой шифр королевы

В 1586 году Мария Стюарт, королева Шотландии, находившаяся в заточении в Англии, обменивалась зашифрованными письмами с Энтони Бабингтоном, который замышлял освободить её и убить королеву Елизавету I. Письма тайно передавали в пивных бочонках, но они проходили через руки начальника разведки Елизаветы Фрэнсиса Уолсингема, чей дешифровщик Томас Фелиппес взломал шифр — замену с несколькими дополнительными символами для частых слов — с помощью частотного анализа. Расшифрованные письма доказали участие Марии в заговоре, и в феврале 1587 года её казнили.

Как скрыть частоты

Создатели шифров нанесли ответный удар. Омофонические шифры давали частым буквам по несколько символов, чтобы каждый символ встречался примерно одинаково часто. По тексту разбрасывали «пустышки» — ничего не значащие символы, чтобы запутать подсчёт. Настоящим ответом стали полиалфавитные шифры, такие как шифр Виженера XVI века, которые по ходу текста переключаются между несколькими алфавитами, так что одна буква открытого текста превращается во множество разных букв шифра. Шифр Виженера продержался до XIX века, когда Чарльз Бэббидж и Фридрих Касиски показали, как найти длину ключа, а затем применить частотный анализ к каждому алфавиту отдельно.

Как компьютеры решают криптограммы

Программа тоже не может перебрать все ключи, но она умеет карабкаться вверх. Она начинает с догадки, оценивает результат по тому, насколько он похож на язык — обычно по тому, насколько часты его группы из двух–четырёх букв, — а затем меняет местами пары букв в ключе, сохраняя каждую перестановку, которая повышает оценку. Когда ни одна перестановка не помогает, она встряхивает ключ и снова начинает подъём, сохраняя лучший результат. Этот метод, называемый восхождением к вершине (hill climbing), решает шифр простой замены из нескольких сотен букв за доли секунды, а его варианты взломали исторические шифры, веками не поддававшиеся людям.

Частотный анализ сегодня

Современные шифры, такие как AES, устроены так, что шифртекст выглядит совершенно случайным: каждое значение байта встречается одинаково часто, а одно и то же сообщение каждый раз шифруется по-разному. Частотному анализу здесь не за что зацепиться. И всё же идея живёт: статистика языка помогает распознать, что расшифровка верна, взламывать шифры в головоломках и квестах и читать старые зашифрованные письма, найденные в архивах. В 2023 году с помощью компьютера были расшифрованы письма Марии Стюарт, считавшиеся утраченными на протяжении веков.

Попробуйте сами

Откройте инструмент частотного анализа, чтобы получить зашифрованный абзац на английском, немецком, французском, испанском, итальянском, португальском или нидерландском языке. Сравните на диаграмме количество букв с языком, используйте зацепки — пары, удвоенные буквы и короткие слова — и заполняйте ключ буква за буквой. Кнопки «Подсказка» и «Проверить» помогут, если вы застрянете, а алгоритм покажет, как восхождение к вершине доводит дело до конца.

Часто задаваемые вопросы

Почему E — самая частая буква в английском?

Потому что она входит во многие из самых частых слов, таких как THE, BE, HE, WE и ARE, и в распространённые окончания вроде -ED и -ES. Это свойственно большинству европейских языков: E лидирует также во французском, немецком, нидерландском и испанском.

Может ли частотный анализ взломать любой шифр?

Нет. Он взламывает шифры, в которых каждая буква открытого текста всегда заменяется одним и тем же символом. Шифры, меняющие замену по ходу текста, и современные шифры, работающие с битами, а не с буквами, требуют других методов или вообще не поддаются взлому.

Что такое криптограмма?

Цитата или предложение, зашифрованные простой заменой и напечатанные, чтобы читатели разгадали их вручную. Криптограммы печатают в газетах с XIX века, и решают их ровно так, как показывает инструмент: начиная с коротких слов и самых частых букв.

Как расшифровали утерянные письма Марии Стюарт?

В 2023 году Джордж Ласри, Норберт Бирманн и Сатоси Томокиё установили, что 57 зашифрованных писем во французской библиотеке принадлежат ей. Шифр использовал почти 200 символов, поэтому они сочетали компьютерное восхождение к вершине, которое подсказало вероятное значение многих символов, с кропотливой ручной работой над остальными.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть инструмент частотного анализа