CRIPTOANÁLISIS, MEDIANTE ALGORITMOS GENÉTICOS, DE TEXTOS CIFRADOS EN LA GUERRA CIVIL ESPAÑOLA CON LA TÉCNICA DE CINTA MÓVIL Proyecto de fin de carrera, Ingeniería Informática Superior Universidad Pontificia de Comillas – ICAI (Madrid – 2011)

Autor: José Miguel Soriano de la Cámara ÍNDICE

Página

Cap 1.- Introducción...................................................................................................... 3 1.1.- Origen del proyecto.......................................................................................... 3 1.2.- Objetivos del proyecto ..................................................................................... 4 1.3.- Herramientas empleadas................................................................................. 4 1.4.- Enfoque de resolución ..................................................................................... 5 Cap 2.- Criptografía y Criptoanálisis.......................................................................... 9 2.1.- Métodos de cifrado clásicos .......................................................................... 10 2.1.1.- Clasificación de los sistemas de cifrado............................................... 10 2.1.2.- Reglas de Kerckhoffs .............................................................................. 12 2.2.- Reseña histórica de los sistemas de cifra..................................................... 13 2.2.1.- La escítala lacedemonia.......................................................................... 13 2.2.2.- Método César........................................................................................... 13 2.2.3.- Cifra Monoalfabética. ............................................................................. 14 2.2.4.- Cifrado Vigenère ..................................................................................... 15 2.2.5.- Cifrado de Playfair.................................................................................. 17 2.2.6.- Cifrado Vernam....................................................................................... 18 2.2.7.- Cifrado Bazeries ...................................................................................... 19 2.3.- Máquinas de cifrar en el siglo XX................................................................. 21 2.3.1.- La máquina Enigma................................................................................ 21 2.3.2.- La máquina Hagelin ............................................................................... 23 2.4.- Cifrado por homófonos ................................................................................. 25 2.4.1.- Cifrado homofónico de orden n>1 ....................................................... 26 2.4.2.- Criptoanálisis de los cifrados por sustitución con homófonos ........ 27 2.4.3.- El método de cinta móvil o método español....................................... 27 2.4.4.- Ataque al método español: sus debilidades........................................ 31 Cap 3.- Método Español: criptoanálisis con algoritmo genético. ......................... 35 3.1.- Teoría general sobre Algoritmos Genéticos................................................ 37 3.2.- Preparación de los datos de entrada............................................................ 41 3.2.1.- Cálculo de frecuencias reales. ............................................................... 41 3.2.2.- Carga del texto cifrado ........................................................................... 44 3.2.3.- Generación de la tabla inversa. ............................................................. 45 3.2.4.- Procesado del diccionario ...................................................................... 47 3.3.- Diseño de la estructura de los cromosomas ............................................... 50

Cap 1.- Introducción.

2/119

3.4.- Inicialización del AG...................................................................................... 51 3.5.- Reproducción o cruce de los individuos ..................................................... 51 3.6.- Mutación de los cromosomas. ...................................................................... 51 3.7.- Evaluación: Función Objetivo (Fitness)....................................................... 52 3.8.- Definición final del texto descifrado............................................................ 54 Cap 4.- Casos de estudio y resultados ...................................................................... 55 Cap 5.- Conclusiones y futuros desarrollos ............................................................. 69 Anexo A: Tabla de frecuencias de uso aplicada...................................................... 72 Anexo B: Método Kasiski (ataque a un cifrado polialfabético)............................. 75 Anexo C: Códigos de Baudot..................................................................................... 78 Anexo D: Cifra con ENIGMA .................................................................................... 79 Anexo E: El Método Español según Carmona: año 1894....................................... 80 Anexo F: Claves y tablas de homófonos de la GC36; ejemplos. ........................... 82 Anexo G- Planificación y Presupuesto ..................................................................... 86 Anexo H.- Código fuente............................................................................................ 88 Índice de Figuras........................................................................................................ 117 Bibliografía.................................................................................................................. 118

José Miguel Soriano de la Cámara

Criptoanálisis, mediante algoritmos genéticos, de textos cifrados en la Guerra Civil Española con la técnica de cinta móvil

Cap 1.- Introducción.

3/119

Cap 1.- Introducción. 1.1.- Origen del proyecto El presente trabajo tiene su origen en el proyecto fin de carrera supervisado por los investigadores Don Francisco Alberto Campos Fernández y Don Jesús María Latorre Canteli del Instituto de Investigación Tecnológica de UP Comillas. Dicho proyecto es la continuación natural del desarrollado por el ingeniero Alberto Gascón González en el curso 2009-2010. Este proyecto aúna por un lado el interés que el acontecimiento “Guerra Civil Española” o “Guerra del 36” (en adelante GC36) ha despertado y despierta en cualquiera (nacional o extranjero) que se acerque y pretenda entender la España del siglo XX. Por otro lado, para cualquier “informático” supone un reto profesional el “romper” el secreto de miles de documentos que aún permanecen cifrados en numerosos archivos históricos (en España y fuera de ella), secreto que, roto, podría revelar datos sobre interpretaciones de hechos que ahora parecen definitivas. Adicionalmente, este proyecto permite la aplicación del algoritmo genético a las técnicas de criptoanálisis y su desarrollo. El proyecto de Don Alberto Gascón referido al inicio ceñía sus hipótesis con las siguientes acotaciones: a) La tabla de homófonos (ver cap. 2.4.3) es conocida pero la clave no. b) Uso de un “diccionario” compuesto con palabras elegidas por la certeza de su pertenencia al texto origen o plano, y ello no es real. c) Todas las palabras del “diccionario” tienen 6 o más caracteres1. Nuestra solución se plantea:  Cuando la tabla de homófonos y la clave (ver pág. 28) no son conocidas porque de hecho el criptógrafo no las conoce.  Por resolución con Algoritmo Genético (en adelante AG) sin limitación de palabras o nº de caracteres.  Incorporando un diccionario real (como fichero de texto) de 550.000 términos para la búsqueda de coincidencias que permite mejorar el análisis estadístico de la frecuencia de los monogramas, bígramas, trigramas e incluso de palabras.  Implementando en el algoritmo reglas de uso del idioma español del tipo “después de Q siempre va U”, “la K, J, H y V siempre van seguidas de vocal”, “cada 4 caracteres hay al menos una vocal”, etc.

Con sólo encontrar una palabra se ha resuelto el 22% (6/27) del problema. ¿Qué pasa con las palabras de uno a cinco caracteres? 1

Criptoanálisis, mediante algoritmos genéticos, de textos cifrados en la Guerra Civil Española con la técnica de cinta móvil

Cap 1.- Introducción.

4/119

1.2.- Objetivos del proyecto a) Objetivo principal: diseño de un algoritmo genético para el criptoanálisis de mensajes generados a partir de tabla de homófonos y clave desconocidas. Objetivos parciales… 1. Análisis de la región factible del problema para identificar debilidades en el cifrado de las que se puedan derivar restricciones que ayuden a resolver el problema. 2. Planteamiento de un problema de optimización con restricciones equivalente al proceso de criptoanálisis. 3. Diseño del AG que permita resolver el problema anterior. El propio desarrollo del AG ha ido generando la necesidad de una obligada interacción del criptoanalista2 con la herramienta que supone, en sí, el AG codificado (por ejemplo, en la fase de inicialización del algoritmo), lo que ha obligado a definir un segundo objetivo: b) Objetivo secundario: diseño de una herramienta Software (SW) con interface amigable que resulte útil e intuitiva para el futuro investigador que pudiera aprovechar los resultados del presente trabajo. Dicho SW… 1. No requiere un ordenador muy potente ni aplica técnicas de descifrado por “fuerza bruta”. 2. Permite opciones de inicialización (diccionarios a usar, texto cifrado, etc.) 3. Facilita informes intermedios y permite restricciones durante la ejecución para que el usuario pueda incorporar su análisis personal en cualquier fase del proceso. Dejamos advertido desde este inicio que aun cuando se consigan todos los objetivos relacionados, nunca podremos implementar un arma esencial para cualquier analista y más en esta materia: la intuición. 1.3.- Herramientas empleadas  Microsoft Visual Studio 2008.  Librería de algoritmos genéticos: GALIB v2.4.6 de Enero del 2005 adaptada a c++.  Excel para realizar análisis estadísticos y matemáticos a la hora de redactar los algoritmos.  Notepad++ para comprobar el funcionamiento de los algoritmos antes de implantarlos.  Microsoft Visio para la realización de los diagramas de flujo de los algoritmos.

2

Ver inicio del Capítulo 2 Criptoanálisis, mediante algoritmos genéticos, de textos cifrados en la Guerra Civil Española con la técnica de cinta móvil

Cap 1.- Introducción.

5/119

1.4.- Enfoque de resolución Como se detalla en capítulo 2.4.3, el método de Cifrado por Cinta Móvil o Método Español consiste en el uso de una tabla con 27 columnas correspondientes a las 27 letras del alfabeto y 8 filas que permiten asignar de 2 a 5 valores numéricos (homófonos) por letra con un rango3 de 00-99 (ver pág. 28). De manera que a cada letra del mensaje origen (texto plano) le pueden corresponder hasta 5 números (= 4) { ProcesarAG(fre_letras, fre_bigramas, fre_trigramas, texto_cifrado, valores_texto, tabla_homofonos_inversa, longitud, compone_diccionario.DevolverDiccionarioCharFormat(), compone_diccionario.DevolverIndiceCharFormat(), compone_diccionario.DevolverValoresIndice(), opcion/10); //ProcesarAG(fre_letras, fre_bigramas, fre_trigramas, texto_cifrado, valores_texto); estado = 5; } break; case 6: printf("\n\nSaliendo... Gracias por utilizar la aplicaci%cn\n",162); break; default: if(!disable_auto) { //1 texto_frecuencias = CargarTexto("Texto largo"); printf("Texto hist%crico cargado\n", 162); //2 fre_letras = analiza_ngramas.Contar(1, texto_frecuencias.c_str()); fre_bigramas = analiza_ngramas.Analiza_ngramas(2, texto_frecuencias.c_str ()); fre_trigramas = analiza_ngramas.Analiza_ngramas(3, texto_frecuencias.c_str ()); printf("Frecuencias analizadas\n"); //3 texto_cifrado = CargarTextoCifrado(); //Trabajamos directamente con un texto cifrado valores_texto = texto_cifrado; //Sacamos un vector con los distintos números hallados en el texto sort(valores_texto.begin(), valores_texto.end()); valores_texto = limpiar(valores_texto); printf("Valores distintos detectados:\n"); for(unsigned int a = 0; a < valores_texto.size(); a++) printf("%d ", valores_texto[a]); printf("\n"); printf("\nValores distintos del texto: %d\n", valores_texto.size()); vector tabla_homofonos_inversa = GenerarTablaHomofonosInversa(texto_cifrado, valores_texto, fre_letras, 0.2); float media = 0; printf("\nEspacio de búsqueda:\n"); for(unsigned short i = 0; i < tabla_homofonos_inversa.size(); i++) { printf("%02d: ", valores_texto[i]); for(unsigned short j = 0; j < tabla_homofonos_inversa[i].size(); j++) { printf("%c ", tabla_homofonos_inversa[i][j]); media++; } printf("\n"); } media /= tabla_homofonos_inversa.size(); printf("\nLa media de letras posibles asignadas a cada homófono es: %5.2f\ n", media); printf("El porcentaje de recducción del espacio de búsqueda es: %0.2f\n", 1-media/27); //4 longitud = 5; Criptoanálisis, mediante algoritmos genéticos, de textos cifrados en la Guerra Civil Española con la técnica de cinta móvil

Anexo H.- Código fuente

91/119

ifstream f0("Diccionarios\\diccionario_completo.txt"); if (f0.fail()) { printf("Diccionario no encontrado. Generando....\n"); //Carga los listados eliminando los acentos y los procesa limpiando y generando un índice compone_diccionario.CargarListado("base",0); compone_diccionario.CargarListado("lista_1",0); compone_diccionario.CargarListado("lista_2",0); compone_diccionario.ProcesarListado(); } else printf("Diccionario encontrado. Cargando....\n"); //Carga el diccionario preprocesado y el índice compone_diccionario.CargarListado("diccionario_completo",1,longitud); compone_diccionario.CargarIndice(longitud); printf("Diccionario e %cndice procesados\n", 'í'); //5 ProcesarAG(fre_letras, fre_bigramas, fre_trigramas, texto_cifrado, valores_texto, tabla_homofonos_inversa, longitud, compone_diccionario.DevolverDiccionarioCharFormat(), compone_diccionario.DevolverIndiceCharFormat(), compone_diccionario.DevolverValoresIndice(), 5); //ProcesarAG(fre_letras, fre_bigramas, fre_trigramas, texto_cifrado, valores_texto); estado = 5; } break; } fflush(stdin); printf("Pulse una tecla para continuar...\n"); _getch(); fflush(stdin); }while(opcion != 6); //printf("Saliendo...\n"); return 0; } short MostrarMenu(short estado) { ... } string CargarTexto(string texto) { string str, cadena; char direccion[80] = "Textos\\"; strcat_s(direccion, texto.c_str()); strcat_s(direccion,".txt"); //ifstream f0("Textos\\" + texto + ".txt"); ifstream f0(direccion); if (!f0.fail()) { while (!f0.eof()) { f0 >> str; cadena+=str; } f0.close(); } return cadena; } vector CargarTextoCifrado() { string str; vector cadena; ifstream f0("Textos\\Texto cifrado.txt"); if (!f0.fail()) { while (!f0.eof()) { f0 >> str; cadena.push_back(atoi(str.c_str())); } f0.close(); } Criptoanálisis, mediante algoritmos genéticos, de textos cifrados en la Guerra Civil Española con la técnica de cinta móvil

Anexo H.- Código fuente

92/119

return cadena; } vector GenerarTablaHomofonosInversa(vector texto_cifrado, vector vector_valores, vector fre_letras, float margen) { vector tabla_homofonos_inversa; vector columna_homofonos_inversa; vector fre_num, fre_num_por_2, fre_num_por_3, fre_num_por_4, fre_num_por_5; float error, error2, error3, error4, error5; int cuenta; char abecedario[29] = "abcdefghijklmnopqrstuvwxyzñ"; //Para cada valor del vector_valores contar cuantas veces aparece en el texto cifrado, hallar la frecuencia relativa del número y de las posibles letras asociadas a dicho número for(unsigned short i = 0; i < vector_valores.size(); i++) { cuenta = count(texto_cifrado.begin(), texto_cifrado.end(), vector_valores[i]); fre_num.push_back(cuenta/(float)texto_cifrado.size()); fre_num_por_2.push_back(fre_num[i]*2); fre_num_por_3.push_back(fre_num[i]*3); fre_num_por_4.push_back(fre_num[i]*4); fre_num_por_5.push_back(fre_num[i]*5); } //Comparamos las frecuencia de cada número con las de las letras for(unsigned short i = 0; i < vector_valores.size(); i++) //Cogemos un número { columna_homofonos_inversa.clear(); //27 con 'ñ', 26 sin 'ñ' for(unsigned short j = 0; j < 26; j++) //Se compara con las letras { error = abs(fre_num[i]-fre_letras[j]); error2 = abs(fre_num_por_2[i]-fre_letras[j]); error3 = abs(fre_num_por_3[i]-fre_letras[j]); error4 = abs(fre_num_por_4[i]-fre_letras[j]); error5 = abs(fre_num_por_5[i]-fre_letras[j]); if(error