En el 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éticos , 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 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 se puede atacar con análisis de frecuencia . [6] 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 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, 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 cadenas más 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 ocurre 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 la abreviatura de criptografía.
" cripto " es una cadena repetida y la distancia entre las ocurrencias es de 20 caracteres. Si alineamos el texto sin formato con una palabra clave de 6 caracteres " abcdef "(6 no se divide en 20):
abcdef abcdefabcdefab cdefab cdefabc crypto es la abreviatura de criptografía .
la primera instancia de " cripto "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 " cripto "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 cuerdas
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 facilitarla mucho. Sin embargo, aún se requiere cuidado, ya que algunas cadenas repetidas pueden ser solo una coincidencia, por lo que algunas de las distancias de repetición son engañosas. El criptoanalista debe descartar las coincidencias para encontrar la longitud correcta. Luego, por supuesto, los textos cifrados monoalfabéticos que resulten deben ser criptoanalizados.
- Un criptoanalista busca grupos repetidos de letras y cuenta el número de letras entre el comienzo de cada grupo repetido. Por ejemplo, si el texto cifrado fuera FGX THJAQWN FGX Q , la distancia entre Grupos FGX es 10. El analista registra las distancias para todos los grupos repetidos en el texto.
- A continuación, el analista factoriza cada uno de estos números. Si se repite cualquier número 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 las mismas letras se cifran utilizando las mismas letras clave que por mera coincidencia; esto es especialmente cierto para cadenas largas coincidentes. Las letras de la 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. Un factor común suele ser evidente.
- 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 letra N debe haber sido cifrada usando la misma letra del texto clave. Agrupando cada letra N , el analista tiene N "mensajes", cada uno encriptado usando una sustitución de un alfabeto, y luego cada pieza puede ser atacada usando análisis de frecuencia .
- Con el mensaje resuelto, el analista puede determinar rápidamente cuál era la palabra clave. O, en el proceso de resolver las piezas, el analista podría usar conjeturas sobre la palabra clave para ayudar a romper el mensaje.
- Una vez que el interceptor conoce la palabra clave, ese conocimiento puede usarse para leer otros mensajes que usan la misma clave.
Superposición
Kasiski realmente usó "superposición" para resolver el cifrado de Vigenère. Comenzó por encontrar la longitud de la clave, como se indicó anteriormente. Luego tomó varias copias del mensaje y las colocó una encima de la otra, cada una desplazada a la izquierda por la longitud de la tecla. Kasiski luego observó que cada columna estaba formada por letras encriptadas con un solo alfabeto. Su método fue equivalente al descrito anteriormente, pero quizás 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 las colocaría una encima de la otra.
Los analistas modernos usan computadoras, pero esta descripción ilustra el principio que implementan los algoritmos informáticos.
El método generalizado:
- El analista desplaza el mensaje inferior una letra a la izquierda, luego una letra más a la izquierda, etc., revisando cada vez el mensaje completo y contando el número de veces que aparece la misma letra en el mensaje superior e inferior.
- El número de "coincidencias" aumenta drásticamente cuando el mensaje de la parte inferior se desplaza en un múltiplo de la longitud de la clave, porque entonces las letras adyacentes están en el mismo idioma usando el mismo alfabeto.
- Habiendo encontrado la longitud de la clave, el criptoanálisis procede como se describe arriba usando análisis de frecuencia .
Referencias
- ↑ Rodriguez-Clark, Daniel, Kasiski Analysis: Breaking the Code , consultado el 30 de noviembre de 2014
- ^ R. Morelli, R. Morelli, Historical Cryptography: The Vigenere Cipher , Trinity College Hartford, Connecticut , consultado el 4 de junio de 2015
- ↑ Kasiski, FW 1863. Die Geheimschriften und die Dechiffrir-Kunst. Berlín: ES Mittler und Sohn
- ^ Franksen, OI 1985 El secreto del Sr. Babbage: el cuento de un cifrado y APL. Prentice Hall
- ^ Singh, Simon (1999), El libro de códigos: La ciencia del secreto desde el Antiguo Egipto hasta la criptografía cuántica , Londres: Cuarto poder, p. 78, ISBN 1-85702-879-1
- ^ Método de Kasiski , Universidad Tecnológica de Michigan , consultado el 1 de junio de 2015