jueves, 30 de octubre de 2008

Criptografía (V)

Bueno, por donde íbamos? Por Babagge creo.
A algunos les sonará el nombre por ser el que desarrolló el precursor del ordenador moderno, pero hoy hablaremos de otro de sus logros, descifrar la cifra indescifrable, la cifra Vigenère.
Decir antes de seguir que podéis encontrar una descripción mucho más detallada de lo que os estoy contando en este blog en el libro de Simon Singh, Los códigos secretos, así como en una fantástica web: http://www.cripto.es .

Sigamos. Para romper una cifra hay que buscar la pequeña grieta en el muro, el fallo en la codificación, la repetición, el contexto probable, etc... algo que nos de una pista por donde atacar. Esto fue lo que buscó Babbage. Recordemos que para codificar con la cifra Vigenère utilizabamos una palabra clave que utilizábamos como base de la codificación, repitiéndola a lo largo del texto, por lo que puede que en algún momento una misma palabra puede ser codificada de la misma forma. Ej, si la palabra clave tiene 5 letras, y codificamos el texto: "la casa de él la compró Juan" las dos palabras "la" se codificarán de la misma forma, pues están separadas por 10 letras que es un múltiplo del número de letras de la clave. A partir de aquí y siguiendo unos simples pasos podemos descodificar el texto. Ahora lo explico un poco más.

Seguiré el ejemplo del libro antes indicado, pues me llevaría mas tiempo del necesario crear un nuevo texto. El ejemplo proviene de un texto en inglés pero el sistema para descodificar viene a ser el mismo, utilizando la lógica gramátical de cada idioma, como hemos visto en otro capítulo

Imaginemos que interceptamos el siguiente mensaje:

Lo primero que hay que hacer es buscar secuencias de letras que aparezcan más de una vez, lo qe quiere decir que ha sido cifrada usando la misma parte de la palabra clave. Pero puede ser que por casualidad otras letras diferentes usando otras partes de la clave hayan sido codificadas igual que otras, para eliminar en la medida de lo posible esta posibilidad buscaremos cadenas repetidas de al menos 4 letras. En la siguiente table podemos ver tales repeticiones y la separación que existe entre ellas. La secuencia EFIQ aparece en la primera linea del texto cifrado y luego en la quinta, 95 letras después.La manera más rápida para descodificar el texto sería tener la palabra clave, pues esta es usada para codificar y para descodificar. De momento la tabla anterior nos da una pista sobre la longitud de la clave. Si miramos los desplazamientos de las repeticiones, podemos obtener los factores de desplazamiento, es decir, los números por los que se pueden dividir los espaciamientos. Veamos, la secuencia WCXYM se repite tras 20 letras, por lo tanto sus factores son el 1, 2, 4, 5, 10 y 20. Esto nos da 6 posibilidades

1- La clave tiene 1 letras y se recicla 20 veces entre las codificaciones
2-La clave tiene 2 letras y se recicla 10 veces entre las codificaciones
3-La clave tiene 4 letras y se recicla 5 veces entre las codificaciones
4-La clave tiene 5 letras y se recicla 4 veces entre las codificaciones
5-La clave tiene 10 letras y se recicla 2 veces entre las codificaciones
6-La clave tiene 20 letras y se recicla 1 veces entre las codificaciones

Sería muy tonto por parte del codificador haber usado la primera opción pues nos encongtraríamos con una clave monoalfabética.Cada marca de la tabla nos indica una longitud potencial de la palabra clave.Observamos que ante todas las posibles longitudes, existe una que es más propensa a aparecer, el espaciamiento divisible por 5. Así que asumimos que la clave tiene 5 letras, y la llamamos:l1-l2-l3-l4-l5, o sea cada una de las letras que la componen.
La primera letra del texto se codifica con la letra l1, la segunda letra con l2, etc…hasta llegar a la sexta letra que volvería a ser codificada con l1.

Parémonos a pensar que es lo que tenemos, 5 cifras monoalfabéticas, cada una de las cuales esta cifrando una quinta parte del mensaje y lo mejor de todo es que sabemos como descifrar cifras monoalfabéticas.
Podemos utilizar el análisis de frecuencia para la cifra l1 con las letras 1ª, 6ª, 11ª, 16ª...
Obtenemos la frecuencia que vemos en el siguiente cuadro,









pero tenemos un problema, no sabemos cual es la letra por la que empezamos a codificar, por lo que el gráfico está desplazado x posiciones. Para solucionar esto, lo comparamos con un cuadro de frecuencias del idioma inglés. Buscamos el desplazamiento que mejor coincide con la frecuencia normal. Por ejemplo las tres columnas RST seguidas de de una depresión de 6 letras a su derecha y un pico. Lo más parecido que encontramos en nuestra l1 son las letras VWX, seguidas de una depresión de 6 letras y un pico. Podemos comparar los
dos gráficos, el l1 desplazado y el normal en el dibujo de abajo.

Esto nos dice que las letras codificadas según l1 se han desplazado 4 posiciones, o que l1 define un alfabeto que comienza por E, F, G, H… y que posiblemente la primera
letra de la clave sea la E.


Realizamos el mismo procedimiento con l2, l3, l4 y l5. Vemos a continuación el gráfico de L2, seguido del mismo desplazado 12 posiciones y comparado con la distribución normal. La segunda letra de la clave es la M.





























Al final obtenemos las 5 letras de la clave: EMILY. Invertimos la cifra Vigenère como vimos el otro día y voilà...tenemos el texto descifrado, un poema de un tal Alfred Tennyson.

Y volvemos a tener la pelota del lado de los criptógrafos...a ver que inventan ahora para proteger sus secretos.>

1 comentario:

Anónimo dijo...

Jajaja yo me estoy leyendo el libro de donde as sacado las imagenes. Además hago un trabajo de unas 100 pg sobre el tema de criptografia.

Podias haverlo hecho en castellano no?