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

Интернет магазин китайских планшетных компьютеров

Компьютеры - Индекс совпадений

23 января 2011

Оглавление:
1. Индекс совпадений
2. Пример использования

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

Предпосылки

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

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

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

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

$I \left = \sum\limits_i {f_i \frac{{f_i - 1}}{{n\left}}}$

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

$I \left = \sum\limits_i p_i^2$

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

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

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

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

$I \left \approx {1 \over m}$

то есть 0,03125 для русского языка и 0,03856 для английского языка.

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

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

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

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

$MI\left = \frac{{\sum\limits_i {f_i g_i } }}{{nn'}}$

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

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

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

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

$MI\left \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 } }$

мы можем построить таблицу относительных сдвигов для любого α от 1 до m / 2, используя их для нахождения значений и в случае m / 2 < α < 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 строк. Найдём индексы взаимных совпадений между исходной строкой и каждой полученной. Максимальный индекс совпадений между двумя строками будет соответствовать случаю использования одинаковых шифров сдвига для соответствующих букв, то есть в случае когда размер сдвига кратен размеру ключевого слова шифра Виженера. Если строка достаточно длинная, то можно сравнивать промежуточные значения со значениями из таблиц выше для определения размера сдвига и последующей проверки.

<<< Имитозащита

Инфраструктура открытых ключей >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие