Historia de la Informática

Soldados alemanes con el enigma

Historia:

El enigma es una máquina de cifrado inventada en Alemania por el ingeniero Arthur Scherbuis, está basado en el uso de ruedas dentadas y fue una de las primeras máquinas de su clase. La expansión de las telecomunicaciones aumentó la necesidad de crear métodos de cifrado automatizados para sustituir los antiguos métodos manuales. En un principio ni el ministerio de exteriores alemán, ni el ejercito se interesó por la maquina inventada por Scherbuis y este vendió los derechos a las patentes a la empresa Chiffriermaschinen-AG que durante los años 20 se dedicó a comercializar la máquina.

En los años 30, con la reconstrucción del ejercito alemán, el alto mando militar de la Alemania nazi se interesó por el Enigma, y se apoderó de la máquina. Al considerar el cifrado del enigma muy bueno y prácticamente indecifrable para sus vecinos europeos adopto la máquina para toda la comunicación dentro del ejercito.

Técnica de cifrado:

El enigma se basa en la sustitución (id est sustituir un carácter por otro), pero variando la sustitución con cada carácter introducido, y además usando más de un alfabeto de sustitución. Aquí es donde entran en acción las ruedas dentadas. Las ruedas dentadas determinan la sustitución que realizará la máquina, tienen una posición por cada signo del alfabeto a cifrar (el Enigma nazi tenía 26 carácteres) y según el estado inicial que tienen, al ponerse a escribir tendrá como salida un mensaje u otro.

Las primeras máquinas usaban 3 ruedas en serie (de 5 ruedas disponibles), esto significa que usaban 3 alfabetos de sustitución. Al rotar una de las ruedas se desplazaba el alfabeto de sustitución, al agotarse los cambios posibles de una rueda, giraba la segunda una posición y vuelta a empezar de la primera, y así sucesivamente generando un cifrado con relativamente poca repetición. El principio fundamental que inspiró el mecanismo del Enigma es el de que si usas una clave completamente aleatoria y el mensaje no tiene repetición de secuencias de carácteres será imposible de descifrar. Más tarde incluirían también una sustitución directa carácter a carácter, mediante cables antes de pasar a los alfabetos de sustitución, añadiendo más calidad al cifrado.

Teóricamente el cifrado logrado por esta máquina es de una calidad altísima, con 3 ruedas en serie (combinando las 5 de todas las maneras salen 60 combinaciones) y 10 cables de intercambio de letra (el estándar del ejército alemán) se obtienen 107.458.687.327.250.619.360.000 (1,07*10²³) combinaciones posibles. Posteriormente, la marina añadiría una rueda a su máquina y 3 más para elegir (8 ruedas en total), pudiendo obtener así 31.291.969.749.695.380.357.632.000 (3,1*10²⁵) combinaciones posibles (equivalente a un cifrado de 84 bits en un ordenador de hoy en día).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Mecanismo y funcionamiento:

El enigma es un aparato electro-mecánico, consiste en un teclado, un panel de luces donde se indica a que letra se ha cifrado la introducida, una batería y 3 o 4 ruedas dentadas (ya mencionadas). A la derecha se ve un dibujo de la circuitería de un enigma (en este caso con solo cuatro letras). Los números indican las siguientes componentes:

 

 

1. Flujo de corriente de la batería.

2. Interruptor bidireccional de la tecla ‘A’ (pulsado).

3. Zócalo cerrado de ‘A’.

4. Entrada a las ruedas dentadas.

5. Ruedas dentadas.

6. Reflector (devuelve la corriente por otro camino).

7. Zócalo abierto de ‘S’.

8. Cable de intercambio de letras (de ‘S’ a ‘D’).

 

 

En el ejemplo se ve como se pulsa la tecla ‘A’ las ruedas devuelvan una ‘S’, pero como están intercambiadas la ‘S’ y la ‘D’, produce una ‘D’.

Las ruedas dentadas son la clave del mecanismo interno de la máquina, cada rueda tenía una codificación distinta y según el orden en el que estaban puestas en la máquina se lograba un cifrado u otro. En la imagen de abajo (derecha) se ve la entrada de corriente a las ruedas dentadas, la corriente saldría por la correspondiente al carácter pulsado, entraría a la primera rueda dentada y esta la sacaría por otra salida, entraría en la segunda rueda, y luego a la tercera. El reflector también tenía una codificación, por lo que la señal volvía por las ruedas, pero por otro camino.

Ahora en la imagen de la abajo (izquierda) se observa uno de los cuatro tipos de reflectores que usaba el ejército alemán. Además se añadió un mecanismo para que la rueda en la segunda posición diera saltos al pasar una letra concreta (la letra en cuestión dependía del tipo de rueda). El mecanismo del Enigma es totalmente simétrico, al recibir un mensaje codificado basta con poner la misma clave que el que la envió y teclear el mensaje cifrado para obtener el mensaje original.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

La codificación de cada rueda y de los reflectores eran fijas, y a continuación veréis las tablas de codificación de cada una.

 

 

 

 

 

 

 

 

 

 

 

 

 

Ejemplo práctico:

Supongamos que queremos enviar un mensaje codificado con el enigma. En concreto queremos enviar una A, utilizando las ruedas I, II y III de derecha a izquierda y un reflector de tipo B. Para simplificar utilizaremos como posición inicial 0 para las tres ruedas.

 

 

Mirando la tabla de la derecha vemos que para desplazamiento cero A se transforma en E. En la segunda rueda E se transforma en S, y en la tercera S en G. En la tabla de la izquierda vemos que el reflector convierte G en L. Ahora hay que mirar la tabla de la derecha de abajo a arriba (esta vez la señal va en sentido opuesto). En la tercera L se convierte en F, en la segunda F en W, y en la primera W en N, que es el mensaje cifrado con la clave 0,0,0 con las ruedas I,II, III, y el reflector B. La máquina pasaría automáticamente a la posición 0,0,1. Si volvemos a introducir una A, al haber un desplazamiento de uno, toma la a como una B, la convierte en K, en L, en V, el reflector la devuelve como W, luego se convierte en R, G y finalmente F, que por el desplazamiento de uno pasa a ser E.

Al ser un mecanismo de cifrado simétrico, si ponemos la misma configuración de inicio, y transmitimos NE, nos devolvería AA, el mensaje original. En este enlace se pueden hacer más pruebas, con las ruedas que se quiera y el reflector B. Ilustración del segundo caso explicado:

 

En estos casos no se han considerado los posibles cables de cambio de carácter por carácter para simplificar. Por ejemplo, en la última figura, de haber un cable entre E y X, la salida sería X en vez de E.

 

 

Debilidades, descifrado:

 

Una de las principales debilidades del Enigma es que es imposible que coincidan las letras sin cifrar y cifrada en este mecanismo, algo que permitía descartar posibles mensajes originales.

 

S

O

H

J

Y

P

D

O

M

Q

N

J

C

O

S

G

A

W

H

L

E

I

H

Y

S

O

P

..

P1

K

E

I

N

E

B

E

S

O

N

D

E

R

E

N

E

R

E

I

G

N

I

S

S

..

P2

K

E

I

N

E

B

E

S

O

N

D

E

R

E

N

E

R

E

I

G

N

I

S

..

P3

K

E

I

N

E

B

E

S

O

N

D

E

R

E

N

E

R

E

I

G

N

I

..

 

Imaginaos estar escuchando una transmisión S cifrada con el enigma, en este caso quedarían totalmente descartadas las opciones P1 y P3 por tener letras coincidentes con el mensaje original S.

Otra era que si se usaba un cable de intercambio de carácter, este intercambio era recíproco, un cambio de A por Q significaba también un cambio de Q por A, algo que redujo mucho la complejidad de los cálculos del descifrado. La tercera gran debilidad era que las ruedas dentadas tenían los anclajes de rotación en posiciones distintas, por lo que con un criptoanálisis se puede detectar que ruedas se están utilizando.

Aún considerando estas debilidades la máquina tenía un potencial muy grande que quedo reducido enormemente por el uso inapropiado y errores cometidos por el ejército alemán. Por ejemplo la repetición de la misma clave, mensajes idénticos repetidos día tras día(con claves distintas), uso de claves fáciles de adivinar(AAA, BBB, ASD…), el hecho de no usar mas cables de sustitución directa de caracteres, etc.

A pesar de tener todas estas debilidades se necesitaron unos recursos enormes para descifrar los mensajes enviados por el enigma, trabajaron más de 10.000 personas (incluidos intelectuales de la talla de Alan Turing) desde el inicio hasta el fin de la guerra. Según Winston Churchill el trabajo de estos intelectuales acortó la guerra en por lo menos 3 años, ya que el alto mando aliado tuvo una ventaja considerable sabiendo de antemano todos los movimientos del ejército alemán.

Proyecto de la universidad de Aarhus para simular una máquina de Turing con LEGO

Infancia y juventud
Alan Mathison Turing nació en Paddington el 23 de junio de 1912. Sus padres Julius y Ethel residían en la India debido a que Julius trabajaba de funcionario en la India, pero decidieron volver al Reino Unido para que su hijo naciera allí. Esto hizo que Alan tuviera una infancia peculiar debido a los constantes viajes de sus padres entre Inglaterra e India durante los cuales dejaban a sus hijos al cargo de amigos.

A los 12 años entra en Sherborne School. Su jefe de estudios dijo de él “si lo único que quiere ser es un especialista científico, está perdiendo el tiempo en una escuela pública”. Durante su estancia en dicha escuela Turing perdió a su amigo Christopher Morcom por una tuberculosis bovina contraída tras beber leche de vaca infectada. Esto le hizo perder su fe religiosa y convertirse en ateo.

Tras Sherborne School, Turing fue a King’s College en Cambridge. A pesar de que destacó en el campo de las matemáticas y la computabilidad, en un artículo suyo de 1950 mostrará un toque filosófico/moralista ya que relacionó el concepto matemático de la computabilidad con problemas tradicionales como la separación de la mente y cuerpo, el libre albedrío y el determinismo.

En 1931 formaliza el concepto de máquina de Turing sustituyendo así el lenguaje formal que Kurt Gödel utilizaba sobre los límites de la computación y la demostrabilidad. En 1935 es nombrado profesor del King’s College, a la temprana edad de 22 años.

La Máquina de Turing
Desarrolló el concepto de la máquina de Turing. Una máquina de Turing es un dispositivo teórico que manipula símbolos de una cinta de entrada en función de unas reglas. Se define como un autómata, que mediante un cabezal lector que lee de una cinta de entrada símbolos de un alfabeto, cambiando entre estados en función de la entrada pudiendo rechazar o aceptar la cadena de entrada dependiendo del lenguaje que acepte. Dicha máquina era capaz de implementar cualquier problema matemático que pudiera representarse mediante un algoritmo. Formalmente se define en función de los estados que tiene dicho autómata el alfabeto de entrada y las transiciones que soportal. Es una herramienta básica para el campo de los autómatas y lenguajes formales.
Demostró el problema de la parada de una manera muy intuitiva, aunque dicha demostración la había publicado previamente Alonzo Church (cálculo lambda) con el que trabajaría en Princeton donde obtuvo en 1938 el Doctorado debido a sus estudios sobre la hipercomputación.

La siguiente etapa de su vida da un cambio radical ya que el objeto de sus estudios no es investigación sin rumbo sino un fin específico: El criptoanálisis.

La Segunda Guerra Mundial
Decide empezar a trabajar para el Ejército porque “Nada estaba haciendo nada al respecto”. En 1939 empieza a trabajar en Bletchley Park (estación secreta del Ejército) liderando el Hut- 8 que era una de las secciones de la estación Británica de “codebreaking” durante la 2ªWW. Fue uno de los principales protagonistas en el desmantelamiento y ruptura de la máquina Enigma, mediante la que el Eje ocultaba sus transmisiones. Tras la declaración de guerra del 3 de Septiembre , Turing se volcó en el criptoanálisis en Bletchley Park. Con el trabajo que habían realizado los criptoanalistas polacos, Turing desarrolló la “Bombe” que era una máquina capaz de romper el código de la Enigma. Pero no bastaba, el ejército polaco había interceptado una máquina enigma parecida a la que utilizaba el ejército alemán y sabían que aun así no les daría tiempo a descifrar mensajes, ya que cada día cambiaban la forma de cifrarlos.
En Diciembre de 1939 resolvió gran parte del indicador que era una parte de la configuración que se cargaba en la máquina cada día, en la misma noche concibió la idea de Banburismus (conocido como análisis secuencial). Desde 1940 en adelante el Hut-8 utilizó la bomba criptográfica para leer mensajes de la Lufftwaffe, en cambio el método utilizado por la Kriegsmarine era mucho más complejo y se tomaba por irrompible. Sin embargo Turing aprovechando el conocimiento que tenían de la máquina proporcionada por el ejército polaco desarrolló, el solo, un sistema para atacar el cifrado: El banburismo.

El banburismo es un proceso de criptoanálisis que desarrolló Alan Turing en Bletcheley Park (instalación militar orientada a romper la máquina enigma). El proceso se basaba en la probabilidad condicional secuencial para deducir información acerca de las configuraciones de la máquina Enigma. El objetivo del banburismo era reducir el tiempo necesario para que la “Bomba” identificara los patrones de los rotores ya que reducía mucho las posibilidades. En 1939 Turing consiguió romper el código ahora solo quedaba capturar mensajes trabajo que hizo la marina. El procedimiento aprovechaba la debilidad del indicador (configuración inicial de la Enigma) comparaban mensajes criptados con distintas configuraciones, si el desplazamiento sólo se diferenciaba de un carácter (CFE-CFT cada letra corresponde a un rotor), podían obtener dicho desplazamiento. En 1941 se empezó a descifrar formalmente mensajes, en particular del submarino U-boat. El Hut 8 aplicó dicho procedimiento durante 2 años, hasta 1943 cuando empezó a ser factible el plan de la bomba criptográfica. Esto dio una gran ventaja al bando aliado en la batalla del atlántico cuando EEUU entró en la guerra. En ese momento Turing tuvo un rol de ingeniero electrónico, ideó el concepto de la mecanización de la ruptura del material FISH (teletipo), aunque fue MHA Newman quien desempeñó el papel organizativo. La mezcla de las ideas sobre estadística de Turing junto con la electrónica a gran escala tuvo resultados trascendentales.

Durante los últimos años de la guerra, Turing colaboró en la creación del Colossus, una máquina totalmente electrónica, que tuvo gran importancia para la invasión de Europa por parte del bando aliado al descifrar un mensaje en el que los alemanes decían que el desembarco se iba a dar lugar en en Calais, al conocer esta creencia del enemigo, los americanos decidieron encauzar el desembarco a las playas de Normandía. Turing consideró dicha máquina como un cerebro primitivo.

Cabe destacar, que debido a ser secreto de estado, la implicación de Alan Turing en la desencriptación de códigos nazis no fue revelada al público hasta 1970. Por lo que murió sin que la gente supiera de su contribución a la victoria de la guerra.

Pasada la segunda guerra mundial
En 1944 ya mencionó al ingeniero civil Donald Bailey sobre la “construcción de un cerebro”, entre 1945, año en el que comenzó a trabajar en el National Physical Laboratory, y 1947, un año antes de abandonar el NPL, se dedico a dicha empresa. Existía un proyecto similar llamado EDVAC desarrollado paralelamente por los americanos pero el Automatic Computing Engine (ACE) de Turing se diferenciaba del proyecto estadounidense en que incluía la implementación de funciones aritméticas en circuitos electrónicos. Turing tenía en mente crear una máquina que pudiera ser configurada para hacer cálculos algebraicos, desencriptar códigos, manipular archivos e incluso jugar al ajedrez.
En 1947 creó el Abbreviated Code Instruction, origen de los lenguajes de programación.
A diferencia de la época de la segunda guerra mundial, en aquella ocasión no tuvo el apoyo de ingenieros y científicos, por lo que el ACE no se llegó a construir.
Gracias a la colaboración del ingeniero Frederic Calland Williams en 1948 se da por primera vez una demostración del principio de la máquina de Turing. Mientras tanto, estuvo entrenando como corredor de fondo y estuvo cerca de participar en los Juegos Olímpicos de ese año en representación de Inglaterra.

Tras la salida del NPL, se puso al cargo del laboratorio de computación de la Universidad de Mánchester, donde realizó parte del software del Mark I y escribió el artículo “Computing Machinery and Intelligence”. En este artículo Turing desarrolló la idea de la inteligencia artificial y propuso el test de Turing que es capaz de discernir una máquina de un ser humano.
En 1950, sus antiguos colegas del NPL hicieron una versión reducida de la máquina inicialmente ideada por Turing, la Pilot Model ACE.

Los dos últimos años de su vida Turing dedicó sus esfuerzos a la formación de patrones y la biología mecánica, más concretamente estudió el proceso que controla la distribución organizada de las células de los organismos (morfogénesis) y si éste seguía la secuencia de Fibonacci. Dichos estudios dieron como resultado su escrito “The Chemical Basis of Morphogenesis”.

Juicio y muerte
Desde el final de la guerra la inteligencia británica había decidido vigilar a Turing, pues sabían de su homosexualidad y no querían que alguien que sabía tantos secretos de la seguridad británica estuviera expuesto al chantaje. Finalmente, en Marzo de 1952 Turing fue detenido con motivo de su homosexualidad, la cual fue descubierta a raíz de las relaciones que mantuvo con un joven mancuniano.
Tras el juicio, en el que no se quiso defender al no considerar que estuviera cometiendo ningún delito, se le dio a elegir entre la cárcel o un tratamiento hormonal a base de estrógenos para neutralizar su libido. Alan eligió lo segundo que, si bien le libró del presidio, lo llevó a unos cambios físicos y anímicos que desencadenarían en el final de su vida.
Alan Turing fue encontrado por su asistenta el 8 de Junio de 1954. Murió el día anterior por ingestión de cianuro. Oficialmente la muerte fue considerada suicidio, se dice que mordiendo una manzana a la que había inyectado el veneno, pero su madre defendió que murió por una ingestión accidental de cianuro tras un experimento químico.

Post mortem
En 1966 se creó el Premio Turing, organizado por la Association for Computing Machinery, está reconocido como el Nobel de la computación.

Numerosas películas y novelas han tratado el tema de la máquina enigma y el test de Turing. Un conocido ejemplo de este último, es el film futurista Blade Runner de 1982, en el que se realizan entrevistas a algunos sujetos con el objetivo de determinar si son humanos o máquinas.

En 1990 Hugh Loebner con la aprobación del “Centro para Estudios del Comportamiento de Cambridge” prometió un premio de 100000 dólares y una medalla de oro para la primera máquina cuyas respuestas fueran indistinguibles de las humanas. Cada año se da un premio de 3000$ y una medalla de bronce a aquella que se acerque más a este objetivo.
Más información del premio Loebner:

http://loebner.net/Prizef/2010_Contest/loebner-prize.html

Premio Loebner del 2010, un chat bot de nombre Suzette creado por Bruce Wilcox engañó a un juez tras 25 minutos de conversación:

http://www.newscientist.com/article/dn19643-prizewinning-chatbot-steers-the-conversation.html?DCMP=OTC-rss&nsref=online-news

Para hablar con el bot:

http://www.chatbots.org/chatbot/suzette/

En 2009, el primer ministro británico Gordon Brown escribió una carta de disculpa en la que reconocía la horrible forma en la que fue tratado.

Los captchas que normalmente nos encontramos por internet, son un tipo de test de Turing, de hecho, la palabra CAPTCHA es un acrónimo de “Completely Automated Public Turing test to tell Computers and Humans Apart”.

Referencias bibliográficas
http://es.wikipedia.org/wiki/Alan_Turing
http://en.wikipedia.org/wiki/Alan_Turing
http://www.microsiervos.com/archivo/ordenadores/gordon-brown-tratamiento-alan-turing-fue-horrible.html
http://www.portalplanetasedna.com.ar/maquina_enigma.htm
http://dis.um.es/~barzana/enlaces/Biografia_turing.html
http://www.turing.org.uk/bio/part1.html
http://anonymous-generaltopics.blogspot.com/2009/12/enigma-machine.html
http://www.csiargentina.com/saberhistoria/
http://www.telegraph.co.uk/news/newstopics/politics/gordon-brown/6170112/Gordon-Brown-Im-proud-to-say-sorry-to-a-real-war-hero.html

Fragmento de la película “Breaking the code” sobre la vida de Alan Turing.

Excelente documental de la BBC sobre los inicios de la informática.

El próximo año 2012 se cumplirán 100 años del nacimiento de Alan Turing. Durante ese año se celebrarán diversos actos para conmemorar el evento.

Información.