Examen de Kasiski

En criptoanálisis , el examen de Kasiski (también conocido como prueba de Kasiski o método de Kasiski ) es un método para atacar los cifrados de sustitución polialfabética , como el cifrado de Vigenère . ^{[1] [2]} Fue publicado por primera vez por Friedrich Kasiski en 1863, ^[3] pero parece haber sido descubierto independientemente por Charles Babbage ya en 1846. ^{[4] [5]}

En los cifrados de sustitución polialfabéticos en los que los alfabetos de sustitución se eligen mediante el uso de una palabra clave , el examen de Kasiski permite a un criptoanalista deducir la longitud de la palabra clave. Una vez que se descubre la longitud de la palabra clave, el criptoanalista alinea el texto cifrado en n columnas, donde n es la longitud de la palabra clave. Luego, cada columna puede tratarse como el texto cifrado de un cifrado de sustitución monoalfabético . Como tal, cada columna puede ser atacada con análisis de frecuencia . ^[6] De manera similar, donde se ha utilizado una máquina de cifrado de flujo de rotor , este método puede permitir la deducción de la longitud de rotores individuales.

El examen de Kasiski implica buscar cadenas de caracteres que se repiten en el texto cifrado . Las cadenas deben tener tres caracteres o más para que el examen sea exitoso. Entonces, las distancias entre ocurrencias consecutivas de las cadenas probablemente sean múltiplos de la longitud de la palabra clave. Por lo tanto, encontrar más cadenas repetidas reduce las longitudes posibles de la palabra clave, ya que podemos tomar el máximo común divisor de todas las distancias. ^[7]

El motivo por el que funciona esta prueba es que si aparece una cadena repetida en el texto sin formato y la distancia entre los caracteres correspondientes es un múltiplo de la longitud de la palabra clave, las letras de la palabra clave se alinearán de la misma manera en ambas apariciones de la cadena. Por ejemplo, considere el texto sin formato:

El hombre y la mujer recuperaron la carta de la oficina de correos.

La palabra " the " es una cadena repetida que aparece varias veces. Si alineamos el texto sin formato con una palabra clave de 5 caracteres " beads ":

bea dsb ead sbe adsbe adsbeadsb ead sbeads bead sbe adsb eadsbe el hombre y la mujer recuperaron la carta de la oficina de correos

La palabra "the" a veces se asigna a "bea", a veces a "sbe" y otras veces a "ead". Sin embargo, se asigna a "sbe" dos veces y, en un texto lo suficientemente largo, es probable que se asigne varias veces a cada una de estas posibilidades. Kasiski observó que la distancia entre esas apariciones repetidas debe ser un múltiplo del período de cifrado. ^[7]

En este ejemplo, el período es 5 y la distancia entre las dos apariciones de "sbe" es 30, que es 6 veces el período. Por lo tanto, el máximo común divisor de las distancias entre secuencias repetidas revelará la longitud de la clave o un múltiplo de esta.

La dificultad de utilizar el examen de Kasiski reside en encontrar cadenas repetidas. Se trata de una tarea muy difícil de realizar manualmente, pero los ordenadores pueden facilitarla mucho. Sin embargo, hay que tener cuidado, ya que algunas cadenas repetidas pueden ser simplemente una coincidencia, por lo que algunas de las distancias de repetición pueden ser engañosas. El criptoanalista tiene que descartar las coincidencias para encontrar la longitud correcta. Después, por supuesto, los textos cifrados monoalfabéticos resultantes deben ser criptoanalizados.

1. Un criptoanalista busca grupos repetidos de letras y cuenta la cantidad de letras entre el comienzo de cada grupo repetido. Por ejemplo, si el texto cifrado fuera FGX THJAQWN FGX Q , la distancia entre los grupos FGX sería 10. El analista registra las distancias de todos los grupos repetidos en el texto.
2. A continuación, el analista factoriza cada uno de estos números. Si algún número se repite en la mayoría de estas factorizaciones, es probable que sea la longitud de la palabra clave. Esto se debe a que es más probable que se produzcan grupos repetidos cuando se cifran las mismas letras utilizando las mismas letras clave que por mera coincidencia; esto es especialmente cierto para cadenas de coincidencia largas. Las letras clave se repiten en múltiplos de la longitud de la clave, por lo que es probable que la mayoría de las distancias encontradas en el paso 1 sean múltiplos de la longitud de la clave. Por lo general, es evidente un factor común.
3. Una vez que se conoce la longitud de la palabra clave, entra en juego la siguiente observación de Babbage y Kasiski. Si la palabra clave tiene N letras, entonces cada N- ésima letra debe haber sido cifrada utilizando la misma letra del texto clave. Al agrupar cada N -ésima letra, el analista tiene N "mensajes", cada uno cifrado utilizando una sustitución de una letra, y cada pieza puede entonces ser atacada utilizando el análisis de frecuencia .
4. Con el mensaje resuelto, el analista puede determinar rápidamente cuál era la palabra clave. O bien, en el proceso de resolver las piezas, el analista puede usar suposiciones sobre la palabra clave para ayudar a descifrar el mensaje.
5. Una vez que el interceptor conoce la palabra clave, ese conocimiento se puede utilizar para leer otros mensajes que utilicen la misma clave.

Kasiski utilizó la "superposición" para resolver el cifrado de Vigenère. Empezó por encontrar la longitud de la clave, como se indica más arriba. Luego tomó varias copias del mensaje y las colocó una sobre otra, cada una desplazada hacia la izquierda por la longitud de la clave. Kasiski observó entonces que cada columna estaba formada por letras cifradas con un único alfabeto. Su método era equivalente al descrito anteriormente, pero quizá sea más fácil de imaginar.

Los ataques modernos a los cifrados polialfabéticos son esencialmente idénticos a los descritos anteriormente, con la única mejora del recuento de coincidencias . En lugar de buscar grupos repetidos, un analista moderno tomaría dos copias del mensaje y colocaría una sobre otra.

Los analistas modernos utilizan computadoras, pero esta descripción ilustra el principio que implementan los algoritmos de la computadora.

El método generalizado:

1. El analista desplaza el mensaje inferior una letra a la izquierda, luego una letra más a la izquierda, etc., recorriendo cada vez todo el mensaje y contando el número de veces que aparece la misma letra en el mensaje superior e inferior.
2. El número de "coincidencias" aumenta drásticamente cuando el mensaje inferior se desplaza por un múltiplo de la longitud de la clave, porque entonces las letras adyacentes están en el mismo idioma y utilizan el mismo alfabeto.
3. Una vez encontrada la longitud de la clave, el criptoanálisis procede como se describió anteriormente utilizando el análisis de frecuencia .

• Criptoanálisis: Cómo descifrar un texto cifrado de Vigenère con el test de Kasiski en YouTube - Un vídeo que muestra cómo descifrar un texto cifrado de Vigenère utilizando el examen de Kasiski