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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править исходный текст]

Блез Виженер представил описание простого, но стойкого шифра перед комиссией Генриха III во Франции в 1586 году, и позднее изобретение шифра было присвоено именно ему. Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. В 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

См. также[править | править исходный текст]

Литература[править | править исходный текст]