En criptografía , el conteo de coincidencias es la técnica (inventada por William F. Friedman [1] ) 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 recuento, ya sea como una proporción del total o normalizado dividiendo por el recuento esperado para un modelo de fuente aleatoria, se conoce como índice de coincidencia o IC para abreviar.
Debido a que las letras en un lenguaje natural no se distribuyen de manera uniforme , el IC es más alto para dichos 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 se codifican con 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 dado. 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 volver a dibujar la misma letra (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 de una clase. Luego, esta probabilidad se puede normalizar multiplicándola por algún coeficiente, generalmente 26 en inglé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" 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:
donde N es la longitud del texto y n 1 a n c son las frecuencias (como números enteros) de las letras c del alfabeto ( c = 26 para inglés monocase ). La suma de los 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 extra 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 n i apariciones de la i -ésima letra coincide con cada una de las n i -1 apariciones 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, asumiendo una distribución aleatoria uniforme de los caracteres (el "modelo nulo"; ver más abajo) . Por lo tanto, esta fórmula da la razó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 letras f i del idioma de origen:
Si todas las letras c de un alfabeto fueran igualmente probables, el índice esperado sería 1.0. El IC monográfico real para 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 informan sin el denominador normalizador, por ejemplo, 0.067 = 1.73 / 26 para inglés; tales valores pueden llamarse κ p ("kappa-texto sin formato") en lugar de IC, con κ r ("kappa-aleatorio") utilizado para denotar el denominador 1 / c (que es la tasa de coincidencia esperada para una distribución uniforme de la misma alfabeto, 0.0385 = 1/26 para inglés).
Solicitud
El índice de coincidencia es útil tanto en el análisis de texto plano en lenguaje natural como en el análisis de texto cifrado ( criptoanálisis ). Incluso cuando solo se dispone de texto cifrado para realizar pruebas y se disfrazan las identidades de letras en texto sin formato, 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 repetida dispuesto 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 puede usarse 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 recuento de coincidencias causales para tales textos será claramente más alto que el recuento de coincidencias accidentales para textos en diferentes idiomas, o textos que usan diferentes alfabetos o textos galimatizados.
Para ver por qué, imagine un "alfabeto" de solo 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:
Par | Probabilidad |
---|---|
Automóvil club británico | 56,25% |
cama y desayuno | 6,25% |
AB | 18,75% |
licenciado en Letras | 18,75% |
En general, la probabilidad de una "coincidencia" es del 62,5% (56,25% para AA + 6,25% para BB).
Ahora considere el caso en el que ambos mensajes se cifran utilizando el cifrado de sustitución monoalfabético simple que reemplaza A con B y viceversa:
Par | Probabilidad |
---|---|
Automóvil club británico | 6,25% |
cama y desayuno | 56,25% |
AB | 18,75% |
licenciado en Letras | 18,75% |
La probabilidad general de una coincidencia en esta situación es del 62,5% (6,25% para AA + 56,25% para BB), exactamente igual que para el caso de "texto plano" sin cifrar. En efecto, el nuevo alfabeto producido por la sustitución es solo un cambio de nombre uniforme de las identidades de los personajes originales, lo que no afecta si coinciden.
Ahora suponga que solo un mensaje (digamos, el segundo) está cifrado usando el mismo cifrado de sustitución (A, B) → (B, A). Ahora se pueden esperar los siguientes pares:
Par | Probabilidad |
---|---|
Automóvil club británico | 18,75% |
cama y desayuno | 18,75% |
AB | 56,25% |
licenciado en Letras | 6,25% |
Ahora la probabilidad de una 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, ocurren 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 que involucran 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 utilizan un texto en inglés y un texto en un idioma extranjero.
Se puede imaginar fácilmente 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, aumentando artificialmente el recuento de coincidencias. No obstante, esta técnica se puede utilizar de forma eficaz para identificar cuándo es probable que dos textos contengan información significativa en el mismo idioma utilizando el mismo alfabeto, para descubrir períodos para la 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 [3] son:
Idioma | Índice de coincidencia |
---|---|
inglés | 1,73 |
francés | 2.02 |
alemán | 2,05 |
italiano | 1,94 |
portugués | 1,94 |
ruso | 1,76 |
Español | 1,94 |
Generalización
La descripción anterior es solo 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 sola distribución, mientras que un IC "kappa" se usa cuando se hacen coincidir dos cadenas de texto. [4] Aunque en algunas aplicaciones factores constantes como y puede ignorarse, en situaciones más generales hay un valor considerable en indexar verdaderamente cada IC contra el valor esperado para la hipótesis nula (generalmente: sin coincidencia y una distribución de símbolo aleatoria uniforme), de modo que en cada situación el valor esperado para no la correlación es 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.
De lo anterior, es fácil ver que la fórmula para kappa IC es
dónde es la longitud común alineada de los dos textos A y B , y el término entre corchetes se define como 1 si el-th letra del texto A coincide con la-ésima letra del texto B , de lo contrario 0.
Un concepto relacionado, el "abultamiento" de una distribución, mide la discrepancia entre el IC 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 IC para un solo alfabeto por el abultamiento observado para el mensaje, aunque en muchos casos (como cuando se utilizó una clave repetida ) mejores técnicas están disponibles.
Ejemplo
Como ilustración práctica del uso de IC, suponga 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 solo 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 plano en inglés cifrado con un cifrado de Vigenère con componentes A – Z normales y una palabra clave que se repite brevemente, podemos considerar el texto cifrado "apilado" en cierto número de columnas, por ejemplo, siete:
QPWKALVRXCQZIKGRBPFAEOMFLJMSDZVDHXCXJYEBIMTRQWN…
Si el tamaño de la clave ha sido 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 simple de César aplicado a una selección aleatoria de caracteres de texto sin formato en inglés. . El conjunto correspondiente de letras de texto cifrado debe tener una distribución de frecuencia 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 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 de alrededor de 1,00. Entonces calculamos el IC delta para tamaños de clave asumidos de uno a diez:
Tamaño | IC de barra delta |
---|---|
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 |
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 IC alto, ya que cada una de sus columnas también corresponde a un cifrado César simple, y lo confirmamos. Entonces deberíamos apilar el texto cifrado en cinco columnas:
QPWKALVRXCQZIKGRBPFAEOMFLJMSDZVDH…
Ahora podemos intentar 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 A – Z para la letra clave y eligiendo la letra clave que produce la correlación más alta. entre las frecuencias de las letras de las columnas descifradas y las frecuencias relativas de las letras para el texto en inglés normal. Esa correlación, de la que no tenemos que preocuparnos por normalizar, se puede calcular fácilmente como
dónde son las frecuencias de letras de columna observadas y son las frecuencias relativas de letras para el inglés. Cuando intentamos esto, se informa que las letras clave que mejor se ajustan son " EVERY
," que reconocemos como una palabra real, y usar eso para el descifrado de Vigenère produce el texto sin formato:
MUSTC HANGE MEETI NGLOC ACIÓN FROMB RIDGE TOUND ERPAS SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX
del cual se obtiene:
DEBE CAMBIAR LA UBICACIÓN DE LA REUNIÓN DE PUENTE A PASO INFERIORYA QUE SE CREE QUE SE HA ASIGNADO A LOS AGENTES ENEMIGOSPARA VER BRIDGE DETENGA EL TIEMPO DE 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" que se utilizan para rellenar el grupo final para la transmisión.
Todo este procedimiento podría empaquetarse fácilmente en un algoritmo automatizado para romper dichos cifrados. Debido a la fluctuación estadística normal, dicho algoritmo ocasionalmente tomará decisiones incorrectas, especialmente al analizar mensajes cortos de texto cifrado.
Referencias
- ^ Friedman, WF (1922). "El índice de coincidencia y sus aplicaciones en criptología". Departamento de Cifrados. Publ 22. Ginebra, Illinois, Estados Unidos: Riverbank Laboratories. OCLC 55786052 . Cite journal requiere
|journal=
( ayuda ) La aplicación original ignoró la normalización. - ^ Mountjoy, Marjorie (1963). "Las estadísticas de la barra". Revista técnica de la NSA . VII (2, 4). Publicado en dos partes.
- ^ Friedman, WF y Callimahos, LD (1985) [1956]. Criptoanalítica militar , Parte I - Volumen 2 . Reimpreso por Aegean Park Press. ISBN 0-89412-074-3.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Kahn, David (1996) [1967]. Los descifradores de códigos: la historia de la escritura secreta . Nueva York: Macmillan. ISBN 0-684-83130-9.
Ver también
- Examen de Kasiski
- Publicaciones de Riverbank
- Temas de criptografía