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

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

Метод основывается на вычислении вероятности того, что два случайных элемента текста совпадут. Эту вероятность называют индексом совпадений. Уильям Фридман показал, что значения индекса совпадений существенно отличаются для текстов различной природы. Это позволяет сначала определить длину ключа шифра, а затем найти и сам ключ.

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

История

Блез Виженер представил описание простого, но стойкого шифра перед комиссией Генриха III во Франции в 1586 году, и позднее изобретение шифра было присвоено именно ему. Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. Первая успешная атака на шифр Виженера была проведена Фридрихом Касиски в 1863 году. Его метод оставался основным методом криптоанализа шифра Виженера вплоть до 1920 года, когда Уильям Фридман опубликовал монографию «Индекс совпадения и его применение в криптоанализе» (англ. «Index of Coincidence and Its Applications in Cryptography»). Новый метод, описанный Фридманом, предлагал более эффективный и устойчивый к ошибкам способ определения длины ключа. Метод индекса совпадений получил широкое применение. Позднее он стал использоваться в криптоанализе с помощью машин.

Метод криптоанализа шифра Виженера

Шифр Виженера является полиалфавитным шифром. Его криптоанализ можно разбить на 2 этапа:

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

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

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

Общий случай

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

${\displaystyle I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1}\right)}{n\left({n-1}\right)}}}$      ${\displaystyle (1)}$

Доказательство

Будем оценивать вероятность как отношение благоприятных исходов (количество пар одинаковых символов в строке) к общему числу исходов (количество различных пар символов в строке).

Количество различных пар ${\displaystyle {\displaystyle i}}$-ого символа в строке равно: 

${\displaystyle {\displaystyle k_{i}=C_{f_{i}}^{2}={\frac {f_{i}\left({f_{i}-1}\right)}{2}}}}$

Количество пар одинаковых символов в строке:

${\displaystyle {\displaystyle k=\sum _{i=1}^{m}k_{i}=\sum _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1}\right)}{2}}}}$

Число различных пар символов в строке:

${\displaystyle {\displaystyle K=C_{n}^{2}={\frac {n\left({n-1}\right)}{2}}}}$

Отсюда получаем:

${\displaystyle {\displaystyle I\left({\vec {x}}\right)={\frac {k}{K}}=\sum \limits _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1}\right)}{n\left({n-1}\right)}}}}$

Открытый текст

Допустим, строка ${\displaystyle {\vec {x}}}$ является открытым текстом либо получена из него простой перестановкой. В этом случае индекс совпадений удобно выразить через вероятности появления ${\displaystyle i}$-го символа. Обозначим их ${\displaystyle p_{i}}$. Тогда получим следующую формулу:

${\displaystyle I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}p_{i}^{2}}$      ${\displaystyle (2)}$

Т.к. величины ${\displaystyle p_{i}}$ имеют вполне определённые значения, то для открытого текста индекс совпадений не зависит от его содержания, а зависит только от языка, на котором написан текст. Более того, значения ${\displaystyle p_{i}}$ исследованы и известны, что позволяет рассчитать значения индекса совпадений открытого текста для различных языков.

Язык	Индекс совпадений
русский	0.0553[1]
английский	0.0644[1] 0.0667[2]
итальянский	0.0738[2]
испанский	0.0775[2]
немецкий	0.0762[2]
французский	0.0778[2]
ведийский санскрит	0.021076696
пракрит	0.046635758
классический санскрит	0.045567736
хинди	0.041837864
урду	0.057535302

Случайная строка

Наконец, пусть ${\displaystyle {\vec {x}}}$ — случайная строка. Тогда вероятность появления каждого символа равна

${\displaystyle p_{i}={\frac {1}{m}}}$

Используя формулу ${\displaystyle (2)}$, получим:

${\displaystyle I\left({\vec {x}}\right)=\sum _{i=1}^{m}{1 \over m^{2}}={1 \over m}}$      ${\displaystyle (3)}$

Этой формулой можно пользоваться для оценки индекса совпадений полиалфавитного шифра. Для английского языка индекс совпадений полиалфавитного шифра составит 0,03846, для русского (без буквы «ё») — 0,03125.

Значения индекса совпадений для открытого текста и для полиалфавитного шифра существенно различаются. Это позволяет, зная индекс совпадений, определить, получен ли текст из открытого простой перестановкой, или является полиалфавитным шифром.

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

Ещё одним важным понятием является взаимный индекс совпадений.

Общий случай

Рассмотрим две строки ${\displaystyle {\vec {x}}}$ и ${\displaystyle {\vec {y}}}$ с длинами ${\displaystyle n}$ и ${\displaystyle n'}$ соответственно. Алфавит, как и прежде, состоит из ${\displaystyle m}$ символов. Взаимным индексом совпадений этих строк называют вероятность того, что символ, случайно выбранный из первой строки, совпадёт со случайно выбранным символом второй строки. Пусть ${\displaystyle f_{i},g_{i}}$ — количество ${\displaystyle i}$-го символа алфавита в первой и второй строках соответственно. Тогда взаимный индекс совпадений будет равен:

${\displaystyle MI\left({{\vec {x}},{\vec {y}}}\right)={\sum \limits _{i=1}^{m}{\frac {f_{i}g_{i}}{nn'}}}}$      ${\displaystyle (4)}$

Доказательство данной формулы аналогично доказательству формулы ${\displaystyle (1)}$.

Строки со сдвигом

Практически важным для метода индекса совпадений является частный случай, когда обе строки получены сдвигом алфавита открытого текста. Обозначим ${\displaystyle p_{i}}$ — вероятности появления ${\displaystyle i}$-го символа в строке ${\displaystyle {\vec {x}}}$, ${\displaystyle s}$ — сдвиг алфавита строки ${\displaystyle {\vec {y}}}$ относительно алфавита строки ${\displaystyle {\vec {x}}}$ (влево). Тогда вероятности появление ${\displaystyle i}$-го символа алфавита в строке ${\displaystyle {\vec {y}}}$ равны ${\displaystyle p_{i+s}}$ (используется нумерация алфавита строки ${\displaystyle {\vec {x}}}$). Для взаимного индекса совпадений получаем следующую формулу:

${\displaystyle MI\left({{\vec {x}},{\vec {y}}}\right)=\sum \limits _{i=1}^{m}{p_{i}p_{i+s}}}$      ${\displaystyle (5)}$

Заметим, что т.к. сдвиг циклический, то

${\displaystyle \sum \limits _{i=1}^{m}{p_{i}p_{i+s}}=\sum \limits _{i=1}^{m}{p_{i-s}p_{i}}=\sum \limits _{i=1}^{m}{p_{i+m-s}p_{i}}}$

и взаимный индекс совпадений для сдвигов ${\displaystyle s}$ и ${\displaystyle m-s}$ принимает одно и то же значение.

Ниже приведены значения взаимного индекса совпадений в зависимости от сдвига для русского и английского языков. Значения приведены для сдвигов от ${\displaystyle 0}$ до ${\displaystyle m/2}$. Как упоминалось выше, на основе этих значений взаимный индекс совпадений может быть вычислен для любого сдвига.

Для русского языка: Сдвиг Взаимный индекс 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

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

Алгоритм нахождения длины ключа

Разобьём текст ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle ...}$ ${\displaystyle x_{n}}$ на столбцы размера ${\displaystyle t}$.

${\displaystyle x_{1}}$   ${\displaystyle x_{t+1}}$   ${\displaystyle x_{2t+1}}$   ${\displaystyle ...}$

${\displaystyle x_{2}}$   ${\displaystyle x_{t+2}}$   ${\displaystyle x_{2t+2}}$   ${\displaystyle ...}$

${\displaystyle ...}$  ${\displaystyle ...}$   ${\displaystyle ...}$   ${\displaystyle ...}$

${\displaystyle x_{t}}$  ${\displaystyle x_{2t}}$   ${\displaystyle x_{3t}}$   ${\displaystyle ...}$

Если ${\displaystyle t}$ кратно длине ключа, то каждые два элемента текста, отстоящие друг от друга на ${\displaystyle a\times t}$ позиций, ${\displaystyle a\in N}$, зашифрованы одним и тем же алфавитом. А это означает, что каждая строка в выписанной выше таблице получена из открытого текста перестановкой. Если же ${\displaystyle t}$ не кратно длине ключа, то строки являются полиалфавитным шифром.

Ранее было показано, что индекс совпадений для перестановки открытого текста и для полиалфавитного шифра заметно отличается. Таким образом, перебирая различные значения ${\displaystyle t}$ и вычисляя для каждого из них индекс совпадений, мы можем выделить те ${\displaystyle t}$, которые кратны длине ключа. Определить длину ключа по этим данным не составляет труда.

Алгоритм нахождения ключа

Предположим, мы определили длину ключа ${\displaystyle t}$. Найдём теперь сам ключ.

Вновь выпишем текст в столбцы размера ${\displaystyle t}$.

${\displaystyle x_{1}}$   ${\displaystyle x_{t+1}}$   ${\displaystyle x_{2t+1}}$   ${\displaystyle ...}$

${\displaystyle x_{2}}$   ${\displaystyle x_{t+2}}$   ${\displaystyle x_{2t+2}}$   ${\displaystyle ...}$

${\displaystyle ...}$  ${\displaystyle ...}$   ${\displaystyle ...}$   ${\displaystyle ...}$

${\displaystyle x_{t}}$  ${\displaystyle x_{2t}}$   ${\displaystyle x_{3t}}$   ${\displaystyle ...}$

Рассмотрим две строки этой таблицы. Сдвинем алфавит одной из строк на ${\displaystyle s}$ символов и вычислим взаимный индекс совпадений полученных строк. Т.к. каждая из этих двух строк получена сдвигом алфавита открытого текста, то максимум взаимного индекса совпадений будет наблюдаться при нулевом конечном относительном сдвиге.

Поэтому применяется следующий алгоритм: вычисляется взаимный индекс совпадений для различных ${\displaystyle s}$, ищется значение ${\displaystyle s}$, при котором взаимный индекс совпадений максимален. Тогда начальный относительный сдвиг строк будет равен ${\displaystyle m-s}$ (${\displaystyle m}$ — размер алфавита). Вычисляются относительные сдвиги между всеми парами строк. Т.к. сдвиги строк таблицы соответствуют сдвигам букв ключа, то остаётся перебрать ${\displaystyle m}$ возможных ключей и выбрать из них наиболее правдоподобный.

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

Пусть дан некоторый текст, зашифрованный шифром Виженера. Найдём ключевое слово и прочитаем открытый текст.

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

Ввиду того, что полный алгоритм поиска длины ключа является крайне громоздким, вычислим индекс совпадений только для ${\displaystyle t=5}$ и убедимся, что длина ключа действительно равна 5.

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

Значения индекса совпадений для каждой из строк:

Строка	Индекс совпадений
1	0.05676
2	0.05896
3	0.06340
4	0.05810
5	0.07230

Процесс поиска относительных сдвигов строк также приведём в кратком виде:

Строка	Сдвиг	Взаимный индекс совпадений
1	—	—
2	6	0.05494
3	3	0.05798
4	16	0.06068
5	3	0.06045

Найденное ключевое слово: «слово».

После расшифровки получаем следующий открытый текст:

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

Примечания

1. Пилиди, 2009, с. 55.
2. 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. Архивная копия от 11 сентября 2010 на Wayback Machine
• Пилиди В. С. Криптография. Вводные главы. — Ростов-на-Дону: ЮФУ, 2009. — 110 с.
• Бауэр Ф., Расшифрованные секреты. Методы и принципы криптологии: Пер. сангл. - М.: Мир, 2007. - 550 с. — ISBN 5-03-003551-6
• Жданов О.Н., Куденкова И.А. Криптоанализ классических шифров — Красноярск 2008