Introducción a la seguridad informática y criptografía clásica

TEMA IV: ALGORITMOS DE CIFRA CLÁSICA


LECCIÓN 9: ALGORITMOS DE CIFRA POR SUSTITUCIÓN POLIALFABÉTICA

Autor: Dr. Jorge Ramió Aguirre.
Fecha de publicación: 24 de abril de 2017.
Colaboración diseño Web: D. Jaime Sánchez Pedrós, becario Talentum Startups.

En esta novena lección del MOOC, nos adentramos a los sistemas más interesantes de la criptografía clásica: la cifra polialfabética. Todos los sistemas de cifra anteriores habían sucumbido muy fácilmente, de una u otra forma, ante un criptoanálisis basado en las estadísticas del lenguaje, en tanto la redundancia del lenguaje, que fue estudiada entre otros por Claude Shannon, se manifestaba de manera clara también en el criptograma. No obstante, al tener varios alfabetos de cifra, el criptograma presentará una relación de frecuencias de sus letras más o menos plana, lo que no nos permite -al menos en una primera aproximación- aplicar las técnicas que nos habían servido en sistemas de cifra monoalfabéticos. Tanto es así, que hubo que esperar hasta casi 300 años para que estos sistemas polialfabéticos fuesen criptoanalizados, todo un récord.

Se seguirá usando el software para prácticas de criptografía clásica Criptoclásicos v2.1, desarrollado por D. Juan Contreras Rubio. Como últimamente se han realizado algunas actualizaciones al software, lo cual se agradece nuevamente a su desarrollador, por favor comprueba desde ese enlace de descarga que tienes instalada la última versión del software.

Comencemos…

Temario


APARTADO 1. EL CIFRADO DE VIGENÈRE

1.1. La figura de Blaise de Vigenère


Figura 1.1. Blaise de Vigenère.

Blaise de Vigenère fue un criptógrafo, químico y diplomático francés que nace en 1523 y fallece en 1596. En 1586 en el libro Traité des chiffres où secrètes manières d'escrire describe de forma detallada y estructurada la cifra polialfabética, basándose en trabajos previos de otros criptógrafos famosos como Alberti, Trithemius, Bellaso y della Porta. La cifra de Vigenère se mantiene por casi 300 años invulnerable, siendo por tanto bautizada como "le chiffre indéchiffrable"; es el sistema de cifra polialfabética más conocido y por ello nos centraremos exclusivamente en él.

        
Figura 1.2. Leon Battista Alberti, Johannes Trithemius, Giovan Battista Bellaso y Giovanni Battista della Porta.

Ejercicio 1.1:
Busca en Internet quiénes eran Alberti, Trithemius, Bellaso y della Porta.

La cifra de Vigenère es muy sencilla, bien sea a través de su tabla o bien usando matemáticas discretas.

La tabla de Vigenère consiste en una matriz cuadrada de nxn elementos, siendo n el número de letras del alfabeto, que en el caso del español en mayúsculas será 27. En la primera fila se escribe el alfabeto desde la A hasta la Z, lo que sería el alfabeto del texto en claro, en la segunda fila el mismo alfabeto pero desplazado un espacio a la izquierda, en la tercera dos veces, y así sucesivamente hasta la última fila en que el desplazamiento será igual a n-1.


Figura 1.3. Tabla de Vigenère para español en mayúsculas mod 27.

Vamos a pensar un poco:
¿Serían manejables tablas de Vigenère con otros alfabetos como por ejemplo mayúsculas y minúsculas, con o sin acentos, con signos de puntuación, etc.?


1.2. Cifrando con el método de Vigenère

Así, si el mensaje es HERMOSO y la clave CIELO, en la columna de la letra H se busca la intersección con la fila de la letra C, dando como resultado el criptograma J, como se muestra en la figura 4. A continuación repetimos el mismo procedimiento para la letra E del texto en claro y la letra I de la clave, y así sucesivamente. Cuando la clave se termina, porque por lo general será menor que el mensaje, ésta se repite de forma cíclico, es decir CIELOCIELOCIELO. Por lo tanto como la clave CIELO tiene 5 letras, la sexta letra S del mensaje HERMOSO se volverá a cifrar con la primera letra C de la clave CIELO.


Figura 1.4. Cifrando con la tabla de Vigenère la letra H con la clave C mod 27.

Realizando esta operación en todo el mensaje, el texto en claro HERMOSO se cifrará con Vigenère y la clave CIELO como JMVWD UW.


Figura 1.5. Destruyendo relaciones del alfabeto con el cifrado de Vigenère.

Como ya sabemos, la cifra polialfabética destruye esa relación directa y proporcional que se observaba en los sistemas de cifra monoalfabéticos entre el texto en claro y el criptograma. En este simple ejemplo esto se ve claramente en la figura 1.5 puesto la letra O, presente dos veces en el texto en claro HERMOSO, se cifra como D o W, en función de la posición relativa que tenga esta letra con respecto a la clave (figura izquierda). Y algo parecido sucede si observamos la letra W del criptograma, que en este caso procede bien de la M o de la O del texto en claro (figura derecha).

Ejercicio 1.2:
¿Además de la D y la W, cómo otras letras podría cifrarse en este caso la O del texto en claro?

En vez de la tabla, para cifrar podemos usar matemáticas discretas módulo n de la siguiente manera: escribimos la clave debajo del mensaje tantas veces como sea necesario y vamos reemplazando el código de las letras para realizar posteriormente la operación suma.


Figura 1.6. Alfabeto mod 27.


Figura 1.7. Cifra de Vigenère aplicando matemáticas discretas.

Las operaciones de la figura 1.7 siguen la siguiente ecuación genérica de cifra de Vigenère:

ci = mi + ki mod n

En donde el subíndice i se refiere al carácter iésimo del texto en claro y de la clave, esta última repetida tantas veces como sea necesario, o lo que es lo mismo, representada en forma cíclica o módulo L, siendo L la longitud de la misma.

Ejercicio 1.3:
Con la ayuda de la calculadora de Windows y con la ecuación ci = mi + ki mod 27 cifra mediante Vigenère al igual que en la figura 1.7 el mensaje NO FUE INDESCIFRABLE con la clave PERO CASI.
Comprueba que el criptograma debe ser: CSWJG IFLTW TWHRS JAI.

Nos vemos en el laboratorio...
Enunciado Práctica 1:
Usando el software Criptoclásicos v2.1, cifra con Vigenère el texto en claro TODOS SOMOS MUY IGNORANTES LO QUE OCURRE ES QUE NO TODOS IGNORAMOS LAS MISMAS COSAS con la clave EINSTEN. Comprueba con la ecuación de cifra genérica las cinco primeras letras del texto en claro.
Solución:
Criptosistemas -> Vigenère. Copiamos el texto en claro en la caja de texto, elegimos como clave EISNTEN y damos a cifrar, obteniendo las siguientes pantallas:



Texto claro: TODOS. Clave: EINST
T + E = 20 + 4 = 24 mod 27 = 24 = X
O + I = 15 + 8 = 23 mod 27 = 23 = W
D + N = 3 + 13 = 16 mod 27 = 16 = P
O + S = 15 + 19 = 34 mod 27 = 7 = H
S + T = 19 + 20 = 39 mod 27 = 12 = M

Si en vez de usar una clave con 5 alfabetos diferentes como en este ejemplo CIELO, o siete como EINSTEIN del ejercicio de laboratorio anterior, se usa una clave que tenga varios caracteres y, mejor aún, si tiene muchas letras diferentes como podría ser MURCIELAGO con 10 alfabetos, en la práctica todas las letras del criptograma tendrán una frecuencia muy similar por lo que se difumina la redundancia del lenguaje. Como es obvio, la clave puede ser una palabra o bien una frase. Por ejemplo, en vez de MURCIELAGO usar la frase EL MURCIELAGO ES UN MAMIFERO VOLADOR, con 31 letras y 15 alfabetos (M, U, R, C, I, E, L, A, G, O, S, N, F, V, D).

Es decir, con una clave larga y con varias letras distintas, en el criptograma se enmascara notoriamente la redundancia del lenguaje del texto en claro, haciendo inútil los ataques por estadísticas del lenguaje conocidos hasta ahora. Aquí ya no tiene sentido intentar un ataque mediante análisis de frecuencias, al menos de la manera como lo veníamos haciendo con los sistemas de cifra monoalfabéticos, pues no tenemos información de interés en esas frecuencias del criptograma al ser todas muy similares.

Vamos a pensar un poco:
Ordena de mejor (mayor confusión) a peor (menor confusión) estas 5 claves para una cifra de Vigenère:
MARIMBA
ESTORNUDO
ABRACADABRA
CAZANDO
MURCIELAGOS
MALABARES
Justifica tu clasificación.

Para comprobar este hecho, a continuación se muestran las frecuencias de las letras de sendos criptogramas de cifras de Vigenère sobre el texto en claro que se indica más abajo, primero con la clave K = S de una única letra y un único alfabeto (cifra monoalfabética), después con la clave K = SOL de 3 letras y 3 alfabetos diferentes y, por último, con la clave K = MURCIELAGO de 10 letras y 10 alfabetos diferentes, obtenido con Criptoclásicos v2.1.

Texto en claro:
Los murciélagos son los únicos mamíferos capaces de volar, se han extendido por casi todo el mundo y han ocupado una gran variedad de nichos ecológicos diferentes.


Figura 1.8. Frecuencias de las letras en el texto en claro.

Cifra de Vigenère y clave S
Cifra de Vigenère y clave SOL
Cifra de Vigenère y clave MURCIELAGO
WWWOJ DKMHZ MÑSVH AUORH GUMFD ETEOW QMVRH ÑITDQ PAHHK ASEUH POEPS JBIPR TLSSD DKEVW FWHRS WTYPR AGLDB AKYSO OWYPO RZEPK MZMHR MLHHB TKLRH PKSÑD RPGRH OPJHG PUXHH WWWOJ DKMHZ MÑSVH AUORH GUMFD ETEOW QMVRH ÑITDQ PAHHK ASEUH POEPS JBIPR TLSSD DKEVW FWHRS WTYPR AGLDB AKYSO OWYPO RZEPK MZMHR MLHHB TKLRH PKSÑD RPGRH OPJHG PUXHH WJKÑC VNIKZ MAGUA SXLUH GHZEW WWARW QYJQA GLPGQ PNUGD SVAXH PBROM BEESR TXGRW VNAYW FJUQM OWUSR ASYCU SNUVO OJMOI KCASK MMZGL EÑDKB TWYQA INOQD RCTQA HSFKG PHLGA
Frecuencias de la letras en el criptograma
Frecuencias de la letras en el criptograma
Frecuencias de la letras en el criptograma



Lógicamente, como el primer cifrado con clave S se corresponde a una cifra monoalfabética, las frecuencias de las letras en el criptograma son exactamente las mismas que en el texto en claro, pero distribuidas según el desplazamiento que ha producido la cifra por la letra S, es decir 19 espacios a la derecha.

Sin embargo, al cifrar primero con la clave SOL y posteriormente con la clave MURCIELAGO, se observa una nivelación de dichas frecuencias, de forma que las letras más frecuentes pierden cada vez más esa notoriedad y, al contrario, las letras menos frecuentes aumentan su frecuencia.

Por este hecho, el sistema de Vigenère parecía indescifrable y prueba de ello es que sobrevivió a los ataques durante casi tres siglos pero, como veremos más adelante, finalmente sucumbe ante un ataque también mediante el análisis de frecuencias de las letras en el criptograma, pero algo más sofisticado que lo que hemos visto hasta ahora.


1.3. Descifrando con el método de Vigenère

Para descifrar un criptograma de Vigenère, simplemente se realiza el proceso inverso, tanto usando la tabla como a través de ecuaciones en matemática discreta.

Mediante la tabla de Vigenère, para descifrar el criptograma del primer ejemplo JMVWD UW conociendo que la clave era CIELO, se busca en la fila de la primera letra C de la clave la letra J del criptograma. Hecho esto, nos posicionamos en esa columna y se lee la letra que aparece en la primera fila como texto en claro, en este caso la letra H, como se observa en la figura 1.9. Este proceso se realiza para cada una de las letras del criptograma con su correspondiente letra de la clave, recuperando así el texto en claro.


Figura 1.9. Descifrando con la tabla de Vigenère la letra J con la clave C mod 27.

Las operaciones de la figura 1.9 siguen la siguiente ecuación genérica de descifrado de Vigenère:

mi = ci - ki mod n

O bien, para trabajar sólo con números positivos:

mi = ci + (n - ki) mod n

Esto es, usando matemáticas discretas, hacemos la misma operación que en la cifra pero en vez de sumar el valor del código de la letra de la clave al de la letra del texto en claro, habrá que restarlo ya que es la operación inversa. O bien, por las propiedades la aritmética modular, si se desea podemos sumarle 27 (el módulo) menos el valor del código de esa letra de la clave, como ya hemos visto en el cifrado del César.


Figura 1.10. Descifrado de Vigenère aplicando matemáticas discretas.

Nos vemos en el laboratorio...
Enunciado:
Si una cifra de Vigenère mod 27 entrega como criptograma AEYZR NTZDJ SEVSJ SFAÑS XRFVH KOFTZ DJLPZ LUO, y se sabe que ha cifrado con la clave PEDRO NAVAJA, ¿cuál era el texto en claro?
Solución:
En Criptoclásicos seleccionamos Criptosistemas -> Vigenère. Copiamos el criptograma en la caja de texto, ponemos como clave PEDRO NAVAJA y damos a descifrar, obteniendo:
M = LA VIDA TE DA SORPRESAS, SORPRESAS TE DA LA VIDA.


Ejercicio 1.4:
Con la ayuda de la calculadora de Windows y con la ecuación mi = ci - ki mod 27 descifra mediante Vigenère al igual que en la figura 1.10 el criptograma YGVMS SKKOX con la clave FORTALEZA.
Comprueba que el texto en claro era: TRES SIGLOS.


1.4. Aumentando la fortaleza: la cifra autoclave

La debilidad que puede intuirse en Vigenère es que la clave por lo general no será demasiado larga y, por lo tanto, ésta será siempre periódica; es decir, se irá repitiendo a largo del mensaje. Esto entregará pistas al criptoanalista como veremos en el apartado 2 de esta lección.

Para evitar esto y aumentar la fortaleza al criptoanálisis, se puede usar una de las variantes del sistema Vigenère conocida como autoclave y que consiste en lo siguiente:

• Se escribe la clave como siempre.
• Cuando se llega a la última letra de esa clave, ésta ya no se repite.
• Se continúa la clave con el propio mensaje en claro.

Por ejemplo, si se cifra el mensaje AUTOCLAVE usando la clave LUNA, obtendremos el criptograma que se muestra en la figura 1.11:


Figura 1.11. Cifrado Autoclave o con Clave Continua.

Y cuyas operaciones modulares son las que se muestran en la figura 1.12.


Figura 1.12. Operaciones en cifrado Autoclave.

Observa que al terminarse la clave LUNA, seguimos con el texto en claro AUTOC como clave.

Obviamente, la cifra sigue siendo tipo Vigenère, es decir ci = mi + ki mod n, salvo que ahora ki no será periódica como en Vigenère, que era el talón de Aquiles de esa cifra, si bien como ya se ha dicho mantuvo su fortaleza durante casi tres siglos.

Como es lógico, para el descifrado usaremos la misma ecuación que con Vigenère, es decir: mi = ci - ki mod n. Como el destinatario de la cifra sólo conoce la clave y no el texto en claro, con dicha clave de n letras será capaz de descifrar solamente las n primeras letras del criptograma. Pero, no obstante, hecho esto, ya conocerá el comienzo del texto en claro que le servirá como clave para el descifrado de las siguientes letras del criptograma.

Nos vemos en el laboratorio...
Enunciado:
Descifra el siguiente criptograma que se ha obtenido mediante una cifra autoclave, siendo la clave UNO DE LOS MAS GRANDES CRIPTOGRAFOS.
C = XHGDQ ESDMP KÑDEE DKNGJ ZPFJS UIFZO LFCIN FJCES VZTGB FXCIU DAYNU UDIZY WWZBE YNVQW IVUNK ZEPHD ODQUZ ZLBDN DRWTH QSERÑ IVMLE RCMGI FLSOR ZXTSD IGLOX QSDJH WVCIW QXQJC KMBPO KMPSK MUVIM NJDNB LCSZH XHNYY UIXDB SOXHZ LXWVG DJGXH WLTDW KÑSAQ IMZLN BVMLX HUOQQ XIQGW GUFTW KZKMO KUDNI NSIFJ DUOZI JBSVV OWFAI EÑGYO WPSOA P.
Solución:
En Criptoclásicos seleccionamos Criptosistemas -> Clave Continua. Copiamos el criptograma en la caja de texto, ponemos como clave UNO DE LOS MAS GRANDES CRIPTOGRAFOS y damos a descifrar, obteniendo:


Es decir, editando en minúsculas y añadiendo signos de puntuación, el texto en claro era:
Durante la Primera Guerra Mundial, William Frederick Friedman sirvió como teniente en la unidad de criptología de la Fuerza Expedicionaria Estadounidense, distinguiéndose por sus trabajos y proezas en el análisis de códigos enemigos inviolables, por lo cual recibió el reconocimiento del Gobierno estadounidense.


Figura 1.13. William F. Friedman, uno de los padres de la criptografía mundial.

Ejercicio 1.5:
En el descifrado del ejercicio anterior con autoclave, ¿qué parte del criptograma puede descifrarse usando solamente la clave inicial?

La cifra con autoclave complica, en principio, el trabajo del criptoanalista. No obstante, incluso en estas condiciones a priori muy poco favorables para el atacante, las características de redundancia del lenguaje permitirán realizar un criptoanálisis y poder descifrar gran parte del criptograma. No profundizaremos más en este tema; el lector interesado puede hacerlo por ejemplo leyendo el capítulo 2.4.3.4 del libro Cifrado de las comunicaciones digitales. De la cifra clásica al algoritmo RSA, publicado por 0xWord en mayo 2013, donde encontrará mayor información sobre este ataque propuesto por el destacado criptógrafo ruso-norteamericano William Friedman.

Vamos a pensar un poco:
Sin tener más información sobre la cifra autoclave que la que has visto en este apartado, y sin conocer aún el trabajo de William Friedman, ¿cómo crees que podría intentarse un criptoanálisis a este tipo de cifra? Pista: una tabla de digramas frecuentes podría ser de mucha ayuda...

En la píldora formativa Thoth 19 ¿Qué es la cifra de Vigenère? de la figura 1.14, tienes mayor información del cifrado y descifrado de Vigenère. Refuerza a través de ella todos los conceptos que has aprendido en este primer apartado de la lección.


Figura 1.14. Píldora formativa Thot 19: ¿Qué es la cifra de Vigenère?


APARTADO 2. SEGURIDAD EN LA CIFRA DE VIGENÈRE

2.1. ¿Una cifra indescifrable?

El cifrado de Vigenère y sus variantes resistieron casi 300 años al criptoanálisis y por ello se le llamó le chiffre indéchiffrable. Pero en 1854, el matemático inglés Charles Babbage rompe la cifra. En realidad, Babbage rompe la cifra de autoclave, aunque desgraciadamente no hace público su trabajo y sus avances. Años más tarde, en 1863, el militar alemán Friedrich Kasiski publica un método para el criptoanálisis del sistema de Vigenère, haciendo uso de la redundancia del lenguaje y la fortaleza de la cifra de Vigenère se rompe definitivamente.

Esto es así porque nuestro lenguaje es tan redundante -da igual que sea francés este caso, español, inglés, etc.-, que si un texto con una cantidad suficiente de caracteres, y que ya sabemos tiene unas estadísticas de frecuencias muy característica en sus letras, se va leyendo ahora a saltos constantes, por ejemplo de tres en tres letras y esas letras se van apuntando y generando un nuevo documento, resulta que en ese nuevo documento, ahora ya sin sentido, se sigue manifestando con bastante claridad la redundancia del lenguaje, de forma que las letras E, A y O tienden nuevamente a ser las más frecuentes.

En el párrafo anterior hemos puesto una condición: cantidad suficiente de caracteres. ¿Qué se entiende entonces por un texto o criptograma con suficientes caracteres? Para dar una respuesta adecuada a esta pregunta, es necesario saber antes la longitud de la clave usada para cifrar. Así, diremos que si la clave tiene una longitud de L de letras, entonces el texto en claro debería tener al menos 100 x L letras para esperar un éxito seguro en el ataque, pero todo esto lo veremos a continuación.


2.2. Algunos protagonistas del ataque a la cifra indescifrable

Corría el año 1854, es decir 268 años después de la invención de la cifra de Vigenère, cuando el matemático y criptógrafo inglés Charles Babbage logra romper esta cifra, aunque en realidad la cifra que rompe es el sistema llamado autoclave, que como hemos visto era un sistema mucho más seguro y complejo que la cifra de Vigenère. Por desgracia, Babbage no hace público sus avances en el criptoanálisis de sistemas polialfabéticos, ni tampoco los resultados a los que llega.


Figura 2.1. Charles Babbage.

Vamos a pensar un poco:
¿Qué error impropio de un investigador que se precie crees que cometió Charles Babbage?

Quien sí lo hace público pero en el año 1863, es el militar alemán Friedrich Kasiski, en el libro "Escritura Secreta y el Arte de Descifrar" (Die Geheimschriften und die Dechiffrierkunst). Kasiski muere 18 años después, en 1881, según dicen los historiadores sin ser del todo consciente del importante legado que había dejado a la criptografía.


Figura 2.2. Libro Die Geheimschriften und die Dechiffrierkunst de F. Kasiski.

También juega un destacado papel en este ataque a los sistemas de cifra polialfabéticos el criptoanalista ruso-norteamericano William Friedman, quien publica en 1922, esto es casi 60 años después del ataque de Kasiski, el famoso libro "El Índice de Coincidencia y sus Aplicaciones en el Criptoanálisis" (The Index of Coincidence and Its Applications in Cryptanalysis), un documento de alto secreto y que se mantiene clasificado como confidencial durante 50 años.

Vamos a pensar un poco:
¿Por qué crees que un libro como el de Friedman se cataloga como información clasificada y se mantiene en secreto durante 50 años?


2.3. Principios del método Kasiski

Debido a la redundancia del lenguaje, si un texto en claro se lee "a saltos entre sus letras", es decir, se observa y anota la letra que aparece cada x espacios en un documento, al contabilizar en ese nuevo documento dichas letras, se observará un comportamiento estadístico bastante similar al del texto en claro original.

En otras palabras, si la letra E era la más frecuente en el texto en claro, entonces en ese nuevo texto que se ha creado leyendo del primer texto las letras separadas por un espacio o longitud L constante, con mucha probabilidad la letra E seguirá siendo también aquí la más frecuente.

Lógicamente, para que ello se manifieste de forma adecuada y por lo tanto nos entregue información válida que permita iniciar el ataque, se deberá contar con una cantidad suficiente de texto cifrado. La pregunta ahora es obvia, ¿cuánto texto es necesario para que funcione el método de ataque de Kasiski? Aunque parezca increíble, en un cuerpo de cifra de 27 letras, las mayúsculas del alfabeto español, solamente con 100 o más letras, es decir poco más de 3 veces el tamaño del alfabeto, ya se manifiesta claramente la redundancia del lenguaje.

Vamos a pensar un poco:
¿Por qué decimos que es asombroso que con un texto de longitud sólo 3 veces el tamaño del alfabeto seamos capaces de extraer datos estadísticos fiables y representativos?

Por lo tanto, y valga como un ejemplo, si una cifra de Vigenère usa una clave de cinco letras, por ejemplo BARCO, y el mensaje tiene quinientas o más letras, tendremos muy buenas expectativas de que el ataque por el método de Kasiski prospere. Y para un cuerpo de sólo veintisiete letras diferentes esta cantidad de texto es muy poca, pero funciona.

Teniendo esto en mente y siguiendo con el mismo ejemplo de la clave BARCO de 5 letras, que sabemos se irá escribiendo debajo del texto en claro para sumar los códigos de las letras uno a uno, y que se repite de manera periódica durante toda la cifra, resulta obvio que las letras en las posiciones 1, 6, 11, 16,... del texto en claro se cifrarán con la letra B de la clave BARCO. Lo mismo sucederá con las letras en posiciones 2, 7, 12, 17,... que lo harán con la letra A de la clave. Otro tanto ocurrirá con la tercera letra R de la clave y el texto en claro de las posiciones 3, 8, 13, 18,… después con la cuarta letra C de la clave y ahora las posiciones 4, 9, 14, 19,… y, por último, con la quinta letra O de la clave con la que se cifrarán las letras en posiciones 5, 10, 15, 20, etc.

Por lo tanto, lo primero que debemos buscar en un criptograma que sabemos es producto de una cifra de Vigenère será el tamaño o longitud L de la clave. Si tenemos este valor L, aunque no sepamos aún las letras que conforman esa clave, podemos decir que con cada una de esas L letras se habrá cifrado la parte correspondiente del texto en claro de un modo monoalfabético y por lo tanto con un desplazamiento constante. En ejemplo anterior con la clave BARCO de 5 letras, se han producido 5 cifrados monoalfabéticos que se indican:

• Un cifrado con la letra B y un desplazamiento b = 1
• Un cifrado con la letra A y un desplazamiento b = 0
• Un cifrado con la letra R y un desplazamiento b = 18
• Un cifrado con la letra C y un desplazamiento b = 2
• Un cifrado con la letra O y un desplazamiento b = 15

Ya sabemos que si en cada uno de esos cinco criptogramas contamos con 100 o más letras, se va a manifestar la redundancia del lenguaje. Pero la pregunta ahora es, ¿cómo puedo saber el período o longitud L de la clave a partir sólo del criptograma?

No hay de qué preocuparse, esto también será muy fácil. Y para ello lo mejor es poner un ejemplo sencillo.

El mensaje LETRAS REPETIDAS, AYUDA RECIBIDA vamos a cifrarlo con la clave MICLAVE mod 27. Con el método tradicional de cifra escribiendo la clave debajo del texto en claro, se obtiene la tabla de la figura 2.3.


Figura 2.3. Cadena IYE repetida en el criptograma.

Como se observa en la figura 2.3, el trigrama IDA (bastante común por cierto en el lenguaje español, e.g. consentida, vida, fallida, bebida, Midas, ...) se cifrará con la misma parte de la clave, en este caso AVE. Obviamente el criptograma en ambos casos será el mismo: IDA + AVE mod 27 = IYE.

¿Qué significa esto? Algo muy interesante. Que al igual que sucede con otros trigramas muy comunes como ADO, IDO, etc., o cuatrigramas como ANDO, CION, etc., o pentagramas como MENTE, IENDO, etc., se repetirán en un texto en claro lo suficientemente extenso y cabe la posibilidad de que ese conjunto de n-gramas frecuentes se cifre más de una vez con la misma parte de la clave, como ha sucedido en el ejemplo anterior con el trigrama IDA del texto en claro y la parte AVE de la clave.

Por lo tanto, resulta obvio que el número de letras que hay entre esas dos repeticiones de texto en el criptograma (en el ejemplo IYE), es decir la separación entre las repeticiones, debe ser un múltiplo de la longitud L de la clave. En este ejemplo, la cadena IYE se repite después de avanzar 14 espacios, justo el doble de las 7 letras de la clave MICLAVE.

Ejercicio 2.1:
Comprueba que en el siguiente texto existen -entre otras muchas- estas cadenas repetidas de 5, 4 y 3 letras, y con esas distancias que las separan:
Texto en claro:
Shannon es reconocido por haber fundado el campo de la teoría de la información. Mientras realizaba su maestría en el Massachusetts Institute of Technology, demostró con su tesis que las aplicaciones electrónicas de álgebra booleana podrían construir cualquier relación lógico-numérica. Contribuyó asimismo al campo del criptoanálisis para la defensa de Estados Unidos durante la Segunda Guerra Mundial, con trabajos sobre el descifrado de códigos y la seguridad en las telecomunicaciones.
Cadenas repetidas:
    ACION - aparece 4 veces, separadas 99, 164 y 183 espacios
    ONES - aparece 3 veces, separadas 158 y 247 espacios
    DELA - aparece 2 veces, separadas 10 espacios
    NICA - aparece 2 veces, separadas 230 espacios
    IDO - aparece 2 veces, separadas 293 espacios
    CON - aparece 6 veces, separadas... encuentra tú esas distancias.

Más adelante, cuando ya conozcamos cómo se realiza el ataque de Kasiski a la cifra de Vigenère, recuperaremos este mismo texto en claro realizando dicho ataque al criptograma resultante.

Luego, lo que hay que hacer ante un criptograma que se ha cifrado polialfabéticamente con una clave periódica como es el caso de Vigenère, es buscar repeticiones de tres, cuatro, cinco o más caracteres en el criptograma y anotar los espacios que separan entre sí a dichas repeticiones, lógicamente cadenas de texto iguales. Encontradas esas repeticiones y apuntadas esas distancias, se calcula el máximo común denominador entre ellas y si todo ha ido bien ese valor será candidata a ser la longitud L de la clave buscada.

Es decir, si las distancias entre las cadenas repetidas observadas han sido d1, d2, d3,… dn, el período L de la clave puede ser:

L = mcd (d1, d2, d3,… dn)

Ejercicio 2.2:
En un criptograma se encuentran estas cadenas repetidas y con estas distancias:
GGMP separadas por 256 y 104 espacios
YEDS separadas por 72 espacios
HASE separadas por 156 espacios
VSUE separadas por 32 espacios.
¿De qué tamaño puede ser la longitud L de la clave?
Puedes usar este software online: Greatest Common Factor Calculator.
Si ahora las cadenas repetidas fuesen éstas, ¿cuál podría ser la longitud L de la clave?
NIXVGW separadas por 60 espacios
KKFT separadas por 165 espacios
QUJK separadas por 405 espacios
JCEE separadas por 230 espacios

No es recomendable buscar repeticiones de dos caracteres en el criptograma (incluso a veces de tres caracteres) porque es posible que éstas se origen por pura casualidad y, en ese caso, pueden echar por tierra la búsqueda de esa longitud L de la clave.

Vamos a pensar un poco:
No hacemos caso de esta última recomendación. Recorremos el criptograma y encontramos 7 repeticiones, dos cadenas PKCW separadas por 124 espacios, tres cadenas HDÑ separadas por 32 y 56 espacios, y dos cadenas YQ separadas por 25 espacios. ¿Qué consecuencias nos puede traer esto?

Con estas premisas, vamos a realizar un ataque de Kasiski. Supongamos que tenemos un texto cifrado con Vigenère con 279 caracteres como el que se muestra a continuación.

C = VOPVC FRTCU MBGHG KGSCT YKTNJ MPKIB VGYQE YSSRK YYEEJ GWGVQ RGPST LNDIF VIOMM TGGYU SLGZN CZCJE YGGSJ VGJIJ DSLRV ARWCY ECOTP VWYUS CEIQL SQLIP DMLGW RJEQJ IAZFG JIJRO RRILV OFGWÑ ZXYCY QHWYE NNKIB VPYUV GUHNE HCVWR RFYZQ EJIQR HNLVY KWSWV GJYLR GAZHC EXCUY PRQRV YLNMY AIBVG YTIPZ ECEFN LWSRQ YIYCC IÑJST GGNMQ YWVYT XSJEC EOYTE BVVY

Vamos a comprobar ahora que para este cifrado de Vigenère en el que se ha elegido una clave de 3 letras, esas 279 letras que tenemos en el criptograma serán más que suficientes para romper la cifra polialfabética.

Buscando cadenas repetidas en el criptograma de 3 o más caracteres, obtenemos:

VOPVC FRTCU MBGHG KGSCT YKTNJ MPKIB VGYQE YSSRK YYEEJ GWGVQ RGPST LNDIF VIOMM TGGYU SLGZN CZCJE YGGSJ VGJIJ DSLRV ARWCY ECOTP VWYUS CEIQL SQLIP DMLGW RJEQJ IAZFG JIJRO RRILV OFGWÑ ZXYCY QHWYE NNKIB VPYUV GUHNE HCVWR RFYZQ EJIQR HNLVY KWSWV GJYLR GAZHC EXCUY PRQRV YLNMY AIBVG YTIPZ ECEFN LWSRQ YIYCC IÑJST GGNMQ YWVYT XSJEC EOYTE BVVY

Observamos dos cadenas de 4 letras repetidas una vez, KIBV y GJIJ. Además, hay otras cuatro cadenas de 3 letras repetidas también una vez, TGG, YUS, VGJ y ECE. Las distancias que separan esas cadenas son:

KIBV = 135; GJIJ = 48; TGG = 189; YUS = 39; VGJ = 114; ECE = 33

Por lo tanto, como mcd (135, 48, 189, 39, 114, 33) = 3, la clave buscada puede tener una longitud L = 3.

Como sospechamos que la clave tiene tres letras, crearemos ahora tres subcriptogramas cada uno de 93 letras (279/3), el primero con las letras en posiciones 1, 4, 7, 10, 13, ... 295 del criptograma, que son resultado de la cifra con la primera letra de la clave, el segundo con las letras 2, 5, 8, 11, 14, ... 296 del criptograma, que son el resultado de la cifra con la segunda letra de la clave y, finalmente, las letras 3, 6, 9, 12, 15, ... 297 del criptograma y que son el resultado de la cifra con la tercera y última letra de la clave. Obtenemos entonces:

C1: VVRUG KCKJK VQSKE GVGTD VMGUG CJGJJ DRRYO VUELL DGJJZ JRRVG ZCHEK VUUEV RZJRL KWJRZ EURVN AVTZE LRICJ GMWTJ ETV

C2: OCTMH GTTMI GESYE WQPLI IMGSZ ZEGVI SVWET WSISI MWEIF IOIOW XYWNI PVHHW FQIHV WVYGH XYQYM IGIEF WQYIS GQVXE OEV

C3: PFCBG SYNPB YYRYJ GRSNF OTYLN CYSGJ LACCP YCQQP LRQAG JRLFÑ YQYNB YGNCR YEQNY SGLAC CPRLY BYPCN SYCÑT NYYSC YBY

Ya hemos pasado la cifra polialfabética de Vigenère con una clave de supuestamente 3 letras, a tres cifras monoalfabéticas, cada una de ellas con una clave o desplazamiento de momento desconocido. ¿Cómo podemos ahora encontrar esas tres letras de la clave? Lo veremos a continuación.


2.4. La regla AEO

Conocida la longitud L de la clave, el procedimiento que se sigue ahora es el siguiente.

Como cada una de estos tres criptogramas ha sido cifrado con una sola letra, se trata de un cifrado monoalfabético. Para encontrar las tres letras de esta clave, primero encontraremos las frecuencias de aparición de letras en cada uno de los subcriptogramas C1, C2 y C3.

Hecho esto, al ser cada subcriptograma una cifra monoalfabética, vamos a buscar las posiciones relativas que ocupan ya cifradas las letras más frecuentes del lenguaje español, esto es la letra A, la letra E y la letra O. Estas posiciones deberán ser las que presenten una mayor frecuencia en ese subcriptograma y, además, muy importante, que cumplan con la misma estructura de nuestro alfabeto. Esto último quiere decir que desde la letra A (código 0) hasta la letra E (código 4) hay 4 espacios y desde la letra E (código 4) hasta la letra O (código 5) hay 11 espacios. Se podría utilizar también la S (código 19), cuarta letra más frecuente del español, pero no aporta demasiado en este ataque, si bien el programa Criptoclásicos v2.1 sí la toma en cuenta. Recuerda que la frecuencia de letras puede presentar ciertas variaciones en función del texto analizado, como por ejemplo que la A sea más frecuente que la E, la O más frecuente que la A, etc.

El método anterior para encontrar las letras de la clave se conoce como regla AEO. Como la letra A tiene como código el número 0, en dicha posición relativa estará la letra de la clave, en tanto clave + A = clave + 0 = clave.

Las frecuencias de aparición de las letras en los tres subcriptogramas C1, C2 y C3 son las indicadas en la figura 2.4, en donde se han marcado las posiciones relativas de la letra A en amarillo, la letra E en verde y la letra O en celeste. Observa que salvo pequeñas variaciones, estas tres letras son las más frecuentes en cada subcriptograma. Ten en cuenta que en este ejemplo estamos sacando conclusiones estadísticas en un cuerpo con 27 elementos posibles, nuestro alfabeto, contando con tan sólo 93 letras.


Figura 2.4. Tabla de frecuencias de subcriptogramas C1, C2 y C3 con indicación de la regla AEO.

Leyendo las celdas en amarillo, la clave del criptograma puede ser REY.

Con esta clave REY desciframos el criptograma y obtenemos el siguiente texto, ya ajustado y con caracteres extras como espacios en blanco y de puntuación, de la prensa española:

"El rey ha pedido disculpas por irse de caza a Botsuana: "Lo siento mucho. Me he equivocado. No volverá a ocurrir". El monarca se ha expresado en estos términos tras recibir el alta en el hospital USP San José de Madrid, donde estaba ingresado tras sufrir un accidente durante un viaje de cacería en Botsuana, que le provocó una fractura en la cadera."
Fuente: Diario Público.es 18/04/2012.

Nos vemos en el laboratorio...
Enunciado:
Criptoanaliza mediante el método Kasiski el siguiente criptograma que se ha obtenido con una cifra de Vigenère.
C = UOFEN QUJKR GKTEO EPIGP QZMRB GZKMN FIIGE NKFDP QLJCA VMTJI CLJCA KUKGR ÑIHZO OTNVN VZFKR GIPZZ CJFKU ÑIJKT TPFVN GSQRS UIHYU UMYLS KUXLI VCYVO HBJTH OWPGG ALJDO UBWGC QUXMT GANKQ WMPRS CXPZC CKNGN GAJCE EBWGN KKFKD GIPXE DZFSO QSJRN CXTUR KIRTO OAYJU KZHMA NYZZE TZJCA EPTEL QÑNTO OCQVR KKFTO OBWZB WGTRS KTNKM QIPTA ÑXTU ENKWZ PVWFE ANPXZ SRIWR LCLJW EOAFU EGAYR DQAZE IFWXU UTIRL ENIXV GWUIR GWMWJ AÑCRU ICSHG NVZFS ALWXK ODZJV LFMXT IHZFU OFMHG DKÑTK YNIXV GWZNU AFMRC AUBJC EEWQM NKKFT IQUJK
Solución:
En Criptoclásicos seleccionamos Criptosistemas -> Vigenère. Copiamos el criptograma en la caja de texto y damos a criptoanalizar. Elegimos Tamaño de repetición 4 porque con valores menores el programa nos indica que no es posible encontrar la clave al obtener una longitud igual a la unidad.
Las cadenas repetidas son NIXVGW, JCEE, KKLT, LJCA, NKKF, NVZF y QUJK y la clave es CIFRA.
Criptoclásicos v2.1 usa la regla AEOS y marca con color rojo la posición relativa de la letra A, con color verde la posición relativa de la letra E, con color celeste la posición relativa de la letra O y con color amarillo la posición relativa de la letra S.


Damos a descifrar en esa misma ventana y obtenemos el texto en claro:


El texto en claro, con minúsculas y puntuación, es el mismo presentado en el ejercicio 2.1.
Shannon es reconocido por haber fundado el campo de la teoría de la información. Mientras realizaba su maestría en el Massachusetts Institute of Technology, demostró con su tesis que las aplicaciones electrónicas de álgebra booleana podrían construir cualquier relación lógico-numérica. Contribuyó asimismo al campo del criptoanálisis para la defensa de Estados Unidos durante la Segunda Guerra Mundial, con trabajos sobre el descifrado de códigos y la seguridad en las telecomunicaciones.

Resumen de los pasos a seguir en el ataque de Kasiski:

1. Buscar en el criptograma repeticiones de al menos 3 letras y anotar la distancia que separa a todas esas repeticiones.

2. Encontrar el máximo común divisor (mcd) de todas esas separaciones. Ese valor nos indicará la posible longitud L de la clave.

3. Conocido L, se procede a dividir el criptograma en L subcriptogramas tomando las letras del criptograma principal de L en L espacios.

4. Para cada uno de los L subcriptogramas, se apunta la frecuencia de aparición de cada una de las letras.

5. Si se usa la letra AEOS, se busca en cada uno de los L subcriptograma las cuatro frecuencias más altas y que, además, cumplan con la distancia que separa a las letras con más frecuencia del alfabeto español mod 27, es decir la A, la E, la O y la S. Esto es, que el espacio entre estas letras más frecuentes de cada subcriptograma cumpla con la siguiente distribución: Letra 1 -> + 4 espacios = Letra 2 -> + 11 espacios = Letra 3 -> + 4 espacios = Letra 4, en donde Letra 1, Letra 2, Letra 3 y Letra 4 serán las posiciones relativas de las letras AEOS del texto en claro.

6. Ubicada la posición de la Letra 1, que es la relativa a la letra A del texto en claro, se mira con qué letra se ha cifrado, dando así la letra correspondiente de la clave en esa posición.

7. Se repite este proceso con todos los subcriptogramas para obtener la clave buscada.

8. Si se cuenta con poco texto cifrado, es posible que no sea fácil encontrar esas posiciones relativas de la AEOS al no existir letras en los subcriptogramas que se destaquen por su alta frecuencia.

Repasa todos estos temas de criptoanálisis visualizando la píldora formativa Thoth 20 ¿Cómo se ataca por Kasiski la cifra de Vigenère? de la figura 2.5.


Figura 2.5. Píldora formativa Thot 19: ¿Qué es la cifra de Vigenère?


APARTADO 3. EJERCICIOS FINALES

3.1. Ejercicios de cifrado, descifrado y criptoanálisis de Vigenère

Para terminar esta lección, resuelve estos cuatro ejercicios con el programa Criptoclásicos v2.1.

Ejercicio 2.3:
a) Cifra con la clave DAN BROWN mod 27 el siguiente texto en claro:
Robert Langdon tardó en despertarse. En la oscuridad sonaba un teléfono, un sonido débil que no le resultaba familiar. A tientas buscó la lámpara de la mesilla de noche y la encendió.
b) Descifra el criptograma.
c) Intenta criptoanalizar el criptograma. ¿Se puede? ¿Por qué sí o por qué no?

Ejercicio 2.4:
a) Cifra mod 27 el siguiente texto en claro si la clave es MAR:
Con diez cañones por banda,
viento en popa, a toda vela,
no corta el mar, sino vuela
un velero bergantín.
Bajel pirata que llaman,
por su bravura, el Temido,
en todo mar conocido
del uno al otro confín.
La luna en el mar riela,
en la lona gime el viento,
y alza en blando movimiento
olas de plata y azul;
y ve el capitán pirata,
cantando alegre en la popa,
Asia a un lado, al otro Europa,
y allá a su frente Estambul.

b) Descifra el criptograma.
c) Criptoanaliza el criptograma y comprueba que la clave era MAR

Ejercicio 2.5:
a) Se pide criptoanalizar el siguiente criptograma mod 27, encontrar la clave y el texto en claro.
MAXYH GAVAP UUGZH EGZQO WOBNI PQKRN ÑMEXI GONII CUCAW IGCTE AGMNO LRSZJ NLWÑA WWIGL DDZSN IZDNB IXGZL AYMXÑ CVEKI ETMOE OPBEW PTNIX CXUIH MECXL NOCEC YXEQP BWUFA NIICÑ JIKIS CZUAI LBGSO ANKBF WUAYW NSCHL CWYDZ HDZAQ VMPTV GFGPV AJWFV PUOYM XCWER VLQCZ WECIF VITUZ SNCZU AIKBF MÑALI EGLBS ZLQUX ÑOHWO CGHNY WÑQKD ANZUD IFOIM XNPHN UWQOK LMVBN NKRMK ONDPD PNMIK AWOXM EEIVE KGBGS FHVAD WPGOY MHOIU EEIPG OLENZ BSCHA GKQTZ DRÑMÑ NWTUZ IÑCMÑ AXKQU WDLVA NNIHL ÑCQNW GEHIP GZDTZ TÑNWÑ EEWFU MGIÑX NTWXN VIXCZ OAZSO QUVEN DNFWU SZYHG LRACP GGUGI YWHOT RMZUG QQDDZ IZFWH VVSHC UGOGI FKBXA XPBOB RDVDU CMVTK GIKDR SZLUQ SDVPM XVIVE YMFGT EANIM QLHLG PQOHR YWCFE WFOIS NÑPUA YINNÑ XNÑPG KWGOI LQGAF OILQT AHEII DWMÑE ÑXNEP RCVDQ TURSK
b) Comprueba que las estadísticas del lenguaje en cuanto a las cuatro letras más frecuentes (A, E, O, S) se manifiestan claramente en cada subcripotgrama.
c) ¿Cuántas letras tiene cada uno de los subcriptogramas? Compara este valor con el tamaño del alfabeto de 27 letras y saca conclusiones.

Ejercicio 2.6:
a) Trabajando en módulo 191 (un subconjunto imprimible del código ASCII solamente definido en el software Criptoclásicos), cifra el siguiente texto en claro con la clave: El ingenioso hidalgo.
En un lugar de la Mancha, de cuyo nombre no quiero acordarme, no ha mucho tiempo que vivía un hidalgo de los de lanza en astillero, adarga antigua, rocín flaco y galgo corredor. Una olla de algo más vaca que carnero, salpicón las más noches, duelos y quebrantos los sábados, lentejas los viernes, algún palomino de añadidura los domingos, consumían las tres partes de su hacienda. El resto della concluían sayo de velarte, calzas de velludo para las fiestas con sus pantuflos de lo mismo, los días de entre semana se honraba con su vellori de lo más fino. Tenía en su casa una ama que pasaba de los cuarenta, y una sobrina que no llegaba a los veinte, y un mozo de campo y plaza, que así ensillaba el rocín como tomaba la podadera.
b) Descifra este criptograma.
c) ¿Por qué crees que el software no permite hacer aquí un criptoanálisis?


APARTADO 4. EVALUACIÓN DE LA LECCIÓN 9

4.1. Test de evaluación personal

En las siguientes 10 preguntas, elige la respuesta correcta. Sería muy recomendable que la primera vez que contestes este test lo hagas sin repasar la lección.

Para confirmar si tus respuestas son las correctas, accede y consulta las redes sociales de Crypt4you en twitter y en Facebook. Las soluciones al test de esta novena lección se publicarán en dichas redes sociales el mismo día en que se publique la próxima y útima lección 10. Recuerda que en twitter se publican sólo las respuestas correctas y en Facebook, además de ello, se justifica la respuesta correcta y se indica por qué son incorrectas las demás.

1. En una tabla de Vigenère de n x n letras, el desplazamiento en la última fila será igual a:

a) n
b) n + 1
c) n - 1
d) 2n

2. Si ciframos módulo 27 el texto HOLA con la clave ABBA, el criptograma será:

a) HMPA
b) HPMA
c) HPAA
d) APMH

3. Si la clave es BCDE, la letra O se podría cifrar como:

a) O, P, Q, R
b) M, N, Ñ, O
c) P, R, Q, S
d) P, Q, R, S

4. Si el cifrado de Vigenère es IZLQOD y la clave SOL, ¿cuál era el mensaje en claro?

a) PLANTA
b) PLAYAS
c) PALETA
d) PALOMA

5. ¿Cuál será la cifra con autoclave del texto HABIA UNA VEZ, con la clave CIRCO?

a) JISKO BNBDE T
b) JISKO BABAE T
c) JISKO JISKO J
d) JISKO BNBDD T

6. En el ataque a Vigenère por Kasiski buscamos preferentemente repeticiones:

a) De los caracteres más frecuentes en el texto cifrado
b) De trigramas en el texto en claro
c) De digramas y trigramas en el texto cifrado
d) De trigramas, cuatrigramas y pentagramas en el texto cifrado

7. Encontradas las cadenas repetidas en el criptograma, con separación d1, d2, d3 y d4:

a) La longitud L de la clave puede ser el mcm (d1, d2, d3, d4)
b) La longitud L de la clave puede ser la media de los valores d1, d2, d3, d4
c) La longitud L de la clave puede ser el mcd (d1, d2, d3, d4)
d) La longitud L de la clave puede ser la desviación estándar entre d1, d2, d3 y d4

8. Si las distancias entre repeticiones de cadenas en el criptograma son 35, 112, 70:

a) La longitud de la clave puede ser 5
b) La longitud de la clave puede ser 7
c) La longitud de la clave puede ser 15
d) La longitud de la clave puede ser 35

9. La regla EAO busca en los subcriptogramas:

a) Las letras menos frecuentes y que tengan la posición relativa de la A, la E y la O
b) Las letras más frecuentes y que tengan la posición relativa de la A, la E y la O
c) Las letras más frecuentes en ese subcriptograma
d) Las letras E, A y O en ese subcriptograma

10. En un ataque de Kasiski, la posición relativa de la E en los 4 subcriptogramas es K, E, X, S:

a) La clave puede ser KEXS
b) La clave puede ser PATO
c) La clave puede ser GATA
d) La clave puede ser GATO


Ir a: [Portada c4y]    [Lección 8] [Índice]