Índice de coincidencia

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Por favor, ayude a mejorar este artículo introduciendo citas más precisas. ( Marzo de 2009 ) ( Aprenda cómo y cuándo eliminar este mensaje )

En criptografía , el conteo de coincidencias es la técnica (inventada por William F. Friedman ^[1] ) que consiste en colocar dos textos uno al lado del otro y contar la cantidad de veces que aparecen letras idénticas en la misma posición en ambos textos. Este conteo, ya sea como proporción del total o normalizado dividiendo por el conteo esperado para un modelo de fuente aleatoria, se conoce como índice de coincidencia o IC para abreviar.

Como las letras de un lenguaje natural no se distribuyen de manera uniforme , el IC es mayor para dichos textos que para cadenas de texto aleatorias uniformes. Lo que hace que el IC sea especialmente útil es el hecho de que su valor no cambia si ambos textos se mezclan con el mismo cifrado de sustitución de una sola letra , lo que permite que un criptoanalista detecte rápidamente esa forma de cifrado.

El índice de coincidencia proporciona una medida de la probabilidad de obtener dos letras iguales seleccionando al azar dos letras de un texto determinado. La probabilidad de obtener una letra determinada en el texto es (número de veces que aparece esa letra / longitud del texto). La probabilidad de obtener esa misma letra nuevamente (sin reemplazo) es (apariciones − 1 / longitud del texto − 1). El producto de estos dos valores le da la probabilidad de obtener esa letra dos veces seguidas. Uno puede encontrar este producto para cada letra que aparece en el texto, luego sumar estos productos para obtener la probabilidad de obtener dos iguales. Esta probabilidad puede luego normalizarse multiplicándola por algún coeficiente, generalmente 26 en inglés.

${\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)}$

donde c es el coeficiente de normalización (26 para inglés), n _a es el número de veces que aparece la letra "a" en el texto y N es la longitud del texto.

Podemos expresar el índice de coincidencia IC para una distribución de frecuencia de letras dada como una suma:

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

donde N es la longitud del texto y n ₁ a n _c son las frecuencias (en números enteros) de las c letras del alfabeto ( c = 26 para el inglés monocase ). La suma de las n _i es necesariamente N .

Los productos n ( n − 1) cuentan el número de combinaciones de n elementos tomados de dos en dos. (En realidad, esto cuenta cada par dos veces; los factores adicionales de 2 aparecen tanto en el numerador como en el denominador de la fórmula y, por lo tanto, se cancelan). Cada una de las n _i ocurrencias de la i -ésima letra coincide con cada una de las n _i − 1 ocurrencias restantes de la misma letra. Hay un total de N ( N − 1) pares de letras en todo el texto, y 1/ c es la probabilidad de una coincidencia para cada par, suponiendo una distribución aleatoria uniforme de los caracteres (el "modelo nulo"; véase más abajo). Por lo tanto, esta fórmula da la relación entre el número total de coincidencias observadas y el número total de coincidencias que se esperaría del modelo nulo. ^[2]

El valor promedio esperado para el IC se puede calcular a partir de las frecuencias relativas de las letras f _i del idioma de origen:

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

Si todas las letras c de un alfabeto tuvieran la misma probabilidad, el índice esperado sería 1,0. El índice de correspondencia monográfico real para el texto telegráfico en inglés es de alrededor de 1,73, lo que refleja la desigualdad de las distribuciones de letras en el lenguaje natural .

A veces, los valores se informan sin el denominador normalizador, por ejemplo, 0,067 = 1,73/26 para inglés; dichos valores pueden llamarse κ _p ("kappa-texto simple") en lugar de IC, y κ _r ("kappa-aleatorio") se utiliza para indicar el denominador 1/ c (que es la tasa de coincidencia esperada para una distribución uniforme del mismo alfabeto, 0,0385 = 1/26 para inglés). El texto simple en inglés generalmente se ubicará en algún lugar en el rango de 1,5 a 2,0 (cálculo normalizado). ^[3]

El índice de coincidencia es útil tanto en el análisis de textos en lenguaje natural como en el análisis de textos cifrados ( criptoanálisis ). Incluso cuando solo se dispone de texto cifrado para realizar pruebas y las identidades de las letras del texto en lenguaje natural están disfrazadas, las coincidencias en el texto cifrado pueden ser causadas por coincidencias en el texto en lenguaje natural subyacente. Esta técnica se utiliza para criptoanalizar el cifrado de Vigenère , por ejemplo. Para un cifrado polialfabético de clave repetitiva organizado en una matriz, la tasa de coincidencia dentro de cada columna normalmente será más alta cuando el ancho de la matriz sea un múltiplo de la longitud de la clave, y este hecho se puede utilizar para determinar la longitud de la clave, que es el primer paso para descifrar el sistema.

El recuento de coincidencias puede ayudar a determinar cuándo dos textos están escritos en el mismo idioma y con el mismo alfabeto (esta técnica se ha utilizado para examinar el supuesto código bíblico ). El recuento de coincidencias causales para dichos textos será claramente superior al recuento de coincidencias accidentales para textos en diferentes idiomas, o textos que utilizan diferentes alfabetos, o textos sin sentido. ^{[ cita requerida ]}

Para entender por qué, imaginemos un "alfabeto" formado únicamente por las dos letras A y B. Supongamos que en nuestro "idioma", la letra A se utiliza el 75% del tiempo y la letra B el 25% del tiempo. Si se colocan dos textos en este idioma uno al lado del otro, se pueden esperar los siguientes pares:

En general, la probabilidad de una "coincidencia" es del 62,5% (56,25% para AA + 6,25% para BB).

Consideremos ahora el caso en el que ambos mensajes se cifran utilizando el cifrado de sustitución monoalfabético simple que reemplaza A por B y viceversa:

La probabilidad total de coincidencia en esta situación es del 62,5% (6,25% para AA + 56,25% para BB), exactamente la misma que en el caso del "texto simple" sin cifrar. En efecto, el nuevo alfabeto resultante de la sustitución es simplemente un cambio de nombre uniforme de las identidades de los caracteres originales, lo que no afecta a su coincidencia.

Ahora supongamos que solo se cifra un mensaje (por ejemplo, el segundo) utilizando el mismo cifrado de sustitución (A,B)→(B,A). Ahora se pueden esperar los siguientes pares:

Ahora la probabilidad de coincidencia es de tan solo el 37,5% (18,75% para AA + 18,75% para BB). Esta es una probabilidad notablemente inferior a la que se da cuando se utilizan textos del mismo idioma y del mismo alfabeto. Evidentemente, las coincidencias son más probables cuando las letras más frecuentes en cada texto son las mismas.

El mismo principio se aplica a los idiomas reales, como el inglés, porque ciertas letras, como la E, aparecen con mucha más frecuencia que otras, un hecho que se utiliza en el análisis de frecuencia de los cifrados de sustitución . Las coincidencias que involucran a la letra E, por ejemplo, son relativamente probables. Por lo tanto, cuando se comparan dos textos en inglés, el recuento de coincidencias será mayor que cuando se utilizan un texto en inglés y un texto en un idioma extranjero.

Este efecto puede ser sutil. Por ejemplo, los idiomas similares tendrán un mayor índice de coincidencias que los idiomas diferentes. Además, no es difícil generar texto aleatorio con una distribución de frecuencia similar al texto real, lo que aumenta artificialmente el índice de coincidencias. Sin embargo, esta técnica se puede utilizar de manera efectiva para identificar cuándo es probable que dos textos contengan información significativa en el mismo idioma y utilizando el mismo alfabeto, para descubrir períodos de repetición de claves y para descubrir muchos otros tipos de fenómenos no aleatorios dentro o entre textos cifrados.

Los valores esperados para varios idiomas ^[4] son:

La descripción anterior es sólo una introducción al uso del índice de coincidencia, que está relacionado con el concepto general de correlación . Se han ideado varias formas de índice de coincidencia; el IC "delta" (dado por la fórmula anterior) mide en efecto la autocorrelación de una única distribución, mientras que un IC "kappa" se utiliza cuando se hacen coincidir dos cadenas de texto. ^[5] Aunque en algunas aplicaciones se pueden ignorar factores constantes como y , en situaciones más generales existe un valor considerable en indexar verdaderamente cada IC contra el valor que se espera para la hipótesis nula (normalmente: no hay coincidencia y una distribución de símbolos aleatorios uniforme), de modo que en cada situación el valor esperado para la no correlación sea 1,0. Por lo tanto, cualquier forma de IC se puede expresar como la relación entre el número de coincidencias realmente observadas y el número de coincidencias esperadas (según el modelo nulo), utilizando la configuración de prueba particular.${\estilo de visualización c}$${\estilo de visualización N}$

De lo anterior, es fácil ver que la fórmula para kappa IC es

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

donde es la longitud alineada común de los dos textos A y B , y el término entre corchetes se define como 1 si la -ésima letra del texto A coincide con la -ésima letra del texto B , de lo contrario es 0.${\estilo de visualización N}$${\estilo de visualización j}$${\estilo de visualización j}$

Un concepto relacionado, el "bulge" de una distribución, mide la discrepancia entre el IC observado y el valor nulo de 1,0. La cantidad de alfabetos de cifrado utilizados en un cifrado polialfabético se puede estimar dividiendo el abultamiento esperado del IC delta para un solo alfabeto por el abultamiento observado para el mensaje, aunque en muchos casos (como cuando se utilizó una clave repetitiva ) hay mejores técnicas disponibles.

Como ilustración práctica del uso de IC, supongamos que hemos interceptado el siguiente mensaje de texto cifrado:

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEAIZRVK CVKVL XNEIC FZPZC ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSPMYKVQ XJTDC IOMEE XDQVS RXLRL KZHOV

(La agrupación en cinco caracteres es sólo una convención telegráfica y no tiene nada que ver con la longitud real de las palabras). Sospechando que se trata de un texto simple en inglés cifrado utilizando un cifrado Vigenère con componentes normales de la A a la Z y una palabra clave corta repetida, podemos considerar el texto cifrado "apilado" en una cierta cantidad de columnas, por ejemplo siete:

QPWKALVRxCQZIKGRBPFAEOMFLJMSDZVDHXCXJYEBITRQWN…

Si el tamaño de la clave es el mismo que el número de columnas asumido, entonces todas las letras dentro de una sola columna se habrán cifrado utilizando la misma letra clave, en efecto un cifrado César simple aplicado a una selección aleatoria de caracteres de texto simple en inglés. El conjunto correspondiente de letras del texto cifrado debería tener una distribución de frecuencias aproximada similar a la del inglés, aunque las identidades de las letras se han permutado (desplazado por una cantidad constante correspondiente a la letra clave). Por lo tanto, si calculamos el IC delta agregado para todas las columnas ("barra delta"), debería ser alrededor de 1,73. Por otro lado, si hemos adivinado incorrectamente el tamaño de la clave (número de columnas), el IC delta agregado debería ser alrededor de 1,00. Por lo tanto, calculamos el IC delta para tamaños de clave asumidos de uno a diez:

Vemos que el tamaño de la clave es probablemente cinco. Si el tamaño real es cinco, esperaríamos que un ancho de diez también indique un IC alto, ya que cada una de sus columnas también corresponde a un cifrado César simple, y lo confirmamos. Por lo tanto, deberíamos apilar el texto cifrado en cinco columnas:

QPWKALVRXCQZIKGAsociación de padres y maestros de la Fundación para la Paz y la Justicia (BPFA)EOMFLJMSDZVDH…

Ahora podemos intentar determinar la letra clave más probable para cada columna considerada por separado, realizando un descifrado de prueba de César de toda la columna para cada una de las 26 posibilidades A–Z para la letra clave, y eligiendo la letra clave que produzca la correlación más alta entre las frecuencias de las letras de la columna descifradas y las frecuencias de las letras relativas para el texto en inglés normal. Esa correlación, que no necesitamos preocuparnos por normalizar, se puede calcular fácilmente como

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

donde son las frecuencias de las letras de la columna observadas y son las frecuencias de las letras relativas para el inglés. Cuando probamos esto, las letras clave que mejor se ajustan son " ", que reconocemos como una palabra real, y al usarla para el descifrado de Vigenère se obtiene el texto sin formato: ${\displaystyle n_{i}}$$estilo de visualización f_{i}}$EVERY

DEBE CAMBIAR LA REUNIÓN DESDE B RIDGE TOUND ERPASSSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNEDTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

de donde se obtiene:

SE DEBE CAMBIAR EL LUGAR DE REUNIÓN DEL PUENTE AL PASO INFERIORSE CREE QUE SE HAN ASIGNADO AGENTES ENEMIGOSPARA VER EL PUENTE DETENER LA HORA DE LA REUNIÓN SIN CAMBIOS XX

después de que se hayan restaurado las divisiones de palabras en las posiciones obvias. " XX" son evidentemente caracteres "nulos" utilizados para rellenar el grupo final para la transmisión.

Todo este procedimiento podría fácilmente empaquetarse en un algoritmo automatizado para descifrar dichos códigos. Debido a la fluctuación estadística normal, un algoritmo de este tipo a veces tomará decisiones equivocadas, especialmente al analizar mensajes de texto cifrado cortos.

• Examen de Kasiski
• Publicaciones de Riverbank
• Temas de criptografía