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

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

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

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

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

Описание

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

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

Ссылки

• [www.statistica.ru/local-portals/data-mining/analiz-tekstov/ Анализ текстов] (недоступная ссылка) [web.archive.org/web/20121025133027/www.statsoft.ru/home/portal/exchange/textanalysis.htm Архивировано из первоисточника 25 октября 2012.] Проверено 15 августа 2013.

Отрывок, характеризующий Частотный анализ

– Как видно, Nicolas! – сказал голос Сони. – Николай оглянулся на Соню и пригнулся, чтоб ближе рассмотреть ее лицо. Какое то совсем новое, милое, лицо, с черными бровями и усами, в лунном свете, близко и далеко, выглядывало из соболей.
«Это прежде была Соня», подумал Николай. Он ближе вгляделся в нее и улыбнулся.
– Вы что, Nicolas?
– Ничего, – сказал он и повернулся опять к лошадям.
Выехав на торную, большую дорогу, примасленную полозьями и всю иссеченную следами шипов, видными в свете месяца, лошади сами собой стали натягивать вожжи и прибавлять ходу. Левая пристяжная, загнув голову, прыжками подергивала свои постромки. Коренной раскачивался, поводя ушами, как будто спрашивая: «начинать или рано еще?» – Впереди, уже далеко отделившись и звеня удаляющимся густым колокольцом, ясно виднелась на белом снегу черная тройка Захара. Слышны были из его саней покрикиванье и хохот и голоса наряженных.
– Ну ли вы, разлюбезные, – крикнул Николай, с одной стороны подергивая вожжу и отводя с кнутом pуку. И только по усилившемуся как будто на встречу ветру, и по подергиванью натягивающих и всё прибавляющих скоку пристяжных, заметно было, как шибко полетела тройка. Николай оглянулся назад. С криком и визгом, махая кнутами и заставляя скакать коренных, поспевали другие тройки. Коренной стойко поколыхивался под дугой, не думая сбивать и обещая еще и еще наддать, когда понадобится.
Николай догнал первую тройку. Они съехали с какой то горы, выехали на широко разъезженную дорогу по лугу около реки.
«Где это мы едем?» подумал Николай. – «По косому лугу должно быть. Но нет, это что то новое, чего я никогда не видал. Это не косой луг и не Дёмкина гора, а это Бог знает что такое! Это что то новое и волшебное. Ну, что бы там ни было!» И он, крикнув на лошадей, стал объезжать первую тройку.
Захар сдержал лошадей и обернул свое уже объиндевевшее до бровей лицо.
Николай пустил своих лошадей; Захар, вытянув вперед руки, чмокнул и пустил своих.
– Ну держись, барин, – проговорил он. – Еще быстрее рядом полетели тройки, и быстро переменялись ноги скачущих лошадей. Николай стал забирать вперед. Захар, не переменяя положения вытянутых рук, приподнял одну руку с вожжами.
– Врешь, барин, – прокричал он Николаю. Николай в скок пустил всех лошадей и перегнал Захара. Лошади засыпали мелким, сухим снегом лица седоков, рядом с ними звучали частые переборы и путались быстро движущиеся ноги, и тени перегоняемой тройки. Свист полозьев по снегу и женские взвизги слышались с разных сторон.
Опять остановив лошадей, Николай оглянулся кругом себя. Кругом была всё та же пропитанная насквозь лунным светом волшебная равнина с рассыпанными по ней звездами.
«Захар кричит, чтобы я взял налево; а зачем налево? думал Николай. Разве мы к Мелюковым едем, разве это Мелюковка? Мы Бог знает где едем, и Бог знает, что с нами делается – и очень странно и хорошо то, что с нами делается». Он оглянулся в сани.
– Посмотри, у него и усы и ресницы, всё белое, – сказал один из сидевших странных, хорошеньких и чужих людей с тонкими усами и бровями.
«Этот, кажется, была Наташа, подумал Николай, а эта m me Schoss; а может быть и нет, а это черкес с усами не знаю кто, но я люблю ее».
– Не холодно ли вам? – спросил он. Они не отвечали и засмеялись. Диммлер из задних саней что то кричал, вероятно смешное, но нельзя было расслышать, что он кричал.
– Да, да, – смеясь отвечали голоса.
– Однако вот какой то волшебный лес с переливающимися черными тенями и блестками алмазов и с какой то анфиладой мраморных ступеней, и какие то серебряные крыши волшебных зданий, и пронзительный визг каких то зверей. «А ежели и в самом деле это Мелюковка, то еще страннее то, что мы ехали Бог знает где, и приехали в Мелюковку», думал Николай.
Действительно это была Мелюковка, и на подъезд выбежали девки и лакеи со свечами и радостными лицами.
– Кто такой? – спрашивали с подъезда.
– Графские наряженные, по лошадям вижу, – отвечали голоса.