Archivo de la categoría ‘ Criptografía ’

Mujeres extraordinarias (I). Una chica La Mar de lista y La Mar de guapa.

 

 

No sólo fue un icono del cine mudo y los principios del sonoro. Era de una belleza inusual, a base de sofisticación y rasgos delineados y perfectos, tirando casi hacia lo oriental, como una princesa de un cuento de Scherezzade. Pero Hedy Lamarr era mucho más que una cara bonita con excelentes dotes interpretativas. Era una máquina de la ingeniería, que tuvo una feliz idea, y que supo hacerla realidad, aunque nunca pudiera explotarla.

 

 

El 11 de agosto de 1942, en plena Segunda Guerra Mundial, en colaboración con el pianista George Antheil, patentó la primera implementación conocida de las técnicas de espectro ensanchado. En aquella guerra se hicieron notorias las dificultades existentes en algunos sistemas de telecomunicaciones o de rádar ante el uso de medidas electrónicas, conocidas también con el nombre de “jamming” en el argot técnico. Las señales de jamming no son sino interferencias creadas adrede por el enemigo para inutilizar por ejemplo los sistemas de rádar, introduciéndose información indeseada y falsa modulando las frecuencias empleadas en el sistema receptor en sí, que se cuela en las antenas, y puede confundir (por ejemplo en el caso del rádar) la interpretación de los blancos o targets e incluso inutilizar completamente la recepción.

 

 

En realidad la técnica básica para conseguir que una determinada información viaje por el espacio consiste en mezclar la señal de información, que podría por ejemplo ser la onda de corriente de baja frecuencia que genera un micrófono capacitivo, con una señal sinusoidal de alta frecuencia, amplificar el resultado y radiarlo en una antena. La mezcla de estas dos señales se puede conseguir aprovechando la no-linealidad de algún dispositivo, como es el caso de un transistor bipolar polarizado a caballo de la zona activa y la de saturación, o de un transistor de efecto de campo, de modo que en el colector o respectivamente drenador tenemos un espectro que incluye no sólo la onda tal cual amplificada, sino además la suma de todos los armónicos que resultan de elevar a las sucesivas potencias un coseno que varía en el tiempo, el que suministraría el oscilador local, junto con los productos de intermodulación que surgen al sumar en el circuito de entrada del mezclador este coseno con la señal de tensión de la información y elevar a cada potencia. Refiriéndome aquí a las potencias implícitas en el desarrollo en serie de Taylor de la señal, válido en este contexto porque se opera siempre con rangos dinámicos de pequeña señal, dado que las mayores amplitudes se suelen conseguir al final de la cadena de transmisión, cuando se realiza la amplificación de potencia. Ésto es así, porque el producto de dos señales de dos frecuencias distintas es igual a la semisuma de una señal de frecuencia suma y otra señal de frecuencia diferencia. De esta forma, en recepción se usa uno de los productos de intermodulación de segundo orden, más concretamente aquél que vibra a la diferencia entre la frecuencia de radio y la frecuencia del oscilador local de dicho receptor, para pasar la información a una determinada frecuencia mucho más baja que la radiofrecuencia, de modo que pueda ser amplificada con calidad y poco ruido y pasada al detector del receptor. Así, la forma más barata para transmitir información en términos de ancho de banda empleado es cualquiera modulación que transmita la señal moduladora que contiene la información por el canal, sin modificaciones, y hablando por supuesto de sistemas analógicos, empleando como límite el ancho de banda positivo de dicha señal.

 

 

¿Entonces cuál fue la idea de Hedy? A Hedy Lamarr se le ocurrió variar de alguna forma sincrónica en el transmisor y el receptor la frecuencia de portadora o señal de radiofrecuencia empleada en la transmisión. Más específicamente, Hedy empleó en su sistema lo que hoy se conoce como espectro ensanchado por salto de frecuencia (“Frequency hoping”). Por aquel entonces no existían los avances que tenemos hoy en día en electrónica de estado sólido (aún se desconocía esta tecnología), por lo que usó como mecanismo de sincronía entre el transmisor y el receptor el bombo de un organillo, que a medida que iba girando iba generando señales de distintas frecuencias para mezclar con la información, ocupando un ancho de banda muchísimo mayor que el estrictamente necesario, de manera que la información quedase enmascarada por el ruido. Cuanto mayor es el ancho de banda, cualquier sistema de transmisión limita la densidad espectral de potencia radiada por elemento de frecuencia. Es decir, cuanto mayor sea el ancho de banda que empleamos en una transmisión, más se limita el nivel de la señal que transmitimos. Asimismo, cuanto mayor sea el ancho de banda en recepción, menos afectarán las interferencias en cualquiera de las frecuencias de la banda, con lo que las señales de jamming se verán muy atenuadas, y sus efectos sobre la señal recibida serán prácticamente inapreciables. En consecuencia, un receptor normal pensado para cualquiera de las frecuencias que empleamos en nuestro transmisor “Hedy” sólo detectaría ruido, y para lograr que un sistema se enganchase a la transmisión que estamos efectuando con salto de frecuencia, debería emplearse cualquier sistema que permitiese variar la frecuencia de sintonía y la frecuencia del oscilador del mezclador receptor en el mismo orden y de forma sincrónica con sus variaciones en transmisión, para lo cual también sería preciso que nuestro sistema de antena estuviese diseñado para banda ancha. Sólo un conocimiento exacto del mecanismo empleado para el salto de frecuencia en transmisión permitiría la recepción correcta de la señal. En cualquier otro caso, la señal recibida sería sólo ruido. Actualmente, la tecnología permite afortunadamente sistemas más prácticos que “el organillo”. Digamos que “el organillo” está hoy en día implementado mediante circuitería a muy alta escala de integración.

 

 

Fue en el año 1957 cuando los ingenieros de la empresa Silvania Electronics Systems Division implementaron por primera vez el sistema ideado por Lamarr mediante transistores. Y en la actualidad las técnicas de espectro ensanchado son cada vez más importantes. No sólo se sigue empleando el sistema de salto de frecuencia, sino que también existe otra variedad denominada “de secuencia directa”, que sintetiza el filtro transmisor mediante un código sólo conocido por transmisor y receptor, y que también desparrama el espectro haciendo la señal indistinguible de ruido en receptores de banda estrecha. El creciente interés en estas tecnologías deriva de que usar espectro ensanchado permite superponer en una misma banda de frecuencia señales de muchas fuentes sin que existan interferencias limitantes entre ellas.

Y todo ello gracias a la Lamarr. La Mar de lista y La Mar de guapa la tía. Pero cuya patente expiró 3 años antes de que se empezasen a sacar los primeros sistemas de espectro ensanchado basados en sus ideas. Por lo tanto, nunca ganó ningún dinero con ésto.

 

El cifrado César y la aritmética modular

 

 

 

Desde la antigüedad se cultivaron los métodos de cifrado y descifrado de mensajes, ya que era de vital importancia que algunas informaciones relevantes llegaran a manos de un destinatario del mismo bando, sobre todo en épocas de guerra, cuando el líder de las tropas necesitaba comunicarse mediante un mensajero con cada uno de los corresponsales de los diversos destacamentos. Así pues, era preciso un convenio para el cifrado y después para el descifrado. Los mensajes podían cifrarse por sustitución –sustituyendo cada letra original por otra letra o símbolo que le correspondía-, o bien por trasposición. El cifrado por trasposición consistía en alterar el orden de las letras del mensaje. Ya en la antigüedad clásica se usaba la escítala, que no era otra cosa que una vara de cierto diámetro convenido entre emisor y receptor. Se enrollaba una tira de papel alrededor de la escítala y se escribía el mensaje sobre líneas consecutivas en el papel enrollado. Cuando se desenrollaba dicho papel aparecía un galimatías de letras –las letras del mensaje-, en el cual el orden de las letras había sido totalmente violado. Pero cuando este papel era vuelto a enrollar en una vara de idéntico diámetro aparecía el mensaje perfectamente legible.

Por lo que se refiere a los métodos de sustitución, existe constancia de que uno de los primeros algoritmos de sustitución fue el cifrado de Polibio, aunque aproximadamente 50 años después, el propio Julio César hacía uso de uno bastante simple, que pasó a ser llamado cifrado César. Este cifrado consiste en establecer una clave común a emisor y receptor, que era un número, y dada una letra a cifrar se desplazaban en el alfabeto tantas posiciones como indicaba el número y se tomaba la letra de esa posición final como carácter cifrado. Para el descifrado podía usarse un rectángulo de cartón en el que estuviesen en orden las letras del alfabeto, por debajo de las cuales se podía deslizar una tira con dos alfabetos consecutivos, y así al mover la tira inferior una cantidad de caracteres igual al número clave, se ponían en correspondencia el alfabeto sin cifrar con el cifrado.

Entre el cifrado César y la aritmética modular –o “aritmética del reloj”- hay una correspondencia clara. La aritmética modular, que es una de las bases del actual sistema de encriptación Rivest-Shamir-Adellman (RSA) utilizado para cifrar y firmar digitalmente la información privada en las comunicaciones de Internet, se basa en atribuir la equivalencia entre un número menor que el tope numérico que consideremos al resultado de efectuar cualquier número entero de pasadas al ciclo que va desde 1 hasta el tope (que en un reloj sería el número 12) más los avances hacia el número considerado. Por ejemplo, podemos decir que las 4 horas equivalen a las 16 horas o a las 28 horas, si damos respectivamente 1 y 2 vueltas al reloj y contamos 4 unidades más. La arimética modular viene a darnos equivalencias basadas en un ciclo que se repite y que es rebasado en la última vuelta la misma cantidad de posiciones que las del carácter a cifrar. Escrito matemáticamente, de una forma rigurosa, se dice que 16 es congruente con 4 en módulo 12, o que 28 es también congruente con 4 en módulo 12. Esta misma forma de razonar la podemos emplear con medidas angulares, diciendo por ejemplo que 380 es congruente con 20 en módulo 360.

De esta manera el cifrado César se puede expresar mediante una fórmula matemática del siguiente modo. Si llamamos C(x) al ordinal de la letra cifrada y a x el ordinal de la letra sin cifrar, y si consideramos una aritmética modular módulo 27 (el número de letras del alfabeto), se puede escribir :

C(x) = (x + k) (módulo 27), donde k es la clave empleada.

Por ejemplo, si la clave es 3, el carácter de ordinal 4, que sería la letra E (se empieza a contar con 0 para el primer carácter) quedará cifrado mediante el carácter de ordinal 7, que sería la letra H. Pero la clave k puede ser todo lo grande que queramos. Así, por ejemplo, si k es igual a 58, el carácter de ordinal 4 (letra E) sería cifrado por el carácter de ordinal 4 + 58 (módulo 27), que es el ordinal 8 (letra I).

Para el desciframiento también podemos usar una fórmula, que sería de la forma O(c) = (c – k) (módulo 27). Ésta sería la fórmula inversa a la anterior, que nos permitiría conocer el ordinal del carácter original a partir del cifrado c.

En principio el cifrado César no sería difícil de romper, si nos basamos en análisis de frecuencia, pero podríamos complicarlo algo más si utilizamos el conocido como cifrado afín, que responde a la fórmula :

C(x) = (ax + b) (módulo 27), siendo a y b dos números menores que el número de caracteres del alfabeto. Para que un carácter fuese cifrable unívocamente mediante este esquema, sería preciso que el mcd(a, b) fuese 1, esto es, que a y b fuesen coprimos.

¿Por qué es más potente el cifrado afín que el cifrado César original?. Pues la razón estriba en que ahora hay dos claves para el cifrado, que son los números a y b, mientras que antes sólo había 1 número clave (k). El número de claves distintas para el cifrado afín será igual a la cantidad de 26 x 26 para un alfabeto de 27 letras, mientras que el número de claves para el cifrado César sería sólo de 26. Es decir, hay una notoria mejoría a favor del cifrador, puesto que existen más claves potenciales con las cuales practicaría un hipotético interceptor del mensaje hasta dar con el mensaje descifrado siguiendo la filosofía afin. Aún así, ninguna de las dos formas de encriptación es invulnerable, basta con emplear fuerza bruta para romperlas.

En la imagen superior se observa una representación de la forma de cifrado por trasposición mediante escítala. En la imagen inferior, un busto de Julio César.

 

  

El cifrado Vigenère y cómo lo rompió Charles Babbage

 

 

La forma más simple de cifrar un mensaje, esto es, de conseguir a partir del texto original otro texto encriptado con forma de galimatías según el cual quede expresado el texto inicial, ha sido, desde que existe la criptografía, el algoritmo de sustitución. Dicho algoritmo se basa en hacer corresponder a cada letra del texto llano otra letra o símbolo, de acuerdo con un convenio entre el emisor y el receptor del mensaje. Por lo tanto ambos deben poseer la tabla de equivalencias y aplicarla para cifrar y posteriormente descifrar el mensaje.

El problema del algoritmo de sustitución es que el mensaje encriptado es en cierto modo fácil de descifrar, aún no poseyendo la tabla de equivalencias. El método que se debe emplear para tal fin fue descrito por primera vez por un sabio nacido en Bagdad en el año 801, llamado Al-Kindi, y que se dedicaba a la astronomía, a la matemática y a la medicina, teniendo también intereses como lingüista. El método que este estudioso describió se conoce como análisis de frecuencias, y consiste en analizar un texto suficientemente grande en un determinado idioma y cuantificar en él la frecuencia de aparición de cada letra. Una vez obtenida esta estimación de lo probable que es la aparición de todas las letras, se puede aplicar este conocimiento para hacer suposiciones sobre los símbolos más frecuentes del texto cifrado, y una vez que éstos han sido asignados se siguen haciendo suposiciones sobre los restantes símbolos de dicho texto, teniendo en cuenta por ejemplo que lo más probable antes o después de una vocal es una consonante y otras apreciaciones en base al conocimiento de la lengua en la que fue redactado el mensaje llano, hasta llegar a un mensaje coherente semánticamente, que será el texto descifrado. El punto débil del algoritmo de sustitución simple que se ha descrito es que una determinada letra se sustituye siempre por el mismo símbolo, por lo que es evidente que las frecuencias de las letras originales, que son similares aproximadamente al del alfabeto de que proceden en el contexto de la lengua utilizada, coinciden con las frecuencias de los símbolos cifrados, y es éste el tendón de Aquiles que aprovecha el análisis de frecuencias.

En criptografía ha habido siempre una lucha sin cuartel entre cifradores y descifradores. Los primeros han intentado con el paso de los siglos perfeccionar los métodos de cifrado hasta aproximarse a un encriptado perfecto. Los segundos han hecho acopio de verdadero ingenio para lograr métodos eficientes a la hora de echar por tierra el trabajo de los primeros. Así pues, el caso de la simplicidad del algoritmo de sustitución y de lo sencillamente que se vino abajo no fue una excepción.

 

 

La solución criptográfica al uso del análisis de frecuencias por parte de los descifradores vino por cuenta de un genio del Renacimiento, el polifacético Leon Battista Alberti, más conocido en sus facetas de arquitecto, matemático y teórico de la perspectiva. Su aportación quedó en el olvido por no escribir ningún tratado sobre la misma, pero fue posteriormente desarrollada por dos académicos llamados Blaise de Vigenère y Johannes Trithemius. Esta aportación se conoce con el nombre de cifrado polialfabético y consiste en utilizar el mismo alfabeto de sustitución para letras cuyo ordinal en el mensaje difiere en la longitud de una palabra utilizada como clave y diferentes alfabetos de sustitución para letras que no cumplen esa propiedad, estando cada alfabeto de sustitución determinado por cada letra de la palabra clave. Así pues, la cifra Vigenère consiste en escribir el mensaje llano sin cifrar y colocar encima de cada letra, en orden sucesivo, las letras de la palabra clave, repitiendo dicha operación deslizando dicha palabra clave una y otra vez hasta cubrir todo el mensaje. A continuación para cada letra de la palabra clave se consulta su alfabeto de sustitución correspondiente y se codifica la letra original como el sustituto para ella hallado en el alfabeto de sustitución parejo a la letra clave empleada. De este modo se obtiene un galimatías ciertamente bastante más robusto que si se emplease sustitución simple.

Pero,…,¿es factible el romper este esquema de cifrado?. El cifrado Vigenère fue inexpugnable durante casi dos siglos, pero allá por el año 1854, uno de los pioneros del cálculo automático, sobre el que escribí un artículo en esta web, Charles Babbage, logró encontrar un método operativo para romper el cifrado Vigenère, aunque no publicó nunca sus resultados, siendo identificada su primicia mucho tiempo después al revisar sus notas.

¿Qué medio se le ocurrió a Babbage para esta tarea? Charles Babbage partió de que el número de letras de la palabra clave empleada determinaba el número de distintos alfabetos de sustitución usados. De esta manera, si por ejemplo dicha longitud era de cinco letras, ello significaba que cada carácter del mensaje original podía quedar cifrado de cinco maneras diferentes. Así pues, el primer paso a llevar a cabo era el determinar la longitud de la palabra clave. Suponiendo que se tenía un texto cifrado lo suficientemente largo, dicho primer paso se acometía aprovechando aquellas palabras que se cifraban de igual manera en el texto, me refiero por ejemplo a artículos o pronombres. Estas palabras aparecen cifradas con la misma equivalencia a lo largo del texto cuando los ordinales de sus letras constituyentes difieren en un múltiplo de la longitud de la palabra clave. De esta manera, viendo las palabras (cifradas) repetidas, determinando la diferencia entre los ordinales de sus letras en relación al inicio del texto y obteniendo los comunes divisores de dichas diferencias se podía obtener un conjunto de longitudes plausibles para la palabra clave. Se seguía el análisis usando la longitud más probable de entre las encontradas. El siguiente paso consistía en aplicar un análisis de frecuencias a aquellas letras del mensaje cifrado cuyo ordinal difiere en un múltiplo de dicha primera longitud supuesta. Como el cifrado polialfabético Vigenère con cinco letras en su palabra clave –por ejemplo- es equivalente a cinco cifrados monoalfabéticos (o cifrados simples de sustitución) que se van repitiendo en letras cuyo ordinal difiere en el mencionado múltiplo se tiene que para aplicar aquí el análisis de frecuencias basta con hacerlo cinco veces. Es algo similar a descifrar por análisis de frecuencias cinco mensajes que forman parte del total, y que son los formados por las letras con ordinales separados por la longitud de la clave. Evidentemente si con la primera longitud de clave bajo prueba no se obtenía nada coherente, se pasaba a la segunda más probable y se volvía a repetir el proceso hasta obtener con alguna de ellas el mensaje descifrado.

 

 

En realidad el cifrado polialfabético es un método robusto de criptografía, sobre todo si se usan claves muy largas. Casos particulares notables de este tipo de encriptación son el cifrado mediante la máquina Enigma, utilizado por el ejército nazi en la Segunda Guerra Mundial y el cifrado mediante libro de claves de único uso. Este segundo método que cito es el mecanismo perfecto de cifrado, ya que se basa en claves formadas por una secuencia aleatoria de letras de gran longitud, con lo que los mensajes pueden ser muy largos. Cada clave es de uso único y es conocida por emisor y receptor mediante un libro de claves. Aún así, el problema de la distribución de claves sigue vigente, ya que siempre es necesaria cierta logística para distribuir los libros entre los usuarios de este mecanismo, y por lo tanto en principio no es un método invulnerable. En la imagen superior de esta entrada aparece el sabio Al-Kindi. En la intermedia, Leon Battista Alberti, y en la inferior Blaise de Vigenère.

 

Los números computables, la máquina Enigma y Alan Mathison Turing

 

alanturing

 

A mediados del Siglo XX, en el año 1936, un matemático llamado Alan Mathison Turing publicó un artículo de investigación que revolucionó el mundo de la lógica matemática. A principios de siglo, otro matemático de nombre David Hilbert planteó un conjunto de 23 problemas no resueltos por aquel entonces, de vital trascendencia para la disciplina matemática, a la espera de que algunas personas los resolvieran. Hilbert tenía una concepción optimista de las matemáticas, y creía que todo podía ser demostrado, tenía una gran confianza en el poder de esta rama del conocimiento.

Aunque Hilbert no lo incluyó en su lista de problemas de 1900, veintiocho años más tarde otra conferencia de Hilbert hizo trascender otro desafío a las matemáticas modernas, conocido como Entscheidungsproblem, esto es, el problema de la decisión. El problema de la decisión consiste en su planteamiento más general en averiguar si existe un algoritmo genérico que decida si un problema matemático tiene o no demostración. En el planteamiento de Turing, éste lo particularizó, indagando acerca de si existe un procedimiento efectivo con el que se pueda averiguar si una fórmula del cálculo funcional es un teorema o no lo es. En su artículo “Sobre los números computables, con una aplicación al Entscheidungsproblem”, publicado por Turing en 1936 se resuelve esta cuestión, llegándose a la afirmación de que tal algoritmo genérico no existe.

Turing utilizó dos demostraciones para lanzar tal afirmación, consiguiendo un artículo de una gran belleza, originalidad y elegancia.

Para llegar a sus conclusiones, Turing parte de unas máquinas hipotéticas, que en su honor se llamarían después “máquinas de Turing”, y cuyo comportamiento viene a ser parecido al de un automáta o sistema de control secuencial.

Una máquina de Turing es un dispositivo ideal que en cada momento sólo lee el contenido de una única casilla de una cinta de papel que se prolonga en ambas direcciones. En función del contenido de la casilla sobre la que está situada y de la configuración interna (lo que sería el estado del autómata), la máquina bascula hacia otro estado distinto, y después de ésto, realiza alguna operación dependiente del estado, como desplazarse una casilla a la izquierda, o borrar el contenido de la casilla o escribir un símbolo sobre la misma. Se trata pues de un dispositivo secuencial, que opera en base a las secuencias de valores de entrada y de estados de configuración.

Turing también definió lo que ahora se conoce como “máquina de Turing universal”, que es un tipo de máquina que recibe la descripción del comportamiento de una máquina de Turing cualquiera y que reproduce su comportamiento. Tal descripción la recibe como una secuencia de números de entrada que se denominan “número de descripción” o “descripción estándar” de la máquina. Una vez introducido este número en una máquina de Turing universal, ésta imita la máquina de Turing cuyo número de descripción es el introducido. Esta máquina universal vendría a ser como un ordenador con un programa en ejecución, pues es capaz de ejecutar un algoritmo que le pasemos mediante el “programa”. Y una máquina de Turing no universal es en realidad lo equivalente a un programa informático o a un sistema electrónico digital secuencial.

Además, el autor del artículo que aquí describo, distinguió entre máquinas que funcionan sin circularidad y máquinas que funcionan con circularidad. El segundo de estos tipos no es deseable para una máquina de Turing pues significaría que el algoritmo que hemos programado en ella con la tabla de configuración (o con el número de descripción) no llega a pararse nunca, sino que vuelve infinitas veces a operar del mismo modo según el programa, y por tanto dicho algoritmo no genera un resultado.

Si Turing teorizó en base a estas idealizaciones y abstracciones de máquinas de Turing, y máquinas libres de circularidad, lo hizo porque las fórmulas del cálculo funcional tienen un equivalente numérico en base a ciertas reglas, algo similar a lo que hizo Kurt Gödel a las fórmulas lógicas de primer orden en su artículo sobre incompletitud, lo que en dicho contexto se conoce como Gödelización. En base a ciertas premisas, se puede conseguir el equivalente a cualquier fórmula de forma biyectiva, esto es, uno a uno, y así, según esta forma de razonar, una demostración no será otra cosa que una secuencia de números en cierto orden. De aquí viene el uso de máquinas de Turing, pues si una máquina de Turing obtiene una secuencia de números computables, en cuya génesis intervienen las reglas mencionadas, y que siguen a la entrada, en la cual se codifican las premisas de la demostración, y al final se para en el número equivalente a una cierta proposición, éllo significará que de cierta premisa se llega a cierta conclusión, y que ésta es un teorema.

La primera de las demostraciones del teorema se basa en lo siguiente: supongamos que existe un procedimiento que decide si una máquina de Turing se va a parar (no tiene circularidad). Supongamos que hacemos una lista con todas las secuencias posibles de números que proporciona la máquina de Turing ante números de entrada crecientes para un algoritmo (o máquina de Turing) fijo, que no presente circularidad, cosa que podemos hacer dado el supuesto de la existencia de la máquina que decide sobre la parada. Supongamos que esta lista la ampliamos para todas las máquinas de Turing posibles con parada, cada una con la lista de secuencias finitas de números computados. Si ahora empleamos un razonamiento de diagonalización al estilo de Cantor se obtiene lo siguiente:

Tomamos el primer elemento de la primera secuencia de la lista y lo incrementamos en uno, tomamos el segundo elemento de la segunda lista y lo incrementamos en uno, tomamos el  tercero de la tercera lista y lo aumentamos en uno,… tomamos el N-ésimo, para cualquier N, de la N-ésima lista y lo incrementamos la unidad…. Así llegamos a una secuencia que es computable, pero que no figura en la lista de todas las posibles secuencias computables. Es computable, puesto que el proceso de extraer los números de la diagonal y de incrementarlos en uno, a partir de una lista de secuencias computables, es programable en una máquina de Turing. Bastaría con conectar los resultados de todas las máquinas que generan todas las secuencias computables, trabajando en paralelo, a una máquina que es secuencial y por tanto de Turing. Con los actuales diseños electrónicos digitales, esta máquina se podría construir con un demultiplexor de las secuencias computadas, a cuyas líneas de selección de canal de entrada se les aplica un contador, seguido de un sistema combinacional que suma la unidad al número situado a su entrada. Se deduce entonces que el algoritmo o máquina de Turing que obtiene la susodicha secuencia es una operativa computable, pero al no figurar esta nueva secuencia en la lista original que supuestamente contenía todas las secuencias computables posibles, se llega a una contradicción, y el supuesto de la existencia del algoritmo de decisión es falso.

La segunda de las demostraciones es totalmente diferente: supongamos que existe el algoritmo que decide sobre la parada o no de una máquina cualquiera T (ausencia o no de circularidad). Supongamos que conectamos esta máquina D de decisión a una máquina de Turing universal U. El funcionamiento de DU consiste en que a D le pasamos el número de descripción de la máquina T, equivalente al algoritmo cuya parada queremos testear, en caso de decidir que es circular el funcionamiento termina ahí y no hay salida, en caso de no circularidad la máquina D le proporciona a la máquina universal U el número de descripción para que imite la máquina T. La máquina DU así construida es una máquina de Turing libre de circularidad pues sólo da una secuencia finita de salida en el caso de que el algoritmo D cuya existencia suponemos decida que la máquina T no es circular, y en caso de ser circular también da una secuencia de salida finita (secuencia vacía). Ahora bien, supongamos que a la propia máquina DU le introducimos el número de descripción de esa misma máquina DU, el cual existe, por ser DU máquina de Turing. ¿Qué pasará?. Pues pasará que DU verificará que DU no es circular, cosa que suponemos, y a continuación la imitará tomando el número de descripción de DU y viendo que ésta no es circular, con lo cual le pasará el número de descripción de DU de nuevo a sí misma, y así indefinidamente, con lo cual la máquina DU es circular, lo cual contradice la hipótesis de no circularidad de DU y por tanto de la existencia de la máquina D.

Por tanto, no existe un algoritmo genérico que determine si una máquina de Turing cualquiera y, por tanto, una secuencia lógica de razonamientos, terminará su evolución en un resultado. De esta manera, en principio no tenemos forma de saber si una fórmula del cálculo funcional, traducidos sus símbolos a números, tiene demostración o no. (No sabemos de antemano si es o no un teorema, con lo cual ignoramos su naturaleza en cuanto a verdad o falsedad). Ésto implica que también podríamos extender este resultado a un problema matemático genérico, dado que hemos encontrado un contraejemplo que niega ya por sí mismo el enunciado “existe un algoritmo que decide si cualquiera enunciado tiene demostración”, aunque la prueba de Turing relativa al EintschengdungProblem estaba específicamente parcelada a las fórmulas del cálculo funcional. No obstante, en su trabajo hace una descripción muy pormenorizada del funcionamiento de las máquinas de Turing y del concepto de número computable, entendido como aquél que puede ser obtenido mediante cómputo en un número finito de pasos.

 

enigma

 

Alan Turing fue por lo tanto el principal fundador de las bases teóricas de la informática (quizás su principal aportación fue el concepto de computador de programa almacenado en memoria), aunque no debemos olvidar que se debe a John Von Neumann la primera descripción pormenorizada de la arquitectura de computadores que lleva su nombre y que aún hoy se utiliza, y que Claude Shannon desarrolló la teoría matemática de la información, ambos coetáneos suyos. Junto a un equipo de investigadores liderado por el ingeniero británico Tommy Flowers, Turing creó uno de los primeros ordenadores de la historia, el “Colossus”, que en realidad no era un computador de propósito general o máquina de Turing universal. El objetivo de “Colossus” era descifrar los mensajes de comunicaciones emitidos por los nazis, ya avanzada la II Guerra Mundial, encriptados con la máquina “Tunny”, creada por la empresa alemana Lorentz. Esta máquina operaba en código binario y alimentaba con un chorro de bits un teletipo. Dicho flujo transmitido se obtenía a partir de dos sumas binarias sucesivas del chorro original o mensaje en claro pasado al código binario, con dos claves binarias obtenidas mediante el concurso de 12 rotores mecánicos, que se emitía con el teletipo y su propia idiosincrasia de señales. Estos mensajes eran de vital importancia, dado que Tunny era utilizada para las comunicaciones del Alto Mando Alemán. Además de la creación de Colossus y de sus contribuciones a la lógica matemática, Turing fue figura clave en la desencriptación de los mensajes codificados por los alemanes mediante la máquina Enigma, gracias a su diseño y puesta a punto de las máquinas bomba que se usaban para agilizar el descifrado de Enigma. En realidad las máquinas bomba no fueron un invento original del protagonista de esta entrada, ya que que en los primeros embites de la guerra, otro grupo de matemáticos y criptógrafos polacos liderados por el matemático Marian Rejewski construyeron máquinas bomba para agilizar la rotura del código Enigma original. Sus desarrollos fueron comunicados a las inteligencias francesa y británica. Pero los nazis perfeccionaron a base de otros añadidos la codificación Enigma original. Por ello los criptógrafos de Bletchley Park, lugar donde se libró la verdadera guerra contra Enigma y donde Alan Turing trabajó, se vieron sumidos en la total oscuridad en lo que al desciframiento se refiere. Bletchley Park está situado a unos 80 km al Norte de Londres, y allí se construyó un complejo de barracones junto a una mansión victoriana ya existente, utilizándose para las operaciones de la escuela gubernamental de códigos y cifrado (GC&CS), entidad vinculada al servicio secreto británico. La figura de Turing en este lugar fue realmente muy importante, ya que rediseñó las máquinas bomba gracias a los “pellizcos” que los aliados obtuvieron consiguiendo máquinas Enigma y documentación de U-boats capturados, y gracias a su portentosa inteligencia. La existencia del complejo de Bletchley Park fue el secreto mejor guardado de los aliados, y todo lo relacionado con él no fue desclasificado hasta muchos años más tarde del final de la guerra. De hecho, Winston Churchill, primer ministro británico a la sazón, y que fue una de las contadas personas que tenía conocimiento de que se estaban descifrando los mensajes, (que los alemanes consideraban, no sin justificación, indescifrables) en sus círculos más privados designaba a Bletchley Park como “mi oca de los huevos de oro que nunca cacarea”. Una vez terminada la II Gran Guerra, Alan M. Turing llevó a cabo diversas investigaciones pioneras en la biología matemática, relacionadas con la morfogenésis, y en el campo de la inteligencia artificial (a la que aportó los fundamentos y algunos conceptos como el que se conoce como “test de Turing”), usando para ello los primeros computadores que se estaban creando en Gran Bretaña.

Pero tal vez la hazaña de Turing que tuvo más trascendencia práctica -aunque desde luego no fue su mayor logro hablando en términos generales- fue romper el código Enigma de los submarinos nazis, conocido en Bletchley Park como “Shark”. Gracias a ello los convoyes de buques mercantes que viajaban desde Estados Unidos transportando suministros, pudieron ser salvaguardados, después de un gran número de bajas, evitándose la derrota británica en el momento crucial posterior a los bombardeos sobre Inglaterra, cuando Francia ya estaba ocupada por el ejército nazi.

La máquina Enigma brindaba un sistema de encriptación polialfabético con muchísimos alfabetos de sustitución, uno por cada avance de los rotores de la máquina, con lo cual para determinar el mensaje cifrado habría que conocer con exactitud los parámetros involucrados en la puesta en marcha de “Enigma”, esto es, la posición de los rotores y de las clavijas, y por supuesto poseer una Enigma idéntica a la “transmisora”. Un análisis de frecuencias complejo no bastaba para descifrar un mensaje, dado que aún a pesar de que el mensaje transmitido fuese largo, los alfabetos de sustitución se sucedían al pulsar cada tecla y no llegaban a repetirse.

 

enigma2

 

Enigma tenía la apariencia de una máquina de escribir, estaba alimentada por una pila, y su funcionamiento se basaba en cerrar circuitos de corriente continua. Cuando ésto ocurría, es decir, al pulsar cada tecla, la corriente fluía desde el teclado, pasando hacia el panel “stecker” o clavijero, que era configurable, y de éste iba al tambor de entrada, que estaba en contacto con el primer rotor. Cada rotor tenía dos superficies planas a ambos lados y 26 dientes, correspondientes a las 26 letras del alfabeto. Existían hasta cinco rotores con distintos cableados. En cada uno de esos rotores había un cableado diferente entre la interfaz de entrada, que una vez colocado contactaría con el rotor anterior (con el tambor de entrada para el primero de ellos), y su interfaz de salida (que ya posicionado estaba en contacto con el rotor siguiente). Después de la cara de salida del último rotor había un reflector, con el que se conseguía que, a igual configuración de la máquina, una letra del teclado fuese la misma que la letra iluminada en el panel luminoso obtenida por la pulsación de su traspuesta, es decir que Enigma sirviera tanto para cifrar como para descifrar si se usaba la misma clave. Desde el reflector la corriente seguía fluyendo por los rotores en sentido inverso al anterior, pero siguiendo otros caminos eléctricos diferentes; y de nuevo a través del clavijero pasando por otra clavija distinta, y de ahí a un terminal de la bombilla de la letra cifrada (o descifrada según el extremo de comunicaciones en que se operase). Como el otro terminal de cada bombilla estaba conectado con uno de los terminales de cada pulsador, al pulsar sobre él se cerraba el circuito y se obraba el milagro, produciéndose además un avance de una letra del rotor de menos peso, que podía acarrear un avance del rotor siguiente al terminarse una vuelta completa del mismo. Esto mismo ocurría con el segundo rotor y sucesivos, y así hasta las 26 x 26 x 26 pulsaciones en la máquina de 3 rotores, momento en que se volvía a tener la misma configuración de rotores que en la primera letra codificada y por tanto el mismo alfabeto de sustitución. Una letra nunca se codificaba en dos pulsaciones consecutivas con la misma letra cifrada, y asimismo una letra jamás se codificaba igual a sí misma, lo cual brindó a los criptógrafos de Bletchley Park un medio para obtener plantillas de letras posibles en un mensaje, constituyendo uno de los tendones de Aquiles que facilitaron el fracaso de Enigma.

Por si ésto solo de por sí no constituyera un sistema robusto, los alemanes lo pulieron aún más, ofreciendo a sus usuarios una logística que se ponía en práctica con determinada frecuencia, consistente en la actualización de documentación relativa a los rotores empleados cada día, el orden en que se colocaban (diferentes entre los distintos ejércitos de tierra, mar o aire), las letras de posición inicial en cada rotor, así como de las posiciones de las clavijas en el panel stecker, y las tablas de codificación de bigramas. Un bigrama es un conjunto de dos letras. En una tabla de 26 x 26 ítems se representaba para cada bigrama original el bigrama transformado correspondiente (era un esquema “hecho a mano” y que también podía variar). De este modo, el protocolo de cifrado establecía que para trabajar con la Enigma de 3 rotores era necesario en primer lugar consultar en la documentación los 3 rotores concretos del día, el orden en que se colocaban, y la letra que tenía que situarse en cada rotor, y además la configuración del clavijero. Después de ésto el operario transmisor elegía 3 letras del alfabeto al azar (la clave), que serían las letras de ventanilla iniciales para usar Enigma en la fase de codificación. Pero antes de ello, las codificaba mediante la Enigma recién configurada y colocaba en un papel cada letra obtenida emparejada con otra elegida al azar debajo de ella. Los tres pares de letras así obtenidos se transformaban mediante la tabla de bigramas y después esos tres bigramas resultantes se colocaban al principio del mensaje. Las 3 letras clave de partida eran las que servían para reconfigurar de nuevo los tres rotores elegidos, y a partir de este punto se empezaba a codificar el mensaje, comenzando la transmisión Morse con los tres bigramas obtenidos a partir de la clave en la operativa antes descrita, pero sin codificar con Enigma, es decir, tal cual se generaron; a lo que seguía ya el mensaje cifrado según lo que fuese “soltando” la máquina mediante los sucesivos cierres de circuitos de corriente. De esta manera, para descifrar se operaba de manera inversa para obtener la clave usada; es decir, se configuraba Enigma con los rotores, posiciones, letras, y clavijas concretos del día; luego se obtenían los 3 bigramas intermedios mediante la tabla de bigramas en sentido inverso. El paso siguiente era coger las tres letras superiores de dichos tres bigramas intermedios y pulsarlas en Enigma, obteniéndose las letras de los rotores empleadas como clave. Se reconfiguraban entonces con ellas los rotores colocándolas como “letras de ventanilla”, y se descodificaba pulsando las letras codificadas y obteniéndose las traspuestas (u originales).

No es muy difícil el darse cuenta de que el número de configuraciones posibles de Enigma era descomunal, del orden de más de diez mil billones de configuraciones. Por ello la máquina Enigma era un sistema muy robusto y dificilísimo de desencriptar. El sistema Enigma viene a ser parecido en cierto modo al cifrado Vigènere, que es también polialfabético, pero que tiene un número de alfabetos diferentes para codificar cada mensaje solamente igual al número de letras de la palabra clave. Enigma tenía una “letra de palabra clave” por cada posición de los rodillos, y éstos realizaban un avance por cada pulsación de una letra en el teclado, generándose en cada pulsación un nuevo alfabeto de sustitución para la letra siguiente.

Por su importante contribución al descifrado de los mensajes Enigma, Turing fue condecorado con la Orden del Imperio Británico.

La muerte de Turing fue prematura y triste. Se cree que se suicidó comiendo una manzana envenenada con cianuro, aunque la verdad no se conoce con certeza absoluta. En un juicio en el que tuvo que prestar declaración, derivado de un robo perpetrado en su casa, tuvo que confesar que era homosexual, y entonces ésto estaba penado por la jurisdicción británica. Le dieron como opciones ir a la cárcel o someterse a un “tratamiento” de castración química basado en hormonas. Eligió lo segundo, pero la consecuencia fue su pérdida de forma física (era un consumado atleta que incluso estuvo a punto de ser elegido para los primeros Juegos Olímpicos posteriores a la II Guerra Mundial, y ésto le afectó mucho) y las taras psicológicas que posiblemente perturbaron aún más su mente, cosa que para un científico destacado como él lo fue tiene que ser una gran desdicha, al saberse incapaz de pensar con claridad. En otras palabras, le hicieron la vida imposible. Pero sus contribuciones han trascendido por su importancia, para el goce de las generaciones presentes y venideras, y para el bien de la mayor cooperativa mundial, la ciencia; y es a él a quien se le puede atribuir el mérito de ser quizás el primero y mayor de los padres conceptuales de los computadores tal y como hoy los conocemos. Quién sabe a lo que llegaría un espíritu agudo y creativo como el de Turing si no muriese a la edad de 42 años. En cualquier caso, es meridianamente claro que la sociedad y en particular la justicia, no fueron lo que se dice recíprocos con él en relación a las impresionantes contribuciones a la Humanidad, en todo su sentido, con que este genio polifacético del Siglo XX nos obsequió.