Turing y el descifrado de Enigma


  • 0

    La máquina Enigma

    Después de la primera guerra mundial, el inventor alemán Arthur Scherbius y su amigo Richard Ritter fundaron una empresa de ingeniería y crearon la máquina Enigma con la finalidad de venderla no solo al ejército sino también a muchas empresas del país. La máquina iba en una caja de dimensiones 34cm x 28cm x 15cm y pesaba unos 12 kg.

    Básicamente, estaba formada por tres componentes conectadas por cables que combinados constituían una compleja máquina para cifrar: Un teclado para escribir cada letra del texto en claro; una unidad modificadora formada por tres rotores, un clavijero y un reflector; y un tablero donde quedaba iluminada la letra cifrada.

    Cada rotor era un disco con dos caras y con 26 contactos eléctricos, uno por cada letra del alfabeto. El clavijero estaba colocado entre el teclado y el primer rotor, con el objetivo de intercambiar 6 pares de letras. Mientras que el reflector conseguía que al codificar un mensaje cifrado, usando la mismas posiciones iniciales de los rotores y los mismos pares de letras interconectadas en el clavijero, se obtuviese el mensaje en claro.

    Podemos imaginar el efecto de un rotor como el de una permutación en las posiciones de las letras del alfabeto, con la característica que cada vez que se codifica una letra, el rotor se desplaza una posición y, por tanto, la permutación sobre el alfabeto es distinta. Sin embargo, al codificar 26 veces una letra obtendríamos su codificación inicial.

    Para evitar precisamente esa repetición, nunca deseada en criptografía, la máquina constaba de tres rotores, de manera que al codificar una letra saltaba una posición el rotor más rápido, el de más a la derecha. Una vez había dado una vuelta entera, empezaba a rotar el de en medio (para cada nuevo movimiento había que esperar los 26 movimientos del rotor rápido) hasta llegar al menos rápido que era el de la izquierda.

    En un principio Scherbius no tuvo el éxito que imaginaba vendiendo máquinas Enigma, sino más bien al contrario. Sin embargo, unos años más tarde, el ejército alemán se decidió a comprar la máquina Enigma a raíz de dos informes británicos publicados en 1923, sobre material criptográfico interceptado en la I guerra mundial: The World Crisis de Winston Churchill e Historia oficial de la I guerra mundial publicada por la Marina Real británica.

    En 1925 Scherbius se lanzó a fabricar máquinas Enigma en serie. El ejército alemán durante los siguientes años compró más de 30000 máquinas Enigma y empezaron a enviar mensajes cifrados. Cada mes los operadores de Enigma recibían un nuevo libro de códigos con las claves que se debían usar cada día:

    Las posiciones del clavijero: A/D C/G M/P R/S T/F L/U La disposición u orden en que se colocaban los rotores: 2-1-3

    • Las posiciones iniciales de los rotores: S M E

    El número total de claves de esta primera máquina Enigma era

    Descifrar Enigma parecía inabordable...

    Primeros intentos de descifrar Enigma
    En 1926, criptoanalistas británicos y de distintos países empezaron a interceptar mensajes procedentes de la máquina Enigma, pero sin posibilidad alguna de descifrarlos, hasta que en 1931 Hans-Thilo Schmidt, resentido por como lo había tratado el ejército alemán, pasó a los aliados documentación de Enigma, que les permitiría crear una réplica. Ello no significaba aún poder descifrar los mensajes, pero sí el reto de saber cómo encontrar la clave.
    En Polonia, nación que se sentía amenazada por si estallaba una segunda guerra, decidieron reforzar su oficina de criptoanálisis, el Biuro Szyfrów, fichando un grupo de matemáticos, entre los que se encontraba Marian Rejewsky (1905-1980).
    Como precaución los alemanes decidieron usar la clave del día sólo para transmitir la clave de mensaje (las posiciones iniciales de los rotores). No obstante, el uso repetido de una sola clave del día debilita el sistema. Rejewsky, intentó aprovechar las repeticiones de las codificaciones de las claves de mensaje. Como la clave del mensaje, p.e. C G H, se tecleaba dos veces para evitar errores, se deducía que la 1ª y la 4ª letra de la codificación correspondían a la misma letra del mensaje original. Al igual que con la 2ª y la 5ª y con la 3ª y la 6ª.
    C G H C G H ---------------> D V Y B Z X
    Rejewsky, si durante el día conseguía suficientes mensajes, podía completar la tabla de relaciones:
    1ª letra A B C D E F G H I . . . . . W X Y Z
    4ª letra H F W B G L R C P . . . . .A T S I
    Pero, ¿qué patrones se podían deducir de estas tablas? Rejewsky se fijó en las cadenas de letras conectadas, en el sentido que provenían de la misma letra original:
    A--->H--->C--->W--->A
    La longitud de estas cadenas no depende de los pares de letras intercambiadas por el clavijero, sólo de la posición de los rotores, de manera que el número de claves posibles se reduce de 1016 a 6 x 263=105456. Rejewsky había simplificado el problema, encontrando primero la clave del día y luego las posiciones del clavijero. Aún así, tardaron un año en completar el catálogo de claves. Más adelante, el equipo de Rejewsky construyó una máquina, a la que denominaron bomba, capaz de comprobar siguiendo su sistema de catalogación la clave correcta. Puesto que los rotores se podían disponer en seis posiciones distintas, usaban seis bombas trabajando en paralelo para conseguir una mayor eficiencia.
    En diciembre de 1938, los criptógrafos alemanes aumentaron la seguridad de Enigma, con dos nuevos rotores que podían intercambiar con los tres que tenían. Polonia se temía lo peor. Los mensajes que interceptaban se habían vuelto de nuevo indescifrables. Para no perder los logros conseguidos invitaron a Varsovia a un equipo de criptoanalistas franceses y británicos para mostrarles las réplicas de Enigma que habían construido. El 1 de septiembre de 1939, Adolfo Hitler invadía Polonia y la guerra comenzaba..
    Alan Turing en Bletchley Park
    En Bletchley Park, sede de la Escuela Gubernamental de Códigos y Cifras, situada en el condado de Buckinghamshire, conocían en otoño de 1939 las características de Enigma y dominaban las técnicas de Polonia que les permitían descubrir en horas la clave del día. Creían, sin embargo, que se acabaría la repetición de las claves y necesitaban encontrar nuevas alternativas a la idea de Rejewsky.
    En septiembre de 1939 llegaba Alan Turing a Bletchley Park para incorporarse al equipo de criptoanalistas. Turing enseguida intuyó, que de entre toda la información que tenían acumulada, se podían beneficiar de los puntales, fragmentos de texto que se pensaba estaban en el mensaje (con mucha probabilidad), como wetter (tiempo en alemán). Y dentro de los puntales se fijó en los rizos, cadenas de pares de letras (en claro - cifrada) que formaban ciclos. Así, en el siguiente ejemplo se tiene el rizo: W-T, T-E, E-W.

    Posición Enigma S S+1 S+2 S+3 S+4 S+5 Texto en claro W _ E T T E R_
    Texto cifrado T _ W P E * B Y_

    Según el funcionamiemto de Enigma, cada letra corresponde a una posición distinta de los rotores, de manera que si para la primera letra suponemos que los rotores se encuentran en una posición S, para la siguiente habría que desplazar una posición el rotor más rápido y así sucesivamente. Entonces Turing tuvo una de las ideas más geniales. Imaginó una nueva máquina formada por tres máquinas Enigma con las posiciones de los rotores desplazadas según el rizo interconectadas de manera que se anulara el efecto del clavijero.
    Bletchley Park consiguió presupuesto para convertir la idea de Turing en una máquina que llamaron bomba como las primeras réplicas de Enigma de Rejewski. El 14 de marzo de 1940 llegaba la primera bomba prototipo a la que llamaron Victory. Y el 8 de agosto la nueva bomba llamada Agnes. Si bien las bombas representaron un gran avance, no siempre conseguían descifrar los mensajes. Había que probar con distintos puntales y una vez hallado el correcto había que encontrar la posición adecuada en el mensaje donde ubicarlo, para entonces iniciar la desencriptación con una bomba.
    Otro factor que dotaba a Enigma de una gran complejidad era que las componentes de la máquina que el ejército alemán usaba no siempre eran las mismas en todas las zonas o áreas. Así, las máquinas de la marina, las más sofisticadas, tenían 8 rotores distintos y el reflector podía colocarse según 26 orientaciones distintas. Estas dificultades añadidas hacían que el equipo de Bletchley Park aún no pudiera descifrar los mensajes que se transmitían por radio los submarinos alemanes y que contaban con una clara ventaja en la batalla del Atlántico. Junto a esta situación, Turing tuvo que trasladarse a Estados Unidos desde noviembre de 1942 a marzo de 1943 para diseñar un sistema de cifrado para las comunicaciones entre Roosevelt y Churchill.
    En circunstancias extremas, los servicios británicos secretos sabían que había que recurrir a otras estrategias. Una de ellas que resultó decisiva consistió en infiltrarse en un barco alemán para conseguir un libro de códigos. Esas acciones en Bletchley Park eran denominadas pellizcos. Con ello, el equipo de criptógrafos pudo lograr el descifrado de los mensajes navales y conocer así la ubicación de sus submarinos.
    Los trabajos de los criptoanalistas de Bletchley Park, conocidos también como Inteligencia Ultra, fueron determinantes pues para acortar la guerra. La mansión y los barracones de Bletchley llegaron a contar con casi 10000 personas que trabajaban en distintos turnos y a disponer de más de 200 bombas. No obstante, después de la guerra, por razones de prudencia y de táctica militar, las bombas se desmantelaron y todos sus logros se mantuvieron en secreto. A finales de los setenta, el Servicio de Inteligencia británico permitió al capitán W.F. Winterbotham escribir el libro The Ultra Secret publicado en 1974.
    Desafortunadamente, para algunos, como Alan Turing, la publicación del libro llegó demasiado tarde...
    La lucha entre criptográfos y criptoanalistas existe desde tiempos muy remotos y continúa despertando un gran interés un siglo después del nacimiento de Turing. Gracias a ello, el avance de la criptografía, en particular, en estas últimas décadas ha sido espectacular. Parece, pues, impredecible aventurar que nos deparará en un futuro próximo.

    Fuente: Josep M. Miret, profesor titular de la Universitat de Lleida



  • 1

    me quedo por aqui que interesa



  • 2

    Recomiendo ver The Imitation Game que habla de ella, de echo es la protagonista



  • 3

    @S1767 said:

    Recomiendo ver The Imitation Game que habla de ella, de echo es la protagonista

    Me gustó mucho la película, pero se inventan muchas cosas. Como "película épica de matemáticos" es muy buena.

    No me acabé el Criptonomicón, de Neal Stephenson, pero creo que hablan de la máquina, entre otras cosas. A quien le interese este tema, le recomiendo leerlo.



  • 4

    Muy interesante, shur, buen hilo.



  • 5

    @SgtBurden said:

    Me gustó mucho la película, pero se inventan muchas cosas. Como "película épica de matemáticos" es muy buena.

    No me acabé el Criptonomicón, de Neal Stephenson, pero creo que hablan de la máquina, entre otras cosas. A quien le interese este tema, le recomiendo leerlo.

    Me apunto el libro!

    Lo de la película es cierto. Antes de que saliera ya había leído bastante de Turing y al verla me di cuenta de que habían metido mucha cosa para hacer la película más amena al espectador general. Me gustó bastante, pero la información hay que buscarla en otra parte.



  • 6

    @Joel said:

    Me apunto el libro!

    Lo de la película es cierto. Antes de que saliera ya había leído bastante de Turing y al verla me di cuenta de que habían metido mucha cosa para hacer la película más amena al espectador general. Me gustó bastante, pero la información hay que buscarla en otra parte.

    Bueno es una película que busca entretener al público general, a mi me gusto bastante pensaba que iba a ser peor.

    Me apunto el libro también



  • 7

    @Joel said:

    Me apunto el libro!

    Lo de la película es cierto. Antes de que saliera ya había leído bastante de Turing y al verla me di cuenta de que habían metido mucha cosa para hacer la película más amena al espectador general. Me gustó bastante, pero la información hay que buscarla en otra parte.

    @S1767 said:

    Bueno es una película que busca entretener al público general, a mi me gusto bastante pensaba que iba a ser peor.

    Me apunto el libro también

    Si os interesa ése, el mismo autor tiene otros que os podrían interesar :mola:

    Por cierto, hace un tiempo se empezó un kickstarter para fabricar máquinas enigma. Muy caras, eso sí xD.



  • 8

    Gracias por el hilo, cojonudo. El tema de teoría de números y criptografía lo conozco un poco ya, pero no supe de estas historias hasta que vi la peli, muy buena por cierto. Apuntando el libro.





Has perdido la conexión. Reconectando a Éxodo.