Индекс совпадений в криптографии: метод Фридмана для анализа текстов, выявления шифров подстановки и оценки языковой структуры. Полезен в криптоанализе.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Как часто идентичные буквы встречаются в одной и той же позиции в двух текстах.
How often identical letters appear in the same position in two texts
В криптографии подсчет совпадений — это метод (изобретенный Уильямом Ф. Фридманом), который заключается в сопоставлении двух текстов и подсчете количества случаев, когда идентичные буквы оказываются в одной и той же позиции в обоих текстах. Этот показатель, выраженный либо как отношение к общему числу, либо нормализованный путем деления на ожидаемое значение для случайной модели источника, известен как индекс совпадения, или сокращенно IC. Поскольку буквы в естественном языке распределены неравномерно, IC для таких текстов выше, чем для равномерно случайных строк. Особенно полезно то, что значение IC не изменяется, если оба текста зашифрованы одним и тем же шифром подстановки, что позволяет криптоаналитику быстро определить, что использовался именно этот вид шифрования.
In cryptography, coincidence counting is the technique (invented by William F. Friedman) of putting two texts side by side and counting the number of times that identical letters appear in the same position in both texts. This count, either as a ratio of the total or normalized by dividing by the expected count for a random source model, is known as the index of coincidence, or IC for short. Because letters in a natural language are not distributed evenly, the IC is higher for such texts than it would be for uniformly random text strings. What makes the IC especially useful is the fact that its value does not change if both texts are scrambled by the same single alphabet substitution cipher, allowing a cryptanalyst to quickly detect that form of encryption.
Обобщение
Вышеприведенное описание является лишь введением в использование индекса совпадения, который связан с общей концепцией корреляции. Разработаны различные формы индекса совпадения; "дельта" И.С. (определяемый формулой выше) фактически измеряет автокорреляцию одного распределения, в то время как "каппа" И.С. используется при сопоставлении двух текстовых строк. Хотя в некоторых приложениях постоянные факторы, такие как и , могут быть проигнорированы, в более общих ситуациях имеет большое значение приведение каждого И.С. к значению, ожидаемому для нулевой гипотезы (обычно: отсутствие совпадений и равномерное случайное распределение символов), так чтобы в любой ситуации ожидаемое значение при отсутствии корреляции составляло 1,0. Таким образом, любая форма И.С. может быть выражена как отношение числа фактически наблюдаемых совпадений к числу ожидаемых совпадений (согласно нулевой модели), с учетом конкретной схемы тестирования. Из вышесказанного легко увидеть, что формула для каппа И.С. имеет вид:
The above description is only an introduction to use of the index of coincidence, which is related to the general concept of correlation. Various forms of Index of Coincidence have been devised; the "delta" I. C. (given by the formula above) in effect measures the autocorrelation of a single distribution, whereas a "kappa" I. C. is used when matching two text strings. Although in some applications constant factors such as and can be ignored, in more general situations there is considerable value in truly indexing each I. C. against the value to be expected for the null hypothesis (usually: no match and a uniform random symbol distribution), so that in every situation the expected value for no correlation is 1.0. Thus, any form of I. C. can be expressed as the ratio of the number of coincidences actually observed to the number of coincidences expected (according to the null model), using the particular test setup. From the foregoing, it is easy to see that the formula for kappa I. C. is
где – общая длина выравнивания двух текстов A и B, а выражение в скобках равно 1, если -я буква текста A совпадает с -й буквой текста B, и 0 в противном случае. Связанное понятие, "выпуклость" распределения, измеряет расхождение между наблюдаемым И.С. и нулевым значением 1,0. Количество шифровых алфавитов, используемых в полиалфавитном шифре, можно оценить, разделив ожидаемую выпуклость дельта И.С. для одного алфавита на наблюдаемую выпуклость для сообщения, хотя во многих случаях (например, при использовании повторяющегося ключа) существуют более эффективные методы.
where is the common aligned length of the two texts A and B, and the bracketed term is defined as 1 if the th letter of text A matches the th letter of text B, otherwise 0. A related concept, the "bulge" of a distribution, measures the discrepancy between the observed I. C. and the null value of 1.0. The number of cipher alphabets used in a polyalphabetic cipher may be estimated by dividing the expected bulge of the delta I. C. for a single alphabet by the observed bulge for the message, although in many cases (such as when a repeating key was used) better techniques are available.