stringtranslate.com

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]

Cómo funciona

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. Luego, es probable que las distancias entre las 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 longitudes posibles de la palabra clave, ya que podemos tomar el máximo común divisor de todas las distancias.

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:

crypto es la abreviatura de criptografía.

" crypto " es una cadena repetida y la distancia entre las apariciones es de 20 caracteres. Si alineamos el texto sin formato con una palabra clave de 6 caracteres " abcdef " (6 no es divisible por 20):

abcdef abcdefabcdefab cdefab cdefabc crypto es la abreviatura de criptografía .

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

abcdea bcdeabcdeabcde abcdea bcdeabc crypto es la abreviatura de criptografía .

Ambas apariciones de " crypto " coinciden con " abcdea ". Las dos instancias cifrarán el mismo texto cifrado y la verificación de Kasiski será efectiva.

Un ataque basado en cadenas

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.

Superposición

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 tal vez 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 hacia la izquierda, luego una letra más hacia 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 .

Enlaces externos

Referencias

  1. ^ Rodriguez-Clark, Daniel, Kasiski Analysis: Breaking the Code , consultado el 30 de noviembre de 2014
  2. ^ R. Morelli, R. Morelli, Criptografía histórica: el cifrado Vigenere, Trinity College Hartford, Connecticut , consultado el 4 de junio de 2015
  3. ^ Kasiski, FW 1863. Die Geheimschriften und die Dechiffrir-Kunst. Berlín: ES Mittler und Sohn
  4. ^ Franksen, OI 1985 El secreto del señor Babbage: la historia de una cifra y APL. Prentice Hall
  5. ^ Singh, Simon (1999), El libro de códigos: La ciencia del secreto desde el Antiguo Egipto hasta la criptografía cuántica , Londres: Fourth Estate, pág. 78, ISBN 1-85702-879-1
  6. ^ El método de Kasiski, Universidad Tecnológica de Michigan , consultado el 1 de junio de 2015