Criptografía (II)

Hoy veremos los comienzos de la parte oscura...el criptoanálisis.

Los primeros indicios de criptoanálisis aparecen en la cultura islámica a finales del siglo IX d.c. 

Abú Yusuf Yaqub ibn Ishaq ibn as Sabbah ibn 'omran ibn Ismail al Kindi, para los amigos Al Kindi, fue un filósofo árabe autor de casi 300 libros de diferente temática, entre ellos estaba (descubierto en 1987) uno titulado "Sobre el desciframiento de mensajes criptográficos", y aquí nos describe la forma de desencriptar un mensaje codificado mediante la sustitución monoalfabética.

Lo que nos viene a decir en pocas palabras que en Europa eramos unos atrasados de tres pares, pues aquí no nos enteramos de anda hasta el siglo XVI.

Durante años la cultura islámica fue una poderosa fuente de erudición, y el estudio teológico fue el culpable del nacimiento del criptoanálisis. Los teólogos se interesaron por establecer la cronología de las revelaciones de Mahoma de manos del arcángel Gabriel. Estas revelaciones son las que forman los 114 capítulos del Corán. Pues bien, la forma para poder datar estar revelaciones anotadas por diferentes personas a lo largo de la vida del profeta se basaba en estudiar la etimología de las palabras y la estructura de las frases. Algunas palabras habían evolucionado relativamente hacía poco, por eso si en alguna revelación había muchas de estas nueva palabras, ésta sería más actual que otra.

Pero puestos a investigar, no se quedaron ahí, sino que analizaron las letras individuales  concluyendo que algunas letras se repiten más que otras en un escrito. 

(Si, claro ahora todo el mundo lo sabe, es algo obvio, pero haberlo descubierto tú.)

Bien, pues de este simple dato a poder descifrar un codigo monoalfabético hay un paso muy simple.

Vamos a verlo en un ejemplo práctico. Imaginemos que interceptamos un mensaje del enemigo con la inscripción de más abajo. Como estamos en España en el siglo XIII o XIV pues imaginamos que lo más lógico es que esté cifrado con una cifra monoalfabética, pues todo el mundo sabe que es indescifrable. Pero nosotros que vamos mucho a la biblioteca leimos hace poco el tratado de un tío con un nombre muy largo que explicaba como romper esta cifra fácilmente. Así que nos ponemos manos a la obra.

LD ULDLICA AFJ CDXBCALJ JFAF GMLVLD CAXBLDKCIJL VL CHMLAAF HML ALJ VXRKC JM DCKMICALSC MDC UXICTC DF GFVIXC JFEILNXNXI C ECJL VL RCIDL DX MD CUMXAC VL WFYCJ. BMRWCJ LJGLRXLJ LJKCD LJGLRXCAXSCVCJ LD JMJ DLRLJXVCVLJ VXLKLKXRCJ.

Para poder descifrar el texto se tiene que tener alguna base sobre el idioma en el que está escrito el texto llano. Supongamos que esta escrito en Castellano, que es el que mejor conocemos. 

Sabemos, porque hemos hecho muchos cálculos antes, que las letras que más aparecen de promedio en un texto son las siguientes, de más a menos: e, a, o, s, n, r, i, l, d, u, t, c, ...

Si analizamos el texto sacamos algunas frecuencias para ciertas letras, la L aparece 30veces, la C 27, la J 20, la X 15, la D 14, la A 11, la M 10, la F 8, la I 8, la V 8, la K 6, ...

Supongamos que  la L corresponde a la letra llana "e" y la C a la "a"

Cambiemos estas dos letras para ver que ocurre.

eD UeDeIaA AFJ aDXBaAeJ JFAF GMeVeD aAXBeDKaIJe Ve aHMeAAF HMe AeJ VXRKa JM DaKMIaAeSa MDa UXIaTa DF GFVIXa JFEIeNXNXI a EaJe Ve RaIDe DX MD aUMXAa Ve WFYaJ. BMRWaJ eJGeRXeJ eJKaD eJGeRXaAXSaVaJ eD JMJ DeReJXVaVeJ VXeKeKXRaJ.

Volvamos a las frecuencias, la tercera letra que más aparece es la J, que podría corresponder con la "o", pero vemos que hay muchas palabras que acaban con J, y no es muy normal en castellano palabras acabadas en "o", así que la siguiente en el orden de frecuencia es la "s" y ésta sí que aparece mucho en finales de palabra, para formar plurales. Sustituimos.

eD UeDeIaA AFs aDXBaAes sFAF GMeVeD aAXBeDKaIse Ve aHMeAAF HMe Aes VXRKa sM DaKMIaAeSa MDa UXIaTa DF GFVIXa sFEIeNXNXI a Ease Ve RaIDe DX MD aUMXAa Ve WFYas. BMRWas esGeRXes esKaD esGeRXaAXSaVas eD sMs DeResXVaVes VXeKeKXRas.

La penúltima palabra sMs, como estamos en la edad media no puede ser sms así que la única posibilidad es que sea "sus". Probamos a cambiar las M por "u".

eD UeDeIaA AFs aDXBaAes sFAF GueVeD aAXBeDKaIse Ve aHueAAF Hue Aes VXRKa su DaKuIaAeSa uDa UXIaTa DF GFVIXa sFEIeNXNXI a Ease Ve RaIDe DX uD aUuXAa Ve WFYas. BuRWas esGeRXes esKaD esGeRXaAXSaVas eD sus DeResXVaVes VXeKeKXRas.

Podemos conjuntar la antepenúltima palabra y la última para formar "en sus" pues parece que sea probable, debido a que la letra "n" está en el quinto puesto de frecuencias, y como ya tenemos la "e", la "a", la "s" y la "o" no puede ser porque no queda demasiado bien "eo" vamos a probar con la "n" a ver si vemos algo raro en alguna otra palabra.

en UeneIaA AFs anXBaAes sFAF GueVen aAXBenKaIse Ve aHueAAF Hue Aes dXRKa su naKuIaAeSa una UXIaTa nF GFdIXa sFbIeNXNXI a base de RaIne nX un aUuXAa de WFYas. BuRWas esGeRXes esKan esGeRXaAXSadas en sus neResXdades dXeKeKXRas.

Podemos seguir probando con conjuntos de palabras lógicos como: "a Ease Ve" que podría ser "a base de" con lo que cambiamos la E por la "b" y la V por la "d"

La penúltima palabra podría ser Necesidades, así que comprobamos cambiando la R por la "c" y la X por la "i"

en UeneIaA AFs aniBaAes sFAF Gueden aAiBenKaIse de aHueAAF Hue Aes dicKa su naKuIaAeSa una UiIaTa nF GFdIia sFbIeNiNiI a base de caIne ni un aUuiAa de WFYas. BucWas esGecies esKan esGeciaAiSadas en sus necesidades dieKeKicas.

De la última linea podemos sacar "esKan" por "estan" y "diekekicas" por "dieteticas", de la palabra de la segunda linea "nF" sacamos "no" pues no puede ser otra cosa lógica pues "ni" no puede ser pues la "i" codifica como X.

Cambiamos todas estas letras, la K por la "t" y la F por la "o"

en UeneIaA Aos aniBaAes soAo Gueden aAiBentaIse de aHueAAo Hue Aes dicta su natuIaAeSa una UiIaTa no GodIia sobIeNiNiI a base de caIne ni un aUuiAa de WoYas. BucWas esGecies estan esGeciaAiSadas en sus necesidades dieteticas.

de la palabra "Hue" podemos afirmar que la H es una "q" por lo que "aHueAAo" puede ser "aquello" con lo que la A puede ser la letra "l" pues tambien concuerda con "soAo" para "solo"

Seguimos sustituyendo:

en UeneIal los aniBales solo Gueden aliBentaIse de aquello que les dicta su natuIaleSa una UiIaTa no GodIia sobIeNiNiI a base de caIne ni un aUuila de WoYas. BucWas esGecies estan esGecialiSadas en sus necesidades dieteticas.

La frase "los aniBales solo Gueden aliBentaIse de aquello que les dicta su natuIaleSa" puede ser "los animales solo pueden alimentarse de aquello que les dicata su naturaleza" con lo que sacamos la B como "m" la G como "p" la I como "r" y la S como "z"

Al cambiar estas letras la palabra "BucWas" se convierte en "MucWas", que podría ser "Muchas" con lo que la W es una "h" y la palabra "WoYas" se convierte en "hoYas" que podremos facilmente por el contexto convertir en "hojas" y así completamos el mensaje que nos confirma que el enemigo esta como una cabra o que nos ha querido tener entretenidos una hora para poder atacarnos por la retaguardia.

Al final el texto queda así: "En general los animales solo pueden alimentarse de aquello que les dicta su naturaleza. Una girafa no podría sobrevivir a base de carne ni un águila de hojas. Muchas especies estan especializadas en sus necesidades dietéticas."

Esta claro que un texto corto mediante este método puede que no nos de tanto juego ni con las frecuencias ni con el contexto. Además se podrían haber unido las palabras para hacer más difícil la detección de palabras con sentido. También se podrían haber añadido simbolos neutros sin correspondencia o escribir con faltas de ortografía que no supondrian ningun problema para leer para el que tuviera la clave, pero que mantendría entretenido mucho más tiempo al criptoanalista. Pero al final era cuestión de más o menos horas o alguno días para terminar descifrando el mensaje, pues la debilidad se encontraba en el propio algoritmo, sin importar demasiado la clave utilizada.

Pues esto fue más o menos lo que le paso a María Estuardo de Escocia, que a finales del siglo XVI ya había alguien en europa que sabía como descifrar sus mensajes facilmente y que mala suerte que estuviera del lado de la reina Isabel de Inglaterra.

Así que a partir de ahora habría que buscar alguna cifra más resistente al criptoanálisis.

Empezó la lucha  entre criptógrafos y criptoanalistas.

Leer más...

Criptografía (I)

Lo prometido es deuda, y como dije que hablaría sobre criptografía cuántica, pues aquí tenéis la primera parte. Como es un tema muy interesante, al menos a mi me lo parece, empezaré desde el principio con un resumen de la historia de la criptografía, desde la Grecia y Roma antigua hasta nuestros días. Os aseguro que si es un tema que desconocéis os gustará. Empecemos pues.

Criptografía: palabra proveniente del griego Kripto (oculto) y graphos (escribir) y a grandes rasgos es la ciencia y arte de escribir un mensaje de manera segura para que sólo pueda ser leído por la persona a quien va dirigido.

Desde siempre (bueno desde que existe la escritura) se ha intentado buscar la manera de que nadie excepto el destinatario pudiera leer el mensaje enviado.
Y esto en algunos casos es más importante de lo que parece, como ejemplo tenemos a la reina María Estuardo de Escocia que todavía tendría la cabeza pegada al cuerpo si hubiera utilizado una cifra más segura para codificar sus mensajes de traición a la reina Isabel.
Pero retrocedamos unos siglos.

Los primeros datos sobre algún tipo de criptografía los podemos encontrar allá por el siglo V a.c. en las guerras entre Griegos y Persas. El ejército Persa pretendía atacar por sorpresa a los griegos, pero un griego exiliado que pululaba por Persia fue capaz de avisar a sus compatriotas con antelación grabando sobre una tablilla de madera una inscripción, posteriormente la cubrió con cera y simplemente la llevó consigo de viaje hasta Grecia. Si algún guarda veía la tablilla no se daría cuenta de nada. Así los griegos fueron avisados y pudieron estar preparados para la llegada de los Persas. Ganaron los griegos por si a alguien le interesa.

Otra referencia nos dice que se afeitaba la cabeza del mensajero, se escribía el mensaje y luego se dejaba crecer el pelo para que tapara el mensaje. Una vez en su destino sólo había que volver a rapar al pobre chaval para leerlo. En aquella época no se estresaban mucho y las cosas funcionaban mucho más despacio que ahora.

Este tipo de criptografía basada en la ocultación del mensaje se denomina esteganografía y a más de un lector/a de este blog le habrá llegado alguna vez alguna carta o mensaje mío esteganografiado, otra cosa es que lo haya descubierto (de momento no tengo indicios).
En china se usaba una pequeña tela de seda escrita, la cual se aplastaba hasta formar una pelotita pequeña, se recubría con cera y luego se tragaba. No voy a comentar la forma de recuperar la bolita.

También mezclando alumbre y vinagre se consigue una tinta con la cual se puede escribir en la cáscara de un huevo cocido, esta penetra en el huevo y el mensaje queda impreso en la clara del huevo. Sólo hay que pelarlo para leer el mensaje. El zumo de limón sobre un papel también produce un efecto invisible que puede luego leerse si se chamusca un poco el papel pasándolo por una llama.

El problema de la esteganografía es que si por alguna razón el mensaje es descubierto no existe ningún problema para ser leído. Y es aquí donde entra el cifrado, con el cual aunque el mensaje sea interceptado, se tendrán serias dificultades para leerlo.

La esteganografía y la codificación pueden ser usadas al mismo tiempo, como en la segunda guerra mundial, donde los alemanes reducían fotográficamente una página de un texto a un tamaño de menos de 1mm y luego ese punto formaba parte de un punto final de cualquier frase de un texto inocente. Si los aliados encontraban el punto, aun les quedaba descodificar el mensaje, pues estaba a su vez cifrado.

Así entramos ya en la criptografía pura y dura, la cual puede dividirse en dos ramas: transposición y sustitución.
En la trasposición las letras del mensaje cambian su posición y en la sustitución las letra cambian su valor.

La trasposición en mensaje cortos no es demasiado segura pues una palabra con las letras cambiadas de lugar es relativamente fácil de localizar, pero una frase de sólo 35 letras tiene 50.000.000.000.000.000.000.000.000.000.000 posibles combinaciones, todo el mundo probando una combinación por segundo día y noche tardarían miles de millones de años en probarlas todas Si aciertas a la primera vale, pero como tardes mucho se ha acabado la guerra y no te has enterado.
El problema es que si la mezcla es al azar para que el nivel de seguridad sea muy alto, el receptor del mensaje tampoco puede descifrarlo, hace falta un sistema sencillo acordado entre el emisor y el receptor. Por ejemplo una frase como "quien vigila a los vigilantes" podría ser codificada siguiendo el sistema de separar las letras impares de las pares y luego colocarlas unas detrás de otras. el mensaje quedaría tal que así: qiniialsiiatsuevglaovglne.
El receptor invierte el proceso y ya tiene listo el mensaje.

La alternativa a la trasposición es la sustitución y una de las primeras descripciones de esta técnica aparece en el Kamasutra, donde una de las artes que debían de estudiar las mujeres era el arte de la escritura secreta para poder ocultar los detalles de sus relaciones amorosas. Una de las técnicas era emparejar al azar cada letra del alfabeto con otra diferente y luego sustituir cada letra del mensaje por su pareja. Si emparejamos la a con la V, la r con la X, la t con la B, la u con la G, y la o con la J. Mi nombre (Arturo) pasaría a ser "VXBGXJ" y ya pueden trasponer las letras que no sacarán nada en claro.

César usaba esta técnica para enviar mensajes a sus tropas por todo el imperio usando una sustitución de tres posiciones, es decir la letra "a" era codificada como la letra que estaba 3 posiciones más adelante en el alfabeto. a-D, b-E, c-F... Esta tipo de cifra (cifra es la sustitución criptográfica en la que cada letra es reemplazada por otra letra o símbolo) es llamada la cifra del Cesar.

Si ciframos con una combinación cualquiera del alfabeto a nuestra elección se pueden generar un total de 400.000.000.000.000.000.000.000.000 combinaciones posibles.
(A partir de ahora el texto llano (original) estará escrito con letras minúsculas mientras que su equivalente texto cifrado estará en mayúsculas.)

La codificación, o sea el método de cifrado es conocido como el algoritmo y la forma exacta para descodificarlo es la clave. En el caso anterior el algoritmo sería la sustitución monoalfabética y la clave sería la sustitución por la letra colocada 3 posiciones delante en el alfabeto.
La clave es lo más importante en la criptografía, se puede conocer el algoritmo, pero sin la clave nos quedamos igual.

Para mantener la calve a salvo esta debe tener una amplia gama de claves potenciales. El cambio del Cesar solo tiene 25 posibles combinaciones, en cambio si el algoritmo puede ser cualquier emparejamiento de letras las posibilidades de claves diferentes aumentan hasta esos miles de millones que he dicho antes. La ventaja de esta cifra, que es fácil de poner en práctica y a su vez tiene un ato nivel de seguridad. El receptor y el emisor sólo necesitan un pequeño papel donde anotar las 25 combinaciones de letras, o memorizar simplemente.

Si utilizamos una palabra clave para comenzar el cifrado todavía se vuelve más fácil memorizar la secuencia. Elegimos la palabra clave Criptografia, eliminamos la letras repetidas: criptogaf y la utilizamos para codificar el alfabeto, siguiendo una vez hemos acabado con la palabra el orden del mismo.
Sólo hay que memorizar la palabra Criptografía

Esta combinación de simplicidad y fortaleza hizo que este sistema de sustitución monoalfabética fuera utilizado durante siglos, pero al final una combinación de lingüística, estadística y religión dio al traste con la seguridad de este tipo de cifrado.
Apareció el criptoanálisis.

¿Alguna pregunta? Leer más...