Índice de coincidencia

En criptografía, el conteo de coincidencias es la técnica (inventada por William F. Friedman) de poner dos textos uno al lado del otro y contar el número de veces que letras idénticas aparecen en la misma posición en ambos textos. Este conteo, ya sea como una proporción del total o normalizado dividiéndolo por el conteo esperado para un modelo de origen aleatorio, se conoce como índice de coincidencia, o IC para abreviar.

Debido a que las letras en un lenguaje natural no se distribuyen uniformemente, el IC es más alto para tales textos que para cadenas de texto uniformemente aleatorias. Lo que hace que el IC sea especialmente útil es el hecho de que su valor no cambia si ambos textos están codificados por el mismo cifrado de sustitución de un solo alfabeto, lo que permite que un criptoanalista detecte rápidamente esa forma de cifrado.

Cálculo

El índice de coincidencia proporciona una medida de la probabilidad de dibujar dos letras coincidentes seleccionando al azar dos letras de un texto determinado. La posibilidad de dibujar una letra determinada en el texto es (número de veces que aparece esa letra / longitud del texto). La posibilidad de dibujar esa misma letra nuevamente (sin reemplazo) es (apariencias − 1 / longitud del texto − 1). El producto de estos dos valores te da la posibilidad de dibujar esa letra dos veces seguidas. Uno puede encontrar este producto para cada letra que aparece en el texto, luego sumar estos productos para tener la oportunidad de dibujar dos iguales. Luego, esta probabilidad se puede normalizar multiplicándola por algún coeficiente, típicamente 26 en inglés.

${displaystyle mathbf {IC} =ctimes left({left({frac {n_{mathrm {a} ################################################################################################################################################################################################################################################################ - Sí. {n_{mathrm} {}} {fn}times {frac {n_{mathrm {b} - Sí. +left({frac {n_{mathrm {z} ################################################################################################################################################################################################################################################################ - Sí.$

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& #34; aparece 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 ¿Por qué?$

donde N es la longitud del texto y n₁ a n_c son las frecuencias (en números enteros) de las letras c del alfabeto (c = 26 para monocase English). La suma de 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 ocurren tanto en el numerador como en el denominador de la fórmula y, por lo tanto, se cancelan). Cada una de las ocurrencias n_i del i -ésima letra coincide con cada una de las restantes n_i − 1 apariciones de la misma carta. 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, asumiendo una distribución aleatoria uniforme de los caracteres (el "modelo nulo"; ver 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 cabría esperar del modelo nulo.

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 {expected} }={frac {displaystyle sum ¿Qué?$

Si todas las letras c de un alfabeto fueran igualmente probables, el índice esperado sería 1,0. El IC 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 lenguaje natural.

A veces, los valores se notifican sin el denominador de normalización, por ejemplo, 0,067 = 1,73/26 para inglés; tales valores pueden llamarse κ_p ("kappa-plaintext") en lugar de IC, con κ_r ("kappa-random") utilizado para denotar 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 sin formato en inglés generalmente se ubicará en algún lugar en el rango de 1.5 a 2.0 (cálculo normalizado).

Solicitud

El índice de coincidencia es útil tanto en el análisis de texto sin formato en lenguaje natural como en el análisis de texto cifrado (criptoanálisis). Incluso cuando solo el texto cifrado está disponible para la prueba y las identidades de las letras del texto sin formato están disfrazadas, las coincidencias en el texto cifrado pueden deberse a coincidencias en el texto sin formato 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 generalmente será más alta cuando el ancho de la matriz es un múltiplo de la longitud de la clave, y este hecho se puede usar para determinar la longitud de la clave, que es el primer paso para descifrar el sistema.

El conteo de coincidencias puede ayudar a determinar cuándo dos textos están escritos en el mismo idioma usando el mismo alfabeto. (Esta técnica se ha utilizado para examinar el supuesto código bíblico). El conteo de coincidencias causales para tales textos será claramente más alto que el conteo de coincidencias accidentales para textos en diferentes idiomas, o textos que usan diferentes alfabetos, o textos incomprensibles.

Para ver por qué, imagina un "alfabeto" de solo las dos letras A y B. Suponga que en nuestro "idioma", la letra A se usa el 75% del tiempo, y la letra B se usa el 25% del tiempo. Si dos textos en este idioma se colocan uno al lado del otro, se pueden esperar los siguientes pares:

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

Ahora considere el caso cuando ambos mensajes están encriptados usando el cifrado de sustitución monoalfabético simple que reemplaza A con B y viceversa:

La probabilidad general de coincidencia en esta situación es del 62,5 % (6,25 % para AA + 56,25 % para BB), exactamente la misma que para el "texto sin formato" caso. En efecto, el nuevo alfabeto producido por la sustitución es solo un cambio de nombre uniforme de las identidades de los caracteres originales, lo que no afecta si coinciden.

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

Ahora la probabilidad de coincidencia es solo del 37,5 % (18,75 % para AA + 18,75 % para BB). Esto es notablemente más bajo que la probabilidad cuando se usaron textos en el mismo idioma y el 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 idiomas reales como el inglés, porque ciertas letras, como la E, aparecen con mucha más frecuencia que otras letras, un hecho que se utiliza en el análisis de frecuencia de los cifrados de sustitución. Las coincidencias relacionadas con la letra E, por ejemplo, son relativamente probables. Entonces, cuando se comparan dos textos en inglés, el recuento de coincidencias será mayor que cuando se usan un texto en inglés y un texto en un idioma extranjero.

Fácilmente se puede imaginar que este efecto puede ser sutil. Por ejemplo, los idiomas similares tendrán un recuento de coincidencias más alto que los idiomas diferentes. Además, no es difícil generar texto aleatorio con una distribución de frecuencia similar al texto real, elevando artificialmente el recuento de coincidencias. Sin embargo, esta técnica se puede usar de manera efectiva para identificar cuándo es probable que dos textos contengan información significativa en el mismo idioma usando el mismo alfabeto, descubrir puntos para repetir claves y descubrir muchos otros tipos de fenómenos no aleatorios dentro o entre textos cifrados.

Los valores esperados para varios idiomas son:

Generalización

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; la "delta" I.C. (dada por la fórmula anterior) en efecto mide la autocorrelación de una sola distribución, mientras que una "kappa" I.C. se utiliza al igualar dos cadenas de texto. Aunque en algunas aplicaciones factores constantes como ${displaystyle c}$ y ${displaystyle N}$ puede ser ignorado, en situaciones más generales hay un valor considerable en realidad indexación cada I.C. contra el valor que se espera para la hipótesis nula (normalmente: ningún partido y una distribución uniforme de símbolos aleatorios), por lo que en cada situación el valor esperado para ninguna correlación es 1.0. Así, cualquier forma de I.C. se puede expresar como la relación del número de coincidencias efectivamente observadas con el número de coincidencias esperadas (según el modelo null), utilizando la configuración de prueba particular.

De lo anterior, es fácil ver que la fórmula para kappa I.C. es

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

Donde ${displaystyle N}$ es la longitud común alineada de los dos textos A y B, y el término entre corchetes se define como 1 si ${displaystyle j}$-la carta del texto A partidos ${displaystyle j}$-la carta del texto B, de lo contrario 0.

Un concepto relacionado, el "bulto" de una distribución, mide la discrepancia entre el I.C. observado. y el valor nulo de 1.0. El número de alfabetos de cifrado utilizados en un cifrado polialfabético se puede estimar dividiendo el abultamiento esperado del delta I.C. para un solo alfabeto por la protuberancia observada para el mensaje, aunque en muchos casos (como cuando se usó una clave repetitiva) hay mejores técnicas disponibles.

Ejemplo

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

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEA
IZRVK CVKVL XNEIC FZPZC ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSP
MYKVQ XJTDC IOMEE XDQVS RXLRL KZHOV

(La agrupación en cinco caracteres es solo una convención telegráfica y no tiene nada que ver con la longitud real de las palabras). Si sospechamos que se trata de un texto sin formato en inglés cifrado con un cifrado Vigenère con componentes normales de la A a la Z y una palabra clave corta que se repite, podemos considerar que el texto cifrado está "apilado" en cierto número de columnas, por ejemplo siete:

QPWKALV
RXCQZIK
GRBPFAE
OMFLJMS
DZVDHXC
XJYEBIM
TRQWN...

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

Vemos que lo más probable es que el tamaño de la clave sea cinco. Si el tamaño real es cinco, esperaríamos que un ancho de diez también reportara un CI alto, ya que cada una de sus columnas también corresponde a un cifrado César simple, y lo confirmamos. Así que deberíamos apilar el texto cifrado en cinco columnas:

QPWKA
LVRXC
QZIKG
RBPFA
EOMFL
JMSDZ
VDH...

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

${displaystyle mathbf {chi } =sum ¿Qué?$

Donde ${displaystyle No.$ son las frecuencias de la letra de la columna observada ${displaystyle F_{i}$ son las frecuencias de letras relativas para el inglés. Cuando probamos esto, las letras clave mejor adaptadas se reportan ser "EVERY," que reconocemos como una palabra real, y usando eso para el desciframiento de Vigenère produce el texto claro:

MUSTC HANGE MEETI NGLOC ATION BYB RIDGE TOUND ERPAS
SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE
DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDX

de donde se obtiene:

DEBEN CAMBIO DE LA LOCALACIÓN DE REUNIONES DEL BRIDGE A UNDERPASS
Desde que se cree que los ORGANISMOS DE ENEMIA han sido asesinados
AL GRUPO DE TRABAJO QUE SE PUEDE REUNIÓN

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

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