forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
polyalphabetic_cipher_cryptanalysis.tex
120 lines (93 loc) · 14.7 KB
/
polyalphabetic_cipher_cryptanalysis.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
\section[Криптоанализ полиалфавитных шифров]{Криптоанализ полиалфавитных \protect\\ шифров}
\selectlanguage{russian}
При дешифровании полиалфавитных шифров криптоаналитику надо сначала определить период, затем преобразовать шифрограмму в матрицу для предполагаемого периода и использовать для каждого столбца методы криптоанализа моноалфавитных шифров. При неудаче надо изменить предполагаемый период.
Известно несколько методов криптоанализа для нахождения периода. Из них наиболее популярными являются метод Касиски, автокорреляционный метод и метод индекса совпадений.
\subsection{Метод Касиски}
Метод Касиски состоит в том, что в шифротексте находят одинаковые сегменты длины не менее трех символов и вычисляют расстояние между начальными символами последовательных сегментов. Далее находят наибольший общий делитель этих расстояний. Считается, что предполагаемый период $n$ является кратным этому значению. Обычно, нахождение периода осуществляется в несколько этапов.
В результате выбирается наиболее правдоподобное значение периода, а затем криптоаналитик переходит к дешифрованию. Приведем пример использования метода Касиски.
\example
Пусть шифруется следующий текст без учета знаков препинания и различия строчных и прописных букв. Пробелы оставлены в тексте для удобства чтения текста, при шифровании пробелы были опущены.
%\begin{center} \begin{minipage}{0.9\textwidth}
\noindent \textit{Игры различаются по содержанию характерным особенностям а также по тому какое место они занимают в жизни детей их воспитании и обучении Каждый отдельный вид игры имеет многочисленные варианты Дети очень изобретательны Они усложняют и упрощают известные игры придумывают новые правила и детали Например сюжетно ролевые игры создаются самими детьми но при некотором руководстве воспитателя Их основой является самодеятельность Такие игры иногда называют творческими сюжетно ролевыми играми Разновидностью сюжетно ролевой игры являются строительные игры и игры драматизации В практике воспитания нашли свое место и игры с правилами которые создаются для детей взрослыми К ним относятся дидактические подвижные и игры забавы В основе их лежит четко определенное программное содержание дидактические задачи и целенаправленное обучение Для хорошо организованной жизни детей в детском саду необходимо разнообразие игр так как только при этих условиях будет обеспечена детям возможность интересной и содержательной деятельности Многообразие типов видов форм игр неизбежно как неизбежно многообразие жизни которую они отражают как неизбежно многообразие несмотря на внешнюю схожесть игр одного типа модели}
%\end{minipage} \end{center}
Для шифрования выберем период $n=4$ и следующие 4 моноалфавитных шифра замены.
\begin{center} \begin{tabular}{|lcl|}
\hline
абвгдежзийклмнопрстуфхцчшщъыьэюя & -- & алфавит \\
йклмнопрстуфхцчшщъыьэюяабвгдежзи & -- & 1-й шифр \\
гаэъчфсолиевяьщцурнкздбюышхтпмйж & -- & 2-й шифр \\
бфзънаужщмятешлюсдчкэргцйьпвхиыо & -- & 3-й шифр \\
пъерыжсьзтэиуюйфякхалцбмчвншгощд & -- & 4-й шифр \\
\hline
\end{tabular} \end{center}
Тогда шифрованный текст примет следующий вид (в шифротексте пробелов нет, они вставлены для удобства чтения).
\begin{center} \begin{minipage}{0.9\textwidth}
\noindent \textit{съсш щгжисюбщыро фч рлыоуупцлы цйубэыфсюдя лкчааюцщдхия б хйеуж шщ чйхк япуща уорчй чьщьйьщуййч еплжюсчахоищцлщдфснбюсл щ йккцжцлщ эйсншт щчыовхюди ззн лъяд лежон еючълмсртжцьвж лгсзйьчш нфчз чюаюе лжйкуахйнаиеьв йцл ккфщуюийч з ьцсйвгых созжъншшо лъяд цсзнкешлгых цщзшо цспллтп с чахйвщ юйцсзхфс кзсахцщ сйффзшо лъяд рльнгыхъж дпхлез нфчгхл шй шущ юоелхчулу щкяйлщнкыэа ечрюзыгчжфж щц чршйлщм длвожыро кйялыожчжфпшйънх хйещж съсш сьлрнг шпртзпзн чечуцжъещус рысоншй щщтжлтез съспхл спрьлесчшйънхщ ъйужыьл ячваечи щрщт оефжыхъж дхщщщховхюдф щрщт щ змув ыщгепылжпялщ е шубэыляж лщдфснбюсж шпбвщ клща уорчй с лъяд р юяйэщийящ эчнлядф дйрчбщыро ыфжнжыфмерулкфтез у ьщу чншйъжчки чщыйечзафдэсф юйнэщсцта з съсш ргфплт з йъьлео лр иосщх афчэч щюяочаиоьшйо цсймубухьлжъщнжщсбюсфнзнгяхсюакула ьйчбмс лгжффшпшубеффшючф лъьюаюсф нии длячыл йщъбюсолейьшйт сщьцл нжыфм е нфчкуще кйчк юощфцччщуч убьцщлъщгжзо лъя ыгя эйе чйфпяй шущоылр аъвлесжр ъьчах чаакшфцжцг нжыже ечоейпьлкып щюыфсжъьлтс рлыоуупыфтгцщм ыожчжфпшйънщуцщъйчаспрла хсцле ллнйл злях лъя цфщькфуюч ебэ цфщькфуючяшймщлъщгжзо сщьцл яйыщсазщшз чнсппгых угяюолжъосшй хьлрчщфяйощжцфдучнсд цгзюоышщзррйпфдхе лъя ччшймщ чзшг ейнфтз}
\end{minipage} \end{center}
Теперь проведем криптоанализ, используя метод Касиски. Предварительно подсчитаем число появлений каждой буквы в шифротексте. Эти данные приведем в таблице, где $i$ в первой строке означает букву алфавита, а $f_{i}$ во второй строке -- это число появлений этой буквы в шифротексте. Всего в нашем шифротексте имеется $L=1036$ букв.
\begin{center} \resizebox{\textwidth}{!}{ \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$i$ & А & Б & В & Г & Д & Е & Ж & З & И & Й & К & Л & М & Н & О & П \\
$f_{i}$ & 26 & 15 & 11 & 21 & 20 & 36 & 42 & 31 & 13 & 56 & 23 & 70 & 10 & 33 & 36 & 25 \\
\hline
\end{tabular} } \end{center}
\begin{center} \resizebox{\textwidth}{!}{ \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$i$ & Р & С & Т & У & Ф & Х & Ц & Ч & Ш & Щ & Ъ & Ы & Ь & Э & Ю & Я \\
$f_{i}$ & 28 & 54 & 15 & 36 & 45 & 32 & 31 & 57 & 35 & 72 & 32 & 35 & 27 & 11 & 30 & 28 \\
\hline
\end{tabular} } \end{center}
В рассматриваемом примере проведенный анализ показал следующее.
\begin{itemize}
\item Сегмент СЪС встречается в позициях $1, 373, 417, 613$. Соответствующие расстояния равны
\[ \begin{array}{l}
373 - 1 = 372 = 4 \cdot 3 \cdot 31, \\
417 - 373= 44 = 4 \cdot 11, \\
613 - 417 = 196 = 4 \cdot 49. \\
\end{array} \]
Наибольший общий делитель равен $4$. Делаем вывод, что период кратен $4$.
\item Сегмент ЩГЖ встречается в позициях $5, 781, 941$. Соответствующие расстояния равны
\[ \begin{array}{l}
781 - 5 = 776 = 8 \cdot 97, \\
941 - 781 = 160 = 32 \cdot 5. \\
\end{array} \]
Делаем вывод, что период кратен $8$, что не противоречит выводу для предыдущих сегментов (кратность $4$).
\item Сегмент ЫРО встречается в позициях $13, 349, 557$. Соответствующие расстояния равны
\[ \begin{array}{l}
349 - 13 = 336 = 16 \cdot 3 \cdot 7, \\
557 - 349 = 208 = 16 \cdot 13. \\
\end{array} \]
Делаем вывод, что период кратен 4.
\end{itemize}
Предположение о том, что период $n=4$, оказалось правильным.
\exampleend
\subsection{Автокорреляционный метод}
Автокорреляционный метод состоит в том, что исходный шифротекст $C_{1},C_{2}, \ldots, C_{L}$ выписывается в строку, а под ней выписываются строки, полученные сдвигом вправо на $t =1, 2, 3, \ldots$ позиций. Для каждого $t$ подсчитывается число $n_{t}$ индексов $i \in \left[ {1,L - t} \right]$, таких, что $C_i = C_{i + t}$.
Вычисляются автокорреляционные коэффициенты
\[ \gamma_t = \frac{n_t}{L - t}. \]
Для чисел $t$, кратных периоду, коэффициенты должны быть заметно больше, чем для сдвигов, не кратных периоду.
\example
Для рассматриваемой криптограммы выделим те значения $t$, для которых $\gamma _t > 0,05.$ Получим ряд чисел:
\begin{center} \begin{minipage}{0.9\textwidth}
\noindent 4, 12, 16, 24, 28, 32, 36, 40, 44, 48, 52, 56, 64, 68, 72, 76, 80, 84, 88, 92, 96, 104, 108, 112, 116, 124, 128, 132, 140, 148, 152, 156, 160, 164, 168, 172, 176, 180, 184, 188, 192, 196, 200, 204, 208, 216, 220, 224, 228, 252, 256, 260, 264, 268, 272, 276, 280, 284, 288, 292, 296, 300, 304, 308, 312, 316, 320, 324, 328, 344, 348, 356, 364, 368, 372, 376, 380, 384, 388, 396, 400, 404, 408, 412, 420, 424, 432, 436, 440, 448, 452, 456, 460, 462, 468, 472, 476, 480, 484, 496, 500, 508, 512, 516.
\end{minipage} \end{center}
Все эти числа, кроме 462, делятся на 4. Выбираем значение $n=4$, что верно и совпадает со значением, полученным по методу Касиски.
\exampleend
\subsection{Метод индекса совпадений}
При применении метода индекса совпадений подсчитывают число появлений букв в случайной последовательности
\[ \mathbf{X} = (X_1 ,X_2 , \ldots , X_L ) \]
и вычисляют вероятность того, что два случайных элемента этой последовательности совпадают. Эта величина называется индексом совпадений и обозначается $I_{c}(\mathbf{x}),$ где
\[ I_{c} (\mathbf{x}) = \frac{{\sum\limits_{i = 1}^A {f_i (f_i - 1)} }} {{L(L - 1)}}, \]
$f_{i}$ -- число появлений буквы $i$ в последовательности $\mathbf{x}$.
Значение этого индекса используется в криптоанализе полиалфавитных шифров для приближенного определения периода по формуле
\[ m \approx \frac{{k_p - k_r }} {{I_{c} (\mathbf{x}) - k_r + \frac{{k_p - I_{c} (\mathbf{x})}} {L}}}, \]
где
\[ k_r = \frac{1}{A}, ~~ k_p = \sum\limits_{i=1}^A p_i^2, \]
$p_i $ -- частота появления буквы $i$ в естественном языке, $A$ -- число букв в алфавите.
Теоретическое обоснование метода индекса совпадений не является простым. Оно приведено в Приложении \ref{chap:coincide-index} к данному пособию.
\example
В рассматриваемом выше примере приведены значения $f_{i}$. Для русского языка
\[ A=32, ~ k_{r} = \frac{1}{32} \approx 0.03125, ~ k_{p} \approx 0.0529. \]
Проведя вычисления, получаем $m \approx 3.376$. Так что полученное по формуле приближенное значение $3.376$ достаточно близко к значению периода $n=4$.
\exampleend
С развитием ЭВМ многие классические полиалфавитные шифры перестали быть устойчивыми к криптоатакам.