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

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

Описание

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

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

Частотный анализ играет чрезвычайно важную роль при взломе шифров, а также при расшифровки древних надписей. Возможно, наиболее известным результатом в этой области служит расшифровка египетских иероглифов Дж.-Ф.Шампольоном в 1822 году. Ключом к расшифровке послужил камень Розетты. На камне один текст записан тремя способами: иероглифическим, демотическим и по-гречески.

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

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

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

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

Частотные характеристики текстовых сообщений

Как упоминалось выше, важными характеристиками текста являются повторяемость букв (количество различных букв в каждом языке ограничено), пар букв, т.е.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.

Но существует некоторая разница значений частот, которая объясняется тем, что частоты существенно зависят не только от длины текста, но и от характера текста. Например, текст может быть технического содержания, где редкая буква Ф может стать довольно частой. Поэтому для надежного определения средней частоты букв желательно иметь набор различных текстов.

См. также

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

Литература

• Книга:С.Коутинхо. Введение в теорию чисел. Алгоритм RSA. Москва: Постмаркет, 2001. - 328 с.

Ссылки

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