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

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

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

Расчет

Индекс совпадения показывает, насколько вероятно, что вы нарисуете две совпадающие буквы, выбрав случайным образом две буквы из заданного текста. Вероятность появления данной буквы в тексте равна (количество раз, когда эта буква встречается / длина текста). Шанс снова нарисовать ту же самую букву (без замены) равен (появления — 1 / длина текста — 1). Произведение этих двух значений дает вам возможность нарисовать эту букву дважды подряд. Можно найти этот продукт для каждой буквы, которая встречается в тексте, а затем суммировать эти продукты, чтобы получить шанс получить две одинаковые буквы. Затем эту вероятность можно нормализовать, умножив ее на некоторый коэффициент, обычно 26 на английском языке.

$\mathbf {IC} =c\times \left({\left({{\frac {n_{\mathrm {a} }}{N}}\times {\frac {n_{\mathrm {a} }-1}{N-1}}}\right)+\left({{\frac {n_{\mathrm {b} }}{N}}\times {\frac {n_{\mathrm {b} }-1}{N-1}}}\right)+\cdots +\left({{\frac {n_{\mathrm {z} }}{N}}\times {\frac {n_{\mathrm {z} }-1}{N-1}}}\right)}\right)$

где c — нормирующий коэффициент (26 для английского языка), n _a — количество раз, когда буква «а» встречается в тексте, а N — длина текста.

Мы можем выразить индекс совпадения IC для данного частотного распределения букв в виде суммирования:

$\mathbf {IC} ={\frac {\displaystyle \sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)/c}}$

где N — длина текста, а от n ₁ до n _c — частоты (в виде целых чисел) c букв алфавита ( c = 26 для однокорпусного английского языка ). Сумма n _i равна N. обязательно

Произведения n ( n − 1) подсчитывают количество комбинаций из n элементов, взятых по два за раз. (На самом деле при этом каждая пара учитывается дважды; дополнительные множители 2 встречаются как в числителе, так и в знаменателе формулы и, таким образом, сокращаются.) Каждое из n _i вхождений i -й буквы соответствует каждому из оставшихся n _i − 1 вхождений. того же письма. Всего N ( N − 1) во всем тексте пар букв, и 1/ c — это вероятность совпадения для каждой пары при условии равномерного случайного распределения символов («нулевая модель»; см. ниже). . Таким образом, эта формула дает отношение общего количества наблюдаемых совпадений к общему количеству совпадений, которое можно было бы ожидать от нулевой модели.

Ожидаемое среднее значение IC можно вычислить на основе относительных частот букв f _i исходного языка:

$\mathbf {IC} _{\mathrm {expected} }={\frac {\displaystyle \sum _{i=1}^{c}{f_{i}}^{2}}{1/c}}.$

Если бы все буквы алфавита были равновероятными, ожидаемый индекс был бы равен 1,0. Фактический монографический IC для телеграфного английского текста составляет около 1,73, что отражает неравномерность распределения букв на естественном языке .

Иногда значения приводятся без нормализующего знаменателя, например 0,067 = 1,73/26 для английского языка; такие значения можно назвать κ _p («каппа-открытый текст»), а не IC, при этом κ _r («каппа-случайный») используется для обозначения знаменателя 1/ c (который представляет собой ожидаемую частоту совпадений для равномерного распределения одних и тех же значений). алфавит, 0,0385=1/26 для английского языка). Английский открытый текст обычно находится где-то в диапазоне от 1,5 до 2,0 (нормализованный расчет).

Приложение

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

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

Чтобы понять почему, представьте себе «алфавит», состоящий только из двух букв А и Б. Предположим, что в нашем «языке» буква А используется 75% времени, а буква Б — 25% времени. Если два текста на этом языке положить рядом, то можно ожидать появления следующих пар:

Пара	Вероятность
АА	56.25%
ББ	6.25%
АБ	18.75%
НЕТ	18.75%

В целом вероятность «совпадения» составляет 62,5% (56,25% для АА + 6,25% для ББ).

Теперь рассмотрим случай, когда оба сообщения зашифрованы с использованием простого одноалфавитного шифра замены , который заменяет A на B и наоборот:

Пара	Вероятность
АА	6.25%
ББ	56.25%
АБ	18.75%
НЕТ	18.75%

Общая вероятность совпадения в этой ситуации составляет 62,5% (6,25% для АА + 56,25% для ББ), ровно такая же, как и для случая незашифрованного «открытого текста». По сути, новый алфавит, полученный в результате замены, представляет собой просто единообразное переименование исходных личностей символов, которое не влияет на их совпадение.

Теперь предположим, что только одно сообщение (скажем, второе) зашифровано с использованием одного и того же шифра замены (A,B)→(B,A). Теперь можно ожидать следующие пары:

Пара	Вероятность
АА	18.75%
ББ	18.75%
АБ	56.25%
НЕТ	6.25%

Теперь вероятность совпадения составляет всего 37,5% (18,75% для АА + 18,75% для ББ). Это заметно ниже, чем вероятность использования текстов на одном языке и на одном алфавите. Очевидно, совпадения более вероятны, когда наиболее часто встречающиеся буквы в каждом тексте совпадают.

Тот же принцип применим к реальным языкам, таким как английский, потому что некоторые буквы, такие как E, встречаются гораздо чаще, чем другие буквы — факт, который используется при анализе частоты шифров замены . Например, совпадения с буквой Е относительно вероятны. Таким образом, при сравнении любых двух английских текстов количество совпадений будет выше, чем при использовании текста на английском языке и текста на иностранном языке.

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

Ожидаемые значения для разных языков являются:

Язык	Индекс совпадений
Английский	1.73
Французский	2.02
немецкий	2.05
итальянский	1.94
португальский	1.94
Русский	1.76
испанский	1.94

Обобщение

Приведенное выше описание представляет собой лишь введение в использование индекса совпадения, который связан с общей концепцией корреляции . Были разработаны различные формы индекса совпадений; IC «дельта» (задаваемая формулой выше) фактически измеряет автокорреляцию одного распределения, тогда как IC «каппа» используется при сопоставлении двух текстовых строк. Хотя в некоторых приложениях постоянные факторы, такие как $c$ и $N$ можно игнорировать, в более общих ситуациях существует значительная ценность в истинной индексации каждой IC относительно значения, ожидаемого для нулевой гипотезы (обычно: отсутствие совпадений и равномерное случайное распределение символов), так что в каждой ситуации ожидаемое значение для отсутствия корреляция равна 1,0. Таким образом, любая форма IC может быть выражена как отношение количества фактически наблюдаемых совпадений к числу ожидаемых совпадений (согласно нулевой модели) с использованием конкретной тестовой установки.

Из вышесказанного легко видеть, что формула каппа IC имеет вид

$\mathbf {IC} ={\frac {\displaystyle \sum _{j=1}^{N}[a_{j}=b_{j}]}{N/c}},$

где $N$ — это общая выровненная длина двух текстов A и B , а термин в квадратных скобках определяется как 1, если $j$-я буква текста А соответствует $j$-я буква текста B , иначе 0.

Связанная с этим концепция, «выпуклость» распределения, измеряет несоответствие между наблюдаемым IC и нулевым значением 1,0. Количество шифралфавитов, используемых в полиалфавитном шифре, можно оценить путем деления ожидаемой выпуклости дельта-IC для одного алфавита на наблюдаемую выпуклость для сообщения, хотя во многих случаях (например, когда повторяющийся ключ использовался ) более эффективные методы доступны.

Пример

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

QPWKA LVRXC QZIKG RBPFA EOMFL  JMSDZ VDHXC XJYEB IMTRQ WNMEA
IZRVK CVKVL XNEIC FZPZC ZZHKM  LVZVZ IZRRQ WDKEC HOSNY XXLSP
MYKVQ XJTDC IOMEE XDQVS RXLRL  KZHOV

(Группировка в пять символов — это всего лишь телеграфное соглашение, не имеющее ничего общего с реальной длиной слов.) Подозревая, что это английский открытый текст, зашифрованный с использованием шифра Виженера с обычными компонентами A–Z и коротким повторяющимся ключевым словом, мы можем рассматривать зашифрованный текст, «сложенный» в некоторое количество столбцов, например семь:

QPWKALV
RXCQZIK
GRBPFAE
OMFLJMS
DZVDHXC
XJYEBIM
TRQWN…

Если размер ключа оказался таким же, как предполагаемое количество столбцов, то все буквы в одном столбце будут зашифрованы с использованием одной и той же ключевой буквы, по сути, это простой шифр Цезаря , применяемый к случайному выбору символов английского открытого текста. . Соответствующий набор букв зашифрованного текста должен иметь грубое распределение частот, аналогичное английскому, хотя идентичность букв была переставлена ​​(сдвинута на постоянную величину, соответствующую ключевой букве). Следовательно, если мы вычислим совокупную дельту IC для всех столбцов («дельта-бар»), она должна составлять около 1,73. С другой стороны, если мы неправильно угадали размер ключа (количество столбцов), совокупная дельта IC должна быть около 1,00. Итак, мы вычисляем дельту IC для предполагаемых размеров ключей от одного до десяти:

Размер	Дельта-бар IC
1	1.12
2	1.19
3	1.05
4	1.17
5	1.82
6	0.99
7	1.00
8	1.05
9	1.16
10	2.07

Мы видим, что размер ключа, скорее всего, равен пяти. Если фактический размер равен пяти, мы ожидаем, что ширина, равная десяти, также будет сообщать о высоком IC, поскольку каждый из ее столбцов также соответствует простому шифрованию Цезаря, и мы это подтверждаем. Итак, нам следует разбить зашифрованный текст на пять столбцов:

QPWKA
LVRXC
QZIKG
RBPFA
EOMFL
JMSDZ
VDH…

Теперь мы можем попытаться определить наиболее вероятную ключевую букву для каждого столбца, рассматриваемого отдельно, выполнив пробную расшифровку Цезаря всего столбца для каждой из 26 возможностей A–Z для ключевой буквы и выбрав ключевую букву, которая обеспечивает наибольшую корреляцию. между частотой букв расшифрованного столбца и относительной частотой букв обычного английского текста. Эту корреляцию, о нормализации которой нам не нужно беспокоиться, можно легко вычислить как

$\mathbf {\chi } =\sum _{i=1}^{c}n_{i}f_{i}$

где $n_{i}$ - наблюдаемые частоты букв столбца и $f_{i}$ — относительная частота букв английского языка. Когда мы попробовали это, выяснилось, что наиболее подходящими ключевыми буквами являются « EVERY», которое мы распознаем как настоящее слово, и используя его для расшифровки Виженера, получаем открытый текст:

MUSTC HANGE MEETI NGLOC ATION FROMB RIDGE TOUND ERPAS 
SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE 
DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

из чего получается:

MUST CHANGE MEETING LOCATION FROM BRIDGE TO UNDERPASS
SINCE ENEMY AGENTS ARE BELIEVED TO HAVE BEEN ASSIGNED
TO WATCH BRIDGE STOP  MEETING TIME UNCHANGED  XX

после восстановления делений слов на очевидных позициях. " XX", очевидно, являются "нулевыми" символами, используемыми для заполнения последней группы при передаче.

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

См. также

• обследование Касиски
• Публикации Ривербанка
• Темы криптографии