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

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

В криптографии , подсчета совпадений является метод (автор Уильям Ф. Фридман ^[1] ) положить два текста бок о бок и подсчета количества раз , что одинаковые буквы в одной и той же позиции в обоих текстах. Этот подсчет, либо как отношение к общему количеству, либо нормализованный путем деления на ожидаемое количество для модели случайного источника, известен как индекс совпадения , или сокращенно 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)+...+\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 ( n −1) подсчитывают количество комбинаций из n элементов, взятых по два за раз. (На самом деле каждая пара учитывается дважды; дополнительные множители 2 встречаются как в числителе, так и в знаменателе формулы и таким образом сокращаются.) Каждое из n _i вхождений i -й буквы соответствует каждому из оставшихся n _i -1 вхождений. того же письма. Есть в общей сложности N ( N - 1) пар букв во всем тексте, и 1 / с есть вероятность совпадения для каждой пары, предполагая равномерное случайноераспределение символов («нулевая модель»; см. ниже). Таким образом, эта формула дает отношение общего количества наблюдаемых совпадений к общему количеству совпадений, которое можно было бы ожидать от нулевой модели. ^[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 для английского языка).

Заявление [ править ]

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

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

Чтобы понять, почему, представьте «алфавит» только из двух букв 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 относительно вероятны. Поэтому при сравнении любых двух английских текстов количество совпадений будет выше, чем при использовании английского текста и текста на иностранном языке.

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

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

Обобщение [ править ]

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

Из вышеизложенного легко видеть, что формула для каппа 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 ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSPMYKVQ XJTDC IOMEE XDQVS RXLRL КЖОВ

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

QPWKALVRXCQZIKGRBPFAEOMFLJMSDZVDHXCXJYEBIMTRQWN…

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

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

QPWKALVRXCQZIKGRBPFAEOMFLJMSDZVDH…

Теперь мы можем попытаться определить наиболее вероятную ключевую букву для каждого столбца, рассматриваемого отдельно, выполнив пробную расшифровку Цезаря всего столбца для каждой из 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 С КОНЬКА ТУНД ERPAS SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

из которого получают:

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

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

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

Ссылки [ править ]

См. Также [ править ]

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