Частотный анализ
Метод криптоанализа, который сопоставляет частоты символов и их сочетаний с языковыми закономерностями, чтобы восстановить классический шифртекст.
Определение
Частотный анализ изучает, как часто в тексте встречаются буквы, символы, слова и их сочетания — например, биграммы и триграммы. У естественных языков есть устойчивые статистические закономерности: в русском среди самых частых букв обычно находятся О, Е и А.
Многие классические шифры заменяют символы, но не полностью уничтожают эти закономерности. Криптоаналитик сравнивает распределение шифротекста с языковым профилем и выдвигает гипотезы об исходных буквах и сочетаниях. Такое сравнение даёт подсказки, а не готовую расшифровку.
Как это работает
Сначала текст нормализуют и подсчитывают отдельные символы. Затем для частых символов шифротекста проверяют несколько соответствий с распространёнными буквами предполагаемого языка. Биграммы, триграммы, повторяющиеся слова и структура слов помогают подтвердить или отбросить каждую гипотезу.
В шифре Цезаря весь частотный профиль сдвинут на одинаковое число позиций, а при моноалфавитной замене — переставлен. Для полиалфавитного шифра с повторяющимся ключом, например Виженера, сначала оценивают период ключа с помощью индекса совпадений или теста Касиски, а затем отдельно анализируют соответствующие позиции шифротекста.
Практический пример
Предположим, что в достаточно длинном моноалфавитном шифротексте один символ встречается заметно чаще остальных. Он может обозначать О, но также Е, А, пробел или букву, характерную для темы текста. Криптоаналитик проверяет несколько вариантов и ищет подтверждения: естественные сочетания букв, правдоподобные повторяющиеся слова и читаемые фрагменты. Гипотеза становится убедительной, только если одновременно объясняет много наблюдений.
Ограничения
На очень коротких текстах частоты нестабильны. Имена, специальная лексика, особенности орфографии и необычный жанр также искажают языковой профиль. Гомофонная замена, полиалфавитные системы, сжатие и намеренное добавление лишних символов дополнительно ослабляют статистические признаки.
Современное шифрование специально скрывает такие закономерности. При правильном использовании одноразового блокнота независимый случайный ключ делает шифротекст статистически независимым от открытого текста. Конкретное распределение не обязано быть идеально ровным: важно, что оно не раскрывает информацию об исходном сообщении.
Метод особенно полезен против шифра Цезаря, аффинного шифра и других моноалфавитных замен. Он также помогает атаковать Виженера с повторяющимся ключом, если определить его период и иметь достаточно длинный шифротекст.
Универсального минимума нет. На длинных текстах распределения букв и сочетаний устойчивее, а короткое сообщение часто допускает несколько одинаково правдоподобных расшифровок. Важны также жанр текста и устройство шифра.
Если ключ действительно случаен, равен сообщению по длине, хранится в секрете и используется только один раз, наблюдаемый шифротекст совместим с любым открытым текстом той же длины. Его статистика не позволяет определить исходное сообщение.
Нет, если современный алгоритм вроде AES реализован и применяется правильно. Такие алгоритмы рассеивают закономерности открытого текста по всему шифротексту; реальные атаки обычно направлены на ключи, протоколы, реализацию или ошибки использования.