Examen de kasiski

En criptoanálisis, el examen de Kasiski (también conocido como prueba de Kasiski o método de Kasiski) es una método para atacar cifrados de sustitución polialfabética, como el cifrado Vigenère. Fue publicado por primera vez por Friedrich Kasiski en 1863, pero parece haber sido descubierto de forma independiente por Charles Babbage ya en 1846.

Cómo funciona

En cifrados de sustitución polialfabéticos donde los alfabetos de sustitución se eligen mediante el uso de una palabra clave, el examen de Kasiski permite al 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 atacarse con análisis de frecuencia. De manera similar, cuando se ha utilizado una máquina de cifrado de flujo de rotor, este método puede permitir la deducción de la longitud de los rotores individuales.

El examen 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, es probable que las distancias entre apariciones consecutivas de las cadenas sean múltiplos de la longitud de la palabra clave. Por lo tanto, encontrar más cadenas repetidas reduce las posibles longitudes de la palabra clave, ya que podemos tomar el máximo común divisor de todas las distancias.

La razón por la que esta prueba funciona 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 con ambas apariciones de la cadena. Por ejemplo, considere el texto sin formato:

crypto es corto para la criptografía.

"crypto"es una cuerda repetida, y la distancia entre las ocurrencias es de 20 caracteres. Si alineamos el texto con una palabra clave de 6 caracteres "abcdef" (6 no se divide en 20):

abcdefabcdefabcdefabcdefabcdefabc
crypto es corto para cryptoGrafi.

la primera instancia de "crypto" se alinea con "abcdef" y la segunda instancia se alinea con "cdefab". Las dos instancias se cifrarán con textos cifrados diferentes y el examen de Kasiski no revelará nada. Sin embargo, con una palabra clave de 5 caracteres "abcde" (5 se divide en 20):

abcdeabcdeabcdeabcdeabcdeabcdeabc
crypto es corto para cryptoGrafi.

ambas apariciones de "crypto" alinearse con "abcdea". Las dos instancias se cifrarán con el mismo texto cifrado y el examen de Kasiski será efectivo.

Un ataque basado en cadenas

La dificultad de utilizar el examen de Kasiski radica en encontrar cadenas repetidas. Esta es una tarea muy difícil de realizar manualmente, pero las computadoras pueden hacerlo mucho más fácil. Sin embargo, aún se requiere cuidado, ya que algunas cadenas repetidas pueden ser simplemente coincidencias, de modo que algunas de las distancias repetidas son engañosas. El criptoanalista debe descartar las coincidencias para encontrar la longitud correcta. Luego, por supuesto, los textos cifrados monoalfabéticos resultantes deben ser criptoanalizados.

1. Un criptanalista busca grupos repetidos de letras y cuenta el número de letras entre el comienzo de cada grupo repetido. Por ejemplo, si el cifertexto fuera FGXTHJAQWNFGXQ, la distancia entre FGX grupos son 10. El analista registra las distancias para todos los grupos repetidos en el texto.
2. El analista siguiente factores cada uno de estos números. Si cualquier número se repite en la mayoría de estos factores, es probable que sea la longitud de la palabra clave. Esto se debe a que los grupos repetidos son más propensos a ocurrir cuando las mismas letras están encriptadas usando las mismas letras clave que por mera coincidencia; esto es especialmente cierto para cadenas de juego largas. Las letras clave se repiten en varios de la longitud clave, por lo que la mayoría de las distancias encontradas en el paso 1 son probablemente múltiples de la longitud clave. Un factor común suele ser evidente.
3. Una vez que se conoce la longitud de la palabra clave, la siguiente observación de Babbage y Kasiski entra en juego. Si la palabra clave es N letras largas, entonces cada Nth letter must have been enciphered using the same letter of the keytext. Grupo de todos Nt carta juntos, el analista tiene N "mensajes", cada uno encriptado usando una sustitución de un alfabeto, y cada pieza puede ser atacada mediante análisis de frecuencia.
4. Utilizando el mensaje resuelto, el analista puede determinar rápidamente cuál era la palabra clave. O, en el proceso de resolución de las piezas, el analista podría usar suposiciones sobre la palabra clave para ayudar a romper el mensaje.
5. Una vez que el interceptor conoce la palabra clave, ese conocimiento se puede utilizar para leer otros mensajes que usan la misma clave.

Superposición

Kasiski en realidad utilizó "superposición" para resolver el cifrado de Vigenère. Comenzó encontrando la longitud de la clave, como se indicó anteriormente. Luego tomó varias copias del mensaje y las colocó una encima de otra, cada una desplazada hacia la izquierda a lo largo de la clave. Luego, Kasiski observó que cada columna estaba formada por letras cifradas con un solo alfabeto. Su método era equivalente al descrito anteriormente, pero quizás sea más fácil de imaginar.

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

Los analistas modernos utilizan computadoras, pero esta descripción ilustra el principio que implementan los algoritmos informáticos.

El método generalizado:

1. El analista cambia el mensaje inferior una carta a la izquierda, luego una carta más a la izquierda, etc., cada vez que pasa por todo el mensaje y contando el número de veces que la misma letra aparece en el mensaje superior e inferior.
2. El número de "coincidencias" sube marcadamente cuando el mensaje inferior se desplaza por un múltiplo de la longitud de la llave, porque entonces las letras adyacentes están en el mismo idioma utilizando el mismo alfabeto.
3. Habiendo encontrado la longitud clave, el criptanálisis procede como se describe anteriormente utilizando análisis de frecuencia.