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

редактировать

Как часто одинаковые буквы появляются в одной позиции в двух текстах

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

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

Содержание

1 Расчет
2Приложение
3 Обобщение
4 Пример
5 Ссылки
6 См. Также

Расчет

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

IC = с × ((на N × на - 1 N - 1) + (nb N × nb - 1 N - 1) +.. + (Nz N × nz - 1 N - 1)) {\ displaystyle \ mathbf {IC} = c \ times \ left ({\ left ({{\ frac {n _ {\ mathrm {a}}} {N}} \ times {\ frac{n _ {\ m at hrm {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)}

\ mat hbf {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} \ tim es \ frac {n_ \ mathrm {z} - 1} {N - 1}} \ right)} \ right)

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

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

IC = я знак равно 1 cni (ni - 1) N (N - 1) / c {\ displaystyle \ mathbf {IC} = {\ frac {\ displaystyle \ sum _ {i = 1} ^ {c} n_ {i} (n_ {i} -1)} {N (N-1) / c}}}

\ mathbf {IC} = \гидроразрыва {\ displaystyle \ sum_ {i= 1} ^ {c} n_i (n_i-1)} {N ( N-1) / c}

где N - длина текста, а от n 1 до n c - частоты (в виде целых чисел) c бук в алфавита (c = 26 для monocase английский ). Сумма n i обязательно равна N.

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

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

Ожидаемый IC = ∑ i = 1 cfi 2 1 / c. {\ Displaystyle \ mathbf {IC} _ {\ mathrm {ожидаемый}} = {\ гидроразрыва {\ displaystyle \ sum _ {я = 1} ^ {c} {f_ {i}} ^ {2}} {1 / c }}.}

\ mathbf {IC} _ {\ mathrm {ожидается}} = \ гидроразрыва {\ 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 для английского языка).

Приложение

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

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

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

Пара	Вероятность
AA	56,25%
BB	6,25%
AB	18,75%
BA	18,75%

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

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

Пара	Вероятность
AA	6,25%
BB	56,25%
AB	18,75%
BA	18, 75%

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

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

Пара	Вероятность
AA	18,75%
BB	18,75%
AB	56,25%
BA	6,25%

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

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

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

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

Язык	Индекс совпадения
Английский	1,73
Французский	2,02
Немецкий	2,05
итальянский	1,94
португальский	1,94
русский	1, 76
испанский	1,94

Обобщение

Вышеприведенное описание является введением виспользование индексасовпадения, который связан с общей концепциейкорреляции.Были разработаныразличные формы Индекса совпадения; "Дельта" I.C. (заданный формулой выше) фактически измеряет автокорреляцию отдельного распределения, тогда как «каппа» I.C. используется при сопоставлении двух текстовых строк. Хотя в некоторых приложениях постоянные факторы, такие как $c {\ displaystyle c}$ $c$ и $N {\ displaystyle N}$ $N$ , можно игнорировать, в более общихситуациях ценность в Такчто в каждой ситуации ожидаемое значение без корреляции равно1.0,соответствует индексу каждой ИС против значения, которое ожидается для нулевой гипотезы (обычно: нет совпадения и равномерное случайное распределение символов). Таким образом, любая форма I.C. может быть выражено как количество реально наблюдаемых совпадений к количеству ожидаемых совпадений (нулевой модели) с использованием тестовой установки.

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

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

\ mathbf {IC} = \ frac {\ displaystyle \ sum_ {j = 1} ^ {N} [a_j = b_j]} {N /c},

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

Родственное понятие,"выпуклость" распределения, измеряетнесоответствие между наблюдаемыми IC и нулевое 1. 0. Использование вполиалфавитномшифре может быть выполнено путем использования ожидаемой выпуклости дельта I.C. для одного алфавита по наблюдаемой выпуклости для сообщений, хотя во многих случаях (например, когда использовалась повторяющаяся клавиша ) доступны лучшие методы.

Пример

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

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEA IZRVK ZVKVL XNE IZRRQ WDKEC HOSNY XXLSP MYKVQ XJTKZ IOMEE. английский открытый текст, зашифрованный с использованием шифра Виженера с обычными компонентами A - Z и коротким повторяющимся словом, мы можем считать, что зашифрованный текст «уложен» в некотором количестве столбцов, например семь:

QPWKALV RXCQZIK GRBPFAE OMFLJMS DZVDHXC XJYEBIM TRQWN…

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

Размер	Дельта-бар I.C.
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

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

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDH…

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

χ =∑ i = 1 cnifi {\ displaystyle \ m athbf{\ chi} =\ sum _ {i =1} ^ {c} n_ { i} f_ {i}}

\ mathbf {\ chi} = \ sum_ {i = 1} ^ {c} n_i f_i

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

MUSTC HANGE MEETINGLOCATION FROMB RIDGETOUND ERPAS SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE DTOWA TCHBR IDGES ИЗ TOPME ETING TIMEU NCHAN GEDXX <получить из134>

НИИ можно получить ИЗГНИТЕЛЬНЫЕ ИЗМЕНЕНИЯ>89 разделение ИЗГМЕНЕНИЯ>89>89>разделение ИЗГМЕНЕНИЯ>89>89>разделение ИЗГМЕНЕНИЯ>89>89>«XX» - это, очевидно, «нулевые» символы, используемые для дополнения последней группы для передачи.

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

Ссылки

^Фридман, В.Ф. (1922 г.). «Индекс совпадений и его приложения в криптологии». Отдел шифрование. Publ 22. Женева, Иллинойс, США: Riverbank Laboratories. OCLC 55786052. Журнал цитирования требует |journal =()Исходное приложение игнорировалонормализацию.
^ Маунтджой,Марджори (1963). «Барная статистика». Техническийжурнал АНБ. VII (2, 4). Опубликовано в двух частях.
^Фридман, В.Ф. и Каллимахос, Л.Д. (1985) [1956]. Военная криптоаналитика, Часть I - Том 2. Перепечатано Aegean Park Press. ISBN 0-89412-074-3. CS1 maint: несколько имен: список авторов (ссылка )
^Кан, Дэвид (1996) [1967].Взломщики кодов - История секретногописьма. Нью-Йорк: Макмиллан. ISBN 0-684-83130-9.