Частотный анализ

Типичное распределение букв в тексте на французском языке. Слабые шифры недостаточно маскируют распределение, и это может быть использовано криптоаналитиками для чтения сообщения

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

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

В простом шифре подстановки каждая буква (символ) исходного текста заменяется какой-либо другой в зашифрованном тексте. При дешифровании анализируется частота повторения этого символа в зашифрованном тексте и сравнивается с частотой типичного распределения букв в тексте данного языка. Аналогичные рассуждения применяются к биграммам (двубуквенным последовательностям), триграммам и так далее в случае полиалфавитных шифров.

Данный метод известен с IX века (работы Ал-Кинди), хотя одной из самых известных его реализаций считается расшифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 году.

Со второй половины XX века большинство алгоритмов шифрования претерпели многократное усложнение и разрабатываются с учетом устойчивости к частотному криптоанализу. При современных вычислительных мощностях классические шифры вряд ли обеспечат какую-либо реальную защиту конфиденциальных данных, поэтому их использование в основном ограничено обучением будущих криптографов.

Описание

В основе лежит понимание, что вероятность появления отдельных букв и их последовательность в словах и фразах следуют статистическим паттернам (англ. pattern — узор, образец, шаблон). Например, сочетание букв «ся» в русском языке встречается значительно чаще, чем «цы», а «оь» вовсе отсутствует (но зато может быть частым в чеченском языке). При анализе достаточно длинного текста, зашифрованного методом замены, можно отследить частоты появления символов и восстановить исходный текст, заменяя символы обратно.

Как было уже сказано, ключевыми характеристиками текста являются повторяемость букв (набор букв в каждом языке ограничен), пар букв, то есть m (m-грамм), сочетаемость букв друг с другом, смена гласных и согласных и другие признаки. Эти характеристики оказываются достаточно стабильными.

Методологически подразумевается подсчёт числа вхождений каждой n^m из возможных m-грамм в достаточно длинных открытых текстах T=t₁t₂...t_l, состоящих из букв алфавита {a₁, a₂, ..., a_n}. При этом анализируются подряд идущие m-граммы текста:

t₁t₂...t_m, t₂t₃... t_m+1, ..., t_i-m+1t_l-m+2...t_l.

Если L(a_i1a_i2...a_im) - это количество появлений m-граммы a_i1a_i2...a_im в тексте T, и L - это общее число подсчитанных m-грамм, то при достаточно больших значениях L частоты L(a_i1a_i2...a_im)/L для данной m-граммы отличаются незначительно.

Из этого следует, что относительная частотность используется как приближение вероятности P(a_i1a_i2...a_im) появления данной m-граммы в случайно выбранной части текста, что составляет основу статистического определения вероятности.

С математической точки зрения, частотность букв в процентах вычисляется так: подсчитывается число вхождений буквы в шифротексте, затем это число делится на общее число букв в тексте, что дает число шифрованных символов. Если необходимо получить значение в процентах, результат просто умножается на 100.

Однако частотность не полностью определяется только длиной текста, важен также его стиль. К примеру, та же буква Ф, редко встречающаяся в обычных текстах, в технической литературе может появляться значительно чаще. Для более точного определения средней частотности букв важно использовать разнообразные тексты.

Возможно, что открытый текст не демонстрирует ожидаемого распределения частот букв или их сочетаний. Более короткие сообщения, вероятно, будут иметь больше вариаций. Также возможно создание искусственно искажённых текстов. Например, были написаны целые романы, в которых вообще отсутствует буква e — форма литературы, известная как липограмма.

Частотный анализ в художественной литературе

Шифрованное послание в виде «Танцующих человечков»

Частотный анализ был описан в художественной литературе. Это «Золотой жук» Эдгара По, «Пляшущие человечки» Конан Дойля и «Дети капитана Гранта» Жюля Верна, которые являются примерами историй, в которых описывается использование частотного анализа для взлома простых шифров с заменой. Шифр в рассказе По инкрустирован несколькими средствами обмана, но это скорее литературный прием, чем что-либо значимое с точки зрения реальной криптографии.

См. также

• Шифр Плейфера
• Шифр Виженера
• Полиалфавитный шифр
• Частотность
• Криптоанализ

Литература

• Михаил Адаменко. Основы классической криптологии. Секреты шифров и кодов. — ДМК-Пресс, 2001. — 296 с. — ISBN 978-5-97060-090-0.
• Липограмма // Литературная энциклопедия терминов и понятий / Под ред. А. Н. Николюкина. — Интелвак, 2016. — Стб. 449—450. — 1596 с. — ISBN 5-93264-026-X.

Ссылки

Анализ текстов