4 e 6552603553 A

7/22/2019 4 e 6552603553 A

1/119

CRIPTOANLISIS, MEDIANTE ALGORITMOS GENTICOS, DETEXTOS CIFRADOS EN LA GUERRA CIVIL ESPAOLA

CON LA TCNICA DE CINTA MVIL

Proyecto de fin de carrera, Ingeniera Informtica SuperiorUniversidad Pontificia de Comillas ICAI

(Madrid 2011)

Autor: Jos Miguel Soriano de la Cmara

NDICE Pgina

Cap 1.- Introduccin...................................................................................................... 31.1.- Origen del proyecto.......................................................................................... 31.2.- Objetivos del proyecto ..................................................................................... 41.3.- Herramientas empleadas................................................................................. 41.4.- Enfoque de resolucin ..................................................................................... 5

Cap 2.- Criptografa y Criptoanlisis.......................................................................... 92.1.- Mtodos de cifrado clsicos .......................................................................... 10

2.1.1.- Clasificacin de los sistemas de cifrado............................................... 102.1.2.- Reglas de Kerckhoffs .............................................................................. 12

2.2.- Resea histrica de los sistemas de cifra..................................................... 132.2.1.- La esctala lacedemonia.......................................................................... 132.2.2.- Mtodo Csar........................................................................................... 132.2.3.- Cifra Monoalfabtica. ............................................................................. 142.2.4.- Cifrado Vigenre..................................................................................... 152.2.5.- Cifrado de Playfair.................................................................................. 172.2.6.- Cifrado Vernam....................................................................................... 182.2.7.- Cifrado Bazeries ...................................................................................... 19

2.3.- Mquinas de cifrar en el siglo XX................................................................. 212.3.1.- La mquina Enigma................................................................................ 212.3.2.- La mquina Hagelin ............................................................................... 23

2.4.- Cifrado por homfonos ................................................................................. 252.4.1.- Cifrado homofnico de orden n>1 ....................................................... 262.4.2.- Criptoanlisis de los cifrados por sustitucin con homfonos ........ 272.4.3.- El mtodo de cinta mvil o mtodo espaol....................................... 272.4.4.- Ataque al mtodo espaol: sus debilidades........................................ 31

Cap 3.- Mtodo Espaol: criptoanlisis con algoritmo gentico. ......................... 353.1.- Teora general sobre Algoritmos Genticos................................................ 373.2.- Preparacin de los datos de entrada............................................................ 41

3.2.1.- Clculo de frecuencias reales. ............................................................... 413.2.2.- Carga del texto cifrado........................................................................... 443.2.3.- Generacin de la tabla inversa.............................................................. 453.2.4.- Procesado del diccionario...................................................................... 47

3.3.- Diseo de la estructura de los cromosomas ............................................... 50

7/22/2019 4 e 6552603553 A

2/119

Cap 1.- Introduccin. 2/119

Jos Miguel Soriano de la Cmara Criptoanlisis, mediante algoritmos genticos, de textos cifradosen la Guerra Civil Espaola con la tcnica de cinta mvil

3.4.- Inicializacin del AG...................................................................................... 513.5.- Reproduccin o cruce de los individuos ..................................................... 513.6.- Mutacin de los cromosomas. ...................................................................... 513.7.- Evaluacin: Funcin Objetivo (Fitness)....................................................... 523.8.- Definicin final del texto descifrado............................................................ 54

Cap 4.- Casos de estudio y resultados ...................................................................... 55Cap 5.- Conclusiones y futuros desarrollos ............................................................. 69Anexo A: Tabla de frecuencias de uso aplicada...................................................... 72Anexo B: Mtodo Kasiski (ataque a un cifrado polialfabtico)............................. 75Anexo C: Cdigos de Baudot ..................................................................................... 78Anexo D: Cifra con ENIGMA .................................................................................... 79Anexo E: El Mtodo Espaol segn Carmona: ao 1894. ...................................... 80Anexo F: Claves y tablas de homfonos de la GC36; ejemplos. ........................... 82Anexo G- Planificacin y Presupuesto ..................................................................... 86Anexo H.- Cdigo fuente............................................................................................ 88ndice de Figuras........................................................................................................ 117Bibliografa.................................................................................................................. 118

7/22/2019 4 e 6552603553 A

3/119


Criptoanlisis, mediante algoritmos genticos, de textos cifradosen la Guerra Civil Espaola con la tcnica de cinta mvil

Cap 1.- Introduccin.

1.1.- Origen del proyecto

El presente trabajo tiene su origen en el proyecto fin de carrerasupervisado por los investigadores Don Francisco Alberto Campos Fernndez yDon Jess Mara Latorre Canteli del Instituto de Investigacin Tecnolgica deUP Comillas. Dicho proyecto es la continuacin natural del desarrollado por elingeniero Alberto Gascn Gonzlez en el curso 2009-2010.

Este proyecto ana por un lado el inters que el acontecimiento GuerraCivil Espaola o Guerra del 36 (en adelante GC36) ha despertado ydespierta en cualquiera (nacional o extranjero) que se acerque y pretendaentender la Espaa del siglo XX. Por otro lado, para cualquier informticosupone un reto profesional el romper el secreto de miles de documentos que

an permanecen cifrados en numerosos archivos histricos (en Espaa y fuerade ella), secreto que, roto, podra revelar datos sobre interpretaciones de hechosque ahora parecen definitivas. Adicionalmente, este proyecto permite laaplicacin del algoritmo gentico a las tcnicas de criptoanlisis y su desarrollo.

El proyecto de Don Alberto Gascn referido al inicio cea sus hiptesiscon las siguientes acotaciones:

a) La tabla de homfonos (ver cap. 2.4.3) es conocida pero la clave no.

b) Uso de un diccionariocompuesto con palabras elegidas por la certezade su pertenencia al texto origen o plano, y ello no es real.

c) Todas las palabras del diccionario tienen 6 o ms caracteres1.

Nuestra solucin se plantea:

Cuando la tabla de homfonos y la clave (ver pg. 28) no son conocidasporque de hecho el criptgrafo no las conoce.

Por resolucin con Algoritmo Gentico (en adelante AG) sin limitacin depalabras o n de caracteres.

Incorporando un diccionario real (como fichero de texto) de 550.000 trminospara la bsqueda de coincidencias que permite mejorar el anlisis estadstico

de la frecuencia de los monogramas, bgramas, trigramas e incluso depalabras. Implementando en el algoritmo reglas de uso del idioma espaol del tipo

despus 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.

1Con slo encontrar una palabra se ha resuelto el 22% (6/27) del problema. Qu pasacon las palabras de uno a cinco caracteres?

7/22/2019 4 e 6552603553 A

4/119



1.2.- Objetivos del proyecto

a) Objetivo principal: diseo de un algoritmo gentico para el criptoanlisis demensajes generados a partir de tabla de homfonos y clave desconocidas.Objetivos parciales

1. Anlisis de la regin factible del problema para identificardebilidades en el cifrado de las que se puedan derivar restriccionesque ayuden a resolver el problema.

2. Planteamiento de un problema de optimizacin con restriccionesequivalente al proceso de criptoanlisis.

3. Diseo del AG que permita resolver el problema anterior.

El propio desarrollo del AG ha ido generando la necesidad de una obligadainteraccin del criptoanalista2con la herramienta que supone, en s, el AG codificado(por ejemplo, en la fase de inicializacin del algoritmo), lo que ha obligado a definir

un segundo objetivo:b) Objetivo secundario: diseo de una herramienta Software (SW) con interface

amigable que resulte til e intuitiva para el futuro investigador que pudieraaprovechar los resultados del presente trabajo. Dicho SW

1. No requiere un ordenador muy potente ni aplica tcnicas dedescifrado por fuerza bruta.

2. Permite opciones de inicializacin (diccionarios a usar, texto cifrado,etc.)

3. Facilita informes intermedios y permite restricciones durante laejecucin para que el usuario pueda incorporar su anlisis personal

en cualquier fase del proceso.

Dejamos advertido desde este inicio que aun cuando se consigan todos losobjetivos relacionados, nunca podremos implementar un arma esencial paracualquier analista y ms en esta materia: la intuicin.

1.3.- Herramientas empleadas

Microsoft Visual Studio 2008.

Librera de algoritmos genticos: GALIB v2.4.6 de Enero del 2005

adaptada a c++.Excel para realizar anlisis estadsticos y matemticos a la hora de

redactar los algoritmos.

Notepad++ para comprobar el funcionamiento de los algoritmosantes de implantarlos.

Microsoft Visio para la realizacin de los diagramas de flujo de losalgoritmos.

2Ver inicio del Captulo 2

7/22/2019 4 e 6552603553 A

5/119



1.4.- Enfoque de resolucin

Como se detalla en captulo 2.4.3, el mtodo de Cifrado por Cinta Mvil oMtodo Espaol consiste en el uso de una tabla con 27 columnascorrespondientes a las 27 letras del alfabeto y 8 filas que permiten asignar de 2 a

5 valores numricos (homfonos) por letra con un rango3

de 00-99

(ver pg.28).De manera que a cada letra del mensaje origen (texto plano) le puedencorresponder hasta 5 nmeros (

7/22/2019 4 e 6552603553 A

6/119



3.Con ese margen de error, en las pruebas realizadas se obtiene para cadanmero del vector de valores un conjunto L de letras candidatas con unamedia de 9 letras por cada homfono en vez de las 27 iniciales. Se hareducido el espacio de bsqueda en un 65%. Se puede componer, as, unatabla, que llamaremos tabla inversa de homfonos que con altaprobabilidad contiene la solucin que estamos buscando:

Homfonos 01 02 03 86 89

Letras

Candidatas

f b a rh g e x iq v dz y lj ju

xTabla inversa de homfonos 0-3

Se puede ver en detalle este anlisis en aptdo. 2.4.4

Cmo inicializamos el cromosoma del AG?

1.El vector de valores numricos obtenido induce un cromosoma inicial en elque cada gen es una letra del alfabeto. Dicha letra es asignada de maneraaleatoria pero

a. Con las limitaciones derivadas del proceso de reduccin del espaciode bsqueda explicado en los prrafos anteriores. Cada gen (letra)debe pertenecer al conjunto L de candidatos del homfono.

b. No puede repetirse una letra ms de cinco veces en el cromosomapuesto que en la tabla de homfonos a una letra no se le asignanms de 5 nmeros.

Ejemplo: si el homfono 01 del vector ejemplo tiene como conjuntocandidato {f, h, q, z, j, u}, el gen de ndice 1 en el cromosoma inducido nopuede ni podr contener una g. Al homfono 86 nunca le podrcorresponder una h dado que h no pertenece a {, x}

01 02 03 06 08 15 23 25 29 34 40 49 50 54 58 68 76 77 79 81 85 86 89

Vector de valores numricos 0-4

z g e a o q a e s u o q s e i t c g r e s x dCromosoma inducido 0-5

2.- La calidad del cromosoma se evala en funcin del texto resultante alaplicar el cromosoma sobre el texto cifrado, comparando la suma de loserrores relativos de las frecuencias de las letras, bigramas y trigramas deltexto de la poca con los del texto resultante. Adems, se realiza unabsqueda secuencial en el texto resultante sobre un diccionario buscandopalabras de una determinada longitud; el nmero de palabras encontradas

incrementa la valoracin del cromosoma de cara al proceso de seleccin (verfuncin objetivo en pg.52).

7/22/2019 4 e 6552603553 A

7/119



3.- El proceso de reproduccin trata de conseguir un cromosoma con mejorresultado en la funcin objetivo, respetando como genes las letras delconjunto candidato de cada homfono

4.- El proceso de mutacin cambia genes al azar dentro del conjunto candidato

y se reitera hasta encontrar un individuo ms ptimo.Cmo definimos el texto final del mensaje descifrado?

El AG informa al analista de los cromosomas que evala y de su resultadoen la funcin objetivo. Escogiendo aquellos cuyo resultado est incluido dentrodel primer 5% de los mejores resultados, definimos los que llamaremoscromosomas candidatos.

En las pruebas realizadas, dichos cromosomas (normalmente de 3 a 6)generan hasta un 65% de acierto en los caracteres del texto plano original. Conesa plataforma de partida, y con la utilidad desarrollada al efecto que permite al

analista actuar a nivel de cromosoma, se pueden evaluar soluciones basadas ensu experiencia, contexto del mensaje o informaciones ajenas a l, que acerquen ala solucin final (ver proceso en detalle desarrollado en cap 4 Casos deEstudio).

Con el proceso descrito se completa el criptoanlisis sin necesidad deencontrar la tabla de homfonos. sta, en todo caso, surge como parte de lainformacin que resulta del proceso.

7/22/2019 4 e 6552603553 A

8/119



Como resumen del enfoque de solucin expuesto se presenta el esquemasiguiente:

Criptograma

delMtodoEspaol

Algoritmo Gentico

Utilidad de Anlisis

Vector de valores

Tabla Inversa dehomfonos

Cromosoma InicialCromosoma InicialCromosoma InicialCromosoma Inicial

Cromosoma InicialCromosoma InicialCromosoma InicialCromosoma candidato

Estudio de

Frecuencias

Funcin Objetivo

Textos planos

Texto Final

Analista

Texto Cifrado

7/22/2019 4 e 6552603553 A

9/119

Cap 2.- Criptografa y Criptoanlisis 9/119


Cap 2.- Criptografa y Criptoanlisis

No siendo objeto de este trabajo el estudio de los diferentes sistemas decifrado o su trayectoria histrica, pero con objeto de enmarcar y clasificar el

mtodo de cifrado por cinta mvily de definir algunos trminos habituales encriptografa, a continuacin se desarrolla un breve estudio sobre la materia y sedescriben algunos de estos sistemas.

Etimolgicamente la palabra criptografaderiva del griego kriptos (oculto)y degraphos (escritura), lo que da una clara idea de su definicin clsica: arte deescribir mensajes en clave secreta o enigmticamente[1].

Fue considerada un arte hasta que Claude Shannon public en 1949 elartculo Teora de los sistemas de comunicacin secretos y poco despus ellibro La teora matemtica de la comunicacin, con Warren Weaver. Entonces

la criptografa empez a ser considerada una ciencia aplicada, debido a surelacin con otras ciencias, como la estadstica, la teora de nmeros, la teora dela informacin y la teora de la complejidad computacional [1].La publicacinen el ao 1976de un artculo por parte de Whitfield Diffiey Martin Hellmanenel que proponen una nueva filosofa de cifra, dando lugar a los criptosistemas declave pblica, se considera el segundo hito significativo en la criptografamoderna[4].

Ahora bien, la criptografa corresponde slo a una parte de lacomunicacin secreta. Si se requiere secreto para la comunicacin, es porqueexiste desconfianza o peligro de que el mensaje transmitido sea interceptado

por alguien hostil. Este enemigo, si existe, utilizar todos los medios a sualcance para descifrar esos mensajes secretos mediante un conjunto de tcnicasy mtodos que constituyen una ciencia conocida como criptoanlisis. Alconjunto de ambas ciencias, criptografa y criptoanlisis, se le denominacriptologa[1].

Histricamente la criptologa ha sido una materia exclusiva del mbitomilitar o diplomtico. Sin embargo en la sociedad actual la criptologa haextendido sus aplicaciones a todo el mbito civil proporcionando la seguridadde las redes telemticas, incluyendo la identificacin de entidades y

autenticacin, el control de acceso a los recursos, la confidencialidad de losmensajes transmitidos, la integridad de los mensajes y su no repudio[1].

7/22/2019 4 e 6552603553 A

10/119



2.1.- Mtodos de cifrado clsicos

Se llama cifrado (o transformacin criptogrfica) a una transformacin deltexto original (texto plano, inicial o texto claro) que lo convierte en el llamadotexto cifrado o criptograma. Anlogamente, se llama descifrado a la

transformacin que permite recuperar el texto original a partir del cifrado. Cadauna de esas transformaciones est determinada por un parmetro llamadoclave[1].

2.1.1.- Clasificacin de los sistemas de cifrado

Por ocultacin: Disimulo del mensaje origen dentro de otros textos.

Por transposicin: Mtodo por el que se reordena el texto originalaplicando un algoritmo que produce el texto cifrado. El receptor reordena eltexto cifrado aplicando el algoritmo inverso.

Por sustitucin: Mtodo decifrado por el que unidades de texto planoorigen son sustituidas contexto cifrado siguiendo un sistema regular; las"unidades" pueden ser una sola letra, pares de letras, tros de letras, mezclas delo anterior, entre otros. El receptor descifra el texto realizando la sustitucininversa [1].

En la figura siguiente hacemos una clasificacin detallada de esas trestcnicas de cifrado clsico generales descritas.

Haremos a lo largo de las siguientes pginas un somero estudiocomparativo de los sistemas reflejados en la fila inferior del esquema de arriba(elaboracin propia).

Si el cifrado opera sobre caracteres simples, se denomina cifrado por

sustitucin simple; un cifrado que opera sobre grupos de letras sedenomina poligrfico. Un cifrado monoalfabticousa una sustitucin fija para

Sistemas de cifra clsicos 1
http://es.wikipedia.org/wiki/Criptograf%C3%ADahttp://es.wikipedia.org/wiki/Texto_cifradohttp://es.wikipedia.org/wiki/Texto_cifradohttp://es.wikipedia.org/wiki/Criptograf%C3%ADa

7/22/2019 4 e 6552603553 A

11/119



todo el mensaje, mientras que un cifrado polialfabtico usa diferentessustituciones en diferentes momentos del mensaje, por ejemplo los homfonos,en los que una unidad del texto plano es sustituida por una de entre variasposibilidades existentes para el texto cifrado [1].

Se llama cifrado producto a la aplicacin iterativa de operaciones decifrado sobre texto ya cifrado, combinando o no sustitucin y transposicin [1].

En un cifrado por transposicin, las unidades del texto plano soncambiadas usando una ordenacin diferente, pero las unidades en s mismas noson modificadas. Por el contrario, en un cifrado por sustitucin las unidades deltexto plano mantienen el mismo orden, lo que se cambia son las propiasunidades del texto plano.

Segn la relacin existente entre la clave de cifrado y descifrado, lossistemas criptogrficos se pueden dividir en dos grandes grupos: cifrado

simtricoode clave secreta en el caso de que ambas coincidan; si es imposibleobtener la clave de descifrado a partir de la clave de cifrado estamos ante unsistema de cifrado asimtricoo de clave pblica[1].

En los sistemas asimtricos la seguridad del sistema no depende delconocimiento de la clave de cifrado. Cualquier usuario puede enviar unmensaje cifrado a otro usando la clave pblica de este ltimo, pero slo aquelque conozca la clave privada correspondiente puede descifrarlo correctamente.El criptoanalista que intente averiguar la clave privada a partir de la pblica seencontrar con un problema intratable[1].

Aqu trataremos los sistemas clsicos. El adjetivo de clsico, encontraposicin al de criptosistemas modernos, se debe tanto a las tcnicasutilizadas en las primeras, bsicamente operaciones de sustitucin y transposicinde caracteres unidas al concepto de clave secreta, como al uso de mquinasdedicadas a la cifra. La criptografa clsica abarca, pues, desde tiemposinmemoriales hasta los aos de la postguerra mundial, es decir, hasta la mitad delsiglo XX. En el caso de los sistemas modernos, stos hacen uso, adems de loanterior, de algunas propiedades matemticas como, por ejemplo, la dificultad delclculo del logaritmo discreto o el problema de la factorizacin de grandesnmeros, unido esto a la representacin binaria de la informacin. No obstante,muchos sistemas modernos y que en la actualidad se siguenutilizando, como los algoritmos de clave secreta DES e IDEA,se basan en conceptos que podramos denominar clsicoscomo son los de transposicin y sustitucin con una claveprivada, si bien en estos sistemas la operacin se realiza sobreuna cadena de bits y no sobre caracteres[4].

Cundo un sistema criptogrficose considera ptimoo eficaz?. En 1883, el francs Auguste Kerckhoffs, en su libroLa criptografa militar, enuncia las reglas que, desdeentonces, la comunidad criptogrfica considera que debe

cumplir un buen sistema criptogrfico [1].

Auguste Kerckhoffs 1

7/22/2019 4 e 6552603553 A

12/119



2.1.2.- Reglas de Kerckhoffs:

1. No debe existir ninguna forma de recuperar mediante el criptograma eltexto inicial o la clave. Esta regla se considera cumplida siempre que lacomplejidad del proceso de recuperacin del texto original sea suficiente

para mantener la seguridad del sistema.2. Todo sistema criptogrfico debe estar compuesto por dos tipos distintos

de informacin. Pblica, como es la familia de algoritmos que lo definen. Privada, como es la clave que se usa en cada cifrado particular.

3. La forma de escoger la clave debe ser fcil de recordar y modificar.4. Debe ser factible la comunicacin del criptograma por los medios de

transmisin habituales.5. La complejidad del proceso de recuperacin del texto original debe

corresponderse con el beneficio obtenido.

Genricamente se conoce como Principio de Kerckhoffs aquel queenuncia de que la seguridad del sistema se debe medir suponiendo que elenemigo conoce completamente ambos procesos de cifrado y descifrado[1].Esdecir, si se mantiene en secreto la clave un sistema perfecto es indescifrable.

7/22/2019 4 e 6552603553 A

13/119



2.2.- Resea histrica de los sistemas de cifra

2.2.1.- La esctala lacedemonia:

Del griego(skytl). Es el primer uso de la escritura secreta de que se tieneconstancia; data del siglo V a. C., durante las guerras entre Atenas y Esparta.Est formada por dos varas idnticas en susmedidas, en especial su grosor. Se basabanicamente en la alteracin del mensajemediante la escritura de los smbolos de

forma vertical sobre una cinta enrollada enun rodillo, de manera que al desenrollarla

los smbolos del mensaje quedaban desordenados otraspuestos, por lo que slo se poda leer el mensajetras enrollar la cinta en un rodillo de igual grosor.

Es el mtodo de transposicin ms elemental;tambin conocido como transposicin de matrices. Esequivalente a disponer en una tabla cada uno de loscaracteres del texto plano en filas y luego tomarlos en

columnas. Siendo el ancho de fila el nmero de caras que presenta la esctala yel nmero de filas la cantidad resultante de dividir el largo total del mensajeentre el ancho de fila. (Verhttp://es.wikipedia.org/wiki/Esctala)

La frase ostentar el bastn de mando" tiene su origen en esta poca. Elbastn (la esctala) aseguraba el control del sistema de informacin y por tanto

de la seguridad y de la vida poltica en la antigua Grecia[4].2.2.2.- Mtodo Csar.

Otra de las primeras noticias sobre criptografa proviene de la pocaromana (siglo I a.c.). El cifrado en este caso consista en una sustitucin segnuna regla fija: un caracter se cifra con un desplazamiento de 3 puestos en elorden del alfabeto; la A ser D, la F ser I

Mensaje: Atacar a las 6 horas del jueves 10Alfabeto

Plano A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Cifrado D E F G H I J K L M N O P Q R S T U V W X Y Z A B CTextoPlano A T A C A R A S E I S H O R A S J U E V E S D I E Z

Cifrado D W D F D U D V H L V K R U D V M X H Y H V G L H CTransmitir: DWDFD UDVHL VKRUD VMXHY HVGLH CXYZM

Matemticamente podemos describir el mtodo usado por Julio Csarcomo una funcin lineal del tipo E(x)= (x+3) mod 26. Para descifraremplearamos la funcin D(x)= (x-3) mod 26[1].

Puede parecer un sistema infantil pero considerando que durante milenios

el 99,9% de la humanidad ha sido analfabeta, no creemos que en la Guerra delas Galias las tribus enemigas tuvieran muchos lectores y, menos an,

Esctala lacedemonia 1
http://es.wikipedia.org/wiki/Matriz_transpuestahttp://es.wikipedia.org/wiki/Esc%C3%ADtalahttp://es.wikipedia.org/wiki/Esc%C3%ADtalahttp://es.wikipedia.org/wiki/Esc%C3%ADtalahttp://es.wikipedia.org/wiki/Esc%C3%ADtalahttp://es.wikipedia.org/wiki/Matriz_transpuesta

7/22/2019 4 e 6552603553 A

14/119



capacitados para leer el latn codificado de esta manera. De hecho, el MtodoCesar se ha usado durante siglos hasta la poca del Renacimiento.

2.2.3.- Cifra Monoalfabtica.

El cifrado Cesar visto, se puede generalizar usando cualquierdesplazamiento hasta 26 con la evidente ventaja de que es muy fcil recordar laclave: slo un nmero entre 1 y 26. Pero tambin es fcil de descifrar: hay 26alfabetos posibles[1].

Podemos anular esta facilidad recordando que si tenemos 26 letraspodramos desordenar el alfabeto plano en alguna de las 26! (4x1026)permutaciones. Una tcnica habitual para generar alguno de esos 26! alfabetosposibles desplazados era usar palabra clave: en dicha palabra se eliminancaracteres repetidos y a continuacin se relaciona el resto del alfabeto si repetir

caracteres. Veamos un ejemplo:Mensaje: Atacar a las 6 horas del jueves 10Alfabeto

Plano A B C D E F G H I J K L M N O P Q R S T U V W X Y ZClave S A N T I A G O

Cifrado S A N T I G O P Q R U V W X Y Z B C D E F H A J K LTexto

Plano A T A C A R A S E I S H O R A S J U E V E S D I E ZCifrado S E S N S C S D I Q D P Y C S D R F I H I D T Q I L

Transmitir SESNS CSDIQ DPYCS DRFIH IDTQI LFINE

En la tabla, de elaboracin propia como todas las que seguirn, hemosdispuesto el mensaje a transmitir como tradicionalmente se ha enseado en lasescuelas de transmisiones[27]:compartimentndolo en grupos de 5 caracteres,formando una especie de palabras que facilitaran la lectura, emisin, copia delmensaje cifrado o comprobacin en la recepcin, con preguntas del tipo repitagrupo 3; en el ejemplo DPYCS. En el ltimo grupo era habitual que lasnormas previeran caracteres de relleno y sin significado para completar hasta 5(en el ejemplo el ltimo grupo es L y se completa con FINE). Estaba previsto eluso de caracteres numricos (coordenadas, fechas y horas) y de abreviaturas (H-hora-, PD posicin defensiva-, BP base de partida-, LZ zona delanzamiento-, PC puesto de mando, etc.). Junto con la palabra clave era normalespecificar qu grupos se introducan como nulos; en el ejemplo claveSANTIAGO, grupos nulos 3 y 5, dara este mensaje a transmitir:

Transmitir SESNS CSDIQ XFRWE DPYCS BFTUP DRFIH IDTQI LFINEIgualmente se instrua en una redaccin a formato telegrama previa al

cifrado, pero que mantuviera la esencia de la informacin, con objeto de reducirlos recursos requeridos y errores en el proceso de transmisin y descifrado.

Es seguro enviar un mensaje con este sistema? Durante siglos esta

tcnica se consider segura. En el siglo XI, Al-Kindi encontr un punto dbil enla codificacin monoalfabtica: cada letra del alfabeto plano se sustituye por

7/22/2019 4 e 6552603553 A

15/119



otra y siempre la misma. Si el texto cifrado es suficientemente largo, un anlisisde frecuencia de sus caracteres comparado con las frecuencias de uso habitualesen el idioma de que se trate permitir deducir la tabla de conversin utilizada[5].El criptoanlisis acababa de nacer.

La idea de la sustitucin se utiliza tambin en la Biblia, donde se puedenencontrar textos cifrados con atbash hebreo: consiste en usar el carctersimtrico en el alfabeto (el de la a es la z), a lo que se llama mtodo espejo,o atbashen hebreo; por ejemplo ayudaser zbfwz[1].

Es del siglo XIV la obra ms antigua que existe sobre criptografa. Se titulaLiber Zifrorum y su autor, Cicco Simoneta, estudia en ella diversos sistemasbasados en simples sustituciones de letras. En el siglo XV la criptografa esimpulsada por las intrigas entre el papado y lasciudades-estado italianas [5]. En 1466 Len BattistaAlberti, msico, pintor, escritor y arquitecto,

concibi un sistema de sustitucin polialfabtica queemplea varios abecedarios, saltando de uno a otro;los cambios se indicaban escribiendo la letra delcorrespondiente alfabeto en el mensaje cifrado. Elemisor y el destinatario han de ponerse de acuerdopara fijar la posicin relativa de dos crculosconcntricos que determinar la correspondencia delos signos; son los llamados discos de Alberti.

2.2.4.- Cifrado VigenreDurante el siglo XVI se generaliza el uso de la criptografa en los

ambientes diplomticos y en 1586 Blaise de Vigenre publica una obra tituladaTrait des chiffres o secrtes manires d'ecrire, donde rene diferentesmtodos utilizados en la poca. En dicho tratado recoge un mtodooriginalmente descrito por Giovan Batista Belaso en 1553. De ah queincorrectamente se le atribuyera en el siglo XIX a Vigenre, conocindose anhoy como el "cifrado Vigenre".

El cifrado Vigenre es un cifrado de sustitucin polialfabtico que se

puede considerar como la generalizacin del cifrado Csar. La clave estconstituida por una secuencia de smbolos del alfabeto K = {k0, k1, ... ,kd-1} delongitud d y donde kikj para todo i,j

7/22/2019 4 e 6552603553 A

16/119



TABLA de VIGENRE Entrada texto plano1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

1 A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z2 B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A3 C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

4 D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C5 E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D6 F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E7 G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F8 H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G9 I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

Entradaclave

J J K L M N O P Q R S T U V W X Y Z A B C D E F G H IK K L M N O P Q R S T U V W X Y Z A B C D E F G H I JL L M N O P Q R S T U V W X Y Z A B C D E F G H I J KM M N O P Q R S T U V W X Y Z A B C D E F G H I J K LN N O P Q R S T U V W X Y Z A B C D E F G H I J K L MO O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

16 P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O17 Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

18 R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q19 S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R20 T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S21 U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T22 V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U23 W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V24 X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W25 Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X26 Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Para cifrados de campo se usaba la llamada Tabla de Vigenre. Veamosun ejemplo de cifrado:

Tras relacionar la palabra clave reiteradamente hasta abarcar todo el mensaje, elcarcter cifrado se obtena leyendo en la primera fila el carcter plano y en laprimera columna el carcter correspondiente de la palabra clave; el carctercifrado resultaba de la interseccin de las dos entradas en la tabla. Ejemplo:

Mensaje: Atacar a las 6 horas del jueves 13Clave: A Z U LTexto:

plano A T A C A R A S E I S H O R A S J U E V E S T R E C Eclave A Z U L A Z U L A Z U L A Z U L A Z U L A Z U L A Z U

cifrado A S U N A Q U D E H M S O Q U D J T Y G E R N C E B YTransmitir: ASUNA QUDEH MSOQU DJTYG ERNCE BYXYZ

En este ejemplo podemos comprobar como la A se cifra en A y en U, la Cen N y en B, la R en Q y en C, etc.

Segn la forma de entrar a la tabla, este mtodo tuvo variantes:

Vigenre Plano Beaufort Cifrado Alemana Cifrado

Clave

CifradoPlano

ClaveClave

Plano

7/22/2019 4 e 6552603553 A

17/119



Durante siglos el mtodo Vigenre fue considerado irrompible; si la clavede Vigenre tiene mas de 6 caracteres distintos, se logra una distribucin defrecuencias en el criptograma del tipo normal, es decir ms o menos plana, porlo que se logra difuminar la redundancia del lenguaje. En1863, FriedrichKasiski (oficial prusiano) public un libro sobrecriptografa,DieGeheimschriften und die Dechiffrierkunst ("La escritura secreta y el arte deldescifrado"). sta fue la primera publicacin sobre criptoanlisis aplicado a loscifrados de sustitucin polialfabticos, especialmente elcifrado de Vigenre,desarrollando lo que luego se ha llamado Mtodo Kasiski(ver Anexo B).

La importancia del trabajo criptoanaltico de Kasiski no fue valoradaentonces o, si lo fue, se mantuvo en secreto. De hecho esta tcnica luego se hasabido que fue diseada tambin por el britnico Charles Babbage (GranBretaa 1791-1871) y usada en campaas militares inglesas, siendo consideradaun secreto militar. Como resultado, el mrito por haber descifrado esta clave le

fue otorgado aFriedrich Kasiski.

2.2.5.- Cifrado de Playfair.

Sustitucin 2-palabras o digrmico

Los cifrados anteriores se hacan carcter a carcter, es decir eranmonogrmicos. Para aumentar la seguridad de la cifra y romper las estadsticas,podemos cifrar por poligramas o bloques de caracteres.

Un sistema inventado a finales del siglo XIX (obra del fsico Charles

Wheatstone pero difundido por su amigo Lord Playfair (que acab dndole elnombre) es el de Playfair que trabaja con una matriz de 5x5 letras, cifrando pordigramas: a cada par de letras del texto claro hace corresponder otras dos letrasen el texto cifrado. Se rellena la matriz de izquierda a derecha y de arriba abajocon la palabra clave, no repitiendo letras, y se completa con el resto del alfabeto,sin repetir letras y eliminando J y : total 25 letras. El texto plano se agrupa porparejas (x,x) de caracteres; (y,y) sern el par respectivo cifrado tras aplicar lassiguientes reglas[1]:

Si (x,x) estn en la misma fila, (y,y) son los dos caracteres de la derecha.

Si (x,x) estn en la misma columna, (y,y) son los dos caracteres de abajo.

Si (x,x) estn en filas y columnas distintas, (y,y) son los dos caracteres dela diagonal, desde la fila de x.

Si x=x, insertar carcter sin significado entre x y x para evitar surepeticin, despus aplicar reglas 1-3

5.- Si el nmero de letras es impar, aadir una sin significado al final deltexto, por ejemplo la X.

Mensaje: Atacar a las 6 horas del jueves 13Clave: MURCIELAGO

Texto plano ATACAR A SEIS HORAS JUEVES TRECEgrupos AT AC AR AS EI SH OR AS JU EV ES TR EC EX
http://es.wikipedia.org/wiki/1863http://es.wikipedia.org/wiki/Criptograf%C3%ADahttp://es.wikipedia.org/wiki/Cifrado_de_Vigen%C3%A8rehttp://es.wikipedia.org/wiki/Friedrich_Kasiskihttp://es.wikipedia.org/wiki/Friedrich_Kasiskihttp://es.wikipedia.org/wiki/Cifrado_de_Vigen%C3%A8rehttp://es.wikipedia.org/wiki/Criptograf%C3%ADahttp://es.wikipedia.org/wiki/1863

7/22/2019 4 e 6552603553 A

18/119



Cuadrado PlayfairM U R C IE L A G OB D F H KN P Q S T

V W X Y Z

Texto cifrado OQ GR FA GQ OM TK AI GQ MR BM GN QI GM AV

Este sistema tambin es criptoanalizable pues en el criptograma persistenalgunas propiedades del lenguaje; en este caso la distribucin de digramastpicos; por ejemplo en el castellano en, de, mb, etc. El secreto de este cifradoest obviamente en la matriz, en la palabra clave elegida.

2.2.6.- Cifrado VernamHemos visto que, segn el principio de Kerckhoffs, un sistema

criptogrfico basa su seguridad en la clave, seguridad que se mide conociendoel oponente el algoritmo de cifrado pero no la clave.

En 1917 Gilbert S. Vernam, ingeniero del MIT que trabajaba en loslaboratorios de la empresa AT&T, disea un dispositivo criptogrfico paracomunicaciones telegrficas basado en los 32 cdigos de Baudot (ver anexo C)que usaban los teletipos desarrollados por su compaa. Estos cdigosrepresentan los caracteres del lenguaje con cinco elementos que pueden ser el

espacio o la marca (el cero y el uno) diseado para transmisiones telegrficas.Es decir, un sistema binario con 5 dgitos: 2^5= 32 caracteres.

Este cifrador, que tuvo una gran aplicacin durante la Primera GuerraMundial, basa su seguridad en el secreto de una clave aleatoria que se suponetan larga o ms que el mensaje y que luego de usarse debe destruirse[4].Estesistema por sustitucin polialfabtica es el caso lmite del cifrado Vigenre. Elhecho de que la seguridad absoluta dependa de un nico uso de la clave le dioel sobrenombre de one time pad[14].

Usa una clave constituida por una sucesin de smbolos (bits o caracteres)

llamada serie cifrante, operando o-exclusivo XOR cada smbolo de sta con elcorrespondiente del texto en claro. Debido a la definicin de la funcin XOR, eldescifrado se realiza, igualmente, operando con dicha funcin cada bit de lamisma serie cifrante con el correspondiente del texto cifrado. Si la serie cifranteno se repite, es aleatoria, y de longitud igual o mayor al texto a cifrar, stecifrado alcanza el secreto perfecto. Adems, es el nico que verifica talcondicin[1].

Cada carcter mi se representa con 5 bits en cdigo Baudot que se sumaOR exclusivo (mdulo 2) con la correspondiente clave ki de una secuenciabinaria aleatoria [4].De esta forma, el cifrador de Vernam genera un flujo de

bits de texto cifrado de la forma:

7/22/2019 4 e 6552603553 A

19/119



C = EK(M) = C1C2C3... Cn

Donde Ci= (mi+ ki) mod 2 para i = 1 ,2 ,..., n; o sea, ci= miXOR ki

Mensaje: Atacar el jueves trece a las seis horasplano: ATACARJUEVESTRECEASEISH 23 caracteres

Clave: TCEGIKMOQSUWYBDFVABCDGT 23 caracteresen cdigo Baudot

Plano Clave Plano Clave Cifra CifraA XOR T 00011 XOR 10000 = 10011 = WT XOR C 10000 XOR 01110 = 11110 = VA XOR E 00011 XOR 00001 = 00010 = 2C XOR G 01110 XOR 11010 = 10100 = HA XOR I 00011 XOR 00110 = 00101 = SR XOR K 01010 XOR 01111 = 00101 = SJ XOR M 01011 XOR 11100 = 10111 = QU XOR O 00111 XOR 11000 = 11111 = 3E XOR Q 00001 XOR 10111 = 10110 = PV XOR S 11110 XOR 00101 = 11011 = 4E XOR U 00001 XOR 00111 = 00110 = IS XOR W 00101 XOR 10011 = 10110 = PT XOR Y 10000 XOR 10101 = 00101 = SR XOR B 01010 XOR 11001 = 10011 = WE XOR D 00001 XOR 01001 = 01000 = 1C XOR F 01110 XOR 01101 = 00011 = AE XOR V 00001 XOR 11110 = 11111 = 3A XOR A 00011 XOR 00011 = 00000 = 6

S XOR B 00101 XOR 11001 = 11100 = ME XOR C 00001 XOR 01110 = 01111 = KI XOR D 00110 XOR 01001 = 01111 = KS XOR G 00101 XOR 11010 = 11111 = 3H XOR T 10100 XOR 10000 = 00100 = 5

Cifrado6: WV2HS SQ3P4 IPSW1 A36MK K35

Para la operacin de descifrado utilizaremos el mismo algoritmo por lapropiedad involutiva de la operacin OR exclusivo. Esto es:

ciXOR ki= (miXOR ki) XOR kiComo kiXOR ki= 0 para ki= 0 y ki= 1 se obtiene ciXOR ki= mi

2.2.7.- Cifrado Bazeries:

Como hemos visto, sustitucin y transformacin no resultan muy fiables;sin embargo combinados resultan la base de sistemas mucho ms difciles deromper. Un ejemplo de cifrado producto (transposicin ms sustitucin) fue

6 Como se explica en Anexo C, los caracteres especiales ha sido representados por losdgitos 1 a 6 a efectos de este ejemplo.

7/22/2019 4 e 6552603553 A

20/119



ideado por Etienne Bazeries (criptlogo y comandante del Ejrcito francs, 1846a 1931). En este sistema se fija un nmero clave menor que 1.000.000 y se leexpresa en texto eliminando las segundas y siguientes repeticiones del mismocarcter. El texto plano se ordena en grupos de cardinal igual a las cifras quecomponen el nmero clave: por ejemplo, grupos de 2, 3, 2, 6 y 7 caracteres si laclave fuera 23.267[1].

Se generan dos matrices de 5x5: la 1 contiene el alfabeto relacionado dearriba a abajo y de izquierda a derecha eliminando y W; la 2 contiene loscaracteres de la clave numrica expresada en texto sin repeticiones,relacionados de izquierda a derecha y de arriba abajo, completando los huecos apartir del ltimo carcter de la clave con los caracteres alfabticos que le siguen,siempre sin repeticiones.

1 fase, transposicin: se invierten simtricamente los caracteres en cadauno de los grupos del texto plano.

2 fase, sustitucin: en la matriz 1 se busca el carcter plano; el carctercifrado es el de su misma posicin en la matriz 2

Mensaje: Atacar a las 6 horas del jueves 13Clave: 23267 VEINTITRES MIL DOSCIENTOS SESENTA Y SIETE VEINTRSMLDOCAYTexto:

plano ATACAR A SEIS HORAS JUEVES TRECEGrupos-clave AT ACA RA SEISHO RASJUEV ES REC EZtransposicin TA ACA AR OHSIES VEUJSAR SE CER ZE

matriz 1 5x5 matriz 2 5x5

A F K P U V E I N TB G L Q V R S M L DC H M R X O C A Y ZD I N S Y A B C F GE J O T Z H J K P Q

sustitucin PV VOV VY KCFBHF DHTJFVY FH OHY QHtransmisin PVVOV VYKCF BHFDH TJFVY FHOHY QHZYX

Para la transmisin se agrupan en grupos de 5 y se completa el ltimo concaracteres nulos.

7/22/2019 4 e 6552603553 A

21/119



2.3.- Mquinas de cifrar en el siglo XX

La rotura de los sistemas tradicionales de cifrado a principios del siglo XXy la masificacin de medios materiales y humanos que permiti la RevolucinIndustrial del XIX en los usos de la guerra moderna en todos los niveles,

incluido el trfico de mensajes cifrados, deriv en el diseo de mquinas quepermitieran automatizar el lento y engorroso sistema manual de cifrado.

Algunos de los esquemas de cifrado producto fueron usados en los aos20 del siglo pasado para el diseo de mquinas de rotor. Las ms conocidasfueron la HAGELIN y la ENIGMA, usadas durante la 2 Guerra Mundial y quefueron criptoanalizadas en su momento destacando tanto por sus caractersticascomo por el halo de misterio que las rode. El sistema de rotores daba lugar aun importante nmero de claves secretas que, para aquel entonces, dificultabain extremis el criptoanlisis.

2.3.1.- La mquina EnigmaInventada por el ingeniero alemn Arthur Scherbius en el ao 1923, la

mquina Enigma[4] consiste en un banco de rotores montados sobre un eje, encuyos permetros haba 26 contactos elctricos, unopor cada letra del alfabeto ingls. En realidad elprecursor de este tipo de mquinas con rotores fueEdward Hugh Hebern que algunos aos antesinventa y comercializa los denominados cifradoresde cdigos elctricos. Esta mquina debe su fama asu amplia utilizacin durante la Segunda GuerraMundial, en especial por parte del ejrcito alemn.El imperio japons tambin cifr sus mensajesdurante el citado conflicto con una mquina similardenominada Purple.

Los rotores se desplazaban como unodmetro. Es decir, al cifrar un carcter el primerrotor avanzaba una posicin (correspondiente a1/26 de una rotacin) y slo cuando ste habarealizado una rotacin completa (26 letras), el

segundo se desplazaba un carcter, y assucesivamente[4].Los rotores volvan a su posicin

inicial, tras un perodo igual a nt. Por ejemplo, en un sistema con 4 rotores, seutilizan 264= 456.976 alfabetos de 26 letras. Si aumentamos los rotores a 5, estacantidad asciende a 11.881.376. Esto implicaba que la Enigma usaba un sistemapolialfabtico, porque la misma letra poda ser sustituida por varias letrasdistintas a lo largo de un mensaje. Por ejemplo, una 'A' poda ser codificadacomo una 'M' al principio de un mensaje y ms adelante (en el mismo mensaje)ser codificada como una 'T'. La operacin de cifra para estas mquinas sigue lasiguiente congruencia[4]:

Ei(M) = ( fi(M - pi) mod (26 + pi) ) mod 26

Enigma K adquirida en Nov-361

7/22/2019 4 e 6552603553 A

22/119



donde pi es la posicin en la que se encuentra el rotor i-simo y fi lacorrespondencia de los caracteres de la cara anterior y posterior de este rotor.Por lo tanto, el carcter i-simo midel mensaje M = m1m2m3... se cifrar como:

Eki(mi) = ft..... f1(M) donde indica la posicin relativa entre dos

rotores colindantes y t el nmero de rotores.

Haba ciertas caractersticas de la Enigma que facilitaban un poco la tareade decodificacin. Por ejemplo, las sustituciones que se realizaban eran talesque una letra nunca poda ser codificada consigo misma. Es decir, una 'A',nunca poda aparecer como 'A' en el mensaje en clave. Si entramos en elsimulador [16] y ciframos el mensaje AAAAAAAAA el resultado esKTWREEOST habiendo colocado los rotores 1, 2 y 3 en posicin inicial H , D yX. Por mucho que repitamos A nunca se cifra como A

Los anillos movibles alrededor de los rotores tambin incrementaban lacomplejidad de la mquina. Su objetivo era asignar un nmero a cada posicindel rotor (la cual a su vez corresponda a una letra), de manera que aunque sesupiera cul era la posicin inicial de los rotores, el mensaje no podradescifrarse si no se conoca la posicin fsica de los anillos.

Cifrar con la mquina Enigma era un proceso lento. Lo operadorestrabajaban en grupos de dos, con una persona pulsando las teclas, operacinmuy lenta ya que las teclas deban pulsarse con mucha fuerza para hacer girarlos rotores, y otro registrando la letra cifrada que se encenda en el panel

superior de bombillas. Las primeras mquinas Enigma tenan tres rotores yunos doce kilos de peso. La mayora de los pases compraron maquinas para suevaluacin y todos ellos hicieron sus versiones. La versin britnica eraconocida como TYPEX y de ella se construyeron unas 12.000 unidades, siendoadoptada por el ejrcito y la RAF. Incluso los polacos, que fueron de losprimeros en romper el cdigo generado por la mquina, tuvieron su versin dela misma que llamaban LACIDA[15].

En Espaa, el Bando Nacional, durante la Guerra Civil del 36, adquiri 10mquinas, como la de la figura del inicio, en Noviembre de 1936, que fuerondedicadas a enlace entre el Alto Mando y con los aliados alemanes e italianos;en total, se calcula que operaron en la Pennsula una cincuentena de estasmquinas[10].

Rotores de Enigma.www.simonsingh.net 1

7/22/2019 4 e 6552603553 A

23/119



Quien desee hacer una prueba de funcionamiento de la mquina entiempo real y cifrado puede hacerlo en

http://enigmaco.de/enigma/enigma.swf

El anexo D es un resultado de esta web

2.3.2.- La mquina Hagelin

La mquina Hagelin [17] fue inventada por el criptlogo sueco BorisHagelin, quien adquiri en 1927la fbrica de mquinas de cifrarde Arvid G. Damm, otro inventorsueco que no tuvo la suerte desacar un producto competitivo enel mercado. Entre los aos veintey los treinta, Hagelin disea

diversas mquinas (B-21, B-211,C-36, C-38, etc.) en las que atravs de ruedas con pionesrealiza una cifra similar a lautilizada por el sistema deBeaufort7[4].

La particularidad de estasmquinas, que a la postre hizomillonario a Hagelin,probablemente ante ladesesperacin de Damm, estaba en unaperiodicidad muy alta puesto que elnmero de dientes de las diferentes ruedas eran primos entre s. Para seisruedas estos valores eran 26, 25, 23, 21, 19 y 17, de forma que el perodo eraigual a su producto, un valor que supera los 100 millones. La ecuacinmatemtica que representa al cifrado de Hagelin es[4]:

Eki(mi) = (k (i mod d)mi) mod n

Siendo, d la longitud de la palabra clave, k el carcter correspondientedentro de dicha palabra, miel i-simo smbolo del texto claro y n el cardinal del

alfabeto.El modelo C-38 de esta mquina fue adquirido por el Ejrcito USA para las

comunicaciones militares y diplomticas durante la IIGM con la designacin deM-209. Un diseo compacto y reducido (del tamao de una sandwichera)facilitaba su uso incluso en niveles tcticos inferiores, pero, sobre todo, eldisponer de un sistema de impresin era lo que de verdad facilitaba su uso enrelacin, por ejemplo, a mquinas como Enigma. Un desarrollo posterior de1952, el modelo C-52, ha estado operativo en ms de 60 pases hasta inicios delos 80 y durante toda la guerra fra[17].En Espaa, en los aos cincuenta y a

7Variante del cifrado Vigenre (ver pg.13)

Hagelin CX-52 1
http://enigmaco.de/enigma/enigma.swfhttp://enigmaco.de/enigma/enigma.swfhttp://enigmaco.de/enigma/enigma.swf

7/22/2019 4 e 6552603553 A

24/119



partir de 19548, con las mquinas Enigma ya retiradas por obsoletas, el Ejrcitoespaol empez a dotarse con mquinas Hagelin para asegurar suscomunicaciones[10].

Para informacin ms completa y descarga de simulador se recomienda

entrar enhttp://users.telenet.be/d.rijmenants/en/c52tech.htm

8Primer Tratado de Amistad y Cooperacin Espaa-USA de 26-sept-1953.
http://users.telenet.be/d.rijmenants/en/c52tech.htmhttp://users.telenet.be/d.rijmenants/en/c52tech.htmhttp://users.telenet.be/d.rijmenants/en/c52tech.htmhttp://users.telenet.be/d.rijmenants/en/c52tech.htm

7/22/2019 4 e 6552603553 A

25/119



2.4.- Cifrado por homfonos

Qu entendemos por homfonos? [4] La definicin del vocablo puedeencontrarse en cualquier diccionario: "palabras de igual pronunciacin o sonido ydistinto significado" como por ejemplo hola y ola. En criptografa entenderemos

por homfonos a las distintas representaciones que damos al mismo carcterplano sin seguir ninguna relacin o funcin determinada. Por ejemplo, siestablecemos una relacin entre los 27 caracteres del alfabeto con los 100 primerosnmeros del 0 al 99, al cifrar podramos sustituir la letra A con cualquiera de lossiguientes nmeros: {1, 15, 18, 29, 50, 97}. Luego, el receptor autorizado, queconoce esta correspondencia, simplemente reemplaza dichos nmeros por la letraA para descifrar el mensaje.

En trminos matemticos, pues, una sustitucin homofnica es unacorrespondencia de uno a muchos en lugar de una correspondencia uno a unotpica de los mtodos de sustitucin monoalfabticos. Se asigna a cada letra delalfabeto original un conjunto de elementos de un alfabeto ampliado o deelementos agrupados de un alfabeto. Los subconjuntos que se asignan a cada unade las letras del alfabeto original deben ser evidentemente disjuntos[6].

La tcnica descrita da lugar a los denonimados cifradores por homfonos,cuya caracterstica principal es la de suavizar la distribucin de frecuencias tpicadel lenguaje, de forma que el criptoanalista no pueda emplear las tcnicasestadsticas aplicables en los mtodos anteriores. Asignamos, para ello, un mayornmero de homfonos a los caracteres ms frecuentes del lenguaje y un menornmero a aquellos menos frecuentes, con el objeto de que la distribucin de estos

valores se asemeje lo ms posible a una distribucin normal[4].Observamos en el ejemplo que sigue como con arreglo a la tabla de

homfonos definida, el mensaje atacar el jueves diez a las 6 horas quedarcifrado segn caracteres de cifrado 1 o de cifrado 2 o de cualquier otracombinacin que se desprenda de la tabla mostrada.

Mensaje: Atacar el jueves diez a las 6 horasTexto:

plano A T A C A R J U E V E S D I E Z A S E I S H O R A SCifrado 1 92 17 53 62 92 35 15 61 44 34 44 86 01 32 14 02 12 76 44 70 86 39 00 77 09 36Cifrado 2 78 30 92 41 33 40 15 61 46 34 74 11 03 73 14 02 09 19 55 32 11 50 99 40 53 86

Tabla de homfonos Entrada texto planoA B C D E F G H I J K L M N O P Q R S T U V W X Y Z09 48 13 01 14 10 06 23 32 15 04 26 22 18 00 38 94 29 11 17 08 34 60 28 21 0212 81 41 03 16 31 25 39 70 37 27 58 05 95 35 19 20 61 89 5233 62 45 24 50 73 51 59 07 40 36 30 6347 79 44 56 83 84 66 54 42 76 4353 46 65 88 71 72 77 86 4967 55 68 93 91 90 80 9678 57 85 99 69 7592 64 9782 748798

Cifrado por homfonos 1

7/22/2019 4 e 6552603553 A

26/119



En la tabla de arriba se observa como las letras que ms frecuencia deaparicin tienen en un texto son las que presentan ms alternativas de eleccin dehomfono.

En http://simonsingh.net/The_Black_Chamber/homophoniccipher.htm

se puede realizar una prctica de cifra homofnica automtica.El criterio para asignar los homfonos no siempre tiene que ser a travs de

una tabla cartesiana. Ms novelesco es el sistema usado en el cifrador homofnicoms conocido de la historia de la criptografa, atribuido al aventurero Thomas

Jefferson Beale, quien en 1821 dej tres mensajes cifrados, llamadosrespectivamente B1, B2 y B3, en el que supuestamente entrega todas las pistaspara descubrir un fabuloso tesoro por l enterrado en Virginia, Estados Unidos.La tcnica aplicada por Beale para formar el conjunto de homfonos del cifrado B2es sencilla pero ocurrente: asigna nmeros a los caracteres del alfabeto segn laposicin de la palabra en cuestin que comienza con dicha letra dentro del texto

de la Declaracin de la Independencia de los Estados Unidos. Se puede ampliarinformacin en[20].

2.4.1.- Cifrado homofnico de orden n>1

La fortaleza del cifrado est, pues, en la tabla o el texto que determina loshomfonos. Un cifrador por homfonos de orden n > 1 ser aquel sistema quepara cada carcter plano prevea dos o ms conjuntos posibles de caractereshomfonos [1].Un orden 2 se puede obtener, por ejemplo, a travs de la tablade homfonos 2 de ejemplo. B entrando por columna se cifrar como A2, Q5,O8, ; entrando por fila ser C2, H0, T3, .

Para el cifrado se dar una funcin que definapara cada carcter del mensaje plano cmo entrar en latabla: por fila o por columna. Por ejemplo, todo filas,todo columnas, fila, fila, columna, columna encaracteres n+3, etc. Esa funcin, junto con la tabla,deber ser conocida por el destinatario del mensaje[27].

Usando la tabla de ejemplo, se puede disear

otro cifrador por homfonos de orden 2. Definimos dostextos planos: uno V, el verdadero, otro F, falso, de la misma longitud que V.

V= atacar juevestrece(17 caracteres)

F= retirada jueves dos(17 caracteres)

El criptograma se forma con los valores de la tabla interseccin V(i) x F(i)entrando V(i) por columna y F(i) por fila.

En el ejemplo, 1 i 18 V(1)= a, F(1)= r V(1)xF(1)= H8.

En el peor de los casos, si el enemigo posee la tabla, nunca sabr cual es el

mensaje correcto[4].

A B C D

A A2 V1 X5

B C2 H0 T3

C W9 Q5 S9

D Z5 O8 R1

R H8 J2 N6 Z0 S1

Tabla de homfonos 2
http://simonsingh.net/The_Black_Chamber/homophoniccipher.htmhttp://simonsingh.net/The_Black_Chamber/homophoniccipher.htmhttp://simonsingh.net/The_Black_Chamber/homophoniccipher.htm

7/22/2019 4 e 6552603553 A

27/119



2.4.2.- Criptoanlisis de los cifrados por sustitucin con homfonos

Si ningn smbolo aparece con ms frecuencia que ningn otro, un intentode desciframiento usando el anlisis de frecuencia no parece posible. Ofrece, por

tanto, una seguridad perfecta el cifrado por homfonos?. No del todo, aunqueestos sistemas pueden llegar a ser extremadamente difciles de romper,especialmente si la asignacin de tales valores no sigue una lgica. Con una grancantidad de texto cifrado es posible encontrar algunas cadenas de nmeros osmbolos que se repiten y, por tanto, se pueden forman digramas, trigramas y enel mejor de los casos palabras y frases completas. Con suerte podremos obtener enalgunos casos la tabla de homfonos[4].

Y es que un texto cifrado, a pesar de la sustitucin, todava contiene pistassutiles. Cada letra de un idioma tiene su propia personalidad, determinada por surelacin con todas las dems letras. Por ejemplo[27]:

La Q es una letra infrecuente y, por tanto, es probable que estrepresentada slo por un smbolo, y sabemos que la u, que suponeaproximadamente el 3 por ciento de todas las letras, probablemente estrepresentada por tres smbolos. Si encontramos un smbolo en el textocifrado que slo est seguido por tres smbolos particulares, entonces serarazonable asumir que el primer smbolo representa la letra qy los otrostres smbolos representan a la u.

Otras letras son ms difciles de localizar, pero tambin las delata su relacincon las dems letras: la K, J, H y V siempre van seguidas de vocal.

En espaol, si se divide el texto en grupos de 4 letras, en cada grupo deberaaparecer una vocal.

En funcin de que se cuente con una gran cantidad de texto cifrado, sepueden asociar los nmeros ms repetidos a letras de alta frecuencia, irrellenando la matriz de homfonos y, a su vez, buscar digramas, trigramas,palabras, etc., con el objeto de obtener la matriz de cifrado.

2.4.3.- El mtodo de cinta mvil o mtodo espaol

Este mtodo consiste en un caso particular del cifrado por sustitucin con

homfonos9

. Su origen data de mediados del siglo XIX y la primera vez queaparece documentado es en 1894 en el libro Tratado de criptografa conaplicacin especial al ejrcito de Joaqun Garca Carmona [7], donde se ledenomina Mtodo Oficial de Guerra(ver Anexo E, pg.80). Poco despus, en1898, aparece en un texto de telegrafa militar de Losada con el nombre demtodo espaol[8].Segn Carmona el mtodo era utilizado en la poca de supublicacin por todos los Ministerios exceptuando el de Estado; Losada, por suparte, afirma que es el procedimiento adoptado en Espaa para cifrar losescritos oficiales.

9 El ataque y rotura de mensajes cifrados con este mtodo conociendo slo el textocifrado es el principal objetivo de este Proyecto de Fin de Carrera.

7/22/2019 4 e 6552603553 A

28/119



El criptgrafo de cinta mvil consiste en una tabla de homfonos a la quese aaden dos filas, una en la que figura el alfabeto en orden normal y en la otrase introduce una cinta mvil con un alfabeto doble totalmente aleatorio. En eldiseo original la cinta pasa a travs de dos ranuras a ambos lados de la tarjetadonde esta ubicada la clave y justo debajo del alfabeto claro, tal como muestrala siguiente figura[5]

Tabla de homfonos con cinta mvil 1

Para formar la tabla de homfonos se utilizaban nmeros de dos cifras del10 al 99 distribuidos correlativamente por filas y de manera que a cada carcterle correspondieran 3 4 nmeros [8], sin embargo, en los sistemas usadosdurante la Guerra Civil del 36 esta limitacin se cambia en algunos casos y seelimina en otros llegndose a representar todos los nmeros del 01 al 99.

El alfabeto de la cinta mvil sola generarse mediante la utilizacin de unapalabra clave. Por ejemplo, si utilizamos la palabra revolucin el alfabetogenerado podra ser, utilizando el mismo esquema que el presentado en el librode Carmona[10]

R E V O L U C I NA B D F G H J K MP Q S T W X Y Z -

Con lo que el alfabeto en la cinta quedara como,RAPEBQVDSOFTLGUHWCJXIKYNMZ

Para cifrar ambos comunicantes deban ponerse de acuerdo en lacolocacin de la cinta mvil, para ello indicaban el par de letras, la primera delalfabeto normal y la segunda de la cinta para posicionarla correctamente (en latabla de ejemplo, N en J). La definicin de la clave completa, siguiendo elejemplo, se daba con la expresin revolucin N en J. Posteriormente seproceda a cifrar utilizando el alfabeto marcado en la cinta como alfabeto base yescogiendo cualquiera de los nmeros de la columna debajo de la letra a cifrarcomo texto cifrado. Ejemplo:

Mensaje: Atacar el jueves diez a las 6 horasTexto:

plano A T A C A R J U E V E S D I E Z A S E I S H O R A SClave Revolucin N en J

cifrado 1 58 29 85 34 58 06 50 08 86 03 25 89 49 76 54 81 23 15 25 02 40 77 01 68 85 79cifrado 2 23 46 85 07 85 68 73 63 54 37 86 36 14 32 25 47 23 79 54 02 15 42 70 38 23 40

7/22/2019 4 e 6552603553 A

29/119



El ejemplo se ha confeccionado con la tabla usada en sus comunicacionespor el barco Mar Cantbrico[12] (ver Anexo F, pg.80)y la clave revolucinN en J.

Si bien el secreto depende de ir variando los nmeros usados como cifra,

lo cierto es que muy frecuentemente eran empleados los mismos nmeros pararepresentar las letras. Al cifrar el mensaje del ejemplo presentado hemosdetectado lo que para textos largos supona, creemos, el Taln de Aquiles deeste mtodo: el cifrador, por mucho cuidado que tuviera, acaba repitiendonmeros porque para cada carcter slo dispone de 3-4 homfonos posibles; lasletras de mayor frecuencia de uso acaban por no poder ser encubiertas10. En elcorto mensaje plano usado (26 letras) la a aparece 5 veces y la e 4 vecesporlo que alguno de sus homfonos es repetido (el 58 en cifrado 1, el 54 en cifrado2, por ejemplo), y esto en un mensaje de 300 400 caracteres termina pordescubrir frecuencias de uso.

Como se ve en Anexo F (pg.80)el sistema descrito no era seguido al pide la letra en 1936. Una de las primeras variaciones fue el cambio del alfabetode la primera fila. Originalmente dicha fila presentaba todas las letras en ordenalfabtico, siendo sustituida ms adelante por un alfabeto en el que las letrasaparecan en un orden aleatorio o no estaban todas. Esta modificacin yaaparece en la clave general de 15 de abril de 1910, con lo que no podemos decirque se trate de una innovacin aparecida en la guerra. Otra fue el aadir variascintas mviles como en la clave aviacin 1931 en la que las cintas eran una latpica del alfabeto mvil y dos correspondientes a dos de las filas de cdigos.Esto hacia que un mismo nmero representase a varias letras en funcin de su

colocacin y permita, tericamente, mejorar la resistencia del cdigo. Ademsse solan incluir pequeos repertorios para las claves ms comunes[10].

Lo expuesto junto a otras faltas en disciplina de transmisiones (falta deconcienciacin sobre el secreto en las comunicaciones, enviar mensajes cifradosparcialmente, uso reiterado de la misma clave, cifrado del mismo mensaje condistintas claves, etc.) haca que el sistema no proporcionara gran seguridad,sobre todo si la tabla era descubierta por el enemigo. Adems, lacompartimentacin de las zonas de operaciones que sufri sobre todo el Bando

10Eliminando, de este modo, la distribucin normal que se consigue en los sistemas desustitucin homofnica puros (ver pg.23).

Tabla de clave X (caso "Mar Cantbrico")A B C D E F G H I J K L M N O P Q R S T U V W X Y ZQ D S O F T L G V U H W C J X I K Y N M Z R A P E B

01 09 03 08 07 02 05 06 0410 14 15 17 13 19 12 18 16 11

29 27 22 20 23 26 25

30 31 35 37 33 34 32 36 38 3949 40 48 46 45 42 44 43 47 41

51 50 53 56 58 5469 67 66 65 63 61 60 62 64 68

79 70 71 72 75 77 74 73 76 7889 81 85 87 86 82

7/22/2019 4 e 6552603553 A

30/119



Rojo (en denominacin de la poca) dificultaba la actualizacin o renovacin declaves y tablas an cuando se tuviera la certeza de haber sido descubiertas porel enemigo.

Por ello es chocante que un sistema con tan poca seguridad fuese tan

ampliamente utilizado, y lo es ms cuando vemos que se utiliz en los nivelesms altos de Mando. Carmona ya avisaba de la poca seguridad del mtodo ydaba un ejemplo11de cmo descifrar un mensaje conocida la tabla pero no laclave [7]. No slo avisaba, sino que la Junta Superior Consultiva de Guerraeleva un informe al Ministro de la Guerra por el cual se le concede Cruz dePrimera Clase al Mrito Militar por el contenido del tratado que ha publicado, yen ese informe se hace eco de la inseguridad del mtodo. Lase en la siguienteimagen extracto de dicho informe[7]

Informe de la Junta Consultiva sobre la seguridad del Mtodo Espaol 1

A pesar de lo dicho, este sistema fue el mtodo ms ampliamente utilizadodurante la GC36 por los dos contendientes, si bien la mayor disciplina ycoordinacin que se estableci en el Bando Nacional en este rea de lascomunicaciones, como en casi todas las dems del esfuerzo blico, le permiti

jugar con ventaja durante los 3 aos de contienda. Como ya se ha dicho al tratarlas mquinas de rotor, para las comunicaciones el Bando Nacional adquiri diez

mquinas Enigma alemanas en noviembre de 1936 que fueron dedicadas alenlace del Alto Mando. El cifrado en escalones operativos altos y medios siguirealizndose con tabla de homfonos y cinta mvil, sistemas de sustitucin otransposicin ms elementales [10] y cdigos de trinchera como el que semuestra en pgina83.Vase en este sentido, apndice VII de[9]

11En pg. 100 de su tratado, para apoyar su crtica, presenta dos ejemplos: en el primeroparte de un mensaje que contiene partes sin cifrar, consiguiendo deducir de la relacin entreesas partes y las cifradas la tabla de homfonos; en el segundo ejemplo, totalmente encriptado,

se apoya en dicha tabla y en un anlisis de frecuencias de uso para salvar el obstculo de lacinta mvil.

7/22/2019 4 e 6552603553 A

31/119



Como curiosidad en Anexo F (pg. 80)se muestran algunos ejemplos declaves y tabla de homfonos y documentos reales utilizados durante elconflicto.

2.4.4.- Ataque al mtodo espaol: sus debilidadesHemos visto, pues, que a cada letra del mensaje origen (texto plano) le

pueden corresponder hasta 5 nmeros (

7/22/2019 4 e 6552603553 A

32/119



posibles por homfono dado que a cada nmero le podra correspondercualquiera de las 27 letras del alfabeto. Cmo reducir ese espacio de bsquedatan amplio -27 letras posibles por nmero-?:

Para abarcar mayor casustica:

a) Se estimar el nmero n de homfonos por columna entre 1 y 5 13.b) frec Ci se comparar con cada (n x frec Hj) donde 1n 5.

c) Si el texto cifrado es corto14 y, por tanto, la frecuencia de uso delhomfono puede estar algo alejada de la habitual de su letra en elidioma, admitimos un margen de fluctuacin o error Me ycomparamos (frec Ci) con (n x frec Hj Me).

d) De dicha comparacin obtenemos para cada homfono Hj unconjunto de letras candidatas L= { Ci } donde

Ci pertenece a L si existe n / (frec Ci) pertenece a [ (n x frec Hj Me ) ],siendo 1 n 5. Es decir, si frec Ci= 8,93% y (2 x frec Hj)= 9,01%, laletra Ci queda incluida en L del homfono Hj, dado que

(9,01%x 0,8) 8,93% (9,01%x 1,2)

Cmo definimos Me?

Se han hecho pruebas sobre un mensaje plano de 511 caracteres del queconocemos la tabla de homfonos y el texto cifrado; se ha podido comparar losresultados de la tcnica expuesta en los prrafos anteriores con la tabla real,buscando definir un Meeficiente. El resumen est en la tabla siguiente:

Me Acierto Cm Reduccin

10% 50,68% 6,31 76,60%

20% 84,00% 9,76 63,83%

30% 89,00% 12,05 55,35%

40% 93,00% 13,23 50,99%

50% 93,00% 14,12 47,69%

60% 93,00% 15,24 43,53%

70% 93,00% 16,52 38,81%

80% 93,00% 17,86 33,84%

90% 95,00% 19,37 28,26%100% 96,00% 21,03 22,12%

110% 96,00% 22,03 18,42%

120% 96,00% 22,23 17,66%

Anlisis de Mey media de letras candidatas 0-1

13 No slo porque la tabla pudiera tener slo 1 nmero en una columna, sino porqueaunque la tabla tuviera 5 homfonos en esa columna, el cifrado de un mensaje en particularpuede que no requiera escoger ms que un nmero de esa columna.

14No ms de 250 caracteres, como se instrua en la poca a los operadores dentro de lasnormas de seguridad a cumplir.

7/22/2019 4 e 6552603553 A

33/119



Donde:

Mees el margen que admitimos en torno a n x frec Hj para dar positiva lacomparacin de frecuencias de uso: 10%, 20%, etc.

Acierto indica el porcentaje de letras de la tabla de homfonos real que

quedan incluidas correctamente en el conjunto L de candidatos de cadahomfono. Para Me= 20%, acierto= 84%.

Cm es el cardinal medio de los conjuntos candidatos. Para Me= 20%, Cm es9,76 en la tabla.

Reduccin es el porcentaje medio en que se reduce el espacio de bsqueda.Para Me=20%, Reduccin= ( (27- 9,76) / 27 ) x 100= 63,86 %.

La grfica siguiente informa de Cm en funcin de Me

Cm en funcin de Me

0,00

5,00

10,00

15,00

20,00

25,00

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

110%

120%

130%

140%

150%

Cm

La grfica siguiente cruza Aciertocon Reduccine informa del punto

de Me ms eficiente: 20%

Rendimiento en funcin del margen

de error Me

0,00%

10,00%

20,00%

30,00%

40,00%

50,00%

60,00%

70,00%

80,00%

90,00%100,00%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

110%

120%

130%

140%

150%

Acierto

Reduccin

7/22/2019 4 e 6552603553 A

34/119



Tras lo expuesto, para cada homfono obtenemos un conjunto L de letrascandidatas que, pudiendo ser amplio (8-10 caracteres), nunca sern las 27 letrasque a priori se nos presentan como posibles para cada homfono. De estamanera podemos componer una tabla inversa de asignacin de letrascandidatas a cada homfono como la que sigue:

Homfonos 01 02 03 86 89

Letras

Candidatas

f b a rh g e x iq v dz y lj ju

xTabla inversa de homfonos 0-2

Con la tcnica descrita hemos reducido, pus, el espacio de bsqueda de27 a 10 letras de media por homfono, un 65% menos.

A partir de esta tabla inversa inicializamos el AG (ver en detalle cap 3.2pg.40).

7/22/2019 4 e 6552603553 A

35/119

Cap 3.- Mtodo Espaol: criptoanlisis con algoritmo gentico. 35/119


Cap 3.- Mtodo Espaol: criptoanlisis con algoritmo gentico.

Habiendo estudiado los sistemas de sustitucin por homfonos yanalizado en particular el Mtodo de Cinta Mvil, pasamos a plantear y

explicar la solucin que proponemos.Sobre el ncleo fundamental que supone el cdigo del Algoritmo Gentico

(ver Cap 3.1), se ha diseado un programa que interactuando con el usuariopermite definir ciertos parmetros como, por ejemplo, las listas que se usarnpara definir un diccionario en el que reconocer las palabras, la longitud mnimade las palabras a buscar. Adems, para permitir que el criptoanalista incorporesu intuicin o criterios personales, se le permite elegir cualquier cromosoma quegenere el AG15, para, a partir de l y con la utilidad desarrollada al efecto,continuar con el criptoanlisis, aceptando que hay un nivel a partir del cual elAG no mejora significativamente sus resultados, ya que la posibilidad de falsos

positivos que desvirten el resultado es muy alta16. Y ello, porque estamos anteun problema de sustitucin polialfabtica (proyeccin inyectiva); el Sr. Gascn,al dar por conocida la tabla, reduca su problema a una sustitucinmonoalfabtica, dado que la misma tabla permite tratar la proyeccin comobiyectiva an siendo, aparentemente, inyectiva17.

NivelExterno

Algoritmo

Gentico Usuario

Parmetros

Men, Cromosomas_candidatos

Nivel externo del Sistema 1

15Lo lgico ser elegir aquellos cromosomas con mejor resultado en la funcin objetivo.

16 Y al contrario, lo que pueden parecer falsos positivos, para el analista pueden tenertodo el sentido lgico: por ejemplo, palabras o caracteres componentes de un cdigo de

trinchera.17f: AB es inyectiva para todo x1, x2/ x1x2=> f(x1) f(x2)

7/22/2019 4 e 6552603553 A

36/119



El diagrama de flujo interno del programa queda definido segn elsiguiente esquema:

1

Nivel

1

Mostrar men

Men

Opcin

Opcin

2

Procesado

Automtico

Opcin = 0

3

Cargar texto

histrico

Opcin = 1

4

Analizar

frecuencias

Cromosomas

candidatos

Opcin = 2

5

Analizar texto

cifrado

Opcin = 3

6

Procesar

diccionario

7Descifrar texto

Opcin = 4

Opcin = 5

1er. Nivel interno del Sistema 1

El esquema muestra la estructura lgica del flujo interno dedicando lospuntos 3, 4, 5 y 6 a la preparacin de los datos (ver aptdos 3.2 y 3.3 siguientes) y

el punto 7 para el AG (ver aptdos. 3.4 a 3.7).

7/22/2019 4 e 6552603553 A

37/119



3.1.- Teora general sobre Algoritmos Genticos

Los algoritmos genticos (AG) son una familia de mtodos de clculoinspirados en la teora de la evolucin de las especies y la seleccin natural.Como algoritmos en s, se puede decir que son mtodos estocsticos de

bsqueda ciega de soluciones cuasi-ptimas[26].Un AG codifica informacin relativa a un problema concreto en una serie

de estructuras de datos denominadas cromosoma o genotipo. Aplicando aestas estructuras sucesivos operadores de recombinacin se puede encontraruna posible solucin al problema planteado.

Funcionamiento interno del AG

En un AG se genera un conjunto de cromosomas (cromosoma, cadasolucin planteada) compuestos por genes (o caractersticas) que representa aun conjunto de posibles soluciones o poblacin. Esa poblacin es sometida aciertas transformaciones y a un proceso de seleccin sesgado a favor de losmejores candidatos con los que se pretende obtener nuevas solucionescandidatas.

La estrategia del AG parte de una poblacin aleatoria de individuosdescritos de diversas formas mediante cromosomas y genes. A partir de esapoblacin y con los operadores de reproduccin y mutacin se genera unanueva poblacin que en general debe ser de mejores caractersticas en relacin auna funcin objetivo o fitness o de adaptacin que gua el proceso debsqueda de la mejor solucin o individuo.

La reproduccin o cruce entre individuos procura obtener nuevoscandidatos (soluciones) mejores que sus padres. La mutacinpermite realizarcambios aleatorios en individuos para obtener material gentico perdido o no

existente.

Individuo o cromosoma 1



Individuo o cromosoma n

genesPOBLACI N

Conceptos bsicos del AG 1

7/22/2019 4 e 6552603553 A

38/119



Ventajas del AG

No requieren representacin matemtica muy elaborada de los problemastratados.

Dan soluciones a problemas desahuciados mediante otras tcnicas o muy

complejos con otros mtodos. Son muy robustos frente a ruido o decisiones puntuales errneas.

Son fcilmente hibridables con otras tcnicas de Inteligencia Artificial:Redes neuronales, Lgica Borrosa.

Modularidad y portabilidad.

Ofrecen un entorno amplio para tratar muy diversos tipos de problemasque requieran optimizacin.

Criterios a implementar

"La naturaleza es sabia: cualquier animal o vegetal en sucesivasgeneraciones ha sido capaz de adaptarse a base de cambios de su forma de vidao de su estructura para sobrevivir" (Charles Darwin).

Lo que sea favorable para la supervivencia hay que conservarlo.

Lo que represente debilidad para la supervivencia hay que descartarlo.

Estructura del Algoritmo Gentico

1.Generacin de una poblacin de individuos totalmente aleatoria.

2.Evaluacin de esta poblacin siguiendo un criterio de distancia al objetivobuscado segn la funcin objetivo.

3.Aplicacin de seleccin de cualidades ms ventajosas de la poblacin.

4.Aplicacin de operadores de cruce y mutacin.

5.Resultado: poblacin siguiente con una generacin ms cercana a lasolucin.

6.Repetir desde punto 2 hasta lograr una solucin similar al objetivobuscado.

7/22/2019 4 e 6552603553 A

39/119



AlgoritmoGent

ico

Inicio

Fin

Inicio estadstico de

la poblacin

Seleccionar

individuos para

reproduccin

Producir

descendencia

Mutar descendencia

Evaluacin de la

poblacin y

bsqueda de

palabras con

impresin de

informes

Fin?

Estructura del AG 1

Origen del trmino AG

La expresin algoritmo gentico aparece por primera vez en la tesisdoctoral de J. D. Bagley "The behavior of adaptive Systems which employgenetic and correlation algorithms". Universidad de Michigan en 1967.

La teora general y su aplicacin tiene origen en el trabajo de John HenryHolland "Adaptation in natural and artificial Systems" (1975), Profesor de

Filosofa, de Ingeniera Elctrica y de Ciencias de la computacin en laUniversidad de Mchigan.

7/22/2019 4 e 6552603553 A

40/119



Un grupo de investigadores seguidores de Holland en los 80 dan un fuerteempuje (Goldberg, Baker y otros). Hoy da es una tcnica muy extendida pararesolver problemas de optimizacin, sobre todo si la funcin a optimizar tienemuchos mximos/mnimos locales. En estos casos se requerirn ms iteracionesdel algoritmo para "asegurar" el mximo/mnimo global. Tambin sonadecuados si la funcin a optimizar contiene varios puntos muy cercanos envalor al ptimo y solamente podemos "asegurar" que encontraremos uno deellos (no necesariamente el ptimo).

7/22/2019 4 e 6552603553 A

41/119



3.2.- Preparacin de los datos de entrada

Como todo sistema de informacin, para el inicio de ejecucin del AGnecesitamos unos imputs o datos de entrada. La definicin de dichos imputs serealiza en las siguientes fases:

3.2.1.- Clculo de frecuencias reales.

Obtencin de las frecuencias de uso de las letras, bigramas y trigramas queaparecen en un texto que podramos considerar como de la poca (ver enAnexo A pg.74), que nos sirva de referencia para poder evaluar la calidad delposible texto plano generado por cada cromosoma (ver aptdo. 3.7):

a. Dicho texto se lee de la carpeta Textos\ (ficheroTextoCalculoFrecuencias.txt, preparado por defecto o definidopor el usuario), y se carga en un string:

Muestra de TextoClculoFrecuencias.txt 1

7/22/2019 4 e 6552603553 A

42/119



3.Cargartexto

clculo

def

recuencias

3.1

Cargar textoTexto texto_frecuencias

Simplemente abre el archivo de texto y lo carga en un string.

Textos

Carga del texto de la poca 1

b. Se recorre el texto leyendo primero en grupos de una letra,luego dos letras y por ltimo tres letras almacenando, en un vectorV la cantidad de veces que aparece cada n-grama. Posteriormentese divide entre el total para hallar la frecuencia de cada n-grama.Para incrementar el contador por cada nueva aparicin del n-grama de manera eficiente se utiliza una funcin HASH que

trabaja en base 2718

, funcin que evita una bsqueda secuencialdentro del vector para encontrar la posicin de memoria dondealmacenar el nuevo valor del contador de iteraciones del n-gramadado.

Ejemplo de trabajo de la funcin Hash F:

ndice 0 1 2 726 727 728

bi-gramas aa ab ac ba bb bc zx Zy zz

Vector V 2 5 6 23 1 4 3 7 9

Aparece el bigrama zx. En base 27 z= 26 y x= 25.

F(zx)= 26x271+ 25x270= 726 V(726)= V(726) + 1= 4

1827 es el nmero de caracteres del alfabeto aplicado. Usamos un sistema de numeracin

en base 27, donde el cero es A y el 26 es Z (comparar con el sistema hexadecimal paracomprender).

7/22/2019 4 e 6552603553 A

43/119



4.Analizarfrecuencias

4.1

Calcularfrecuencia

letras

Texto_frecuencias

4.2

Calcularfrecuencia

bigramas

4.3

Calcularfrecuencia

trigramas

fre_letras fre_bigramas fre_trigramas

Recibe el texto_frecuencias y analiza las frecuencias de los monogramas,bigramas y trigramas

Frecuencias

Esquema de anlisis de frecuencias 1

4.1,2,3

Calcularfrecuenciangramas

7.1.1

Leer ngrama

7.1.2

Calcular

Posicin

Texto_frecuencias

letra

7.1.3

Colocar

Letra, pos

fre_letras

Recorre el texto frecuencias letra a letra, cada letra es pasada

a una funcin hash que trabajando en base 27 halla la

posicin adecuada y es almacenada en el vector.

Inicio

Leer ngrama

Potencia = 0Val = 0

Long = long(ngrama)

Pos = Long - 1

Pos >= 0

val += (ngrama[pos]

- 'a')*27^ potencia;

Potencia++

Pos--

Devolver val

Fin

Procedimiento de clculo de frecuencias 1

7/22/2019 4 e 6552603553 A

44/119



Las frecuencias resultantes sern almacenadas en ficherosindependientes en la carpeta Frecuencias\. En Anexo A (pg. 72) sepuede observar el resultado de frecuencias obtenido para los n-gramas

ms significativos.

3.2.2.- Carga del texto cifrado

Se lee el texto cifrado cargando los distintos valores numricos que lointegran y se ordenan de menor a mayor para eliminar los repetidos y facilitarlas bsquedas, de manera que obtenemos un vector numrico que se usar dereferencia a la hora de aplicar los cromosomas para poder generar un textoplano candidato con el que comparar las frecuencias cargadas anteriormente.Estos valores formarn la base de los cromosomas del algoritmo gentico. (ver

apartado 3.3)

Texto cifrado 1

Vector de Valores01 02 04 05 06 08 09 10 1112 13 14 17 18 19 21 22 24

25 27 28 29 30 32 33 35 3738 39 40 42 44 46 47 48 4951 52 53 54 56 57 58 59 6162 64 65 67 68 69 70 71 7274 75 76 77 78 79 80 81 8385 86 87 88 89 93 95

4 e 6552603553 A

Documents

Transcript of 4 e 6552603553 A