3.5. Криптоанализ полиалфавитных шифров

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

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

3.5.1. Метод Касиски

Метод Касиски, созданный Фридрихом Вильгельмом Касиски (нем. Friedrich Wilhelm Kasiski, 1805--1881, [51]), состоит в том, что в шифртексте находят одинаковые сегменты длиной не менее трёх символов и вычисляют расстояния между начальными символами последовательных сегментов. Далее находят наибольший общий делитель этих расстояний. Считается, что предполагаемый период $n$ является кратным этому значению. Обычно нахождение периода осуществляется в несколько этапов.

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

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

Игры различаются по содержанию характерным особенностям а также по тому какое место они занимают в жизни детей их воспитании и обучении Каждый отдельный вид игры имеет многочисленные варианты Дети очень изобретательны Они усложняют и упрощают известные игры придумывают новые правила и детали Например сюжетно ролевые игры создаются самими детьми но при некотором руководстве воспитателя Их основой является самодеятельность Такие игры иногда называют творческими сюжетно ролевыми играми Разновидностью сюжетно ролевой игры являются строительные игры и игры драматизации В практике воспитания нашли своё место и игры с правилами которые создаются для детей взрослыми К ним относятся дидактические подвижные и игры забавы В основе их лежит четко определенное программное содержание дидактические задачи и целенаправленное обучение Для хорошо организованной жизни детей в детском саду необходимо разнообразие игр так как только при этих условиях будет обеспечена детям возможность интересной и содержательной деятельности Многообразие типов видов форм игр неизбежно как неизбежно многообразие жизни которую они отражают как неизбежно многообразие несмотря на внешнюю схожесть игр одного типа модели

Для шифрования выберем период $n=4$ и следующие 4 моноалфавитных шифра замены:

абвгдежзийклмнопрстуфхцчшщъыьэюя	–	алфавит
йклмнопрстуфхцчшщъыьэюяабвгдежзи	–	1-й шифр
гаэъчфсолиевяьщцурнкздбюышхтпмйж	–	2-й шифр
бфзънаужщмятешлюсдчкэргцйьпвхиыо	–	3-й шифр
пъерыжсьзтэиуюйфякхалцбмчвншгощд	–	4-й шифр

Тогда шифрованный текст примет следующий вид (в шифртексте пробелов нет, они вставлены для удобства чтения):

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

Теперь проведём криптоанализ, используя метод Касиски. Предварительно подсчитаем число появлений каждой буквы в шифртексте. Эти данные приведём в таблице, где $i$ в первой строке означает букву алфавита, а $f_{i}$ во второй строке – это число появлений этой буквы в шифртексте. Всего в нашем шифртексте имеется $L=1036$ букв.

$i$	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П
$f_{i}$	26	15	11	21	20	36	42	31	13	56	23	70	10	33	36	25

$i$	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
$f_{i}$	28	54	15	36	45	32	31	57	35	72	32	35	27	11	30	28

В рассматриваемом примере проведённый анализ показал следующее.

Сегмент СЪС встречается в позициях $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$.
Сегмент ЩГЖ встречается в позициях $5, 781, 941$. Соответствующие расстояния равны
$$ \begin{array}{l} 781 - 5 = 776 = 8 \cdot 97, \\ 941 - 781 = 160 = 32 \cdot 5. \\ \end{array} $$
Делаем вывод, что период кратен $8$, что не противоречит выводу для предыдущих сегментов (кратность $4$).
Сегмент ЫРО встречается в позициях $13, 349, 557$. Соответствующие расстояния равны
$$ \begin{array}{l} 349 - 13 = 336 = 16 \cdot 3 \cdot 7, \\ 557 - 349 = 208 = 16 \cdot 13. \\ \end{array} $$
Делаем вывод, что период кратен 4.

Предположение о том, что период $n=4$, оказалось правильным.

3.5.2. Автокорреляционный метод

Автокорреляционный метод состоит в том, что исходный шифртекст $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$, кратных периоду, коэффициенты должны быть заметно больше, чем для $t$, не кратных периоду.

Пример. Для рассматриваемой криптограммы выделим те значения $t$, для которых $\gamma _t~>~0{,}05.$ Получим ряд чисел:

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.

Все эти числа, кроме 462, делятся на 4. Выбираем значение $n=4$, которое верно и совпадает со значением, полученным по методу Касиски.

3.5.3. Метод индекса совпадений

Метод индекса совпадений был описан Уильямом Фредериком Фридманом в 1922 году (англ. William Frederick Friedman, 1891--1969, [41]). При применении метода индекса совпадений подсчитывают число появлений букв в случайной последовательности

$$ \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}$, $A$ – число букв в алфавите.

Значение этого индекса используется в криптоанализе полиалфавитных шифров для приближённого определения периода по формуле:

$$ 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$ в естественном языке. Теоретическое обоснование метода индекса совпадений не является простым. Оно приведено в приложении 16.9 к данному пособию.

Пример. В рассматриваемом выше примере приведены значения $f_{i}$. Для русского языка:

$$ A=32, ~ k_{r} = \frac{1}{32} \approx 0.03125, ~ k_{p} \approx 0.0529. $$

Проведя вычисления, получаем $m \approx 3.376$. Полученное по формуле приближённое значение m достаточно близко к значению периода $n=4$.

С развитием ЭВМ многие классические полиалфавитные шифры перестали быть устойчивыми к криптоатакам.