Частотный криптоанализ

Частотный криптоанализ — это метод взлома шифров, основанный на анализе частоты появления отдельных символов, их сочетаний (биграмм, триграмм) или других элементов зашифрованного текста. Метод опирается на статистические закономерности открытого языка, в частности на то, что в любом естественном языке одни буквы, слоги и слова встречаются значительно чаще других. Частотный криптоанализ является одним из старейших и наиболее известных методов криптоанализа, эффективным прежде всего против простых моноалфавитных шифров замены (шифр Цезаря, шифр простой замены) и некоторых полиалфавитных систем при недостаточной длине ключа.

История

Ранние упоминания и арабский период

Первое известное описание частотного криптоанализа принадлежит арабскому учёному Аль-Кинди (IX век). В его трактате «Рукопись о расшифровке криптографических сообщений» изложен принцип: «Один из способов расшифровать зашифрованное сообщение, если мы знаем язык оригинала, — это найти в зашифрованном тексте наиболее часто встречающуюся букву, а затем сопоставить её с наиболее частой буквой известного языка». Этот метод применялся для взлома арабской криптографии, основанной на замене букв.

Развитие в Европе

В Европе частотный криптоанализ стал широко известен в эпоху Возрождения. Итальянский учёный Леон Баттиста Альберти в XV веке описал принципы частотного анализа в своём трактате «О шифрах». Однако практическое применение метода началось с работ французского дипломата и криптографа Блеза де Виженера (XVI век), который, несмотря на изобретение полиалфавитного шифра, также подробно описал методы его взлома, включая частотный анализ.

Классический период

В XVII–XIX веках частотный криптоанализ стал основным инструментом криптографических служб европейских государств. Например, «Чёрный кабинет» во Франции и аналогичные структуры в Австрии и Англии активно использовали этот метод для перехвата дипломатической и военной переписки. В России частотный криптоанализ применялся в работе криптографических служб при императорском дворе, а также в деятельности Министерства иностранных дел.

XX век и современность

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

Теоретические основы

Статистические закономерности языка

Частотный криптоанализ базируется на том, что в любом естественном языке распределение букв неравномерно. Для русского языка наиболее частые буквы — о, е (и её вариант ё), а, и, н, т, с. Редкие — ф, щ, ъ, э, ю. Аналогично для английского: e, t, a, o, i, n, s, h, r.

Кроме того, существуют закономерности для биграмм (пар букв) и триграмм. Например, в русском языке биграмма «ст» встречается чаще, чем «яъ», а триграмма «про» — чаще, чем «жые».

Принцип работы

1. Подсчёт частот — для зашифрованного текста строится таблица частот каждого символа.
2. Сравнение с эталоном — полученные частоты сравниваются с известным распределением для языка оригинала (например, для русского языка — по частотам букв в литературных текстах).
3. Гипотеза замены — наиболее частый символ в шифротексте предполагается соответствующей наиболее частой букве языка (например, если самый частый символ — «X», то это, вероятно, «о» или «е»).
4. Проверка — гипотеза проверяется на осмысленность полученного открытого текста. Если текст становится читаемым, ключ найден; если нет — корректировка.

Ограничения

• Короткие тексты — при длине сообщения менее 100–200 символов статистические закономерности могут не проявиться из-за случайных отклонений.
• Полиалфавитные шифры — частотный анализ эффективен только для моноалфавитных шифров; для полиалфавитных (например, шифр Виженера) требуется предварительное определение длины ключа (метод Касиски или индекс совпадений).
• Современные алгоритмы — симметричные шифры (AES, ГОСТ 28147-89) и асимметричные (RSA) устойчивы к частотному анализу, так как их выходные данные статистически неотличимы от случайных.

Применение

Взлом классических шифров

Частотный криптоанализ является основным методом для расшифровки исторических сообщений, зашифрованных простой заменой. Например, он широко применяется при анализе шифров средневековых рукописей, дипломатической переписки XVII–XIX веков, а также в криптоанализе шифра Цезаря.

Криптоанализ в компьютерных играх и головоломках

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

Исторические исследования

Историки и лингвисты применяют частотный криптоанализ для расшифровки древних текстов, написанных неизвестными алфавитами или зашифрованных простыми методами. Например, он использовался при анализе рукописи Войнича, хотя окончательного успеха не принёс.

Обучение криптографии

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

Примеры

Шифр Цезаря

Шифр Цезаря — простейший моноалфавитный шифр со сдвигом. Частотный анализ позволяет определить сдвиг: если в зашифрованном тексте чаще всего встречается буква «В», а в русском языке — «О», то сдвиг составляет 2 (В → О). После сдвига на 2 позиции назад весь текст расшифровывается.

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

Пусть дан шифротекст: «ХЩЖФ ЪЮЧВ ЮЖШЧ ЪЮЧВ». Подсчёт частот показывает, что «Ч» встречается 2 раза, «Ю» — 2 раза, «Ъ» — 1 раз, «Ж» — 1 раз. По эталону русского языка, наиболее частые буквы — «о», «е», «а». Гипотеза: «Ч» = «о», «Ю» = «е». Подстановка даёт «ХЩЖФ ЪечВ еЖШч ЪечВ». После проверки и корректировки (например, «Ж» = «т», «Щ» = «л») получается осмысленный текст: «ХЛТФ ЪечВ еТШч ЪечВ» — что может быть «ХЛТФ ЪЕЧВ ЕТШЧ ЪЕЧВ» (после уточнения — «ХЛТФ» = «СЛОВ»). В итоге текст: «СЛОВО ЕЩЁ ЕСТЬ ЕЩЁ» (гипотетический пример).

Критика и ограничения

Неэффективность против современных шифров

Частотный криптоанализ бесполезен против современных симметричных и асимметричных алгоритмов, так как их выходные данные не имеют статистических закономерностей, отличных от случайных. Например, шифр AES (Advanced Encryption Standard) даёт равномерное распределение байтов в зашифрованном тексте.

Зависимость от длины текста

Для надёжного применения метода требуется текст длиной не менее 200–300 символов. Для коротких сообщений (например, паролей или коротких фраз) частотный анализ даёт ложные результаты.

Ошибки при нестандартных языках

Если открытый текст написан на языке с нестандартным распределением (например, стихотворение, технический текст с большим количеством цифр), эталонные частоты могут не совпадать, что приводит к ошибкам.

Устойчивость к полиалфавитным шифрам

Для шифра Виженера частотный анализ напрямую не работает: требуется сначала определить длину ключа (методом Касиски или индексом совпадений), а затем анализировать каждый столбец отдельно. Это усложняет процесс, но не делает его невозможным.

Интересные факты

• В 2011 году с помощью частотного криптоанализа была расшифрована часть переписки итальянского художника Леонардо да Винчи, зашифрованная простой заменой.
• В русском языке наиболее частой буквой является «о» (около 10,9% в среднем по текстам), а наиболее редкой — «ф» (около 0,2%).
• Частотный криптоанализ упоминается в романе Эдгара По «Золотой жук», где главный герой расшифровывает криптограмму, используя подсчёт частот букв.
• В советской криптографии частотный анализ применялся для взлома шифров немецких войск в начальный период Великой Отечественной войны, когда использовались простые коды.

Источники

• Аль-Кинди. «Рукопись о расшифровке криптографических сообщений» (IX век).
• Кан Д. «Взломщики кодов» (1967).
• Шнайер Б. «Прикладная криптография» (1996).
• Баричев С.Г., Гончаров В.В., Серов Р.Е. «Основы современной криптографии» (2002).
• Материалы курса «Криптография и криптоанализ» (МГУ, 2015).