El ataque polaco al protocolo Enigma

UNIVERSIDAD DE SEVILLA FACULTAD DE MATEM ´ ATICAS TRABAJO FIN DE GRADO El ataque polaco al protocolo ENIGMA PRESENTADO POR: Roc´ıo Gallardo G´omez DIRIGIDO POR: Jos´e Mar´ıa Tornero S´anchez Sevilla, 2016 ´ Indice general Resumen 5 Abstract 7 1. Introducci´on hist´orica 9 1.1. Evoluci´on de la criptolog´ıa . . . . . . . . . . . . . . . . . . . . . 9 1.2. El origen de Enigma . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3. El origen del ataque . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4. El principio del fin de Enigma . . . . . . . . . . . . . . . . . . . 13 1.5. Unos h´eroes olvidados . . . . . . . . . . . . . . . . . . . . . . . 16 2. Descripci´on del modelo Enigma atacado por los polacos 19 2.1. Estructura f´ısica de la m´aquina . . . . . . . . . . . . . . . . . . 19 2.2. El funcionamiento de Enigma . . . . . . . . . . . . . . . . . . . 23 2.3. El procedimiento de cifrado . . . . . . . . . . . . . . . . . . . . 27 3. Resultados matem´aticos necesarios para el ataque 33 3.1. Primer intento de b´usqueda de la desencriptaci´on del c´odigo Enigma ............................... 33 3.2. El m´etodo de las permutaciones. Fundamentaci´on te´orica . . . . 35 3.3. El conjunto de ecuaciones . . . . . . . . . . . . . . . . . . . . . 47 4. El ataque, propiamente dicho 59 4.1. La caracter´ıstica . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2. M´etodos criptol´ogicos . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3. Bomba criptol´ogica . . . . . . . . . . . . . . . . . . . . . . . . . 70 ´ Indice de figuras 73 A. Referencias de figuras 75 B. Referencias por cap´ıtulos 77 Referencias generales 79 3 Resumen El principal objetivo de nuestro trabajo ser´a desvelar las claves del exitoso ataque polaco al protocolo Enigma protagonizado por Marian Rejewski. Para ello, detallaremos el contexto hist´orico en el que se produjo dicho ataque, as´ı como iremos desarrollando los diferentes m´etodos y t´ecnicas que resultaron claves para la consecuci´on de tal hito matem´atico. Comenzaremos describiendo el modelo Enigma atacado por los polacos, dando todo tipo de detalles tanto de la estructura f´ısica de la m´aquina, como del funcionamiento de la misma y el procedimiento de cifrado. Posteriormente, llevaremos a cabo una escrupulosa explicaci´on sobre los resultados matem´aticos necesarios para el ataque, basados en la teor´ıa de permutaciones. Seguidamente, ilustraremos el procedimiento que sigui´o Rejewski para efectuar la desencriptaci´on. Y, por ´ultimo, desarrollaremos el ataque, propiamente dicho, exponiendo todos los m´etodos criptol´ogicos, tanto manuales como mec´anicos, que inventaron los polacos. Palabras clave: criptograf´ıa, Enigma, Rejewski, permutaciones. Abstract The aim of our work will be to unveil the keys of the successful Polish attack to the Enigma protocol led by Marian Rejewski. In order to do so, we are going to introduce the historical context in which that attack was performed, while we develop the different methods and techniques that were vital for the success of such a mathematical milestone. After that, we will proceed to a detailed explanation of the mathematical results needed for the attack, based on permutation theory. Then, we are going to depict the procedure followed by Rejewski to carry out the decyphering. And, finally, we will describe the attack itself, expounding every cryptological method, manual and mechanical ones, that were created by the Polish cryptographers. Keywords: cryptography, Enigma, Rejewski, permutations. Cap´ıtulo 1 Introducci´on hist´orica El origen de la criptograf´ıa1se remonta a miles de a˜nos. Hist´oricamente ha estado vinculada a la protecci´on de la confidencialidad de informaciones militares y pol´ıticas, lo que conlleva la necesidad de buscar m´etodos que rompan dicha protecci´on, dif´ıcil tarea, m´as a´un sin conocimientos matem´aticos. A principios del siglo XX, la invenci´on de m´aquinas mec´anicas y electromec´anicas complejas, como la m´aquina de rotores Enigma, proporcionaron m´etodos de cifrado m´as sofisticados y eficientes. As´ı nace la criptolog´ıa2cient´ıfica, iniciada en 1949. En ´epoca de guerra se hace indispensable que en el caso de que el enemigo intercepte nuestros mensajes, no tenga manera de saber qu´e significan. Con el paso del tiempo, la criptograf´ıa se convirti´o en una pieza clave dentro de los ej´ercitos de todo el mundo. 1.1. Evoluci´on de la criptolog´ıa Desde las m´as sencillas t´ecnicas de encriptaci´on, como el Cifrado de C´esar, hasta las m´as modernas basadas en sofisticados algoritmos matem´aticos manejados por potentes ordenadores, un sinf´ın de m´etodos de cifrado se han sucedido en la historia. Algunos ejemplos de ello son3: Esc´ıtala espartana:Bast´on en el cual se enrollaba en espiral una tira de cuero donde se escrib´ıa el mensaje en columnas paralelas al eje del palo. Pod´ıa leerse volviendo a enrollar la tira sobre un palo del mismo 1Arte y t´ecnica de escribir con procedimientos o claves secretas o de un modo enigm´atico, de tal forma que lo escrito solamente sea inteligible para quien sepa descifrarlo. Proviene del griego kryptos que significa oculto, y graphia, que significa escritura. 2Disciplina cient´ıfica que se dedica al estudio de la escritura secreta, es decir, estudia los mensajes que, procesados de cierta manera, se convierten en dif´ıciles o imposibles de leer por entidades no autorizadas. Proviene del griego krypto, y logos, que significa palabra. 3Podemos encontrar m´as detalles y ejemplos en [3]. 9 Introducci´on hist´orica Unos h´eroes olvidados Alan Turing La criptograf´ıa de ese tiempo desconfiaba de los matem´aticos y, rec´ıprocamente, estos la consideraban un arte menor, pero Turing, despu´es de haber visitado los m´as ´aridos altiplanos de la teor´ıa matem´atica, bien pod´ıa rebajarse un poco por Inglaterra. As´ı que decidi´o aceptar la oportunidad de ayudar a su pa´ıs y con ello dio un paso que le otorgar´ıa una inesperada gloria militar, pero tambi´en le llevar´ıa al infierno personal m´as terrible. Su t´ecnica consisti´o en buscar lo que en criptolog´ıa se denominan puntales9. Adem´as, fue capaz de construir un modelo mejorado de la bomba polaca, al que denomin´o bombe. La combinaci´on de los estudios polacos junto con las t´ecnicas halladas por los aliados result´o ser finalmente una estrategia extraordinaria de criptoan´alisis, capaz ´unicamente de ser planificada por una mente privilegiada como la de Turing. 1.5. Unos h´eroes olvidados Tras la invasi´on germana de Polonia, una gran cantidad del BS4 fueron capturados, torturados y asesinados. Afortunadamente, Rejewski, Zygalski y R`o˙zycki pudieron abandonar el pa´ıs a tiempo y pusieron rumbo a Ruman´ıa. No obstante, lejos de querer abandonar su carrera, estos decidieron seguir con su guerra criptol´ogica en el centro de inteligencia franco-polaca10. La unidad Bruno se vio obligada a evacuar tras la amenaza de invasi´on de Alemania, por lo que nuestros protagonistas tuvieron que volver a huir, poniendo rumbo a Argel. Sin embargo, tras la rendici´on francesa, los integrantes de esta unidad decidieron crear una nueva unidad encubierta denominada Cadix. Debido al c´umulo de amenazas y con el fin de evitar sospechas, Rejewski decidi´o emplearse como profesor de matem´aticas en Nantes. Varios problemas surgieron de nuevo. Varios criptol´ogos pertenecientes a Cadix tuvieron que realizar un viaje a Argel. Cuando volv´ıan de este, el barco donde viajaban naufrag´o. Entre los 301 pasajeros que perdieron la vida se encontraron varios cript´ologos fundamentales en el trabajo contra el c´odigo Enigma, desgraciadamente uno de ellos fue Jerzy R`o˙zycki. Los alemanes volvieron a descubrir las operaciones secretas de los criptoanalistas, por lo que los miembros de Cadix tuvieron que huir de nuevo. As´ı, 9Cribs en ingl´es. 10A este centro se le denomin´o Bruno. Trabajo Fin de Grado 16 El ataque polaco al protocolo ENIGMA Rejewski y Zygalski pusieron rumbo a Espa˜na, con el infortunio de ser descubiertos tras cruzar los Pirineos. Tras esto, fueron arrestados y encarcelados. Sin embargo, pronto fueron liberados y enviados a Madrid. Cuando parec´ıa que hab´ıa llegado la tranquilidad a nuestros personajes, estos se vieron sucumbidos por la traici´on de un oficial de la inteligencia militar francesa. De este modo, fueron nuevamente capturados y enviados a un campo de concentraci´on alem´an. Tras el fin de la guerra, Rejewski regres´o a Polonia y comenz´o a trabajar como contable, Zygalski permaneci´o exiliado en el Reino Unido donde trabaj´o como profesor de estad´ıstica matem´atica en la Universidad de Surrey, y Turing, tras ser sometido a la castraci´on qu´ımica por ser homosexual, decidi´o quitarse la vida. Este fue el indecente, inmoral y deshonesto reconocimiento recibido por estos matem´aticos que, convertidos pr´acticamente en soldados, decidieron consagrar su vida en la lucha contra Enigma. Cap´ıtulo 2 Descripci´on del modelo Enigma atacado por los polacos Como hemos visto en el cap´ıtulo anterior, la m´aquina Enigma fue el c´odigo secreto utilizado por el ej´ercito alem´an para sus comunicaciones en la Segunda Guerra Mundial. Dicha m´aquina dispon´ıa de un mecanismo de cifrado rotatorio, que permit´ıa usarla tanto para cifrar como para descifrar mensajes. Realmente era una evoluci´on de otros modelos electromec´anicos que intentaba hacer m´as sencilla y automatizada la tediosa tarea de encriptar y desencriptar mensajes. Su amplio uso se debe a su facilidad de manejo y supuesta inviolabilidad. 2.1. Estructura f´ısica de la m´aquina Enigma era muy similar a una m´aquina de escribir1, con la salvedad de que se alimentaba de una bater´ıa y no empleaba papel. Aunque la m´aquina dispon´ıa de dicha bater´ıa, tambi´en pod´ıa usar la energ´ıa el´ectrica si estaba disponible. Al igual que las m´aquinas de escribir, se transportaba en la caja en la que estaba incluida. Dicha caja, de dimensiones 34cm×28cm×15cm, pesaba aproximadamente 12kg. La m´aquina Enigma fue un dispositivo electromec´anico, lo que significa que usaba una combinaci´on de partes mec´anicas y el´ectricas. El mecanismo estaba basado en una serie de teclas que accionaban los dispositivos el´ectricos y provocaban el movimiento de unos cilindros rotatorios. Dichas teclas, compuestas por las letras del alfabeto, eran realmente interruptores el´ectricos. Podemos decir que Enigma estaba formada b´asicamente por tres componentes conectados por cables que, combinados, constitu´ıan una compleja m´aquina para cifrar: un teclado para escribir cada letra del texto en claro; una unidad 1Este hecho provoc´o la confusi´on de muchos soldados cuando a finales de la guerra se encontraban con uno de estos aparatos. 19 Descripci´on del modelo Enigma atacado por los polacos Estructura f´ısica de la m´aquina modificadora formada por tres rotores, un clavijero y un reflector; y un tablero donde quedaba iluminada la letra cifrada. La supuesta inviolabilidad de la m´aquina se debe a la que hemos llamado unidad modificadora. En esta unidad se encuentran, como hemos dicho, los tres rotores, un clavijero y un reflector. Los componentes de esta unidad pod´ıan ser modificados manualmente cuando se quisiera tanto por el encriptador como por el desencriptador, de modo que, el hecho de que cualquier criptoanalista encontrase la m´aquina no era de gran importancia, puesto que lo realmente importante ser´ıa conocer dichas modificaciones de las que m´as adelante daremos detalles. Los componentes de la m´aquina Para poder entender el funcionamiento de Enigma, el cual explicaremos m´as adelante, primero necesitamos ver detalladamente cada una de las partes de las que se compone la m´aquina. Gracias a la Figura 2.1 podemos hacernos una idea de la apariencia f´ısica de Enigma. Adem´as, nos ofrece la posibilidad observar claramente cada uno de los componentes de la m´aquina de los que, a continuaci´on, daremos una escrupulosa descripci´on. Figura 2.1: Diagrama de las partes de Enigma. Trabajo Fin de Grado 20 El ataque polaco al protocolo ENIGMA Descripci´on del modelo Enigma atacado por los polacos Estructura f´ısica de la m´aquina Teclado: Estaba compuesto por 26 teclas, las correspondientes a cada una de las letras del alfabeto. La m´aquina solamente usaba 26 caracteres ya que la puntuaci´on fue reemplazada por combinaciones de diferentes letras. Algunos ejemplos de dichas combinaciones son: el espacio se sustituye con una X, la coma con ZZ y el signo de interrogaci´on con FRAGE oFRAQ2. Panel luminoso: Situado justo en frente del teclado. Al igual que este, estaba compuesto por 26 teclas (una por cada letra del alfabeto), aunque ninguna de ellas pod´ıa ser pulsada. Debajo de cada una de estas teclas hab´ıa una bombilla que permit´ıa, al final del procedimiento de cifrado, que la letra codificada se iluminase. La letra iluminada era siempre diferente de la tecla pulsada. Rotores: Fueron el principal componente de cifrado. Este conjunto estaba formado por tres rotores3que no eran sino permutaciones de las letras que actuaban consecutivamente. Cada uno de ellos era un disco de aproximadamente 10cm de di´ametro y estaban marcados con los n´umeros romanos para distinguirlos: I, II, III, ya que aparentemente eran iguales. Todos ten´ıan las letras del alfabeto situadas sobre sus bordes, aunque solo era posible apreciar algunas de ellas. Las que pod´ıan verse, situadas en el lugar que sobresale un poco, eran discos dentados que permit´ıan la manipulaci´on de los rotores. As´ı, en estos rotores era donde el operador llevaba a cabo los ajustes de la m´aquina. Cada uno de ellos ten´ıa, en una cara, 26 contactos fijos dispuestos de forma conc´entrica y, por el otro, los 26 contactos de resorte. Los contactos fijos se conectaban con los de resorte de manera irregular por cables aislados que pasaban a trav´es del coraz´on del rotor. Cada uno de los rotores se encajaba en la ranura correspondiente de forma que sus contactos de salida se conectaban con los contactos de entrada del rotor siguiente y el tercer y ´ultimo rotor se conectaba al reflector que, a su vez, un´ıa el contacto de salida del tercer rotor con otro contacto del mismo rotor para realizar el mismo proceso pero en sentido contrario y por una ruta diferente. El impulso el´ectrico pasaba de derecha a izquierda a trav´es de los cables de cada rotor. Para hacernos una idea de la apariencia f´ısica de ´estos podemos observar la Figura 2.2. 2Algunos signos de puntuaci´on fueron diferentes en otras partes de las fuerzas armadas. As´ı, la Kriegsmarine (Marina alemana), por ejemplo, sustitu´ıa la coma con la Yy el signo de interrogaci´on con UD. 3Dependiendo de la versi´on, Enigma podr´ıa tener m´as rotores. Tambi´en era posible a˜nadirlos, lo que supuso un gran alivio para los alemanes, que con el avance de la guerra vieron peligrar la seguridad de Enigma, por lo que incluyeron 2 rotores m´as. La versi´on con m´as rotores y, por lo tanto, la m´as segura era la utilizada por la Kriegsmarine, que lleg´o a tener hasta 8 rotores. La que nosotros estudiaremos, como hemos dicho, se compone solamente de 3. Trabajo Fin de Grado 21 El ataque polaco al protocolo ENIGMA Descripci´on del modelo Enigma atacado por los polacos Estructura f´ısica de la m´aquina Figura 2.2: Rotores de Enigma. Bater´ıa: Se encontraba a la derecha de los rotores y era el componente que hac´ıa funcionar la m´aquina. La potencia de dicha bater´ıa era de 4,5 voltios. Reflector: Era un elemento establecido en un ´unico eje que pod´ıa ser movido con una palanca. No era sino un producto de trasposiciones disjuntas. Esto es, emparejaba las letras dos a dos y cambiaba cada letra por su pareja. El impulso el´ectrico era devuelto por el reflector de izquierda a derecha, en sentido contrario al que pasaba a trav´es de los cables de cada rotor. Este elemento consegu´ıa que al codificar un mensaje cifrado, usando las mismas posiciones iniciales de los rotores y los mismos pares de letras interconectadas en el clavijero, se obtuviese el mensaje en claro. Aunque aparentemente el reflector parece muy ventajoso y un elemento clave en la m´aquina, dio a Enigma la propiedad de que ninguna letra ser´ıa cifrada como ella misma. Esto fue un fallo conceptual grave y un error criptogr´afico que posteriormente ser´ıa explotado por los criptoanalistas. Clavijero: Tambi´en llamado conmutador o panel Stecker4. Situado en la parte delantera de la m´aquina, debajo de las teclas, entre el teclado y el primer rotor. Era un tablero de clavijas, cada una asociada a una letra del alfabeto. Dichas clavijas estaban conectadas mediante cables que pod´ıan conmutarse. De esta forma, daban lugar a una permutaci´on que actuaba doblemente, entre el teclado y el banco de rotores y entre este y el panel de l´amparas. As´ı, cada vez que se pulsa una tecla se origina una corriente el´ectrica que circula primero por el Stecker antes de adentrarse en el banco de rotores. Tras abandonar el banco de rotores, la corriente el´ectrica pasa de nuevo por el Stecker antes de concluir su viaje en el panel luminoso, produciendo el mismo efecto que antes. Si se conectaban dos de las clavijas, las dos letras conectadas eran intercambiadas en el proceso de cifrado. El sistema de encriptaci´on que estamos estudiando 4Abreviatura de Steckerbrett que en alem´an significa “panel de conexiones de clavija”. La versi´on comercial de Enigma no estaba dotada con este dispositivo, que fue incluido en la versi´on militar con la intenci´on de aumentar la seguridad, ya que este panel contribu´ıa con m´as fuerza criptogr´afica que un rotor adicional. Trabajo Fin de Grado 22 El ataque polaco al protocolo ENIGMA Descripci´on del modelo Enigma atacado por los polacos El funcionamiento de Enigma estaba formado por 6 pares de clavijas5ostecker pairs, haciendo posible el intercambio de 12 letras. 2.2. El funcionamiento de Enigma El funcionamiento de la m´aquina, aparentemente, era bastante sencillo. El operador deb´ıa teclear las letras de su mensaje e ir anotando una a una las letras que le devolv´ıa la m´aquina iluminadas en el panel de luces. Cada vez que el operador pulsaba una tecla se enviaba un impulso el´ectrico que recorr´ıa el interior de la m´aquina. Dicho impulso hac´ıa que la corriente circulara a trav´es del clavijero, luego los rotores derecho, central e izquierdo, se refleja en el reflector y deshace su camino de nuevo a trav´es de los rotores y una vez m´as a trav´es del clavijero. Al terminar este proceso, la corriente el´ectrica concluye su viaje en el panel de l´amparas, donde una luz se encend´ıa bajo una de las letras. Aunque m´as adelante daremos m´as detalles sobre el circuito el´ectrico de Enigma, veamos antes un peque˜no esquema: Figura 2.3: Circuito el´ectrico de Enigma. Como hemos dicho anteriormente, los rotores fueron el principal componente de cifrado. Esto se debe a que la complejidad de la m´aquina reside, en gran parte, en estos elementos. Una de las razones es el hecho de que la pulsaci´on de una tecla provocaba que el primer rotor avanzase una letra en el alfabeto6. Podemos imaginar el efecto de un rotor como el de una permutaci´on en las posiciones de las letras del alfabeto, con la caracter´ıstica de que cada vez que se codifica una letra, el rotor se desplaza una posici´on y, por tanto, la permutaci´on sobre el alfabeto es distinta. Sin embargo, al codificar 26 veces una letra obtendr´ıamos su codificaci´on inicial. Se quiso evitar precisamente esa repetici´on, nunca deseada en criptograf´ıa, raz´on por la cual la m´aquina constaba de tres rotores, de manera que al codificar una letra saltaba una posici´on el rotor m´as r´apido, el que estaba situado m´as a la derecha. Una vez el rotor 5En sucesivas transformaciones de la m´aquina, con el fin de aumentar su seguridad, el n´umero de pares de clavijas utilizado lleg´o a ser de hasta 10. 6El principio original de esta idea data del siglo IV a.C. Fue un invento del romano Aeneas Tacitus. Trabajo Fin de Grado 23 El ataque polaco al protocolo ENIGMA Descripci´on del modelo Enigma atacado por los polacos El funcionamiento de Enigma derecho diera toda una vuelta, entonces giraba una posici´on el rotor central hasta llegar al menos r´apido que era el de la izquierda. Los rotores central e izquierdo giraban de forma diferente al rotor derecho, ya que adem´as de la rotaci´on ya descrita, rotaban tambi´en cuando llegaban hasta la posici´on de su propia muesca, teniendo en cuenta tambi´en que para cada nuevo movimiento del rotor central hab´ıa que esperar los 26 movimientos del rotor r´apido7. Veamos con un ejemplo lo que ocurre al presionar una tecla en el tablero. Consideremos que s´olo tenemos un rotor. Cuando se presiona, por ejemplo, la letra Bla corriente pasa a trav´es del rotor y en el panel de luz se enciende la letra A. Ve´amoslo en la siguiente imagen: Como hemos dicho anteriormente, al presionar una tecla el rotor giraba una tuerca. Por lo tanto, despu´es de presionar, la imagen que ilustrar´ıa nuestro ejemplo ser´ıa la siguiente: Una vez observado esto, veamos un ejemplo8con el abecedario al completo del camino que seguir´ıa una letra desde su tecleado hasta su cifrado. En dicho ejemplo aparecer´an cuatro bloques de dos filas cada uno. La primera fila de cada bloque se corresponde con el abecedario ordenado (puesto para ver el 7Estos movimientos podr´ıan complicarse para hacer la m´aquina a´un m´as segura incluyendo en esta un controlador para el movimiento del segundo y tercer rotor. Esto es, en lugar de que cada rotor girase cuando el anterior hubiera dado una vuelta completa, se pod´ıa hacer que el segundo rotor girara, por ejemplo, cuando Npasara por la primera posici´on en el primer rotor (y an´alogamente, escoger una posici´on concreta para el giro del tercer rotor). 8La situaci´on planteada en el ejemplo ofrece una aut´entica configuraci´on de un modelo de Enigma. Extra´ıda de: [10]. Trabajo Fin de Grado 24 El ataque polaco al protocolo ENIGMA Descripci´on del modelo Enigma atacado por los polacos El funcionamiento de Enigma ejemplo con mayor claridad), la segunda fila de los tres primeros bloques se corresponde con cada uno de los rotores y la ´ultima fila es la correspondiente al reflector. Primero veremos el caso en el que supondremos que no hay movimiento del primer rotor: ABCDEFGHIJKLMNOPQRS T U V W X Y Z EKMFLGDOVZNTOWYHXUS P A I B R C J ABCDEFGHIJKLMNOPQRSTUVW X Y Z AJDKSIRUXBLHWTMCQGZNPYF V O E ABCDEFGHIJKLMNOPQRSTUVWXYZ BDFHJLCPRTXVZNYEIWGAKMUSQO A B C D EFGHIJKLMNOPQRSTUVWXYZ Y R U H QSLDPXNGOKMIEBFZCWVJAT Nota: Las letras de color magenta representan el camino de ida a trav´es de los rotores hasta llegar al reflector y las azules representan el camino de vuelta una vez ha actuado ´este. As´ı, vemos que si pulsamos, por ejemplo R, el camino que sigue la letra es: R7−→ U7−→ P7−→ E La letra Ellegaba finalmente al reflector, donde se produce un nuevo cambio, en este caso, cambia Epor Q, y luego Qrealiza el camino inverso por los tres rotores: E7−→ Q7−→ Y7−→ V7−→ I De esta forma, Rse cifraba como I. Veamos ahora lo que ocurrir´ıa al producirse el movimiento del rotor: Trabajo Fin de Grado 25 El ataque polaco al protocolo ENIGMA R´ıgida disciplina alemana: Se empezaron a generar mensajes con formatos de texto constantemente repetidos y que identificaban f´acilmente la procedencia de los mismos. Un ejemplo de ello es la emisi´on todos los d´ıas a las 00:00 horas reportando indicativos de estaciones, frecuencias, horarios de transmisi´on, etc. Los errores antes mencionados fueron debidos a la confianza, en exceso, que los alemanes depositaron en la m´aquina. Cierto es que Enigma fue muy segura, por lo que parece l´ogico confiar en ella. Sin embargo, jam´as debieron bajar la guardia, ya que eso supuso el principio del fin de Enigma. Cap´ıtulo 3 Resultados matem´aticos necesarios para el ataque El trabajo de los polacos se bas´o fundamentalmente en el estudio de la repetici´on de patrones. Teniendo en cuenta lo expuesto al final del cap´ıtulo anterior, podemos observar que el patr´on m´as obvio de la encriptaci´on de Enigma era la repetici´on de la clave del mensaje. Este hecho les proporcion´o una v´ıa para comenzar el ataque. 3.1. Primer intento de b´usqueda de la desencriptaci´on del c´odigo Enigma Los polacos realizaron un gran avance en el estudio del funcionamiento de Enigma mediante el an´alisis de los patrones de repetici´on. Con este m´etodo llegaron a descubrir que las cadenas de caracteres cifrados estaban directamente relacionados con la posici´on de los rotores de la m´aquina1. Sin embargo, se encontraron con nuevas dificultades: el desconocimiento de la distribuci´on del cableado interno de la m´aquina y las sucesivas modificaciones de dicho cableado, producidas por los alemanes con el fin de conservar la integridad de sus comunicaciones. El punto de partida para este primer intento de ataque fue la intercepci´on de algunos mensajes por parte de las estaciones polacas de radiomonitoreo. Estos mensajes fueron usados para la reconstrucci´on de las claves de Enigma. As´ı, el objetivo era completar lo que se denomin´o tabla de relaciones que no buscaba otra cosa que relacionar todas las letras del alfabeto. Como la clave del mensaje se tecleaba dos veces, se deduc´ıa que la 1ay la 4aletra de la codificaci´on correspond´ıan a la misma letra del mensaje original. Al igual que con la 2ay la 5ay con la 3ay la 6a. De esta forma, si durante un d´ıa 1Este descubrimiento lo llev´o a cabo Marian Rejewski, matem´atico del que dimos detalles en el primer cap´ıtulo y cuyas haza˜nas fueron claves para el posterior ataque a Enigma. 33 Resultados matem´aticos necesarios para el ataque Primer intento de b´usqueda de la desencriptaci´on del c´odigo Enigma se consegu´ıan suficientes mensajes, todas las letras del alfabeto aparecer´ıan al principio de dichos mensajes. Veamos c´omo se constru´ıa dicha tabla2. El primer paso a seguir era observar las seis primeras letras de cada mensaje interceptado y estudiar su relaci´on. Si por ejemplo ve´ıamos QWERTY, que se corresponde con la codificaci´on de la clave del mensaje usando la clave del d´ıa, pod´ıamos observar que QyReran codificaciones de la misma letra. De esta forma, si tenemos, por ejemplo3, los siguientes 4 mensajes: Mensaje 1: L O K R G M Mensaje 2: M V T X Z E Mensaje 3: J K T M P E Mensaje 4: D V Y P Z X vemos que en el primer mensaje LyRest´an relacionadas, as´ı como MyX,Jy M, y DyPen los otros tres mensajes. Por lo tanto, obtendr´ıamos las siguientes relaciones: ABCDEFGHIJKLMNOPQRSTUVWXYZ PMRX El siguiente paso a seguir para la construcci´on de la tabla es interceptar el mayor n´umero de mensajes posible y, as´ı, poder completar la segunda l´ınea del ejemplo anterior, correspondiente a las relaciones de cada letra del alfabeto con su codificada. De este modo, despu´es de interceptar un gran n´umero de mensajes, la tabla de relaciones para un d´ıa determinado se completar´ıa del siguiente modo: 1aletra ABCDEFGHIJKLMNOPQRSTUVWXYZ 4aletra FQHPLWOGBMVRXUYCZITNJEASDK Cuadro 3.1: Ejemplo de tabla de relaciones. Una vez construida la tabla, el objetivo era encontrar alg´un patr´on que se pudiera deducir de ella. Estaba claro que dicha tabla era el reflejo de la disposici´on inicial de Enigma con la clave del d´ıa, por lo que era de vital importancia centrarse en estudiar esas relaciones para, as´ı, poder obtener alguna estructura que le indicara la clave del d´ıa, el anhelado objetivo. Despu´es de intentar encauzar el estudio desde diferentes puntos de vista, Rejewski se centr´o en lo que posteriormente se llamar´ıa cadenas de letras. Estas cadenas se construyen 2Para poder entender mejor el procedimiento, solo tendremos en cuenta la relaci´on de la 1aletra con la 4a. Para las dem´as el proceso es an´alogo. 3Extra´ıdo de http://portierramaryaire.com/arts/enigma 1.php. Trabajo Fin de Grado 34 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El m´etodo de las permutaciones. Fundamentaci´on te´orica de la siguiente forma: teniendo en cuenta el Cuadro 3.1, se trata de formar una cadena cerrada empezando con una letra de la fila superior, buscando su relaci´on en la fila inferior y, a su vez, volviendo a buscar esta ´ultima letra en la fila superior y su relaci´on con la fila inferior, y as´ı hasta llegar a la letra con la que comenzamos. Veamos, en nuestro caso, como quedar´ıa formada dicha cadena. Vemos en el Cuadro 3.1 que la Ade la fila superior est´a relacionada con la Fde la inferior; la Fde la superior est´a relacionada con la Wde la inferior; la Wde la superior est´a relacionada con la Ade la inferior, que es la letra con la que comenzamos la cadena, quedando, as´ı, cerrada. Por ´ultimo, Rejewski desarroll´o todas las cadenas de la tabla4, apuntando en cada una de ellas el n´umero de conexiones que ten´ıan, obteniendo lo siguiente: A - F - W - A 3 conexiones B-Q-Z-K-V-E-L-R-I-B 9 conexiones C-H-G-O-Y-D-P-C 7 conexiones J-M-X-S-T-N-U-J 7 conexiones Una vez construidas las cadenas, Rejewski observ´o que estas cambiaban cuando lo hac´ıa la clave del d´ıa, llegando a la conclusi´on de que estas cadenas eran el reflejo de la disposici´on de los rotores y que el clavijero no influ´ıa en ellas ni en sus longitudes. De esta forma, observando (2.1) vemos que ahora solo deber´ıamos preocuparnos de las 105456 claves debidas a la disposici´on de los rotores y no de los billones de claves posibles de las que nos ten´ıamos que ocupar antes. Tediosa tarea, pero ya susceptible de ser realizada manualmente. Gracias a esos estudios y a numerosas observaciones, Rejewski pronto se dio cuenta de que pod´ıa resolver su problema con teor´ıa de grupos y permutaciones. 3.2. El m´etodo de las permutaciones. Fundamentaci´on te´orica Como avanz´abamos con el t´ıtulo de este cap´ıtulo, para poder llevar a cabo el ataque se necesitaron varios resultados matem´aticos, los cuales expondremos a continuaci´on. Sea Γn={x1, x2, ..., xn}un conjunto finito de nelementos, el ejemplo de grupo finito m´as usado en la teor´ıa de grupos es el grupo de las permutaciones de Γn. 4Estas cadenas se forman sin repetir letras, es decir, comenzamos con la letra Ay formamos su cadena, si la Baparece en la cadena de A, se omite, si no formamos su cadena correspondiente, y as´ı sucesivamente. Trabajo Fin de Grado 35 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El m´etodo de las permutaciones. Fundamentaci´on te´orica Permutaciones Intuitivamente, decimos que una permutaci´on es la variaci´on del orden o de la disposici´on de los elementos de un conjunto. Es decir, podemos considerar que una permutaci´on es una reordenaci´on de elementos. Definici´on 3.2.1 Si X es un conjunto no vac´ıo, una permutaci´on de X es una funci´on biyectiva α:X→X. Definici´on 3.2.2 Si X es un conjunto no vac´ıo, el grupo sim´etrico de X, denotado por SX, es el grupo cuyos elementos son las permutaciones de X y cuya operaci´on binaria es la composici´on de funciones. Como adelant´abamos anteriormente, es de particular inter´es el caso especial en el que Xes finito. En dicho caso, siendo X={x1, x2, ..., xn}, nosotros escribiremos Snen lugar de SX, y llamaremos Snal grupo sim´etrico de grado n, o al grupo sim´etrico de nletras, teniendo en cuenta que |Sn|=n!, donde |Y|denota el n´umero de elementos de un conjunto Y. Sea Xel conjunto {1,2, ..., n}. Una forma de denotar una permutaci´on α de Xes mediante su representaci´on en una matriz de correspondencias de la forma: α=1 2 · · · n α1α2· · · αn lo cual significa que α(k) = αk. Por lo tanto, si denotamos: α=1 2 3 3 2 1  esto quiere decir que α(1) = 3, α(2) = 2 y α(3) = 1. Si, adem´as, definimos otra matriz de la siguiente forma: β=1 2 3 2 3 1  tenemos que αyβson permutaciones de {1,2,3}. Adem´as, la composici´on de permutaciones es, claramente, una permutaci´on y cumple las siguientes propiedades: Asociativa: α◦(β◦τ) = (α◦β)◦τ∀α, β, τ. Trabajo Fin de Grado 36 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El m´etodo de las permutaciones. Fundamentaci´on te´orica Existe una permutaci´on Ital que: α◦I=α=I◦α∀α. Dicha permutaci´on Ies la aplicaci´on identidad, por lo tanto cumple: I(x) = x∀x∈X. Existe una permutaci´on α−1tal que α◦α−1=I=α−1◦α∀α. Dicha permutaci´on α−1es la aplicaci´on inversa de α. As´ı, el conjunto Snde las permutaciones de Xcon la composici´on es, pues, un grupo. El producto de dos permutaciones se interpreta como composici´on de aplicaciones, por lo que escribiremos, a veces, αβ en lugar de α◦β. De esta forma, el producto de dos permutaciones cumplir´ıa lo siguiente: αβ(k) = α(β(k)),∀k∈ {1,2, ..., n}. Aunque algunos autores realizan el producto en el orden contrario, es decir, aplicando primero βy despu´es α. Los productos de estas permutaciones son5: αβ =123 321·123 231=123 213 βα =123 231·123 321=123 132 As´ı, podemos observar que αβ 6=βα. De ello se deduce que S3no es conmutativo y, por lo tanto, no es abeliano. De esta forma, podemos enunciar la siguiente proposici´on. Proposici´on 3.2.1 Si n≥3,Snno es es conmutativo. Demostraci´on. Se sigue del ejemplo anterior.  Definici´on 3.2.3 Un elemento k se denomina fijo por una permutaci´on αsi α(k) = k. Definici´on 3.2.4 Se denomina soporte de la permutaci´on al conjunto de elementos {1,2, ..., n}que no son fijos por una permutaci´on α, y se denota Aα. Definici´on 3.2.5 Sean αyβdos permutaciones, se dice que estas son disjuntas si Aα∩Aβ=∅. 5Hemos realizado estos productos de acuerdo a la definici´on anterior. As´ı, en el primer caso, por ejemplo, el producto se realizar´ıa del siguiente modo: αβ(1) = α(β(1)) = α(2) = 2; αβ(2) = α(β(2)) = α(3) = 1; αβ(3) = α(β(3)) = α(1) = 3. Trabajo Fin de Grado 37 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El m´etodo de las permutaciones. Fundamentaci´on te´orica En el caso de nuestras permutaciones anteriormente definidas, αyβ, podemos observar: Elementos fijos: en αs´olo aparece un elemento fijo: 2, y en βno aparece ninguno. Soporte: Aα={1,3}yAβ={1,2,3}. Entonces, Aα∩Aβ={1,3} ∩ {1,2,3}={1,3} 6=∅. Por lo tanto, αyβno son disjuntas. Veamos ahora un ejemplo en el que se cumpla que dos permutaciones sean disjuntas. Sean σyτlas siguientes permutaciones: σ=12345 13425;τ=12345 52341 Entonces, en este caso tenemos: Elementos fijos: en σaparecen dos elementos fijos: {1,5}, y en τaparecen tres: {2,3,4}. Soporte: Aσ={2,3,4}yAτ={1,5}. Entonces, Aσ∩Aτ={2,3,4}∩{1,5}=∅. Por lo tanto, σyτson disjuntas. Como hemos visto el producto de permutaciones no es conmutativo, en general. Sin embargo, el concepto de disyunci´on de permutaciones nos permite enunciar resultados como el siguiente. Teorema 3.2.1 Dos permutaciones disjuntas conmutan entre s´ı. Es decir, si αyβson dos permutaciones disjuntas, entonces αβ =βα. Demostraci´on. Sea k∈ {1,2, ..., n}, consideramos los siguientes casos: 1. kes un elemento fijo en αyβ. En este caso se tiene: αβ(k) = α(k) = k βα(k) = β(k) = k)=⇒αβ(k) = βα(k) Entonces, αyβconmutan para k. Trabajo Fin de Grado 38 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El m´etodo de las permutaciones. Fundamentaci´on te´orica 2. kes un elemento fijo en βy no en α. Como kes un elemento fijo en β, tenemos que β(k) = k. Supongamos que α(k) = l, con l6=k. Como lno es fijo en α, y αyβson disjuntas, entonces lser´a fijo en β. Por lo tanto, tenemos que β(l) = l. Entonces, tenemos: αβ(k) = α(k) = l βα(k) = β(l) = l)=⇒αβ(k) = βα(k) Por lo tanto, αyβconmutan para k. 3. kes un elemento fijo en αy no en β. An´alogo al anterior. Entonces, queda demostrado que αβ =βα. Uno de los problemas fundamentales cuando se estudian estructuras algebraicas es poder factorizar los elementos de la estructura en t´erminos de elementos m´as simples. En el caso de las permutaciones se pudo solventar este problema con el concepto de ciclo. Ciclos Un ciclo es un tipo especial de permutaci´on que fija cierto n´umero de elementos (quiz´as ninguno) mientras que mueve c´ıclicamente el resto. Definici´on 3.2.6 Una permutaci´on α∈Snse denomina ciclo, si existe I= {a1, a2, ..., am}∈{1,2, ..., n}tal que: Se tienen las relaciones α(ak) = α(ak+1),∀i= 1,2, ..., m−1, y α(am) = a1. Todos los elementos de {1,2, ..., n}distintos de los akson fijos para la permutaci´on α. Es decir, α(j) = j, ∀j /∈I. Definici´on 3.2.7 Sea m∈Nel n´umero usado en la definici´on anterior. Se denomina longitud del ciclo a dicho n´umero m. Definici´on 3.2.8 Sea α∈Snuna permutaci´on. Se define el orden de αcomo m´ın{k≥1 : αk=id}. Trabajo Fin de Grado 39 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El m´etodo de las permutaciones. Fundamentaci´on te´orica Nota: En el caso de los ciclos los conceptos de longitud yorden coinciden. Notaci´on: Sea αun ciclo y msu orden. Dicho orden lo denotaremos como o(α) = m. De esta forma, diremos que αes un m−ciclo. Ejemplo. En S5un ciclo de longitud 5 es 12345 23514 En S5un ciclo de longitud 2 es 12345 14325 Notaci´on: Para representar permutaciones de acuerdo con las definiciones anteriores usaremos una notaci´on c´ıclica. As´ı, denotaremos al ciclo αde longitud mpor (a1a2... am). Con esa notaci´on se tiene: (a1a2... am) = (a2... ama1) = · · · = (ama1... am−1). Ejemplo. La permutaci´on α∈S8dada por 12345678 31527486es un ciclo, se denota por α= (1 3 5 7 8 6 4 2) y su longitud es 8. La permutaci´on β∈S7dada por 1234567 5134762es un ciclo, se denota por β= (1 5 7 2) y su longitud es 4. Como adelantamos, el concepto de ciclo se utiliza, entre otras cosas, para factorizar las permutaciones. Constancia de ello se tiene gracias a un teorema que enunciaremos a continuaci´on. Teorema 3.2.2 Toda permutaci´on α∈Sn, con α6=I, se puede expresar de manera ´unica, salvo orden de los factores, como producto de ciclos disjuntos de longitud ≥2. Demostraci´on. La prueba consiste en dos etapas. Existencia: Sea α=1 2 · · · n α1α2· · · αn una permutaci´on arbitraria de Sn. Se nos presentan dos casos: Trabajo Fin de Grado 40 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El m´etodo de las permutaciones. Fundamentaci´on te´orica 1. α= 1. 2. α6= 1. Sea kun n´umero tal que α(k)6=k, construimos entonces α2(k), α3(k), α4(k), ... hasta que, siguiendo este procedimiento, volvamos a obtener k. Al n´umero de pasos que debamos realizar hasta volver a obtener klo denotaremos i+ 1. De esta forma, hemos construido el ciclo (k α(k)α2(k)· · · αi(k)), el cual describe parte de la permutaci´on α. De nuevo tenemos dos casos: a) El resto de la permutaci´on no contiene n´umeros o los n´umeros que contiene son fijos. b) El resto de la permutaci´on contiene n´umeros que no son fijos. En este caso, tendr´ıamos que repetir el procedimiento anterior con ese resto y, as´ı, sucesivamente. Tras realizar un n´umero finito de pasos se obtendr´ıa la descomposici´on. Unicidad: Supongamos que (α=ar· · · a2·a1 α=bs· · · b2·b1 son dos descomposiciones de αen producto de ciclos disjuntos. Sea k1un n´umero que es movido por α. Entonces, es evidente que k1debe estar en un ciclo y s´olo uno de {ar, ..., a2, a1}, y de igual forma, en s´olo uno de {bs, ..., b2, b1}. Como estos ciclos son disjuntos, entonces conmutan. Por tanto, podemos suponer que k1est´a en a1y en b1. Por otra parte, sabemos que los n´umeros que aparecen en a1(respectivamente b1) son fijos por el resto de los ciclos ai (respectivamente bi), entonces el elemento k1ha de transformarse en un mismo elemento k2mediante a1(respectivamente b1). Por la misma raz´on, k2debe transformarse en un mismo elemento k3mediante a1yb1, y as´ı sucesivamente. Por lo tanto, ai=bi. De esta forma, repitiendo el procedimiento, se deduce que r=sy que los ciclos aiybison iguales.  Ejemplo. Sea αla permutaci´on dada en S8 α=12345678 52763418 su descomposici´on en ciclos disjuntos ser´ıa α= (1 5 3 7) (2) (4 6) (8). Sin embargo, los ciclos de longitud 1 suelen omitirse, sobreentendi´endose que los n´umeros que no aparecen corresponden a ciclos de longitud 1. Teniendo en cuenta esto, escribir´ıamos α= (1 5 3 7) (4 6). Hemos visto que la forma de descomponer una permutaci´on como producto de ciclos disjuntos es ´unica. Esta descomposici´on no es ´unica sin la restricci´on de la disyunci´on. Sin embargo, una puede transformarse en la otra. Trabajo Fin de Grado 41 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones Π2: permutaci´on que indica c´omo cambian las letras cuando se pulsa una tecla por segunda vez. . . . Π6: permutaci´on que indica c´omo cambian las letras cuando se pulsa una tecla por sexta vez. De esta forma, observamos que desconocemos las permutaciones7de la Π1 a la Π6, pero s´ı podr´ıamos conocer las permutaciones Π4·Π1, Π5·Π2y Π6·Π3. Supongamos que tenemos como primera cabecera para un d´ıa determinado ARWSJN. Recordemos que las cabeceras son el resultado de cifrar dos veces tres letras desconocidas para el criptoanalista. Representemos con la letra Xla primera de ellas. Deducimos, entonces, que Π1transforma Xen Amientras que Π4sustituye Xpor S. Esto lo podr´ıamos expresar del siguiente modo: Π1(X) = A Π4(X) = S Recordemos ahora que el cifrado de Enigma tiene una propiedad denominada reciprocidad, es decir, se cumple que A−1=A,B−1=B, etc. En nuestro caso esto significa que si al pulsar Xobtenemos T, entonces al pulsar Tobtendremos X. Por lo tanto, tenemos Π1(A) = X. Sustituyendo Xen la otra igualdad: Π4(Π1(A)) = S. Esto es, el producto Π4·Π1transforma la letra Aen S, es decir, Π4·Π1(A) = S. De la misma forma ocurrir´a con las dem´as permutaciones. As´ı, obtenemos lo siguiente:      Π4·Π1(A) = S Π5·Π2(R) = J Π6·Π3(W) = N (3.5) Por lo tanto, con solo el principio de los mensajes es posible obtener grandes avances para la desencriptaci´on del c´odigo. As´ı, debido a la importancia de este hecho, Rejewski le prest´o especial atenci´on. Sustrajo las cabeceras de todos los mensajes de un mismo d´ıa y obtuvo listas como la que figura a continuaci´on8. Los pasos a llevar acabo para obtener las cabeceras son los siguientes: 7Dichas permutaciones deben ser representadas como producto de ciclos disjuntos. 8Este conjunto se ha obtenido mediante el simulador de Enigma de la p´agina http://enigmaco.de/enigma/enigma es.html. La configuraci´on inicial de la m´aquina ha sido la propuesta en el Cuadro 2.1 que se encuentra en la secci´on 3 del cap´ıtulo 2. Se propone para disfrute del lector averiguar el personaje mencionado en la lista de cabeceras. Para ello es necesario usar el simulador (con la configuraci´on mencionada) y descifrar las tres primeras letras de cada cabecera. Trabajo Fin de Grado 48 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones 1. Configurar Enigma de acuerdo al Cuadro 2.1. 2. Escribir tres letras al azar dos veces. 3. Volver a poner la m´aquina en la posici´on inicial9y repetir el procedimiento. De esta forma, obtenemos el siguiente conjunto: ARW SJN JRL ZJR MSM REG AAH SIQ IZR BDZ ZPT MTM TFH NXQ BVA KCI MOH RKQ ARI SJV JGC ZNP WGW LNN JKI ZGV CCW EPN MUC RQP HTN WZD MGC RNP VFH XXQ ZTN MZD BGT KNM CVC ECP XRA YJI MWQ RFF JVM ZCG DVT OCM KIM DSG DXK OWL JDJ ZMO CDT EMM FMS CRT CSH EEQ OMZ TRU NRK AJL CKW EGN JVO ZCB JKM ZGG XFV YXY MSC REP HTW WZN MXH RWQ ARL SJR JRH ZJQ RXM FWG ZZX MDA BVK KCL MCQ RPF DAW OIN MIQ RSF RST FEM MXG RWK FJH CYQ OAB TIS FTN CZD CCT EPM ORO TJB PMH VRQ QZA HDI DVI OCV ZTZ MZV NZP ADH YDD PMX DRL OJR EGC GNP XXH YWQ MCQ RPF DDP OMH DAF OIW WAC LIP SBO IHB GMG URK NZP ADH MLB RUS GQG ULK LBF QHW SND IBX PEI VOV QBD HHX KOE DKJ UAU JIE GHQ UAF YYY PVC UAI JIV XXN YWD OGO TNB EQQ GLF IJR BYZ WPS LTT ZMX MRA DVO OCB JRM ZJG CHQ EAF DSQ OEF XXN YWD CPM ETG TEE NOJ NRN AJD OGO TNB AZL SDR Cuadro 3.2: Lista de cabeceras. Teniendo en cuenta las f´ormulas de 3.5 y la tabla 3.2, podemos observar que disponemos de las suficientes cabeceras como para obtener completamente los productos de 3.5 (representados en el cuadro 3.3). ABCDEFGHIJKLMNOPQRSTUVWXYZ Π4·Π1SKEOGCUWBZDQRATVHFINJXLYPM Π5·Π2IHPMOXNASYGURBKTLJEZQCFWVD Π6·Π3ISPXJWKQVOLRGDBHFZTMEYNACU Cuadro 3.3: Los productos Π4·Π1, Π5·Π2y Π6·Π3. Procedemos ahora a factorizar los productos anteriores en ciclos disjuntos, recordando que el orden de los ciclos es indiferente debido a la conmutatividad de los ciclos disjuntos. 9Es necesario realizar este paso debido al giro del rotor derecho, el cual modifica la posici´on de dicho rotor con cada pulsaci´on. Trabajo Fin de Grado 49 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones Π4·Π1= (asibkdotn)(cegujzmrf)(h w l q)(p v x y) Π5·Π2= (a i s e o k g n b h)(c p t z d m r j y v)(l u q)(w f x) Π6·Π3= (aivycphqfwndx)(jobstmgklrzue) En las tres factorizaciones anteriores aparecen pares de ciclos de igual longitud. Esto ya se sab´ıa gracias al Teorema 3.2.7, por lo que deducimos que los tres productos consisten en trece transposiciones disjuntas. Adem´as, Rejewski, con su demostraci´on, indic´o la forma de encontrar dichas transposiciones. Explicamos el procedimiento a seguir fij´andonos, por ejemplo, en el producto Π6·Π3. Observamos que hay dos ciclos de la misma longitud. Elegimos una letra en cada ciclo y escribimos los ciclos uno debajo del otro, empezando por las letras elegidas y ordenando las letras de uno de ellos en modo inverso. Seleccionamos, por ejemplo, las letras HyK, tenemos entonces: (hqfwndxaivycp) (kgmtsbojeuzrl) Ahora, las dos letras de cada columna determinan transposiciones del segundo factor y las diagonales ascendentes proporcionan transposiciones del primer factor. Esto es: Π3: (h k),(q g),(f m),(w t), ..., (p l) Π6: (k q),(g f),(m w),(t n), ..., (l h) Al realizar la descomposici´on vemos que existen varias soluciones para cada uno de los factores buscados, ya que, variando las letras elegidas obtendremos resultados diferentes. ¿C´omo resolver el problema? Rejewski observ´o que, entre las decenas de mensajes que los alemanes se transmit´ıan diariamente, era frecuente encontrar cabeceras repetidas. Este hecho le provoc´o confusi´on. Teniendo en cuenta que hay 263= 17576 tr´ıos de letras para escoger es inusual que alg´un tr´ıo se repita en un mismo d´ıa. Por tanto, Rejewski pens´o que eso se deb´ıa al hecho de que algunos operadores eleg´ıan ternas con las tres letras iguales10. Observando el cuadro 3.2 podemos encontrar fragmentos que se repiten. Ellos son: XXNYWD yOGOTNB. Suponiendo que hemos seguido fielmente el modo de proceder de los operadores alemanes, podemos sospechar que estos fragmentos provienen de tr´ıos de letras iguales. Veamos, entonces, el m´etodo para hallar dichas letras. 10Como solo hay 26 distintas, es f´acil que se produzcan repeticiones. Trabajo Fin de Grado 50 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones 1. Consideremos primero XXNYWD. Una letra que mediante Π1se transforme en Xdebe estar en el ciclo de Π4·Π1que se empareja con el que contiene dicha X. Ese ciclo es (h w l q). De la misma forma, una letra que mediante Π2se transforme en Xdebe estar en el ciclo (l u q). An´alogamente, una letra que mediante Π3se transforme en Ndebe estar en el ciclo (jobstmgklrzue). Estos tres ciclos tienen ´unicamente una letra en com´un: L. Por lo tanto, XXNYWD ha sido originada por la terna LLL. 2. Consideremos ahora OGOTNB. Procediendo del mismo modo que en el caso anterior, los tres ciclos que obtendr´ıamos son: (cegujzmrf), (c p t z d m r j y v)y(aivycphqfwndx). La ´unica letra que tienen en com´un es la C. Por lo tanto, OGOTNB ha sido originada por la terna CCC. Para aplicar el m´etodo que describimos para obtener las trece transposiciones disjuntas y para que esta descomposici´on sea ´unica, necesitamos comenzar con un producto que est´e ´unicamente compuesto por dos ciclos de longitud trece11. Para comenzar, centraremos nuestra atenci´on en el producto Π6·Π3, el cual cumple dichas condiciones. Tenemos entonces: Π3(C) = O. Este dato permite ya determinar tanto Π3 como Π6. Para obtener sus trece transposiciones disjuntas, procedemos seg´un explicamos anteriormente: asociamos ahora la Ocon la Cy escribimos de nuevo los dos ciclos de longitud trece de Π6·Π3, uno debajo del otro y con las letras del segundo en orden inverso: (obstmgklrzuej) (cyviaxdnwfqhp) Entonces: Π3= (o c)(b y)(s v)(t i)(m a)(g x)(k d)(l n)(r w)(z f)(u q)(e h)(j p) Π6= (c b)(y s)(v t)(i m)(a g)(x k)(d l)(n r)(w z)(f u)(q e)(h j)(p o) Emparejamos ahora la Ocon la Ccon el fin de obtener Π4·Π1. Observamos que, de esta forma, solo podemos obtener 9 transposiciones12. Para calcular las otras cuatro, necesitar´ıamos emparejar letras de los otros dos ciclos. Consideremos otra vez la cabecera repetida XXNYWD. De aqu´ı se deduce: Π1(L) = X. 11Tambi´en se podr´ıa realizar si tuvi´esemos dos ciclos de igual longitud y los dem´as ciclos de longitud 1. 129 es la longitud de los dos ciclos que contienen a OyC. Trabajo Fin de Grado 51 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones Por lo tanto, ya tenemos el emparejamiento que nos faltaba: Lcon X. Solo nos falta escribir convenientemente los ciclos de Π4·Π1y, de ah´ı, obtener Π1y Π4. (otnasibkd) (l q h w) (cfrmzjuge) (x v p y) Entonces: Π1= (o c)(t f)(n r)(a m)(s z)(i j)(b u)(k g)(d e)(l x)(q v)(h p)(w y) Π4= (c t)(f n)(r a)(m s)(z i)(j b)(u k)(g d)(e o)(x q)(v h)(p w)(y l) En el caso del producto Π5·Π2ocurre algo parecido a lo anterior. Ahora solo podremos obtener 10 transposiciones emparejando gcon c. Para calcular las otras tres, necesitar´ıamos emparejar letras de los otros dos ciclos. Consideremos nuevamente la cabecera repetida XXNYWD. De aqu´ı se deduce: Π2(L) = X. Por lo tanto, ya tenemos el emparejamiento que nos faltaba: lcon x. Solo nos falta escribir convenientemente los ciclos de Π5·Π2y, de ah´ı, obtener Π2y Π5. (g n b h a i s e o k) (l u q) (c v y j r m d z t p) (x f w) Entonces: Π2= (g c)(n v)(b y)(h j)(a r)(i m)(s d)(e z)(o t)(k p)(l x)(u f)(q w) Π5= (c n)(v b)(y h)(j a)(r i)(m s)(d e)(z o)(t k)(p g)(x u)(f q)(w l) Una vez calculadas las permutaciones Πide un cierto d´ıa, es posible recuperar todas las claves de ese d´ıa. Veamos, por ejemplo, cu´al es la terna que dio lugar a la primera cabecera de nuestra lista: ARWSJN. Tenemos que Π1(A) = M, Π2(R) = Ay Π3(W) = R. Por lo tanto, dicha terna es MAR. As´ı, el primer paso hacia el criptoan´alisis de Enigma ya estaba dado, gracias al doble cifrado de las claves. Sin embargo, el hecho de conocer las claves no sirve relativamente de nada, ya que para poder descifrar los mensajes se necesitaba un ejemplar de la m´aquina con las mismas conexiones internas que las que usaban los alemanes. No obstante, a Rejewski no le hizo falta disponer de dicha m´aquina, puesto que supo c´omo deducir las conexiones de los rotores. Trabajo Fin de Grado 52 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones La reconstrucci´on del cableado Como podemos observar, con el razonamiento anterior, solo estamos teniendo en cuenta en nuestro estudio la parte correspondiente a los rotores. Sin embargo, Rejewski supo vislumbrar que todo el mecanismo de Enigma pod´ıa ser representado con permutaciones. Recordemos el funcionamiento de la m´aquina: el operario pulsaba una tecla, entonces la se˜nal el´ectrica pasaba primero por el clavijero, donde algunas letras eran intercambiadas, produci´endose as´ı la primera permutaci´on; despu´es segu´ıa su camino hasta el cilindro de entrada, donde se produc´ıa la segunda; a continuaci´on, la se˜nal el´ectrica llegaba a los rotores, pasando por ellos de derecha a izquierda y, por ´ultimo, dicha se˜nal rebotaba en el reflector e invert´ıa el orden de su camino, ilumin´andose la correspondiente letra cifrada en el panel de luces. As´ı, podemos representar el recorrido de la se˜nal el´ectrica como el producto de las siguientes permutaciones: S: permutaci´on causada por el clavijero. E: permutaci´on causada por el cilindro de entrada. N: permutaci´on causada por el rotor derecho. M: permutaci´on causada por el rotor central. L: permutaci´on causada por el rotor izquierdo. R: permutaci´on causada por el reflector. De esta forma, podemos expresar el recorrido de la se˜nal el´ectrica tanto en su camino de ida como de vuelta. Camino de ida: SENMLR Camino de vuelta: (S E N M L)−1=L−1M−1N−1E−1S−1 Cabe se˜nalar que el camino de vuelta es casi la inversa del recorrido de ida, con la excepci´on de la permutaci´on debida al reflector, que es donde se conectan los dos caminos. Por lo tanto, el efecto de pulsar una tecla se representa mediante la permutaci´on: SENMLRL−1M−1N−1E−1S−1= (S E N M L)R(S E N M L)−1 Debido a que los alemanes utilizaron el mismo tipo de reflector para todos los modelos de Enigma, se pudo conocer el resultado de la permutaci´on causada por este: R= (a e)(b j)(c m)(d z)(f l)(g y)(h x)(i v)(k w)(n r)(o p)(p u)(s t) Trabajo Fin de Grado 53 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones Otro hecho a tener en cuenta es el giro del rotor derecho. ´ Unicamente tras el giro de dicho rotor se cerraba el circuito el´ectrico. Para tomar en cuenta este movimiento debemos introducir una nueva permutaci´on especial de un ciclo que transforma cada letra del alfabeto en la siguiente; la designaremos con la letra P: P= (abcdefghijklmnopqrstuvwxyz) De esta forma, podemos decir que cuando el rotor derecho gira, se produce la permutaci´on P, luego la Ny despu´es la inversa de P, es decir, PNP−1. En el camino de vuelta, la permutaci´on ser´a la inversa de la anterior, es decir, P−1N−1P. Al pulsar por segunda vez una tecla, con el correspondiente giro del rotor, se produce la permutaci´on P2NP−2=PPNP−1P−1a la ida y P−2N−1P2a la vuelta. La siguiente figura13 nos permite seguir el recorrido de la corriente el´ectrica antes y despu´es del movimiento del rotor N. Figura 3.1: Recorrido de la corriente el´ectrica a trav´es de los componentes de Enigma. Observando la Figura 3.1, parece evidente que las permutaciones desconocidas Π1hasta Π6puedan ser representadas de la siguiente forma: 13Aclaraciones: •Rotors: Rotores (en este conjunto se incluyen el reflector, los tres rotores y el cilindro de entrada; •Commutator: Clavijero; •Glowlamps: Panel de luces; • Source of current: Fuente de corriente; •Keyboard: Teclado. Trabajo Fin de Grado 54 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones Π1=SEPNP−1MLRL−1M−1PN−1P−1E−1S−1 = (S E P N P−1M L)R(S E P N P−1M L)−1 Π2=SEP2NP−2MLRL−1M−1P2N−1P−2E−1S−1 = (SEP2N P−2M L)R(SEP2N P−2M L)−1 Π3=SEP3NP−3MLRL−1M−1P3N−1P−3E−1S−1 = (SEP3N P−3M L)R(SEP3N P−3M L)−1 Π4=SEP4NP−4MLRL−1M−1P4N−1P−4E−1S−1 = (SEP4N P−4M L)R(SEP4N P−4M L)−1 Π5=SEP5NP−5MLRL−1M−1P5N−1P−5E−1S−1 = (SEP5N P−5M L)R(SEP5N P−5M L)−1 Π6=SEP6NP−6MLRL−1M−1P6N−1P−6E−1S−1 = (SEP6N P−6M L)R(SEP6N P−6M L)−1 La primera parte de nuestra tarea consiste esencialmente en resolver este conjunto de ecuaciones. Para ello, debemos conocer S,E,N,M,LyR, ya que de este modo podr´ıamos averiguar la configuraci´on del cableado de los rotores y el reflector. Al ser estas permutaciones desconocidas, el conjunto es sin duda irresoluble. Por lo tanto, buscaremos simplificarlo. El primer paso es puramente formal y consiste en reemplazar el producto repetido MLRL−1M−1 por una sola letra Q; de este modo quedan reducidas temporalmente el n´umero de inc´ognitas a 4, las denominadas E,S,NyQ. As´ı, tenemos: Π1=SEPNP−1QPN−1P−1E−1S−1 Π2=SEP2NP−2QP2N−1P−2E−1S−1 Π3=SEP3NP−3QP3N−1P−3E−1S−1 Π4=SEP4NP−4QP4N−1P−4E−1S−1 Π5=SEP5NP−5QP5N−1P−5E−1S−1 Π6=SEP6NP−6QP6N−1P−6E−1S−1                    =⇒ =⇒     Π4·Π1=SEPNP−1QPN−1P3NP−4QP4N−1P−4E−1S−1 Π5·Π2=SEP2NP−2QP2N−1P3NP−5QP5N−1P−5E−1S−1 Π6·Π3=SEP3NP−3QP3N−1P3NP−6QP6N−1P−6E−1S−1 Trabajo Fin de Grado 55 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones Llegado a este punto, Rejewski no conoc´ıa a´un siquiera si la ecuaciones que dan Π1, Π2, Π3, Π4, Π5y Π6resultaban ser despejables para obtener S,E,N yQ. Dichas ecuaciones podr´ıan ser resueltas si dispusi´eramos de mensajes de dos d´ıas diferentes, en los cuales las conexiones del clavijero fuesen diferentes, pero los rotores estuvieran en las mismas posiciones. Algo que era muy poco probable que ocurriese. Es aqu´ı cuando tuvo importancia la aparici´on del esp´ıa alem´an Hans Thilo Schmidt, del que hablamos en el primer cap´ıtulo. Fue en este momento cuando Rejewski se apoy´o en los documentos proporcionados por Hans. As´ı, adem´as de las permutaciones Π4·Π1, Π5·Π2y Π6·Π3(obtenidas mediante radioescucha) y las Π1, Π2, Π3, Π4, Π5y Π6(deducidas por los criptoanalistas polacos), ahora se conoc´ıan tambi´en las permutaciones SyE(esta ´ultima se dio por supuesta). De esta forma tenemos ahora14:                    E−1S−1ASE =PNP−1QPN−1P−1 E−1S−1BSE =P2NP−2QP2N−1P−2 E−1S−1CSE =P3NP−3QP3N−1P−3 E−1S−1DSE =P4NP−4QP4N−1P−4 E−1S−1ESE =P5NP−5QP5N−1P−5 E−1S−1FSE =P6NP−6QP6N−1P−6 Ahora solo tenemos las inc´ognitas NyQ. Por lo tanto, definimos ahora nuevas permutaciones, denominadas U,V,W,W,YyZ, del siguiente modo:                    U=P−1E−1S−1ASEP =NP−1QPN−1 V=P−1E−1S−1BSEP =NP−2QP2N−1 W=P−1E−1S−1CSEP =NP−3QP3N−1 X=P−1E−1S−1DSEP =NP−4QP4N−1 Y=P−1E−1S−1ESEP =NP−5QP5N−1 Z=P−1E−1S−1FSEP =NP−6QP6N−1 Una vez obtenidas estas permutaciones, Rejewski calcul´o las permutaciones compuestas UV ,V W,WX,XY eY Z, resultando: 14Multiplicando Π1, Π2, Π3, Π4, Π5y Π6por: E−1S−1por la izquierda. SE por la derecha. Trabajo Fin de Grado 56 El ataque polaco al protocolo ENIGMA Resultados matem´aticos necesarios para el ataque El conjunto de ecuaciones                UV =NP−1(QP−1QP)PN−1 V W =NP−2(QP−1QP)P2N−1 WX =NP−3(QP−1QP)P3N−1 XY =NP−4(QP−1QP)P4N−1 Y Z =NP−5(QP−1QP)P5N−1 Ahora, despejando (QP−1QP) de una de las ecuaciones anteriores e introduci´endolo en las otras, obtenemos:          V W =NP−1N−1UV NPN−1 WX =NP−1N−1V WNPN−1 XY =NP−1N−1WXNPN−1 Y Z =NP−1N−1WY NPN−1 donde la ´unica inc´ognita es la permutaci´on NPN−1. As´ı, para un mismo d´ıa se podr´ıan obtener decenas de soluciones para V W,WX,XY eY Z, todas con una estructura com´un. Adem´as, empleando el m´etodo usado para obtener Π1, Π2, Π3, Π4, Π5y Π6partiendo de los productos Π4·Π1, Π5·Π2y Π6·Π3, podemos determinar NPN−1partiendo de WX, obteniendo tambi´en distintas soluciones. Tambi´en podemos obtener varias soluciones a partir de WX, y ´unicamente existe soluci´on id´entica para V W yWX. Del mismo modo, se puede obtener Na partir de NPN−1. Para ello basta con aplicar una de las 26 permutaciones Pque existen para obtener N15. Todo este estudio fue un logro. Sin embargo, Rejewski tuvo un error al principio de su estudio, el hecho de considerar la permutaci´on Econocida, es decir, la suposici´on de que dicha permutaci´on era la misma que la de la Enigma comercial. No obstante, una vez m´as, Rejewski supo resolver este problema. Consider´o Ecomo la permutaci´on alfab´etica. Esto es, supuso que las teclas se unir´ıan mediante cables al cilindro de entrada siguiendo el orden ABCDE.... Una vez supuesto esto, Rejewski lo prob´o, obteniendo gran ´exito al resultar correcta dicha hip´otesis. A todo este estudio debemos a˜nadir dos complicaciones m´as. Rejewski no hab´ıa tenido en cuenta hasta ahora que no solo el rotor derecho giraba con cada pulsaci´on, sino que tambi´en lo hac´ıan, en intervalos menos frecuentes, los rotores central e izquierdo. Adem´as, hay que sumar el hecho de que el orden de estos rotores pod´ıa ser cambiado. 15Parece apropiado mostrar c´omo los resultados te´oricos anteriores se aplican en la pr´actica para obtener las conexiones internas del rotor N. Un ejemplo de ello lo podemos encontrar en [6]. Trabajo Fin de Grado 57 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho M´etodos criptol´ogicos 1. La permutaci´on Ses la identidad. 2. La distribuci´on inicial de los anillos de los rotores es la misma. 3. Conocemos el orden en el que se establen los rotores. entonces bastar´ıa con establecer los rotores en la posici´on RTJ y, a continuaci´on, pulsar tres veces seguidas la tecla W. As´ı, la misma luz se encender´ıa. Lo mismo ocurrir´ıa con las posiciones DQY yHPN. De esta forma, podemos ver que el ajuste de los anillos hace que las posiciones de los rotores pasen a ser desconocidas. Sin embargo, las diferencias en las posiciones se mantendr´an y, por tanto, pasar´an a ser conocidas. Gracias a lo deducido anteriormente, podemos concluir que, como la longitud de los ciclos en las permutaciones Π4·Π1, Π5·Π2, Π6·Π3es invariable respecto a las transformaciones producidas por la permutaci´on S, la aparici´on o no aparici´on de female en los productos era invariable respecto a estas transformaciones. Recordemos que el objetivo fundamental del trabajo criptol´ogico consist´ıa principalmente en identificar correctamente el orden de cada uno de los rotores y la configuraci´on del anillo entre las 105456 posibles configuraciones. Dado que el 40 % de las permutaciones Π4·Π1, Π5·Π2, Π6·Π3contiene ciclos de longitud uno, el n´umero anterior se reduc´ıa en un factor de 0,4 cada vez que aparec´ıa uno de estos ciclos. Por tanto, como 105456·0,412 = 1,7 es muy posible que doce o trece females determinen de manera un´ıvoca el orden de los rotores y el Ringstellung. Usando la teor´ıa de probabilidades se deduce que, si las permutaciones Πi y el Grundstellung se eligen aleatoriamente, el 11,5 % de las cabeceras presentar´an females. Esto implica que se requiere de poco m´as de un centenar de mensajes para obtener una docena de ellas, cantidad factible de ser alcanzada en algunas de las redes de comunicaciones del Ej´ercito alem´an. Por tanto, es posible determinar el orden de los rotores y el Ringstellung a partir de las females. En consecuencia, ahora ser´ıa necesario crear un cat´alogo de females para los 17576 productos posibles y compararlos con las females presentes en las claves del mensaje durante un determinado d´ıa. 4.2. M´etodos criptol´ogicos La dificultad de la anterior tarea radica en la realizaci´on de las comparaciones. Esta labor, a menos que se disponga de tecnolog´ıa, engloba muchas dificultades. Sin embargo, a Zygalski se le ocurri´o un ingenioso m´etodo para llevarla a cabo. Trabajo Fin de Grado 64 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho M´etodos criptol´ogicos Hojas de Zygalski El m´etodo de las hojas de Zygalski, basado en la repetici´on de females, result´o ser bastante efectivo, aunque rudimentario. Para cada uno de los ´ordenes posibles de los rotores y para cada una de las posiciones del rotor izquierdo, se confeccionaron unas hojas como las que podemos ver en la Figura 4.3. Dichas hojas, de material bastante grueso, se clasificaron en paquetes, donde cada uno de ellos representaba una posible configuraci´on de los rotores. Por tanto, hizo falta construir 6 ×26 = 156 hojas. Figura 4.3: Hoja de Zygalski. En cada una de las hojas se dibuj´o un peculiar sistema de coordenadas en el que los ejes marcaban las sucesivas posibles posiciones de los rotores central y derecho. As´ı, tanto en las abcisas como en las ordenadas se rotularon todas las letras del alfabeto, comenzando por la esquina superior izquierda. Las letras horizontales representaban las posiciones del rotor central y las verticales las del derecho. Este sistema de coordenadas, que delimitaba un recuadro en la hoja, se dividi´o en 51 ×51 cuadrados peque˜nos. Cada uno de ellos representaba una permutaci´on para esa determinada posici´on de los rotores. Si en dicha posici´on se hallaba una 1,4−female11, el recuadro correspondiente ser´ıa perforado. 11Recordemos que las hojas se construyeron en base a las posiciones del rotor izquierdo. Trabajo Fin de Grado 65 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho M´etodos criptol´ogicos Antes de emplear las hojas es preciso realizar un proceso de “normalizaci´on” a las 2,5−y 3,6−females. Este proceso consiste en adelantar una posici´on el Grundstellung de las 2,5−female y dos posiciones el de las 3,6−female. Ejemplo. Usando el ejemplo de la secci´on 4.1.2, la normalizaci´on consistir´ıa en lo siguiente: DQY DWJMWR=⇒DRY DWJMWR HPNRAWKTW=⇒HPPRAWKTW Realizada la normalizaci´on, el siguiente paso a realizar ser´ıa repetir el proceso anterior para cada orden de los rotores y cada posici´on del Ringstellung correspondiente al rotor izquierdo. A continuaci´on, una vez fijado el orden de los rotores, se procede a normalizar de nuevo aquellas females cuyo Grundstellung indique un avance del rotor central. Ejemplo. Supongamos lo siguiente: El orden de los rotores es III I II. El Grundstellung es REJ. Dicho Grundstellung debe ser normalizado a RFJ, ya que la Jes la letra que provoca en el rotor III un avance del rotor situado inmediatamente a su izquierda, en este caso el rotor central, donde se encuentra el I. Seguidamente, se seleccionan las 26 hojas asociadas al orden de los rotores establecido y se aparta el resto. Ahora, fijada una letra del Ringstellung del rotor izquierdo, se considera el Grundstellung de una primera female. Ejemplo. Consideramos lo siguiente: Fijamos la letra Ren el Ringstellung del rotor izquierdo. Tenemos, entre otras, las 1,4−females TUR yZYG. Tenemos que T - R = C, por lo tanto, usaremos la letra Ccomo patr´on b´asico sobre el que comenzar a trabajar. Escogemos la hoja correspondiente a dicha letra y la colocamos encima de una mesa transparente iluminada por debajo. Seguidamente, tomamos la otra 1,4−female:ZYG. Como Z - R = I, seleccionamos la hoja correspondiente a I y la colocamos sobre el patr´on b´asico representado por la letra C, desplaz´andola 22 cuadros hacia la derecha12 y 11 cuadros hacia abajo13. Una vez realizado el proceso descrito en el ejemplo anterior, repetimos la operaci´on con el resto de females. Tras colocar todas las hojas, se hace actuar 12De la Ya la Uvan 22 letras. 13De la Ga la Rvan 11 letras. Trabajo Fin de Grado 66 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho M´etodos criptol´ogicos un foco de luz sobre ellas y se observa si la luz traspasa alg´un agujero com´un a todas ellas. Si se consigue una cantidad suficiente de females, el haz de luz atravesar´a un ´unico agujero. Dicho agujero proporcionar´a de manera inmediata el orden de los rotores y el Ringstellung del rotor izquierdo. Llegados a este punto, el trabajo se centrar´ıa en conseguir el Ringstellung de los otros dos rotores. Para ello, se observ´o que, fijada una de las females (normalizada previamente si era necesario), las letras del agujero de la hoja correspondiente determinaban la posici´on de los rotores que hab´ıan producido dicha female. Dicha posici´on era precisamente la diferencia entre el Grundstellung de la female y el Ringstellung que se pretend´ıa obtener, ergo para obtener el Ringstellung de los rotores central y derecho bastaba con restar al Grundstellung de una female las letras del agujero. El trabajo anteriormente expuesto, aparte de consumir much´ısimo tiempo, result´o ser bastante tedioso, ya que, entre otras cosas, cada female deb´ıa ser perforada hasta cuatro veces. Sin embargo, los criptoanalistas tuvieron una observaci´on que reducir´ıa en gran medida dicho trabajo. Esta observaci´on se recoge en el siguiente comentario realizado por Rejewski14: “Cuando las hojas de papel estaban situadas una sobre la otra de acuerdo a un programa precisamente definido, en el orden adecuado y desplazadas propiamente una respecto a la otra, el n´umero de perforaciones disminu´ıa gradualmente. Si dispon´ıamos de un n´umero adecuado de claves con ciclos de longitud uno, al final una misma perforaci´on aparecer´ıa en todas las hojas de papel, probablemente correspondiendo a un buen caso”. As´ı, se puede deducir que, teniendo un cantidad suficiente de datos, finalmente obtendr´ıamos la soluci´on. Adem´as, a partir de la posici´on de la perforaci´on mencionada en el comentario, se podr´ıa calcular el orden de los rotores y la disposici´on de sus anillos. Y, comparando las letras del cifrado de la clave con las letras de la m´aquina, podr´ıamos deducir, de la misma forma, la permutaci´on S. En otras palabras, obtendr´ıamos la clave completa del cifrado. Finalmente, faltar´ıa obtener las conexiones del Stecker. Recordemos que este no cambiaba la estructura de los ciclos, sino que ´unicamente alteraba las letras de los mismos. Por consiguiente, en este caso, el Stecker cambiaba las letras de los ciclos de longitud uno del cat´alogo de caracter´ısticas por las letras repetidas de las females. As´ı, la letra repetida de una female estar´ıa conectada con una de las letras de los ciclos de longitud uno de la correspondiente permutaci´on Π4·Π1del cat´alogo. De este modo, contemplando todas las females al mismo tiempo, no ser´ıa dif´ıcil averiguar de qu´e letra se trataba. 14Extra´ıdo de: [5]. Trabajo Fin de Grado 67 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho M´etodos criptol´ogicos Adem´as de la dificultad del trabajo tenemos que considerar una dificultad a˜nadida. Se podr´ıa dar el caso de que el haz de luz atravesase m´as de un agujero. Si este hecho se daba, se proced´ıa a realizar las anteriores operaciones con cada uno de ellos, y las contradicciones descartar´ıan casi todos los casos. Si, a´un as´ı, seguimos teniendo m´as de uno, elegir´ıamos como soluci´on correcta aquella que permitiese descifrar los mensajes. De forma adicional al trabajo realizado por Zygalski, R`o˙zycki dise˜n´o un m´etodo para identificar el rotor derecho. M´etodo del reloj El m´etodo del reloj desarrollado por Jerzy R`o˙zycki hac´ıa posible determinar, en ocasiones, cu´al de los rotores ocupaba la posici´on del rotor derecho15, bas´andose fundamentalmente en las caracter´ısticas propias del lenguaje alem´an, es decir, en la frecuencia de aparici´on de las letras de su alfabeto. Veamos un ejemplo para observar en qu´e consist´ıa dicho m´etodo. Ejemplo. Supongamos que tenemos los siguientes textos16 en alem´an: BEGINNDESUNEINGESCHR¨ ANKTEN... SIEWERDENDENPR¨ ASIDENTENSOG... Observando las letras marcadas, podemos deducir que de media existir´a una probabilidad de coincidencia de letras en ambos textos de 2/26. Debemos esperar que esta caracter´ıstica se repita con textos cifrados mediante una clave id´entica. Sin embargo, si se encripta cada texto utilizando una clave distinta17, resultar´ıa: NWTDTYBXYFTTAAARJEPJPEUPOY... SIEWERDENDENPRASIDENTENSOG... En este caso aparecen 3 letras marcadas, por lo que de media la probabilidad de coincidencia ser´a 3/26. El hecho de la diferencia de probabilidad entre el texto en claro y el cifrado se debe a la distinta frecuencia de aparici´on de las letras en idioma alem´an. En un lapso de 26 letras este hecho no ocurrir´a demasiadas veces. Si por el contrario se dispusiera de dos mensajes de 260 letras, con este m´etodo se podr´ıa diferenciar, normalmente, si dos mensajes hab´ıan sido cifrados con la misma clave o con diferente. Por tanto, si se dispon´ıa de una cantidad suficiente 15Este m´etodo cobr´o vital importancia en el momento en el que los alemanes decidieron comenzar a cambiar el orden de los rotores cada d´ıa. 16Corresponden al telegrama Zimmermann. Extra´ıdo de [11]. 17Han sido encriptados, mediante el simulador, con las claves TUR yREJ y las conexiones AT DS IJ MO WZ XY del Stecker. Trabajo Fin de Grado 68 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho M´etodos criptol´ogicos de material cifrado, en general, se podr´ıa encontrar una docena de pares de mensajes tales que en cada pareja las primeras dos letras de las claves eran id´enticas y las terceras diferentes. Entonces se proced´ıa a escribir el mensaje uno encima del otro. Exist´ıan dos formas de escribir los mensajes uno sobre el otro, dependiendo de la posici´on que ocupara el rotor derecho tras producirse el desplazamiento del central. Dichas posiciones eran conocidas y diferentes para cada uno de los rotores. Ejemplo. Supongamos que tenemos las Spruchschl¨ussels TFG yTFP, las cuales coindicen en sus dos primeras letras. Diferenciemos casos para ver lo que ocurrir´ıa para cada posici´on del rotor derecho. 1. El rotor de la derecha es el I. El rotor Ihace avanzar al de su derecha en el momento en el que la Tde su anillo se hace visible en la ventanilla del rotor. Entonces de TFT se pasa a TFU. Por tanto, partiendo de TFG nunca se llega a TFP. 2. El rotor de la derecha es el II. An´alogo al anterior, ya que de TFG se pasar´ıa a TGH. 3. El rotor de la derecha es el III. En este caso de TFG se llega a TFP al cabo de 9 pasos. Ya que para que se produzca el avance del rotor vecino, el rotor derecho debe llegar hasta la posici´on O. Por tanto, en este caso: a) La d´ecima letra del mensaje que arranca con TFG se cifra con la misma permutaci´on que la primera letra del mensaje que parte con TFP. b) An´alogamente, la und´ecima se cifrar´a con la misma que la segunda. c) Lo mismo ocurrir´ıa con el resto. Por tanto, colocando los criptogramas uno debajo del otro y desplazando el segundo 9 lugares18, el n´umero de letras coincidentes ser´a el mismo que el de los textos en claro. En el idioma alem´an el porcentaje de coincidencias es de 7,6. Luego, si el porcentaje de coincidencias se aproxima a ese n´umero, muy probablemente estemos en el caso en el que el rotor derecho es el III. Si, en cambio, el porcentaje ni se acerca a ese valor, el rotor derecho ser´a el Io el II. En ese caso, probar´ıamos el mismo procedimiento con otro par de Spruchschl¨ussels con las dos primeras letras iguales. Para cubrir la necesidad de calcular las posiciones de los rotores central y derecho a partir del m´etodo del reloj, se desarroll´o otro, el denominado m´etodo ANX. 18Para que su primera letra quede debajo de la d´ecima del primero. Trabajo Fin de Grado 69 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho Bomba criptol´ogica M´etodo ANX El m´etodo ANX surgi´o a partir de la observaci´on de los mensajes en claro de los que dispon´ıan los polacos. Recordemos que dichos mensajes fueron descifrados gracias a las Tageschl¨ussels proporcionadas por Asch´e. Los criptoanalistas descubrieron que el texto en claro de muchos mensajes alemanes empezaba por ANX19. Por tanto, una vez determinada la posici´on del rotor derecho en un mensaje que comience con ese trigrama, la de los otros dos rotores se puede obtener mediante la utilizaci´on del cat´alogo de caracter´ısticas. Adem´as de los m´etodos anteriormente descritos para la reconstrucci´on de las claves, fueron usados otros dispositivos mecanizados para cubrir la necesidad que iba surgiendo en distintas ocasiones. Entre ellos se encuentra la bomba criptol´ogica, la ´ultima aportaci´on de Rejewski. 4.3. Bomba criptol´ogica El m´etodo de la “bomba criptol´ogica”20 consiste mayormente en la automatizaci´on y aceleraci´on del proceso de reconstrucci´on de las claves diarias. Su apariencia f´ısica la podemos ver en la Figura 4.421. Figura 4.4: Bomba criptol´ogica. 19En alem´an AN significa para y la Xera usada para separar palabras. 20Se dice que a Rejewski se le ocurri´o la idea de este m´etodo mientras com´ıa un t´ıpico helado en forma de esfera llamado bomba, de ah´ı ese nombre. 211. Rotores; 2. Motor el´ectrico; 3. Interruptores. Trabajo Fin de Grado 70 El ataque polaco al protocolo ENIGMA El ataque, propiamente dicho Bomba criptol´ogica Esencialmente, la bomba de Rejewski es un aparato electro-mec´anico basado en la combinaci´on de tres cicl´ometros conectados convenientemente y un motor el´ectrico que hace girar de forma sincronizada los seis bancos de rotores recorriendo las 17576 posibles posiciones. Dado que los rotores pod´ıan ser colocados de seis formas diferentes, fue necesario construir seis bombas, una para cada orden. De esta forma, con cada mensaje interceptado, se desarrollaba una tabla de relaciones (como la que aparece en el cuadro 3.1) para encontrar las cadenas resultantes, y con estas se acud´ıa al cat´alogo, encontrando, as´ı, la disposici´on de los rotores de la clave del d´ıa. Por tanto, el ´unico problema restante era el de conocer las conexiones del Stecker. Para resolver el problema del clavijero, Rejewski actu´o de la siguiente forma: una vez conocida la disposici´on de los rotores, quitaba todos los cables y comenzaba a teclear el texto del mensaje. Frecuentemente el resultado obtenido era un galimat´ıas, puesto que se desconoc´ıa las conexiones del clavijero. Sin embargo, cuando se consegu´ıan textos muy parecidos a algo razonable, se deduc´ıa f´acilmente qu´e letras estaban intercambiadas. As´ı, con una cantidad suficiente de material cifrado, era posible deducir todas las posiciones del clavijero. Ejemplo. Supongamos que obtenemos el mensaje INVADIT PELENIA. De aqu´ı se deduce f´acilmente que el mensaje original ser´ıa INVADIR POLONIA. Por lo tanto, en este caso, se ve´ıa claramente que RyThab´ıan sido intercambiadas, as´ı como OyE. Previamente a la utilizaci´on de estos aparatos, era necesario ajustar adecuadamente las posiciones de los rotores correspondientes a los cicl´ometros. Para ello, primero se deber´ıa normalizar las females a trav´es del m´etodo explicado en la secci´on 4.2.1. Hecho esto, se asociaba cada uno de los tres cicl´ometros a una female y se colocaban sus rotores en la posici´on indicada en el Grundstellung, con el rotor derecho del segundo conjunto desplazado tres posiciones respecto a su correspondiente del primer conjunto. Veamos el procedimiento que segu´ıa la bomba mediante el siguiente ejemplo. Ejemplo. Supongamos que disponemos de tres females para un d´ıa determinado en las que se presentan las mismas letras repetidas22. RTJ WAHWIK DQY DWJMWR HPN RAWKTW La primera de estas females indica que el ciclo West´a presente en la permutaci´on Π4·Π1. Supongamos que la Wno se ve alterada por el Stecker, es decir, 22Tomamos las mismas que usamos en el ejemplo de la secci´on 4.1.2. Trabajo Fin de Grado 71 El ataque polaco al protocolo ENIGMA que no est´a intercambiada con ninguna otra letra. Entonces, tambi´en el ciclo Waparece en la permutaci´on Π4·Π1que se obtendr´ıa sin ninguna conexi´on del Stecker. Como ya sabemos, el n´umero de tales productos Π4·Π1es 105456, tantos como configuraciones posibles de los rotores (orden y posiciones iniciales). Ahora bien, desconocemos cu´antos de estos productos contienen al ciclo W. No obstante, recordemos que la teor´ıa de probabilidades muestra que, fijado un ciclo de longitud 1, si Π1y Π4se eligen aleatoriamente entre las de su clase, entonces el 4 % de los productos Π4·Π1contienen dicho ciclo. Admitamos esta regla para las sustituciones de Enigma. Entonces, el anterior n´umero se reduce en un factor de 0,04 cada vez que se observe una female con la letra Wrepetida. Como 105456 ·0,043= 6,75, resulta que muy probablemente tan solo seis o siete configuraciones de los rotores pueden ocasionar las tres females anteriores. El objetivo de la bomba era, por tanto, automatizar la identificaci´on de las configuraciones de las que habl´abamos en el ejemplo del siguiente modo: en el momento en el que los tres cicl´ometros que componen la bomba reconocen el ciclo W, el mecanismo se detiene mostrando posici´on. En nuestro ejemplo, los rotores del cicl´ometro asociado a la primera female deben colocarse del siguiente modo: el primer conjunto en la posici´on RTJ y el segundo en la RTN. Tras situar los rotores se activa la palanca de la letra W y se pone en marcha la bomba. Las seis bombas encontrar´ıan las seis o siete posiciones posibles que ocasionaban las tres females y, entre ellas, se hallar´ıa la que proporcionaba la clave. Para poder conocerla era necesario aplicar el m´etodo de las hojas de Zygalski. Este m´etodo, aunque provoc´o que una gran cantidad de personas se dedicaran a ´el, congregando a alrededor de 100 trabajadores, hizo que se acortara el tiempo para la obtenci´on de la clave a aproximadamente dos horas. Cuando parec´ıa que los polacos ya hab´ıan logrado descifrar la m´aquina y que no les supondr´ıa ning´un impedimento desencriptar los mensajes que los alemanes se enviaban, surgieron nuevos problemas. Los alemanes introdujeron dos rotores m´as, incrementaron las conexiones del clavijero de seis a trece pares y el n´umero de redes de comunicaciones de radio alemanas tambi´en creci´o. Debido a todo ello, los m´etodos anteriormente descritos quedaron inservibles, ya fuese por la falta de presupuesto, personal o la inoperancia de estos. Para m´as a˜nadidura, tal y como mencion´abamos en el cap´ıtulo 1, Polonia lleg´o a encontrarse duramente amenazada por los alemanes. Este c´umulo de acontecimientos provoc´o la b´usqueda de aliados (franceses y brit´anicos) que pudieran aprovechar los trabajos realizados por los polacos. ´ Indice de figuras 1.1. Patente americana de Enigma. . . . . . . . . . . . . . . . . . . . 11 2.1. Diagrama de las partes de Enigma. . . . . . . . . . . . . . . . . 20 2.2. RotoresdeEnigma.......................... 22 2.3. Circuito el´ectrico de Enigma. . . . . . . . . . . . . . . . . . . . 23 2.4. Diagrama de funcionamiento de Enigma. . . . . . . . . . . . . . 26 3.1. Recorrido de la corriente el´ectrica a trav´es de los componentes deEnigma. ............................. 54 4.1. Cicl´ometro. ............................. 61 4.2. Diagrama del cicl´ometro. . . . . . . . . . . . . . . . . . . . . . . 62 4.3. HojadeZygalski........................... 65 4.4. Bomba criptol´ogica. . . . . . . . . . . . . . . . . . . . . . . . . . 70 73