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

Как часто одинаковые буквы встречаются в одном и том же месте в двух текстах?

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

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

Расчет

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

${\displaystyle \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 — количество появлений буквы «a» в тексте, а N — длина текста.

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

${\displaystyle \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 — вероятность совпадения для каждой пары, предполагая равномерное случайное распределение символов («нулевая модель»; см. ниже). Таким образом, эта формула дает отношение общего числа наблюдаемых совпадений к общему числу совпадений, которое можно было бы ожидать от нулевой модели. ^[2]

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

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

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

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

Приложение

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

Подсчет совпадений может помочь определить, когда два текста написаны на одном языке с использованием одного и того же алфавита . (Эта техника использовалась для изучения предполагаемого библейского кода ). Количество причинных совпадений для таких текстов будет значительно выше, чем количество случайных совпадений для текстов на разных языках, текстов с использованием разных алфавитов или текстов-тарабарщины. ^{[ необходима цитата ]}

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

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

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

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

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

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

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

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

Ожидаемые значения для различных языков ^[4] :

Обобщение

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

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

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

где — общая выровненная длина двух текстов A и B , а заключенный в скобки термин определяется как 1, если -я буква текста A совпадает с -й буквой текста B , в противном случае — 0. ${\displaystyle N}$ ${\displaystyle j}$ ${\displaystyle j}$

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

Пример

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

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEAИЗРВК CVKVL XNEIC FZPZC ЗЖКМ LVZVZ IZRRQ WDKEC HOSNY XXLSPMYKVQ XJTDC IOMEE XDQVS RXLRL KZHOV

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

QPWKALVРКСКЗИКGRBPFAEOMFLJMSДЗВДХХСXJYEBIMТРКВН…

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

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

QPWKALVRXCQZIKGРБПФАEOMFLJMSDZВДХ…

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

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

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

MUSTC HANGE MEETI NGLOCATION FROMB RIDGE TOUND ERPASССИНК ЭЕНЕМ ЯГЕН ЦАРЕ БЕЛИЕ ВЕДТО ХАВЕБ ЭЕНАС СИГНЕDTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

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

НЕОБХОДИМО ИЗМЕНИТЬ МЕСТО ВСТРЕЧИ С МОСТА НА ПОДЗЕМНЫЙ ПЕРЕХОДПОСКОЛЬКУ СЧИТАЮТ, ЧТО БЫЛИ ЗАДАНЫ ВРАЖЕСКИЕ АГЕНТЫСМОТРЕТЬ МОСТ ОСТАНОВКА ВСТРЕЧИ ВРЕМЯ БЕЗ ИЗМЕНЕНИЙ XX

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

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

Ссылки

1. Фридман, Уильям Ф. (1922). «Индекс совпадений и его применение в криптографии». Department of Ciphers. Publ 22. Женева, Иллинойс, США: Riverbank Laboratories . OCLC  55786052. Первоначальное приложение игнорировало нормализацию.
   • 2-е изд. (1935). Вашингтон, округ Колумбия: Управление связи, Военное министерство .
   • 3-е изд. (1996). Лагуна-Хиллз, Калифорния: Aegean Park Press . ISBN 0894121383 . 
2. Маунтджой, Марджори (1963). «Статистика адвокатуры». Технический журнал АНБ . VII (2, 4).Опубликовано в двух частях.
3. Конту, Элени (18 мая 2020 г.). «Индекс совпадений». Открытые журналы Университета Лестера – через CORE .
4. Фридман, У. Ф. и Каллимахос, Л. Д. (1985) [1956]. Военная криптоаналитика , часть I – том 2. Перепечатано Aegean Park Press. ISBN 0-89412-074-3.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
5. Кан, Дэвид (1996) [1967]. Взломщики кодов - История тайнописи . Нью-Йорк: Macmillan. ISBN 0-684-83130-9.

Смотрите также

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