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

Частотный анализ – это один из методов криптоанализа, основывающийся на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей как в открытом тексте, так и шифрованном тексте, которое с точностью до замены символов будет сохраняться в процессе шифрования и дешифрования. Кратко говоря, частотный анализ предполагает, что частота появления заданной буквы алфавита в достаточно длинных текстах одна и та же для разных текстов одного языка. При этом в случае моноалфавитного шифрования, если в шифрованном тексте будет символ с аналогичной вероятностью появления, то можно предположить, что он и является указанной зашифрованной буквой. Аналогичные рассуждения применяются к биграммам (двубуквенным последовательностям), триграммам в случае полиалфавитных шифров. Частотный анализ. Одним из методов атак является частотный анализ. Распределение букв в криптотексте сравнивается с распределением букв в алфавите исходного сообщения. Буквы с наибольшей частотой в криптотексте заменяются на букву с наибольшей частотой из алфавита. Вероятность успешного вскрытия повышается с увеличением длины криптотекста. Метод частотного анализа известен с еще IX-го века и связан и именем АлКинди. Но наиболее известным случаем применения такого анализа является дешифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 году. Данный вид анализа основывается на том, что текст состоит из слов, а слова из букв. Количество различных букв в каждом языке ограничено и буквы могут быть просто перечислены. Важными характеристиками текста являются повторяемость букв, пар букв (биграмм) и вообще m-ок (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие. Идея состоит в подсчете чисел вхождений каждой nm возможных m-грамм в достаточно длинных открытых текстах T=t1t2…tl, составленных из букв алфавита {a1, a2, ..., an}. При этом просматриваются подряд идущие m-граммы текста: t1t2...tm, t2t3... tm+1, ..., ti-m+1tl-m+2...tl. Если – число появлений m-граммы ai1ai2...aim в тексте T, а L – общее число подсчитанных m-грамм, то опыт показывает, что при достаточно больших L частотыдля данной m-граммы мало отличаются друг от друга. В силу этого, относительную частоту считают приближением вероятности P (ai1ai2...aim) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности). Существуют множество различных таблиц о распределении букв в том или ином языке, но ни одна из них не содержит окончательной информации - даже порядок букв может отличаться в различных таблицах. Распределение букв очень сильно зависит от типа теста: проза, разговорный язык, технический язык и т.п. Практически в каждом языке примерно девять букв заполняют около 70% любого текста – остальное распределение зависит от содержания и формы текста. В представленной ниже таблице приводятся частоты встречаемости букв в русском языке (в процентах): Буква Показатель частоты Буква Показатель частоты алфавита встречаемости алфавита встречаемости А В Д Ж И К М О 0,062 0,038 0,025 0,007 0,062 0,028 0,026 0,09 Р Т Ф Ц Ш Ъ, Ь Э Я 0,04 0,053 0,002 0,004 0,006 0,014 0,003 0,018 Имеется мнемоническое правило запоминания десяти наиболее частых букв русского алфавита. Эти буквы составляют слово СЕНОВАЛИТР. Устойчивыми являются также частотные характеристики биграмм, триграмм и четырехграмм осмысленных текстов. Существуют специальные таблицы с указанием частоты биграмм некоторых алфавитов. По результатам исследований с помощью таких таблиц ученые определили наиболее часто встречаемые биграммы и триграммы для русского алфавита: СТ, НО, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО, СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА. Из таблиц биграмм можно также легко извлечь информацию о сочетаемости букв, т.е. о предпочтительных связях букв друг с другом. Результатом таких исследований является таблица, в которой слева и справа от каждой буквы расположены наиболее предпочтительные «соседи» (в порядке убывания частоты соответствующих биграмм). В таких таблицах обычно указывается также доля гласных и согласных букв (в процентах), предшествующих (или следующих за) данной букве. Г 3 80 68 78 72 19 83 89 27 55 77 80 55 11 65 55 69 57 15 70 90 69 82 67 84 14 58 43 С 97 20 32 22 28 81 17 11 73 45 23 20 45 89 35 45 31 43 85 30 10 31 18 33 16 100 100 86 42 57 Слева л, д, к, т, в, р, н я, е, у, и, а, о я, т, а, е, и, о р, у, а, и, е, о р, я, у, а, и, е, о м, и, л, д, т, р, н р, е, и, а, у, о о, е, а, и р, т, м, и, о, л, н ь, в, е, о, а, и, с г, в, ы, и, е, о, а я, ы, а, и, е, о д, ь, н, о р, п, к, в, т, н в, с, у, а, и, е, о и, к, т, а, п, о, е с, т, в, а, е, и, о ч, у, и, а, е, о, с п, т, к, д, н, м, р н, а, е, о, и у, е, о, а, ы, и е, ю, н, а, и е, а, у, и, о ь, у, ы, е, о, а, и, в е, б, а, я, ю м, р, т, с, б, в, н н, с, т, л с, ы, м, л, д, т,, р, н ь, о, а, и, л, у о, н, р, л, а, и, с А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Э Ю Я Справа л, н, с, т, р, в, к, м о, ы, е, а, р, у о, а, и, ы, с, н, л, р о, а, р, л, и, в е, а, и, о, н, у, р, в н, т, р, с, л, в, м, и е, и, д, а, н а, н, в, о, м, д с, н, в, и, е, м, к, з о, а, и, р, у, т, л, е и, е, о, а, ь, я, ю, у и, е, о, у, а, н, п, ы о, а, и, е, ы, н, у в, с, т, р, и, д, н, м о, р, е, а, у, и, л а, е, о, и, у, я, ы, н т, к, о, я, е, ь, с, н о, а, е, и, ь, в, р, с т, п, с, д, н, ю, ж и, е, о, а, е, о, а о, и, с, н, в, п, р и, е, а, ы е, и, т, н е, и, н, а, о, л е, и, а л, х, е, м, и, в, с, н н, к, в, п, с, е, о, и н, т, р, с, к д, т, щ, ц, н, п в, с, т, п, д, к, м, л Г 12 81 60 69 68 12 71 51 25 73 75 73 80 15 68 80 32 63 16 81 43 93 66 68 97 56 24 11 16 С 88 19 40 31 32 88 29 49 75 27 25 27 20 85 32 20 68 37 84 19 57 7 34 32 3 44 76 100 89 84 Давно известно, что буквы в естественных языках распределены не равномерно. К примеру, частоты появления букв английского языка в текстах имеют следующие значения: Т.е. в английском тексте наиболее встречающимися буквами будут E, T, A. В то время как самыми редкими буквами являются J, Q, Z. Следовательно, посчитав частоту появления каждой буквы в тексте мы можем определить насколько частотная характеристика текста соответствует английскому языку. Простейшая защита против атак, основанных на подсчете частот, обеспечивается в системе омофонов (HOMOPHONES) - однозвучных подстановочных шифров, в которых один символ открытого текста отображается на несколько символов шифротекста, их число пропорционально частоте появления буквы. Шифруя букву исходного сообщения, мы выбираем случайно одну из ее замен. Следовательно простой подсчет частот ничего не дает криптоаналитику. Однако доступна информация о распределении пар и троек букв в различных естественных языках. Криптоанализ, основанный на такой информации будет более успешным. шифры моноалфавитной замены довольно легко расшифровать даже без знания ключа. Делается это при помощи частотного анализа зашифрованного текста - надо посчитать, сколько раз каждая буква встречается в тексте, и затем поделить на общее число букв. Получившуюся частоту надо сравнить с эталонной. Самая частая буква для русского языка - это буква О, за ней идѐт Е и т.д. Правда, работает частотный анализ на больших литературных текстах. Если текст маленький или очень специфический по используемым словам, то частотность букв будет отличаться от эталонной, и времени на разгадывание придѐтся потратить больше. Ниже приведена таблица частотности букв (то есть относительной частоты встречаемых в тексте букв) русского языка, рассчитанная на базе НКРЯ. Использование метода частотного анализа для расшифровки шифрованных сообщений красиво описано во многих литературных произведениях, например, у Артура КонанаДойля в романе «Пляшущие человечки» или у Эдгара По в «Золотом жуке».