Индекс совпадений

Индекс совпадений — один из методов криптоанализа шифра Виженера. Описание метода опубликовано Уильямом Фридманом в 1922 году.

Предпосылки

Взлом шифра Виженера состоит из двух этапов — определение длины ключевого слова и использование частотного анализа для взлома нескольких шифров Цезаря. C 1863 года можно было использовать метод Касиски, однако этот метод предполагал достаточно длительный ручной поиск совпадающих подстрок, которые также могут иметь низкую вероятность появления в шифротексте. Новый метод, описанный Фридманом в 1922 году, предлагал более быстрый и простой способ определения длины ключа.

Описание метода

Индекс совпадений

Рассмотрим текст, написанный на некотором языке. Алфавит данного языка будем полагать состоящим из $m$ букв. Рассмотрим достаточно длинную строку $\vec x$ из $n$ букв. Если $f_i$ задаёт количество $i$-той буквы алфавита в строке $\vec x$, то можно определить индекс совпадений как вероятность совпадения двух произвольных букв в строке:

$I \left( \vec x \right) = \sum\limits_i {f_i \frac{{f_i - 1}}{{n\left( {n - 1} \right)}}}$

откуда при достаточно больших $n$ и определении $p_i$ как $p_i = f_i / n$ получаем приближённую формулу:

$I \left( \vec x \right) = \sum\limits_i p_i^2$

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

Язык	Индекс совпадений
русский	0,0553[1]
английский	0,0644[1] 0.0667[2]
итальянский	0.0738[2]
испанский	0.0775[2]
немецкий	0.0762[2]
французский	0.0778[2]

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

Для случайной строки символов алфавита это значение примерно равно

$I \left( \vec x \right) \approx {1 \over m}$

то есть 0,03125 для русского языка (без буквы «ё») и 0,03856 для английского языка.

Важным свойством является то, что индекс совпадения для строки не меняется при шифровании этой строки моноалфавитным шифром.

Взаимный индекс совпадений

Теперь рассмотрим две строки $\vec x$ и $\vec y$ с длинами $n$ и $n'$ соответственно, составленные из букв некоторого алфавита. Алфавит также имеет $m$ букв. Взаимным индексом совпадений этих строк будет называть вероятность того, что буква, случайно выбранная из первой строки, совпадёт со случайно выбранной буквой второй строки.

Пусть $f_i, g_i$ — количество $i$-ой буквы алфавита в первой и второй строке соответственно. Тогда взаимный индекс совпадений будет равен:

$MI\left( {\vec x,\vec y} \right) = \frac{{\sum\limits_i {f_i g_i } }}{{nn'}}$

Достаточно легко показать следующие свойства:

1. Если строки относятся к открытым текстам, написанным на одном и том же языке, то их взаимный индекс будет примерно равен табличному индексу для этого языка
2. Если строки совпадают, то их взаимный индекс совпадений примерно равен индексу совпадений (с точностью до $1/n$)
3. Если хотя бы одна из строк является строкой из случайных символов, то взаимный индекс совпадений равен индексу совпадений для случайной строки, то есть $1 / m$
4. При шифровании обоих сравниваемых строк произвольным шифром подстановки (но одинаковым для обоих строк) взаимный индекс не изменяется
5. Если из первой строки $\vec x$ выбрать достаточно большую группу символов $\vec x'$, с такими же частотами символов $p^x_i$, как и в исходной строке, то её взаимный индекс со второй строкой $MI \left( \vec x', \vec y \right)$ будет примерно равен взаимному индексу оригинальной строки и второй строки $MI \left( \vec x, \vec y \right)$

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

Пусть $\vec y_i, \vec y_j$ — строки, зашифрованные шифром Виженера с ключевым словом $\vec k= \overrightarrow {k_1 ,k_2 ,...,k_k }$. Можно показать, что для этих строк величина индекса совпадений примерно равна:

$MI\left( {\vec y_i ,\vec y_j } \right) \approx \sum\limits_i^m {p_{i - k_i } p_{i - k_j } } = \sum\limits_i^m {p_i p_{h + k_i - k_j } }$

Правая часть выражения зависит только от величины $k_i - k_j$, которая называется относительным сдвигом строк $\vec y_i$ и $\vec y_j$. С учётом очевидного равенства

$\sum\limits_i^m {p_i p_{i - \alpha } } = \sum\limits_i^m {p_i p_{i + \alpha } }$

мы можем построить таблицу относительных сдвигов для любого $\alpha$ от $1$ до $m/2$, используя их для нахождения значений и в случае $m / 2 < \alpha < m$.

Для русского языка: Сдвиг Взаимный индекс 0 0,0553 1 0,0366 2 0,0345 3 0,0400 4 0,0340 5 0,0360 6 0,0326 7 0,0241 8 0,0287 9 0,0317 10 0,0265 11 0,0251 12 0,0244 13 0,0291 14 0,0322 15 0,0244 16 0,0249

Для английского языка: Сдвиг Взаимный индекс 0 0,0644 1 0,0394 2 0,0319 3 0,0345 4 0,0436 5 0,0332 6 0,0363 7 0,0389 8 0,0338 9 0,0342 10 0,0378 11 0,0440 12 0,0387 13 0,0428

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

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

Возьмём строку $\vec y$ и последовательно циклически сдвигая строку на $m/2$ позиций построим новые $m/2-1$ строк. Найдём индексы взаимных совпадений между исходной строкой и каждой полученной. Максимальный индекс совпадений между двумя строками будет соответствовать случаю использования одинаковых шифров сдвига для соответствующих букв, то есть в случае когда размер сдвига кратен размеру ключевого слова шифра Виженера. Если строка достаточно длинная (то есть статистика достаточно точная), то можно сравнивать промежуточные значения со значениями из таблиц выше для определения размера сдвига и последующей проверки.

Пример использования

Рассмотрим использование метода индекса совпадений для нахождения периода шифра Виженера. Пусть дан некоторый текст:

МЭИЁЫ РНЁЬЧ ГДКЧГ ЕЖЦМБ ХЩЭЪУ ЩЖЩЩД ГГЧЛП ИУНЛТ ФЮМГЬ ЮЩБЧЪ ЙЁОЪЗ ОПЧМЩ 
ПЦПИЭ ЬЖЮПЩ МХНЪЙ ЁМЪЗЩ ЩГИЧА ЭАЬЭЧ ЩМЪЛЛ ЙКЧМЕ КБНЁЭ ЪБЫКД ЛЬФШМ ЫПЭАТ 
ЬЪИАЧ ТЮШЩФ АВЩЬЖ ОШРАЁ ЧАОЧХ РЫЙЩЮ РЁЦЭР ТФШМГ ЩПМБВ РЙЁМР ИШЁЧЛ ЬТЛИЁ 
ШЩЩБЬ ЖЛЯШЛ КЬШФР ЁНЪГВ КЮГЗУ ЩЖЕЬЦ МЪЩНГ ГЖШМЮ УООЧЯ ЛЯЬТЯ УЁНЪС ДУЬЮЩ 
ГРБЁЭ РНЬЫЗ АДЩЭИ ЩПЪЛЕ УОВЬШ РПГЮТ ЖГПЕГ ЙЩЧЪВ ЩГРЁЪ ЬЖЬАЛ ЙАТУЮ ЪЫЛЛА 
БЖБЫП ЪЛЩЩЭ НАЭЖА ЧЦЭЭА ЛЖЙЩЪ РОЩЁХ ОЧТНМ ШДРПЙ МРЮЕШ ЛНЧМЧ МЩШЛН ЗУНГЙ 
ЬЮАЁМ ЛЙЧПО МЖЩЦЙ ЁШЪКЁ ЭЩМИЙ ЕЖДЬК ИГИПЭ ДЬЛКЁ ФЩЖЯГ РЗАПЬ ЮЗАФЖ ЩПРПЧ 
ЦЪЛЬШ ЪЛЬЬШ МЙЫКЛ ЧЗЮМЕ УУЦЬП ЫМИМЪ ГДЮЭМ ЗЭЯНЗ УНГЙЬ ЮААПЫ ОАМФВ ЬМЪЦЬ 
ОДГЪЩ ЫЪЬЫЛ АГУВГ ЧШЩЩЖ КНЙЁМ ЩЩАТЪ ЯЗКУЖ ГЩЭЪШ ПЭНЁХ ЪЗИЭН МАЬЮО ЧАЫМЫ 
ЩМЛТФ ЮМДЮЦ МЙЩЬЩ БМЖОЧ СЛГЙЬ КНЗУН ЖЫПГГ ЪЩЩЖШ ЮПЪИЦ ФЦВЩШ МЪЫЪК ЕЩОМА 
ШРПЩЩ ХПЙМР ЛЕЩОМ ДПЭРК АЪРЦО РЗИЭН ЖЙПЧЪ ЕЩЫЪЬ ЫМЩГШ РПВЩЧ ЪВЩММ ГЖДГЫ 
ЫЯБАА ШСЮВФ ЛЩХЪК ЕКЮГЕ ЩИРЁЭ ЭРЗКБ КЁНЪР ЕЩЭЖЙ ЖЭЭЙЩ ЧЪВЩЦ РЁЧЯС ДШЪКК 
УНКЬЬ ЮГЗЩМ ИЁЧЯЛ ЧЛЧЬЫ КЮГГЖ ЩМДЮФ ГИЭРП ЙМРЛЕ ЩШСЩТ ОЙЦОЯ МЙЦФХ ЧМДГД 
ЮРБЁЩ ЮАИПБ АФЭЪЗ ЪЩЭРА ШЪЗ

Нам известно, что это шифротекст, в качестве алфавита используется русский алфавит из 33-х букв (то есть включая букву «Ё»). Запишем исходную строку 16 раз, каждый раз циклически сдвигая её на одну позицию влево:

МЭИЁЫРНЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХ...
ЭИЁЫРНЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХН...
ИЁЫРНЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪ...
ЁЫРНЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙ...
ЫРНЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁ...
РНЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМ...
НЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪ...
ЁЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗ...
ЬЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩ...
ЧГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩЩ...
ГДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩЩГ...
ДКЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩЩГИ...
КЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩЩГИЧ...
ЧГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩЩГИЧА...
ГЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩЩГИЧАЭ...
ЕЖЦМБХЩЭЪУЩЖЩЩДГГЧЛПИУНЛТФЮМГЬЮЩБЧЪЙЁОЪЗОПЧМЩПЦПИЭЬЖЮПЩМХНЪЙЁМЪЗЩЩГИЧАЭА...

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

Сдвиг	Количество совпадений	Доля
1	26	0.032
2	22	0.027
3	29	0.036
4	44	0.055
5	21	0.026
6	21	0.026
7	24	0.030
8	44	0.055
9	26	0.032
10	27	0.034
11	21	0.026
12	43	0.054
13	22	0.027
14	21	0.026
15	24	0.030

Из таблицы видно, что потенциальными кандидатами на длину ключа являются 4, 8 и 12. Предполагая, что 4 является длиной ключа, найдём частоты букв в группах (выделены буквы, встретившиеся 10 и более раз):

Буква	А	Б	В	Г	Д	Е	Ё	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
Ожидаемое количество букв (согласно статистике для русского языка)	17	3	8	3	5	16	0	2	4	15	3	7	9	7	13	19	7	11	11	13	6	1	2	1	3	2	1	0	4	4	0	2	4
1-я группа	6	1	2	2	1	0	2	5	1	1	1	10	2	14	4	4	17	0	1	6	12	5	4	5	6	14	32	3	8	13	12	6	1
2-я группа	1	3	1	3	5	2	0	5	1	1	0	3	13	4	10	6	3	20	0	2	3	8	2	6	12	7	11	24	5	6	15	13	6
3-я группа	11	5	2	20	0	0	0	14	7	8	9	8	16	28	9	7	9	11	4	0	1	0	1	3	0	0	7	8	1	1	4	5	2
4-я группа	13	5	7	12	11	13	24	2	9	9	15	2	0	1	0	2	0	0	0	4	0	1	1	2	14	5	13	7	7	16	0	3	2

Глядя на статистику появления отдельных букв в группах (и помня, что у нас используется шифр со сдвигом), можно сделать очевидные предположения о размере сдвига для отдельных групп:

Группа	Сдвиг	Ключевая буква
1-я группа	+11	К
2-я группа	+12	Л
3-я группа	-2, то есть +31	Ю
4-я группа	-9, то есть +24	Ч

Итого, ключевое слово для данного текста — «КЛЮЧ».

Примечания

1. ↑ ^{1 2} Пилиди, 2009, с. 55
2. ↑ ^{1 2 3 4 5} Friedman, 1938, p. 117

Литература

• William Frederick Friedman Military Cryptanalysis. Part II. Simpler vrieties of polyalphabetic substitution systems. — Washington: United States goverment printing office, 1938. — 120 p.
• Пилиди В. С. Криптография. Вводные главы. — Ростов-на-Дону: ЮФУ, 2009. — 110 с.