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

Самой распространённой буквой в алфавите русского языка можно смело назвать «о». Не «а», хотя все дети учат первые слова именно с этой буквой: «мама», «папа» или «дай». Не «и», хотя может показаться, что мы часто употребляем ее как соединительный союз.

Как показывают данные, именно буква «о» имеет частотность, превышающую 0, 1%, по сравнению с другими гласными буквами алфавита, у которых частотность составляет, например, 0,07-0,08%, это немало

Среди согласных на первом месте стоит буква «н».

Такие данные получают путем анализа частотности в НКРЯ – Национальном корпусе русского языка, по специальной формуле. НКРЯ – это электронный архив письменных и устных текстов, который состоит примерно из 230 миллионов словоупотреблений.

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

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

Забавно, правда? Не такая уж и чепуха выходит:)

Кстати, в английском языке самой распространенной буквой является “е". А согласной – “t"

Ну, и тавтограмма на английском языке:

Minerva-like majestic Mary moves.

Law, Latin, Liberty, learned Lucy loves.

Eliza"s elegance each eye espies.

Serenely silent Susan"s smiles surprise.

From fops, fools, flattery, fairest Fanny flies.

В данной статье мы начнем обсуждение чрезвычайно интересной темы - применение статистики для анализа текстовой информации. Заметим, что применение статистики для анализа текстов - традиционная задача.

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

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

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

Используя систему STATISTICA Вы можете проверить эти закономерности, например, в текстах Интернет.

Идея состоит в подсчете чисел вхождений каждой n m возможных m -грамм в достаточно длинных открытых текстах T =t 1 t 2 …t l , составленных из букв алфавита {a 1 , a 2 , ..., a n }. При этом просматриваются подряд идущие m -граммы текста:

t 1 t 2 ...t m , t 2 t 3 ... t m+1 , ..., t i-m+1 t l-m+2 ...t l .

Если – число появлений m -граммы a i1 a i2 ...a im в тексте T , а L – общее число подсчитанных m -грамм, то опыт показывает, что при достаточно больших L частоты

для данной m -граммы мало отличаются друг от друга.

В силу этого, относительную частоту (1) считают приближением вероятности P (a i1 a i2 ...a im ) появления данной m -граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

Ниже приводится таблицы частот букв (в процентах) ряда европейских языков. Данные заимствованы из книги .

Буква алфавита Французский язык Немецкий язык Английский язык Испанский язык Итальянский язык
A 7.68 5.52 7.96 12.90 11.12
B 0.80 1.56 1.60 1.03 1.07
C 3.32 2.94 2.84 4.42 4.11
D 3.60 4.91 4.01 4.67 3.54
E 17.76 19.18 12.86 14.15 11.63
F 1.06 1.96 2.62 0.70 1.15
G 1.10 3.60 1.99 1.00 1.73
H 0.64 5.02 5.39 0.91 0.83
I 7.23 8.21 7.77 7.01 12.04
J 0.19 0.16 0.16 0.24 -
K - 1.33 0.41 - -
L 5.89 3.48 3.51 5.52 5.95
M 2.72 1.69 2.43 2.55 2.65
N 7.61 10.20 7.51 6.20 7.68
O 5.34 2.14 6.62 8.84 8.92
P 3.24 0.54 1.81 3.26 2.66
Q 1.34 0.01 0.17 1.55 0.48
R 6.81 7.01 6.83 6.95 6.56
S 8.23 7.07 6.62 7.64 4.81
T 7.30 5.86 9.72 4.36 7.07
U 6.05 4.22 2.48 4.00 3.09
V 1.27 0.84 1.15 0.67 1.67
W - 1.38 1.80 - -
X 0.54 - 0.17 0.07 -
Y 0.21 - 1.52 1.05 -
Z 0.07 1.17 0.05 0.31 1.24

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

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

Наглядное представление о частотах букв дает диаграмма встречаемости. Так, для ангийского языка, в соответствии с таблицей, такая диаграмма изображена на рис.1. Для ее построения мы импользовали систему STATISTICA .

Для русского языка частоты (в порядке убывания) знаков алфавита, в котором отождествлены E c Ё , Ь с Ъ , а также имеется знак пробела (-) между словами, приведены в следующей таблице (см. ).

-
0.175 		О
0.090 		Е, Ё
0.072 		А
0.062
И
0.062 		Т
0.053 		Н
0.053 		С
0.045
Р
0.040 		В
0.038 		Л
0.035 		К
0.028
М
0.026 		Д
0.025 		П
0.023 		У
0.021
Я
0.018 		Ы
0.016 		З
0.016 		Ь, Ъ
0.014
Б
0.014 		Г
0.013 		Ч
0.012 		Й
0.010
Х
0.009 		Ж
0.007 		Ю
0.006 		Ш
0.006
Ц
0.004 		Щ
0.003 		Э
0.003 		Ф
0.002

На основании таблицы получаем следующую диаграмму частот (рис.2).

Имеется мнемоническое правило запоминания десяти наиболее частых букв русского алфавита. Эти буквы составляют нелепое слово СЕНОВАЛИТР. Можно также предложить аналогичный способ запоминания частых букв английского языка, например с помощью слова TETRIS-HONDA (см. таблицу).

Устойчивыми являются также частотные характеристики биграмм, триграмм и четырехграмм осмысленных текстов.

Приведем таблицы частот биграмм для русского и английского языков (таблицы заимствованы из книги ). Для удобства они разбиты на четыре части по следующей схеме:

Часть1 Часть2
Часть3 Часть4

Часть 1

А Б В Г Д Е Ж З И Й К Л М Н О П
А 2 12 35 8 14 7 6 15 7 7 19 27 19 45 5 11
Б 5 9 1 6 6 2 21
В 35 1 5 3 3 32 2 17 7 10 3 9 58 6
Г 7 3 3 5 1 5 1 50
Д 25 3 1 1 29 1 1 13 1 5 1 13 22 3
Е 2 9 18 11 27 7 5 10 6 15 13 35 24 63 7 16
Ж 5 1 6 12 5 6
З 35 1 7 1 5 3 4 2 1 2 9 9 1
И 4 6 22 5 10 21 2 23 19 11 19 21 20 32 8 13
Й 1 1 4 1 3 1 2 4 5 1 2 7 9 7
К 24 1 4 1 4 1 1 26 1 4 1 2 66 2
Л 25 1 1 1 1 33 2 1 36 1 2 1 8 30 2
М 18 2 4 1 1 21 1 2 23 3 1 3 7 19 5
Н 54 1 2 3 3 34 58 3 1 24 67 2
О 1 28 84 32 47 15 7 18 12 29 19 41 38 30 9 18
П 7 15 4 9 1 46

Часть 2

Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Э Ю Я
А 26 31 27 3 1 10 6 7 10 1 2 6 9
Б 8 1 6 1 11 2
В 6 19 6 7 1 1 2 4 1 18 1 2 3
Г 7 2
Д 6 8 1 10 1 1 1 5 1 1
Е 39 37 33 3 1 8 3 7 3 3 1 1 2
Ж 1
З 3 1 2 4 4
И 11 29 29 3 1 17 3 11 1 1 1 3 17
Й 3 10 2 1 3 2
К 10 3 7 10 1
Л 3 1 6 4 1 3 20 4 9
М 2 5 3 9 1 2 5 1 1 3
Н 1 9 9 7 1 5 2 36 3 5
О 43 50 39 3 2 5 2 12 4 3 2 3 2
П 41 1 6 2 2

Часть 3

А Б В Г Д Е Ж З И Й К Л М Н О П
Р 55 1 4 4 3 37 3 1 24 3 1 3 7 56 2
С 8 1 7 1 2 25 6 40 13 3 9 27 11
Т 35 1 27 1 3 31 1 28 5 1 1 11 56 4
У 1 4 4 4 11 2 6 3 2 8 5 5 5 1 5
Ф 2 2 2 1
Х 4 1 4 1 3 1 2 3 4 3 3 4 18 5
Ц 3 7 10 2 1
Ч 12 23 13 2 6
Ш 5 11 14 1 2 2 2
Щ 3 8 6 1
Ы 1 9 1 3 12 2 4 7 3 6 6 3 2 10
Ь 2 4 1 1 2 2 2 6 3 13 2 4
Э 1 1
Ю 2 1 2 1 3 1 1 1 1 1 3
Я 1 3 9 1 3 3 1 5 3 2 3 3 4 6 3 6

Часть 4

Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Э Ю Я
Р 1 5 9 16 1 1 1 2 8 3 5
С 4 11 82 6 1 1 2 2 1 8 17
Т 26 18 2 10 1 11 21 4
У 7 14 7 1 8 3 2 9 1
Ф 1 1
Х 3 4 2 2 1 1
Ц 1 1
Ч 7 1 1 1
Ш 1 1
Щ 1
Ы 3 9 4 1 16 1 2
Ь 1 11 3 1 4 1 3 1
Э 1 9
Ю 1 1 7 1 1 4
Я 3 6 10 2 1 4 1 1 1 1 1

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

Для получения более точных сведений об открытых текстах можно строить и анализировать таблицы k -грамм при k >2, однако для учебных целей вполне достаточно ограничиться биграммами. Неравномерность k -грамм (и даже слов) тесно связана с характерной особенностью открытого текста – наличием в нем большого числа повторений отдельных фрагментов текста: корней, окончаний, суффиксов, слов и фраз. Так, для русского языка такими привычными фрагментами являются наиболее частые биграммы и триграммы:

СТ, НО, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО
СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА

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

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

Сочетаемость букв русского языка:

Г С Слева Справа Г С
3 97 л, д, к, т, в, р, н A л, н, с, т, р, в, к, м 12 88
80 20 я, е, у, и, а, о Б о, ы, е, а, р, у 81 19
68 32 я, т, а, е, и, о В о, а, и, ы, с, н, л, р 60 40
78 22 р, у, а, и, е, о Г о, а, р, л, и, в 69 31
72 28 р, я, у, а, и, е, о Д е, а, и, о, н, у, р, в 68 32
19 81 м, и, л, д, т, р, н Е н, т, р, с, л, в, м, и 12 88
83 17 р, е, и, а, у, о Ж е, и, д, а, н 71 29
89 11 о, е, а, и З а, н, в, о, м, д 51 49
27 73 р, т, м, и, о, л, н И с, н, в, и, е, м, к, з 25 75
55 45 ь, в, е, о, а, и, с К о, а, и, р, у, т, л, е 73 27
77 23 г, в, ы, и, е, о, а Л и, е, о, а, ь, я, ю, у 75 25
80 20 я, ы, а, и, е, о М и, е, о, у, а, н, п, ы 73 27
55 45 д, ь, н, о Н о, а, и, е, ы, н, у 80 20
11 89 р, п, к, в, т, н О в, с, т, р, и, д, н, м 15 85
65 35 в, с, у, а, и, е, о П о, р, е, а, у, и, л 68 32
55 45 и, к, т, а, п, о, е Р а, е, о, и, у, я, ы, н 80 20
69 31 с, т, в, а, е, и, о С т, к, о, я, е, ь, с, н 32 68
57 43 ч, у, и, а, е, о, с Т о, а, е, и, ь, в, р, с 63 37
15 85 п, т, к, д, н, м, р У т, п, с, д, н, ю, ж 16 84
70 30 н, а, е, о, и Ф и, е, о, а, е, о, а 81 19
90 10 у, е, о, а, ы, и Х о, и, с, н, в, п, р 43 57
69 31 е, ю, н, а, и Ц и, е, а, ы 93 7
82 18 е, а, у, и, о Ч е, и, т, н 66 34
67 33 ь, у, ы, е, о, а, и, в Ш е, и, н, а, о, л 68 32
84 16 е, б, а, я, ю Щ е, и, а 97 3
0 100 м, р, т, с, б, в, н Ы л, х, е, м, и, в, с, н 56 44
0 100 н, с, т, л Ь н, к, в, п, с, е, о, и 24 76
14 86 с, ы, м, л, д, т, р, н Э н, т, р, с, к 0 100
58 42 ь, о, а, и, л, у Ю д, т, щ, ц, н, п 11 89
43 57 о, н, р, л, а, и, с Я в, с, т, п, д, к, м, л 16 84

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

Наблюдения над открытыми текстами показывают, что для условных вероятностей выполняются неравенства p(a i1)≠p(a i1 /a i2) , p(a i1 /a i2)≠p(a i1 /a i2 a i3) ,....

Систематически вопрос о зависимости букв алфавита в открытом тексте от предыдущих букв исследовался известным русским математиком А. А. Марковым (1856 – 1922). Он доказал, что появления букв в открытом тексте нельзя считать независимыми друг от друга. В связи с этим А. А. Марковым отмечена еще одна устойчивая закономерность открытых текстов, связанная с чередованием гласных и согласных букв. Им были подсчитаны частоты встречаемости биграмм вида гласная-гласная (г , г ), гласная-согласная (г , с ), согласная-гласная (с , г ), согласная-согласная (с , с ) в русском тексте длиной в 10 5 знаков. Результаты подсчета отражены в следующей таблице:

Г С Всего
Г 6588 38310 44898
С 38296 16806 55102

Из этой таблицы видно, что для русского языка характерно чередование гласных и согласных, причем относительные частоты могут служить приближениями соответствующих условных и безусловных вероятностей:

p (г /с )≈0.663, p (с /г )≈0.872,
p (г )≈0.432, p (с )≈0.568.

После А. А. Маркова зависимость появления букв текста вслед за несколькими предыдущими исследовал методами теории информации К. Шеннон. Фактически им было показано, в частности, что такая зависимость ощутима на глубину приблизительно в 30 знаков, после чего она практически отсутствует.

Доля гласных букв в литературном тексте:

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

В качестве примера приведем частотные характеристики букв английского алфавита, входящих в состав кода ASCII.

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

Литература:

Алферов А.П. и др., "Криптография"

Яглом А.М., Яглом И.М., Вероятость и информация, М.: Наука, 1973.

Baudouin C., Elements de cryptographie / Ed. Pedone A. – Paris, 1939.

Friedman W. F., Callimahos D., Military cryptanalysis, Part i, Vol 2, Aegean Park Press, Laguna Hills CA, 1920.

so dominating and happy individuality that Youth is drawn to him as is a fly to a sugar bowl. (см. ).

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

Частоты встречаемости букв в других языках, кроме английского

Для любого языка с алфавитной записью шифр простой замены вскрывается описанным выше методом: подсчетом частот встречаемости знаков с последующим использованием контекстной информации языка. Ясно, что для этого криптоаналитику необходимо по крайней мере неплохо знать язык, хотя в случае шифра простой замены ему не обязательно говорить на нем свободно. Не менее очевидно, что подсчет частот встречаемости знаков в типичном отрывке текста будет для разных языков давать разные результаты, хотя для языков с общей основой, такой как латынь, это отличие будет меньше, чем для языков различного происхождения. Не во всех языках используется 26-буквенный алфавит; в некоторых букв меньше - в итальянском обычно употребляются только 22; в других, например в русском, букв больше, а в третьих (например, в китайском), алфавита вообще нет. Поскольку итальянцы обычно не используют буквы K, W и Y, то их частоты полагают равными нулю, но если в итальянском тексте упоминается Нью-Йорк (New York), то и эти буквы в нем встретятся. Во французском и немецком языках необходимо различать гласные с различными диакритическими знаками (акцентами и умляутами), но ради упрощения приведенных ниже таблиц все формы одной и той же буквы подсчитывались вместе. Так, для французского языка частоты букв E, E, E и E учтены вместе в суммарной частоте буквы E. Числа также исключены из подсчета, кроме тех, которые записаны словами; все неалфавитные символы (пробел, запятая, точка, кавычки, точка с запятой и т.д.) учтены в графе "другие". Заглавные и строчные буквы считались одинаковыми. В таблице 2.6 приведены (с учетом приведенных оговорок) частоты встречаемости букв для четырех европейских языков в расчете на 1000 знаков. Для удобства мы повторяем здесь таблицу частот встречаемости букв английского языка.

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

различных произношения. В английском языке она встречается гораздо реже, а в других языках и вовсе очень редка. Подсчеты также показывают, что букву N можно назвать "наиболее постоянной буквой", поскольку во всех пяти языках частота ее встречаемости практически одинакова - от 6% до 7% всех букв латинского алфавита. Объяснение сути статистических тестов, применяемых обычно для сравнения частот, подобных приведенным здесь, можно найти в ; дополнительный комментарий содержится в приложении M20.

Таблица 2.6

английский

французский

немецкий

итальянский

валлийский

Сколько знаков необходимо для дешифрования простой замены?

Выше в примере 2.2 у нас было в наличии 265 знаков, и дешифрование простой замены оказалось не очень трудным делом. Смогли бы мы справиться с ним столь же легко, будь у нас, к примеру, 120 знаков? И вообще (этот вопрос уже ставился нами ранее), каково минимальное число знаков, которое, скорее всего, окажется достаточным для криптоаналитика при дешифровании подобного шифра? На данный вопрос отвечает теория информации: оценку этого числа дает формула, зависящая от частот одиночных знаков или полиграфов языка. В описано применение этой формулы для конкретного приложения. Если использовать только частоты отдельных знаков, то для шифра простой замены, возможно, окажется достаточно 200 знаков, но использование диграфов (таких как ON, IN или AT) или триграфов (таких как THE или AND) чрезвычайно усиливает возможности дешифрования. Полагают, что в этом случае может оказаться достаточно всего 50 или 60 знаков.

Задача 2.1 Перехвачен шифрованный текст на английском языке длиной 202 знака.

Известно, что использован шифр простой замены, и что пробелы в открытом тексте заменены на букву Z, а все остальные знаки препинания опущены. Есть основания полагать, что автор предпочитает использовать устаревшую форму местоимения "thy" вместо местоимения "your". Дешифруйте текст.

VHEOC WZIHC BUUCW HDWZB IRWDH TDOZH VIHVI YBWIU HQOWU HUFWH ZOXBI LHTBI LWDHG DBUWE HVIRH FVXBI LHGDB UHZOX WEHOI HIODH VCCHU FPHQB WUPHI ODHGB UHEFV CCHCN DWHBU HSVYJ HUOHY VIYWC HFVCT HVHCB IWHIO DHVCC HUFPH UWVDE HGVEF HONUH VHGOD RHOTH BU

Пример 2.2 показывает, что хотя шифры простой замены вскрыть гораздо сложнее, чем шифры Юлия Цезаря, всё же их слишком легко дешифровать, и поэтому применение их не имеет большого смысла. Для вскрытия такого шифра криптоаналитику всего лишь необходимо иметь достаточный объем шифрованного текста (это соответствует первой ситуации, упомянутой в предыдущей главе). Если ему известен также и соответствующий открытый текст (как во второй ситуации), его задача становится просто тривиальной, если только "сообщение" не состоит из очень малого числа различных букв. В третьей ситуации, когда у криптоаналитика есть возможность подобрать текст для зашифрования, ему достаточно задать такое "сообщение":

ABCDEFGHIJKLMNOPQRSTUVWXYZ

и его работа на этом завершена.

Несведущему читателю может показаться, что поскольку число различных вариантов превосходит 1026 (то есть сто миллионов миллионов миллионов миллионов), то задача вскрытия шифра простой замены только по шифрованному тексту (для решения которой методом "грубой силы", как уже отмечалось ранее, компьютеру потребуются миллионы лет для перебора всех вариантов) является невыполнимой. Однако мы только что видели, как это можно сделать вручную в течение часа, если использовать известные неравновероятные частоты встречаемости знаков и грамматические правила английского, или любого другого языка, на котором составлено сообщение, вкупе с любой доступной контекстной информацией. Из этого следует один очень важный урок:

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

Итак, на следующем этапе мы рассмотрим способы повышения стойкости этих простых методов шифрования. Это сделано в следующей главе.

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

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

Метод частотного анализа известен с еще 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-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

В представленной ниже таблице приводятся частоты встречаемости букв в русском языке (в процентах):

Буква алфавита Буква алфавита Показатель частоты встречаемости
А 0,062 Р 0,04
В 0,038 Т 0,053
Д 0,025 Ф 0,002
Ж 0,007 Ц 0,004
И 0,062 Ш 0,006
К 0,028 Ъ, Ь 0,014
М 0,026 Э 0,003
О 0,09 Я 0,018

Имеется мнемоническое правило запоминания десяти наиболее частых букв русского алфавита. Эти буквы составляют слово СЕНОВАЛИТР .

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

СТ, НО, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО, СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА.

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

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

Г С Слева Справа Г С
3 97 л, д, к, т, в, р, н А л, н, с, т, р, в, к, м 12 88
80 20 я, е, у, и, а, о Б о, ы, е, а, р, у 81 19
68 32 я, т, а, е, и, о В о, а, и, ы, с, н, л, р 60 40
78 22 р, у, а, и, е, о Г о, а, р, л, и, в 69 31
72 28 р, я, у, а, и, е, о Д е, а, и, о, н, у, р, в 68 32
19 81 м, и, л, д, т, р, н Е н, т, р, с, л, в, м, и 12 88
83 17 р, е, и, а, у, о Ж е, и, д, а, н 71 29
89 11 о, е, а, и З а, н, в, о, м, д 51 49
27 73 р, т, м, и, о, л, н И с, н, в, и, е, м, к, з 25 75
55 45 ь, в, е, о, а, и, с К о, а, и, р, у, т, л, е 73 27
77 23 г, в, ы, и, е, о, а Л и, е, о, а, ь, я, ю, у 75 25
80 20 я, ы, а, и, е, о М и, е, о, у, а, н, п, ы 73 27
55 45 д, ь, н, о Н о, а, и, е, ы, н, у 80 20
11 89 р, п, к, в, т, н О в, с, т, р, и, д, н, м 15 85
65 35 в, с, у, а, и, е, о П о, р, е, а, у, и, л 68 32
55 45 и, к, т, а, п, о, е Р а, е, о, и, у, я, ы, н 80 20
69 31 с, т, в, а, е, и, о С т, к, о, я, е, ь, с, н 32 68
57 43 ч, у, и, а, е, о, с Т о, а, е, и, ь, в, р, с 63 37
15 85 п, т, к, д, н, м, р У т, п, с, д, н, ю, ж 16 84
70 30 н, а, е, о, и Ф и, е, о, а, е, о, а 81 19
90 10 у, е, о, а, ы, и Х о, и, с, н, в, п, р 43 57
69 31 е, ю, н, а, и Ц и, е, а, ы 93 7
82 18 е, а, у, и, о Ч е, и, т, н 66 34
67 33 ь, у, ы, е, о, а, и, в Ш е, и, н, а, о, л 68 32
84 16 е, б, а, я, ю Щ е, и, а 97 3
0 100 м, р, т, с, б, в, н Ы л, х, е, м, и, в, с, н 56 44
0 100 н, с, т, л Ь н, к, в, п, с, е, о, и 24 76
14 86 с, ы, м, л, д, т, р, н Э н, т, р, с, к 0 100
58 42 ь, о, а, и, л, у Ю д, т, щ, ц, н, п 11 89
43 57 о, н, р, л, а, и, с Я в, с, т, п, д, к, м, л 16 84

Пример: Проведем анализ текста следующего содержания

"СОКРАТ из Афин (469–399 до н.э.) – знаменитый античный философ, учитель Платона, воплощенный идеал истинного мудреца в исторической памяти человечества. С именем Сократа связано первое фундаментальное деление истории античной философии на до- и после-Сократовскую («Досократики»), отражающее интерес ранних философов VI–V вв. к натурфилософии, а последующего поколения софистов V в. – к этико-политическим темам, главная из которых – воспитание добродетельного человека и гражданина. Сократу был близок софистическому движению. Учение Сократа было устным; все свободное время он проводил в беседах с приезжими софистами и местными гражданами, политиками и обывателями, друзьями и незнакомыми на темы, ставшими традиционными для софистической практики: что есть добро и что – зло, что прекрасно, а что безобразно, что добродетель и что порок, можно ли научиться быть хорошим и как приобретается знание. Об этих беседах мы знаем в основном благодаря ученикам Сократа – Ксенофонту и Платону. Кроме их сочинений, имеются также фрагменты и свидетельства о содержании «сократических диалогов» других сократиков, пародийное изображение Сократа в комедии Аристофана Облака и ряд замечаний о Сократе у Аристотеля. Проблема достоверности изображения личности Сократа в сохранившихся произведениях – ключевой вопрос всех исследований о нем."

в поле ввода этот текст и получаем ответ

Проведен анализ текста

Количество символов в тексте 1329

Количество пробелов 179

Количество цифр 6

Количество точек и запятых 25

Количество английских букв 4

Количество русских букв 1094

Посимвольная статистика и частотный анализ

Символ встречается 179 раз. Частота 13.47%

Символ о встречается 130 раз. Частота 9.78%

Символ и встречается 117 раз. Частота 8.80%

Символ а встречается 88 раз. Частота 6.62%

Символ е встречается 86 раз. Частота 6.47%

Символ с встречается 70 раз. Частота 5.27%

Символ н встречается 70 раз. Частота 5.27%

Символ т встречается 70 раз. Частота 5.27%

Символ р встречается 55 раз. Частота 4.14%

Метод, предложенный Аль-Кинди легче объяснить с точки зрения русского алфавита. Прежде всего, необходимо изучить достаточно длинный отрывок текста на русском языке, или несколько отрывков разных текстов, чтобы установить частоту появлений каждой буквы алфавита. В русском языке о - самая частая буква, после неё е , затем а и так далее, как указано в таблице. Потом изучим зашифрованный текст и установим частоту появлений каждого символа в нём. Например, если самый частый символ в зашифрованном тексте Ю , то, вероятнее всего, его следуют заменить на букву о . Если второй по частоте символ зашифрованного текста Э , то его, вероятно, следует заменить на е , и так далее. Благодаря методу Аль-Кинди, известному как частотный криптоанализ, не нужно проверять каждый из миллиардов потенциальных ключей. Вместо этого можно расшифровать сообщение просто проанализировав частоту символов в нём.

Таблица относительных частот букв русского алфавита.
Буква Частота % Буква Частота % Буква Частота % Буква Частота %
О 11,08 Р 4,45 Ы 1,96 Х 0,89
Е, Ё 8,41 В 4,33 Ь 1,92 Ш 0,81
А 7,92 К 3,36 З 1,75 Ю 0,61
И 6,83 М 3,26 Г 1,74 Э 0,38
Н 6,72 Д 3,05 Б 1,71 Щ 0,37
Т 6,18 П 2,81 Ч 1,47 Ц 0,36
С 5,33 У 2,80 Й 1,12 Ф 0,19
Л 5,00 Я 2,13 Ж 1,05 Ъ 0,02

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

Если не удаётся расшифровать криптограмму с помощью простого частотного криптоанализа (например если сообщение слишком короткое), Ал-Кинди предлагает использовать характерные сочетания букв или, наоборот, несочетаемость определённых букв друг с другом. Например, наиболее распространённые биграммы (группы из двух букв) русского языка: ст , но , ен , то , на , ов , ни , ра , во , ко . Важна статистика сочетаемости гласных и согласных букв. Например перед буквами ь , ы , ъ и после э не могут стоять гласные, а после любой гласной буквы следует согласная с вероятностью 87 %. Так же подсказкой для криптоаналитика могут быть общепринятые вступительные слова, которые используются почти в каждом языке. Например в арабском часто употреблялось «Во имя Бога, милостивого и милосердного» (بسم الله الرحمن الرحيم). При расшифровке стихотворений можно использовать рифмы и стопы.

Арабские буквы: их порядок и повторяемость

Ал-Кинди приводит таблицу с частотами букв арабского алфавита, вычисленными в выборке из семи листов текста.

В арабском алфавите 28 букв. Из них 27 могут обозначать согласные звуки, 3 (ﺍ (/aː/), ﻭ (/uː/), ﻱ (/iː/)) - долгие гласные звуки, букв, обозначающих короткие гласные, - нет (например в слове Муха́ммед пишутся только четыре согласные буквы: محمد). Таким образом в арабском письме преобладают чисто согласные буквы. Однако этот факт не противоречит указанному в начале трактата утверждению о том что самая частая буква на письме любого языка, как правило, гласная, так как в арабском таковой является ﺍ (/aː/).

Рекомендуем почитать