Índice de coincidencia

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 31 de marzo de 2013; las comprobaciones requieren 28 ediciones .

El índice de coincidencia es uno de los métodos de criptoanálisis del cifrado de Vigenère . La descripción fue publicada por William Friedman en 1920.

El método se basa en calcular la probabilidad de que coincidan dos elementos de texto aleatorios. Esta probabilidad se llama índice de coincidencia. William Friedman demostró que los valores del índice de coincidencia difieren significativamente para textos de diferente naturaleza. Esto le permite determinar primero la longitud de la clave de cifrado y luego encontrar la clave en sí.

El advenimiento del método del índice de coincidencia abrió nuevas posibilidades en el criptoanálisis del cifrado de Vigenère. En comparación con el método Kasiska común en ese momento , el nuevo método requería menos trabajo, requería menos texto, era más fácil de automatizar y menos propenso a errores. El índice de coincidencia fue más eficiente y permitió el análisis de cifrados con claves largas.

Historia

Blaise Vigenère presentó una descripción de un cifrado simple pero fuerte ante la comisión de Enrique III de Francia en 1586, y más tarde se le atribuyó la invención del cifrado. El cifrado Vigenère tenía la reputación de ser excepcionalmente resistente al descifrado "manual". El primer ataque exitoso al cifrado de Vigenère lo llevó a cabo Friedrich Kasiski en 1863. Su método siguió siendo el método principal de criptoanálisis del cifrado de Vigenère hasta 1920, cuando William Friedman publicó la monografía Índice de coincidencias y sus aplicaciones en criptografía . El nuevo método que describió Friedman ofreció una forma más eficiente y tolerante a errores para determinar la longitud de la clave. El método del índice de coincidencia ha sido ampliamente utilizado. Más tarde se utilizó en el criptoanálisis asistido por máquina.

Método de criptoanálisis para el cifrado de Vigenère

El cifrado Vigenère es un cifrado polialfabético . Su criptoanálisis se puede dividir en 2 pasos:

Primero, intentan determinar la longitud de la clave. La longitud de la clave especifica el número de alfabetos utilizados y el período de cifrado por estos alfabetos. Por lo tanto, en esta etapa se investiga la periodicidad del texto cifrado;
Después de encontrar la longitud, comienzan a buscar un tipo específico de clave. Para ello, se calculan los desplazamientos relativos de los alfabetos utilizados, y luego se selecciona la clave por fuerza bruta.

Índice de coincidencias

A continuación se muestran las fórmulas para calcular el índice de aciertos. En primer lugar, se considera el caso general. Luego consideramos varios casos especiales en los que el índice de coincidencia se puede estimar sin análisis de texto.

Caso general

Considere un texto escrito en algún idioma. Se supondrá que el alfabeto de un idioma dado consiste en símbolos. Considere una cadena de caracteres lo suficientemente larga. El índice de coincidencia es la probabilidad de que coincidan dos caracteres arbitrarios en una cadena. Si es el número del -ésimo carácter del alfabeto en la cadena , el índice de coincidencia se calcula mediante la fórmula: $metro$ ${\vec x}$ $norte$ $f_{i}$ $i$ ${\vec x}$

I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1 }\derecha)}{n\izquierda({n-1}\derecha)}}

(una)

Prueba

Estimaremos la probabilidad como la razón de los resultados favorables (el número de pares de caracteres idénticos en una cadena) al número total de resultados (el número de diferentes pares de caracteres en una cadena).

El número de pares distintos del carácter th en la cadena es: ${\ estilo de visualización {\ estilo de visualización i))$

${\displaystyle k_{i}=C_{f_{i}}^{2}={\frac {f_{i}\left({f_{i}-1}\right)}{2}} }$

Número de pares de caracteres idénticos en una cadena:

${\displaystyle k=\sum _{i=1}^{m}k_{i}=\sum _{i=1}^{m}{\frac {f_{i}\left({f_ {i}-1}\derecho)}{2}}}$

Número de pares distintos de caracteres en una cadena:

${\displaystyle {\displaystyle K=C_{n}^{2}={\frac {n\left({n-1}\right)}{2))))$

De aquí obtenemos:

${\displaystyle I\left({\vec {x}}\right)={\frac {k}{K}}=\sum \limits _{i=1}^{m}{\frac { f_{i}\left({f_{i}-1}\right)}{n\left({n-1}\right)}}}$

Texto sin formato

Digamos que la cadena es texto sin formato o se obtiene de ella mediante una simple permutación . En este caso, el índice de coincidencias se expresa convenientemente en términos de las probabilidades de ocurrencia del -ésimo carácter. Vamos a designarlos . Entonces obtenemos la siguiente fórmula: ${\ vec {x}}$ $i$ $Pi}$

I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}p_{i}^{2}

(2)

Porque valores tienen valores bien definidos, entonces para texto plano el índice de coincidencias no depende de su contenido, sino que depende únicamente del idioma en el que está escrito el texto. Además, los valores se investigan y conocen, lo que permite calcular los valores del índice de coincidencia de texto sin formato para varios idiomas. $Pi}$ $Pi}$

Idioma	Índice de coincidencia
ruso	0.0553 [1]
inglés	0,0644 [1] 0,0667 [2]
italiano	0.0738 [2]
español	0.0775 [2]
Alemán	0.0762 [2]
Francés	0.0778 [2]
sánscrito védico	0.021076696
prácrito	0.046635758
sánscrito clásico	0.045567736
hindi	0.041837864
urdu	0.057535302

Cadena aleatoria

Finalmente, sea una cadena aleatoria. Entonces la probabilidad de ocurrencia de cada símbolo es igual a ${\ vec {x}}$

p_{i}={\frac{1}{m))

Usando la fórmula , obtenemos: $(2)$

I\left({\vec {x}}\right)=\sum _{i=1}^{m}{1 \sobre m^{2}}={1 \sobre m}

(3)

Esta fórmula se puede utilizar para estimar el índice de coincidencia de un cifrado polialfabético . Para el idioma inglés, el índice de coincidencias del cifrado polialfabético será 0.03846, para el ruso (sin la letra "e") - 0.03125.

Los valores del índice de coincidencia para el texto plano y para el cifrado polialfabético son significativamente diferentes. Esto permite, conociendo el índice de coincidencias, determinar si el texto se obtiene del abierto por una simple permutación, o es un cifrado polialfabético.

Índice de coincidencia mutua

Otro concepto importante es el índice de coincidencia mutua .

Caso general

Considere dos cadenas y con longitudes y respectivamente. El alfabeto, como antes, consta de símbolos. El índice de coincidencia mutua de estas cadenas es la probabilidad de que un carácter elegido al azar de la primera cadena coincida con un carácter elegido al azar de la segunda cadena. Sea el número del carácter enésimo del alfabeto en la primera y segunda línea, respectivamente. Entonces el índice mutuo de coincidencias será igual a: ${\vec x}$ ${\vec{y}}$ $norte$ $norte'$ $metro$ ${\ Displaystyle f_ {i}, g_ {i}}$ $i$

MI\left({{\vec {x)),{\vec {y))}\right)={\sum \limits _{i=1}^{m}{\frac {f_{i }g_{i}}{nn'}}}

(cuatro)

La prueba de esta fórmula es similar a la prueba de la fórmula . $(una)$

Líneas desplazadas

Prácticamente importante para el método de índice de coincidencia es un caso especial cuando ambas cadenas se obtienen cambiando el alfabeto del texto sin formato. Indicar — las probabilidades de que ocurra el carácter -ésimo en la cadena , — el cambio del alfabeto de la cadena en relación con el alfabeto de la cadena (hacia la izquierda). Entonces las probabilidades de aparición del carácter -ésimo del alfabeto en la cadena son iguales (se utiliza la numeración del alfabeto de la cadena ). Para el índice mutuo de coincidencias, obtenemos la siguiente fórmula: $Pi}$ $i$ ${\vec x}$ $s$ ${\vec{y}}$ ${\vec x}$ $i$ ${\vec{y}}$ ${\ Displaystyle p_ {i + s}}$ ${\vec x}$

MI\left({{\vec {x)),{\vec {y))}\right)=\sum \limits _{i=1}^{m}{p_{i}p_{i +s}}

{\ estilo de visualización (5)}

Tenga en cuenta que desde el cambio es cíclico, entonces

\sum \limits _{i=1}^{m}{p_{i}p_{i+s}}=\sum \limits _{i=1}^{m}{p_{is}p_ {i}}=\sum \limits _{i=1}^{m}{p_{i+ms}p_{i}}

y el índice de coincidencia mutua para los turnos y toma el mismo valor. ${\ estilo de visualización}$ $ms$

A continuación se muestran los valores del índice de coincidencia mutua según el cambio para los idiomas ruso e inglés. Se dan valores para turnos de a . Como se mencionó anteriormente, en base a estos valores, el índice de acierto mutuo se puede calcular para cualquier turno. ${\ estilo de visualización 0}$ ${\ estilo de visualización m/2}$

Para el idioma ruso:

Cambio	índice mutuo
0	0.0553
una	0.0366
2	0.0345
3	0.0400
cuatro	0.0340
5	0.0360
6	0.0326
7	0.0241
ocho	0.0287
9	0.0317
diez	0.0265
once	0.0251
12	0.0244
13	0.0291
catorce	0.0322
quince	0.0244
dieciséis	0.0249

Para inglés:

Cambio	índice mutuo
0	0.0644
una	0.0394
2	0.0319
3	0.0345
cuatro	0.0436
5	0.0332
6	0.0363
7	0.0389
ocho	0.0338
9	0.0342
diez	0.0378
once	0.0440
12	0.0387
13	0.0428

Tenga en cuenta que en el cambio cero, el índice de coincidencia mutua es notablemente mayor que en los cambios distintos de cero. Entonces, según el valor conocido del índice mutuo de coincidencias, podemos concluir si el cambio de los alfabetos de las cadenas es cero o no.

Algoritmo para encontrar la longitud de la clave

Dividamos el texto en columnas de tamaño . $x_{1}$ $x_{2}$ $...$ $x_{n}$ $t$

x_{1}

{\ estilo de visualización x_ {t + 1}}

{\ estilo de visualización x_ {2t+1}}

...

x_{2}

{\ estilo de visualización x_ {t + 2}}

{\ estilo de visualización x_ {2t+2}}

...

...

...

...

...

x_t

{\ Displaystyle x_ {2t}}

{\ Displaystyle x_ {3t}}

...

Si es un múltiplo de la longitud de la clave, entonces cada dos elementos del texto separados por posiciones, se cifran con el mismo alfabeto. Y esto significa que cada fila de la tabla escrita arriba se obtiene del texto sin formato por permutación . Si no es un múltiplo de la longitud de la clave, entonces las cadenas son un cifrado polialfabético . $t$ ${\ estilo de visualización a \ veces t}$ ${\ estilo de visualización a \ en N}$ $t$

Previamente, se demostró que el índice de coincidencias para una permutación de texto sin formato y para un cifrado polialfabético es notablemente diferente. Así, iterando sobre varios valores y calculando para cada uno de ellos el índice de coincidencias, podemos seleccionar aquellos que sean múltiplos de la longitud de la clave. No es difícil determinar la longitud de la clave a partir de estos datos. $t$ $t$

Algoritmo para encontrar la llave

Supongamos que hemos definido la longitud de la clave . Busquemos la clave ahora. $t$

Escribamos el texto nuevamente en columnas de tamaño . $t$

x_{1}

{\ estilo de visualización x_ {t + 1}}

{\ estilo de visualización x_ {2t+1}}

...

x_{2}

{\ estilo de visualización x_ {t + 2}}

{\ estilo de visualización x_ {2t+2}}

...

...

...

...

...

x_t

{\ Displaystyle x_ {2t}}

{\ Displaystyle x_ {3t}}

...

Considere dos filas de esta tabla. Cambiemos el alfabeto de una de las cadenas por caracteres y calculemos el índice mutuo de coincidencias de las cadenas recibidas. Porque cada una de estas dos cadenas se obtiene desplazando el alfabeto del texto sin formato, luego el máximo índice mutuo de coincidencias se observará en el desplazamiento relativo final cero. $s$

Por lo tanto, se aplica el siguiente algoritmo: se calcula el índice mutuo de coincidencias para varios , se busca el valor en el que el índice mutuo de coincidencias es máximo. Entonces el desplazamiento relativo inicial de las líneas será igual a ( - el tamaño del alfabeto). Se calculan los desplazamientos relativos entre todos los pares de líneas. Porque los desplazamientos de las filas de la tabla corresponden a los desplazamientos de las letras de la clave, luego queda ordenar las posibles claves y elegir la más plausible de ellas. $s$ $s$ $ms$ $metro$ $metro$

Ejemplo de uso

Que se dé algún texto encriptado con el cifrado Vigenère . Encuentre la palabra clave y lea el texto sin formato.

vltsduzhbutzhyarrmshbrkhtseooetsgbrtsmyfktyyumshesyatspunuyashcheytaedkzibr tsgbrpackkkutspbsegktsguuschartsyoevryuoyuekaaebrnyafukabarpyaafkyzhyaffnyo yafyvbnenfuyugbrsshzhetbeyochyuyuryegofkbchyabashvyoyyuadnzhzhzhuztseevlrnchulb yuptsurun'shseyuuzktskhyarrnryuvyaspemaschkpeuzhzhyatufuyaruravrtuburpeshlafouf buatsmnubsyukytaedyunooegyuozhbgkbryntsepotchmeodztsvbtsshshvshchepchdchdryyusksag yppegyukdoyrsrevoopchschshokazrbbneugnyaloksrbyuyebdeulbyuasshowetshkrsdugefl bubujchchtrtpegyukiugyuemegyukk'pegyaapufuezradzzhchyurmftskhrayuyuanchechyuhyyhy tsomeftspoirknshchpeteuzyabaschushchbayechdfrpetsjrtsjtspoillufedtsoyedyatrrachkubu fnytaedktskrnntsyuabugyuuuburpyuezhtgyurkuyuschoufegyasuoichschshchdtssfyredella yuyafshechtsyuyrshvyakhvmkrshrpgyuopeutschytaedktsybrtsyyazhturbuetebduyascheubibruv erizogibrbagbrympunotsshyazhtechkfodscho'chzhshyuytskhchshvuebdldegyasuahzzebdeulkn shbzhyatseeredyvyuvlnyafuoohfekgtschchgezhtanopchynazhpackkyumenkyrefshchebbud endadyaryeyueletchoubcefevlnoegfdseveyokbschoukgouteypubbtschkpegyuchsaabenefark atskhyovaetufyaepryuvrzhadfezhbfutoshchoyavgupchrshhuiteachychiramchufchouyayuonkyazhy kgstsbryasshchyot'zhrsshchl

Debido al hecho de que el algoritmo completo para encontrar la longitud de la clave es extremadamente engorroso, calculamos el índice de coincidencia solo y nos aseguramos de que la longitud de la clave sea realmente igual a 5. ${\ estilo de visualización t = 5}$

vthmtststmtsyaatstsatsyavoayabya'fyanyustuyebauduvu... lzhshagmshpshchgchpegryuefyiffegshbgshzhnzhll ... tsbyabobyeueebbkgutsrebuaanynbeyuochvchtsrb ... durrorfusnydrrbkuyoukrkrfzhyvfrzherfyayoyuzhenyu... utsrhekyautkputsshcheuanapkyaobuyechkykbeachechp...

Haga coincidir los valores del índice para cada una de las filas:

Línea	Índice de coincidencia
una	0.05676
2	0.05896
3	0.06340
cuatro	0.05810
5	0.07230

El proceso de búsqueda de cambios de línea relativos también se resume:

Línea	Cambio	Índice de coincidencia mutua
una	—	—
2	6	0.05494
3	3	0.05798
cuatro	dieciséis	0.06068
5	3	0.06045

Palabra clave encontrada: "palabra".

Después del descifrado, obtenemos el siguiente texto sin formato:

Es lo mismo estar sano que no estar enfermo, definitivamente la salud es algo doloroso cuello para nosotros salud física esta condición y la capacidad y energía para hacer cosas Necesito disfrutarlo y recuperarme sin ninguna ayuda de salud, paradójicamente, no puedes obligarte directamente a estar sano. todo lo que queda es observar cómo la asombrosa capacidad de su cuerpo para sanar usted mismo comienza a actuar por su cuenta su riqueza o pobreza crueldad u otra aquí la actividad no parece importar la salud es algo positivo pero no significa la negación del placer, la salud es una consecuencia natural de nuestro estilo de vida en relación dieta ambiente salud es un indispensable dmethproperty esto es un proceso esto es lo que hacemos el resultado de nuestros pensamientos y sentimientos esto o forma de existencia es interesante que la dirección de la investigación médica es cada vez más se desvía más hacia un área que hasta ahora ha sido considerada una esfera de actividad psicólogos sti y ahora es difícil establecer distinciones claras entre físico y factores mentales de las enfermedades

Notas

↑ 1 2 Pilidi, 2009 , pág. 55.
↑ 1 2 3 4 5 Friedman, 1938 , pág. 117.

Véase también

Literatura

Guillermo Federico Friedman. Criptoanálisis militar. Parte II. Variedades más simples de sistemas de sustitución polialfabéticos . - Washington: Imprenta del gobierno de los Estados Unidos, 1938. - 120 p. Archivado el 11 de septiembre de 2010 en Wayback Machine .
Pilidi VS Criptografía. Capítulos introductorios . - Rostov del Don: SFU, 2009. - 110 p.
Bauer F., Secretos descifrados. Métodos y principios de la criptología: Per. inglés - M.: Mir, 2007. - 550 p. — ISBN 5-03-003551-6
Zhdanov O.N., Kudenkova I.A. Criptoanálisis de cifrados clásicos - Krasnoyarsk 2008