El criptoanálisis del cifrado de Lorenz fue el proceso que permitió a los británicos leer mensajes de alto nivel del ejército alemán durante la Segunda Guerra Mundial . La Escuela de Códigos y Cifrados del Gobierno Británico (GC&CS) en Bletchley Park descifró muchas comunicaciones entre el Oberkommando der Wehrmacht (OKW, Alto Mando Alemán) en Berlín y sus comandos del ejército en toda la Europa ocupada, algunas de las cuales estaban firmadas "Adolf Hitler, Führer". [3] Estas fueron transmisiones de radio no Morse interceptadas que habían sido cifradas por los accesorios de cifrado de flujo del rotor del teleimpresor Lorenz SZ . Los descifrados de este tráfico se convirtieron en una fuente importante de inteligencia " Ultra ", que contribuyó significativamente a la victoria aliada. [4]
Para sus mensajes secretos de alto nivel, las fuerzas armadas alemanas cifraron cada carácter utilizando varias máquinas de cifrado de flujo Geheimschreiber (escritor secreto) en línea en ambos extremos de un enlace telegráfico utilizando el Alfabeto Telegráfico Internacional No. 2 (ITA2) de 5 bits . Posteriormente se descubrió que estas máquinas eran la Lorenz SZ (SZ por Schlüssel-Zusatz , que significa "accesorio de cifrado") para el ejército, [5] la Siemens y Halske T52 para la fuerza aérea y la Siemens T43, que fue poco utilizada y nunca roto por los aliados. [6]
Los descifrados de Bletchley Park de mensajes cifrados con las máquinas Enigma revelaron que los alemanes llamaron a uno de sus sistemas de transmisión por teleimpresor inalámbrico "Sägefisch" (pez sierra), [7] lo que llevó a los criptógrafos británicos a referirse al tráfico radiotelegráfico alemán cifrado como " pez ". [5] " Tunny " (atún) fue el nombre dado al primer enlace no Morse, y posteriormente se utilizó para las máquinas de cifrado y su tráfico. [8]
Al igual que con el criptoanálisis completamente independiente del Enigma , fueron las deficiencias operativas alemanas las que permitieron el diagnóstico inicial del sistema y una forma de descifrarlo. [9] A diferencia de Enigma, ninguna máquina física llegó a manos aliadas hasta el final de la guerra en Europa, mucho después de que se hubiera establecido el descifrado total. [10] [11] Los problemas de descifrar los mensajes de Tunny llevaron al desarrollo de " Colossus ", la primera computadora digital electrónica programable del mundo, diez de las cuales estaban en uso al final de la guerra, [12] [13] por momento en el que alrededor del 90% de los mensajes seleccionados de Tunny estaban siendo descifrados en Bletchley Park. [14]
Albert W. Small, un criptoanalista del Cuerpo de Señales del Ejército de EE. UU. que fue adscrito a Bletchley Park y trabajó en Tunny, dijo en su informe de diciembre de 1944 a Arlington Hall que:
Las soluciones diarias de los mensajes de Fish en GC&CS reflejan una base de genio matemático británico, una excelente capacidad de ingeniería y un sólido sentido común. Cada uno de estos ha sido un factor necesario. Se podría haber enfatizado demasiado o subestimado cada una de ellas en detrimento de las soluciones; un hecho destacable es que la fusión de los elementos ha sido aparentemente en perfecta proporción. El resultado es una contribución excepcional a la ciencia criptoanalítica. [15]
Los archivos adjuntos de cifrado Lorenz SZ implementaron un cifrado de flujo Vernam , utilizando una compleja matriz de doce ruedas que entregaban lo que debería haber sido un número pseudoaleatorio criptográficamente seguro como un flujo de claves . El flujo de claves se combinó con el texto sin formato para producir el texto cifrado en el extremo transmisor utilizando la función exclusiva o (XOR) . En el extremo receptor, una máquina idénticamente configurada produjo el mismo flujo de claves que se combinó con el texto cifrado para producir el texto sin formato, es decir, el sistema implementó un algoritmo de clave simétrica .
El flujo de claves fue generado por diez de las doce ruedas. Esto fue producto de aplicar XOR al carácter de 5 bits generado por las cinco ruedas de la derecha, las ruedas chi ( ), y las cinco de la izquierda, las ruedas psi ( ). Las ruedas chi siempre se movían en una posición por cada carácter de texto cifrado entrante, pero las ruedas psi no.
Las dos ruedas centrales mu ( ) o "motor" determinaban si las ruedas psi giraban o no con un nuevo carácter. [17] [18] Después de cifrar cada letra, las cinco ruedas psi se movían o permanecían quietas y se usaba nuevamente la misma letra de la clave psi. Al igual que las ruedas chi , la rueda 61 avanzaba después de cada personaje. Cuando 61 tenía la leva en la posición activa y así generó x (antes de moverse), 37 avanzó una vez: cuando la leva estaba en la posición inactiva (antes de moverse) 37 y las ruedas psi permanecieron quietas. [19] En todas las máquinas, excepto en las primeras, había un factor adicional que influía en el movimiento o no de las ruedas psi . Eran de cuatro tipos diferentes y se denominaban "Limitaciones" en Bletchley Park. Todos involucraban algún aspecto de las posiciones previas de las ruedas de la máquina. [20]
El número de levas en el conjunto de doce ruedas de las máquinas SZ42 ascendía a 501 y estaban cocebadas entre sí, dando un período extremadamente largo antes de que se repitiera la secuencia clave. Cada leva podría estar en una posición elevada, en cuyo caso contribuyó x a la lógica del sistema, invirtiendo el valor de un bit, o en una posición baja, en cuyo caso generó • . [10] El número total posible de patrones de levas elevadas era 2 501 , que es un número astronómicamente grande. [21] En la práctica, sin embargo, aproximadamente la mitad de las levas de cada rueda estaban en posición elevada. Más tarde, los alemanes se dieron cuenta de que si el número de levas elevadas no era muy cercano al 50%, habría series de x sy • s, una debilidad criptográfica. [22] [23]
El proceso de determinar cuál de las 501 levas estaba en la posición elevada se llamó "rotura de rueda" en Bletchley Park. [24] Deducir las posiciones iniciales de las ruedas para una transmisión particular se denominó "ajuste de ruedas" o simplemente "ajuste". El hecho de que todas las ruedas psi se movieran juntas, pero no con cada carácter de entrada, fue una debilidad importante de las máquinas que contribuyó al éxito criptoanalítico británico.
La telegrafía electromecánica se desarrolló en las décadas de 1830 y 1840, mucho antes que la telefonía , y operaba en todo el mundo en la época de la Segunda Guerra Mundial . Un extenso sistema de cables unía sitios dentro y entre países, con un voltaje estándar de −80 V que indica una "marca" y +80 V que indica un "espacio". [25] Cuando la transmisión por cable se volvió impracticable o inconveniente, como en el caso de las unidades móviles del ejército alemán, se utilizó la transmisión por radio.
Los teleimpresores en cada extremo del circuito consistían en un teclado y un mecanismo de impresión y, muy a menudo, un mecanismo de perforación y lectura de cinta de papel perforada de cinco orificios . Cuando se usaba en línea , presionar una tecla del alfabeto en el extremo transmisor hacía que el carácter relevante se imprimiera en el extremo receptor. Sin embargo, normalmente el sistema de comunicación implicaba que el operador transmisor preparara un conjunto de mensajes fuera de línea pegándolos en una cinta de papel y luego conectándose en línea sólo para la transmisión de los mensajes grabados en la cinta. Normalmente, el sistema envía unos diez caracteres por segundo, por lo que ocupa la línea o el canal de radio durante un período de tiempo más corto que al escribir en línea.
Los caracteres del mensaje estaban representados por los códigos del Alfabeto Telegráfico Internacional N° 2 ( ITA2 ). El medio de transmisión, ya sea por cable o por radio, utilizaba comunicación en serie asíncrona con cada carácter señalado por un impulso de inicio (espacio), 5 impulsos de datos y 1½ impulsos de parada (marca). En Bletchley Park, los impulsos de marca se indicaban con x("cruz") y los impulsos espaciales con •("punto"). [26] Por ejemplo, la letra "H" se codificaría como ••x•x.
Los caracteres de desplazamiento de cifras (FIGS) y de letras (LETRS) determinaban cómo el extremo receptor interpretaba la cadena de caracteres hasta el siguiente carácter de desplazamiento. Debido al peligro de que un carácter de cambio se corrompa, algunos operadores escribirían un par de caracteres de cambio al cambiar de letras a números o viceversa . Entonces escribirían 55M88 para representar un punto. [28] Esta duplicación de caracteres fue muy útil para el criptoanálisis estadístico utilizado en Bletchley Park. Después del cifrado, los caracteres de desplazamiento no tenían ningún significado especial.
La velocidad de transmisión de un mensaje radiotelegráfico era tres o cuatro veces mayor que la del código Morse y un oyente humano no podía interpretarlo. Sin embargo, un teleimpresor estándar produciría el texto del mensaje. El archivo adjunto de cifrado de Lorenz cambió el texto plano del mensaje a texto cifrado que no era interpretable para aquellos que no tenían una máquina idéntica configurada de manera idéntica. Éste fue el desafío al que se enfrentaron los descifradores de códigos de Bletchley Park.
La interceptación de transmisiones Tunny presentó problemas sustanciales. Como los transmisores eran direccionales, la mayoría de las señales eran bastante débiles en los receptores de Gran Bretaña. Además, se utilizaban unas 25 frecuencias diferentes para estas transmisiones y, en ocasiones, la frecuencia se cambiaba a mitad de camino. Después del descubrimiento inicial de las señales no Morse en 1940, se instaló una estación de intercepción de radio llamada Establecimiento de Investigación y Desarrollo del Ministerio de Asuntos Exteriores en una colina en Ivy Farm en Knockholt , Kent, específicamente para interceptar este tráfico. [29] [30] El centro estaba dirigido por Harold Kenworthy, tenía 30 equipos receptores y empleaba a unas 600 personas. Entró en pleno funcionamiento a principios de 1943.
Como un solo carácter perdido o dañado podía hacer imposible el descifrado, se requería la mayor precisión. [31] La tecnología del ondulador utilizada para registrar los impulsos se había desarrollado originalmente para Morse de alta velocidad. Produjo un registro visible de los impulsos en una estrecha cinta de papel. Luego, esto fue leído por personas empleadas como "lectores de deslizamientos" que interpretaron los picos y valles como marcas y espacios de los caracteres ITA2. [32] Luego se produjo cinta de papel perforada para transmisión telegráfica a Bletchley Park, donde se perforó. [33]
El cifrado Vernam implementado por las máquinas Lorenz SZ utiliza la función booleana "exclusiva o" (XOR) , simbolizada por ⊕ y verbalizada como "A o B pero no ambas". Esto se representa en la siguiente tabla de verdad , donde x representa "verdadero" y • representa "falso".
Otros nombres para esta función son: disyunción exclusiva, no igual (NEQ) y suma de módulo 2 (sin "llevar") y resta (sin "pedir prestado"). La suma y la resta del módulo 2 son idénticas. Algunas descripciones del descifrado de Tunny se refieren a la suma y otras a la diferenciación, es decir, a la resta, pero significan lo mismo. El operador XOR es tanto asociativo como conmutativo .
La reciprocidad es una característica deseable de una máquina de cifrado, de modo que la misma máquina con las mismas configuraciones pueda usarse para cifrar o descifrar. El cifrado Vernam logra esto, ya que la combinación del flujo de caracteres de texto sin formato con el flujo de claves produce el texto cifrado, y la combinación de la misma clave con el texto cifrado regenera el texto sin formato. [34]
Simbólicamente:
y
La idea original de Vernam era utilizar la práctica de la telegrafía convencional, con una cinta de papel del texto sin formato combinada con una cinta de papel de la clave en el extremo transmisor, y una cinta de clave idéntica combinada con la señal de texto cifrado en el extremo receptor. Cada par de cintas clave habría sido único (una cinta de una sola vez ), pero generar y distribuir dichas cintas presentaba considerables dificultades prácticas. En la década de 1920, cuatro hombres de diferentes países inventaron máquinas de cifrado Vernam de rotor para producir un flujo de claves que actuara en lugar de una cinta de claves. El Lorenz SZ40/42 fue uno de ellos. [35]
.svg/1280px-English_letter_frequency_(alphabetic).svg.png)
Un cifrado de sustitución monoalfabético como el cifrado César se puede descifrar fácilmente, dada una cantidad razonable de texto cifrado. Esto se logra mediante el análisis de frecuencia de las diferentes letras del texto cifrado y comparando el resultado con la distribución de frecuencia de letras conocida del texto sin formato. [36]
Con un cifrado polialfabético , hay un alfabeto de sustitución diferente para cada carácter sucesivo. Entonces, un análisis de frecuencia muestra una distribución aproximadamente uniforme , como la obtenida de un generador de números (pseudo)aleatorios . Sin embargo, debido a que un conjunto de ruedas Lorenz giraba con cada carácter mientras que el otro no, la máquina no ocultó el patrón en el uso de caracteres adyacentes en el texto claro alemán. Alan Turing descubrió esta debilidad e inventó la técnica de diferenciación que se describe a continuación para explotarla. [37]
El patrón de cuáles de las levas estaban en la posición elevada y cuáles en la posición bajada se cambiaba diariamente en las ruedas del motor ( 37 y 61). Los patrones de levas de la rueda chi se cambiaban inicialmente mensualmente. Los patrones de las ruedas psi se cambiaron trimestralmente hasta octubre de 1942, cuando la frecuencia se aumentó a mensual, y luego a diario el 1 de agosto de 1944, cuando la frecuencia de cambio de los patrones de las ruedas chi también se cambió a diaria. [38]
El número de posiciones iniciales de las ruedas era 43×47×51×53×59×37×61×41×31×29×26×23, que es aproximadamente 1,6×10 19 (16 mil millones de millones), un número demasiado grande. que los criptoanalistas intenten un " ataque de fuerza bruta " exhaustivo. En ocasiones, los operadores de Lorenz desobedecían las instrucciones y se transmitían dos mensajes con las mismas posiciones iniciales, fenómeno denominado "profundidad" . El método mediante el cual el operador transmisor le decía al operador receptor la configuración de la rueda que había elegido para el mensaje que estaba a punto de transmitir se denominó "indicador" en Bletchley Park.
En agosto de 1942, los comienzos formulados de los mensajes, que eran útiles para los criptoanalistas, fueron reemplazados por algún texto irrelevante, lo que hizo que identificar el mensaje verdadero fuera algo más difícil. Este nuevo material fue denominado quatsch (que en alemán significa "tonterías") en Bletchley Park. [39]
Durante la fase de las transmisiones experimentales, el indicador constaba de doce nombres alemanes, cuyas letras iniciales indicaban la posición en la que los operadores giraban las doce ruedas. Además de mostrar cuándo dos transmisiones estaban completamente en profundidad, también permitió identificar profundidades parciales donde dos indicadores diferían solo en una o dos posiciones de las ruedas. A partir de octubre de 1942, el sistema indicador cambió y el operador emisor transmitió las letras no cifradas QEP [40] seguidas de un número de dos dígitos. Este número se tomó en serie de un libro de códigos que se había entregado a ambos operadores y proporcionaba, para cada número QEP, los ajustes de las doce ruedas. Los libros fueron reemplazados cuando se agotaron, pero entre reemplazos, las profundidades completas podían identificarse mediante la reutilización de un número QEP en un enlace Tunny en particular. [41]
El primer paso para descifrar un nuevo cifrado es diagnosticar la lógica de los procesos de cifrado y descifrado. En el caso de una máquina de cifrado como Tunny, esto implicaba establecer la estructura lógica y, por tanto, el funcionamiento de la máquina. Esto se logró sin el beneficio de ver una máquina, lo que sólo ocurrió en 1945, poco antes de la victoria aliada en Europa. [45] El sistema de cifrado fue muy bueno para garantizar que el texto cifrado Z no contuviera características estadísticas, periódicas o lingüísticas que lo distinguieran del azar. Sin embargo, esto no se aplica a K , χ , ψ' y D , que fue la debilidad que significó que las claves Tunny pudieran resolverse. [46]
Durante el período experimental de las transmisiones de Tunny, cuando se utilizaba el sistema indicador de doce letras, John Tiltman , el criptoanalista veterano y notablemente talentoso de Bletchley Park, estudió los textos cifrados de Tunny e identificó que utilizaban un cifrado Vernam.
Cuando dos transmisiones ( a y b ) utilizan la misma clave, es decir, son en profundidad, combinarlas elimina el efecto de la clave. [47] Llamemos a los dos textos cifrados Za y Zb , a la clave K y a los dos textos claros Pa y Pb . Entonces tenemos:
Si se pueden resolver los dos textos sin formato, la clave se puede recuperar de cualquier par de texto cifrado-texto sin formato, por ejemplo:
El 31 de agosto de 1941 se recibieron dos mensajes largos que tenían el mismo indicador HQIBPEXEZMUG. Los primeros siete caracteres de estos dos textos cifrados eran iguales, pero el segundo mensaje era más corto. Los primeros 15 caracteres de los dos mensajes fueron los siguientes (según la interpretación de Bletchley Park):
John Tiltman probó varias piezas probables de texto sin formato, es decir, "cunas" , contra la cadena Za ⊕ Zb y descubrió que el primer mensaje de texto sin formato comenzaba con la palabra alemana SPRUCHNUMMER (número de mensaje). En el segundo texto sin formato, el operador había utilizado la abreviatura común NR para NUMMER . Había más abreviaturas en el segundo mensaje y, en ocasiones, la puntuación difería. Esto permitió a Tiltman determinar, durante diez días, el texto sin formato de ambos mensajes, ya que una secuencia de caracteres de texto sin formato descubierta en Pa podría luego compararse con Pb y viceversa . [48] A su vez, esto arrojó casi 4000 caracteres de clave. [49]
Miembros de la Sección de Investigación trabajaron en esta clave para intentar derivar una descripción matemática del proceso de generación de claves, pero sin éxito. Bill Tutte se unió a la sección en octubre de 1941 y se le asignó la tarea. Había leído química y matemáticas en el Trinity College de Cambridge antes de ser reclutado para Bletchley Park. En su curso de formación, le habían enseñado la técnica de examen Kasiski de escribir una clave en papel cuadriculado con una nueva fila después de un número definido de caracteres que se sospechaba que era la frecuencia de repetición de la clave. Si este número fuera correcto, las columnas de la matriz mostrarían más repeticiones de secuencias de caracteres que el azar por sí solo.
Tutte pensó que era posible que, en lugar de utilizar esta técnica en todas las letras de la clave, que probablemente tuvieran una frecuencia de repetición larga, valdría la pena probarla en la secuencia formada tomando solo un impulso (bit). de cada letra, basándose en que " la parte podría ser criptográficamente más simple que el todo ". [50] Dado que los indicadores Tunny usaban 25 letras (excluyendo J) para 11 de las posiciones, pero solo 23 letras para la duodécima, probó la técnica de Kasiski en el primer impulso de los caracteres clave usando una repetición de 25 × 23 = 575 Esto no produjo un gran número de repeticiones en las columnas, pero Tutte sí observó el fenómeno en diagonal. Por lo tanto, volvió a intentarlo con 574, que mostraba repeticiones en las columnas. Al reconocer que los factores primos de este número son 2, 7 y 41, volvió a intentarlo con un punto de 41 y " obtuvo un rectángulo de puntos y cruces que estaba repleto de repeticiones ". [51]
Estaba claro, sin embargo, que la secuencia de los primeros impulsos era más complicada que la producida por una sola rueda de 41 posiciones. Tutte llamó a este componente de la clave χ 1 ( chi ). Supuso que había otro componente, al que se le aplicaba XOR con esto, que no siempre cambiaba con cada nuevo carácter, y que era el producto de una rueda a la que llamó ψ 1 ( psi ). Lo mismo se aplica a cada uno de los cinco impulsos, indicados aquí mediante subíndices. Entonces, para un solo carácter, la clave K constaba de dos componentes:
La secuencia real de caracteres agregados por las ruedas psi , incluidos aquellos cuando no avanzan, se denominó psi extendida , [43] y se simboliza por ψ′
La derivación de Tutte del componente ψ fue posible gracias al hecho de que era más probable que los puntos fueran seguidos de puntos, y que era más probable que las cruces fueran seguidas de cruces. Esto fue producto de una debilidad en la configuración clave alemana, que luego frenaron. Una vez que Tutte hizo este avance, el resto de la Sección de Investigación se unió para estudiar los otros impulsos, y se estableció que las cinco ruedas ψ se movían todas juntas bajo el control de dos ruedas μ ( mu o "motor").
Diagnosticar el funcionamiento de la máquina Tunny de esta manera fue un logro criptoanalítico verdaderamente notable, y fue descrito cuando Tutte fue nombrado Oficial de la Orden de Canadá en octubre de 2001, como " una de las mayores hazañas intelectuales de la Segunda Guerra Mundial ". [52]
En julio de 1942, Alan Turing pasó unas semanas en la Sección de Investigación. [53] Se había interesado en el problema de liberar a Tunny de las llaves que se habían obtenido de las profundidades. [54] En julio, desarrolló un método para derivar los ajustes de la leva ("rotura de rueda") a partir de una longitud de llave. Llegó a ser conocido como "Turingery" [55] (apodado en broma "Turingismus" por Peter Ericsson, Peter Hilton y Donald Michie [54] ) e introdujo el importante método de "diferenciación" en el que se basa gran parte del resto de la resolución de Tunny Keys en el ausencia de profundidades, se basó. [55]
Se estaba buscando un proceso que manipulara el texto cifrado o la clave para producir una distribución de frecuencia de caracteres que se apartara de la uniformidad que el proceso de cifrado pretendía lograr. Turing descubrió que la combinación XOR de los valores de caracteres sucesivos (adyacentes) en un flujo de texto cifrado o clave enfatizaba cualquier desviación de una distribución uniforme. [55] [56] La secuencia resultante se llamó diferencia (simbolizada por la letra griega "delta" Δ ) [57] porque XOR es lo mismo que la resta de módulo 2. Entonces, para una secuencia de caracteres S , la diferencia ΔS se obtuvo de la siguiente manera, donde el subrayado indica el carácter siguiente:
El flujo S puede ser texto cifrado Z , texto plano P , clave K o cualquiera de sus dos componentes χ y ψ . La relación entre estos elementos todavía se aplica cuando se diferencian. Por ejemplo, además de:
Es el caso que:
Lo mismo ocurre con el texto cifrado, el texto sin formato y los componentes clave:
Entonces:
La razón por la que la diferenciación proporcionó un camino hacia Tunny fue que, aunque la distribución de frecuencia de los caracteres en el texto cifrado no podía distinguirse de una secuencia aleatoria, no ocurría lo mismo con una versión del texto cifrado a partir de la cual el elemento chi de la clave tenía sido eliminado. Esto se debe a que, cuando el texto sin formato contenía un carácter repetido y las ruedas psi no se movían, el carácter psi diferenciado ( Δ ψ ) sería el carácter nulo (' / ' en Bletchley Park). Cuando se aplica XOR con cualquier carácter, este carácter no tiene ningún efecto, por lo que en estas circunstancias, ΔK = Δ χ . El texto cifrado modificado mediante la eliminación del componente chi de la clave se denominó de- chi D en Bletchley Park, [58] y el proceso de eliminación como "de- chi -ing". Lo mismo ocurrió con la eliminación del componente psi , que se conocía como "de- psi -ing" (o "suspiro profundo" cuando era particularmente difícil). [59]
Entonces el delta dechi ΔD fue :
Los caracteres repetidos en el texto plano eran más frecuentes debido a las características del alemán (EE, TT, LL y SS son relativamente comunes) [60] y porque los telegrafistas repetían con frecuencia los caracteres de desplazamiento de cifras y letras [61] como sus La pérdida en una transmisión telegráfica ordinaria podría dar lugar a un galimatías. [62]
Para citar el Informe General sobre Tunny:
Turingery introdujo el principio de que la clave diferenciada en uno, ahora llamada ΔΚ , podía proporcionar información que no se podía obtener de la clave ordinaria. Este principio Δ iba a ser la base fundamental de casi todos los métodos estadísticos de rotura y ajuste de ruedas. [55]
Se aplicó diferenciación a cada uno de los impulsos de los caracteres codificados ITA2. [63] Entonces, para el primer impulso, que fue cifrado por las ruedas χ 1 y ψ 1 , diferenciadas en uno:
Y para el segundo impulso:
Etcétera.
La periodicidad de las ruedas chi y psi para cada impulso (41 y 43 respectivamente para el primer impulso) también se refleja en el patrón de ΔK . Sin embargo, dado que las ruedas psi no avanzaron para cada carácter de entrada, como lo hicieron las ruedas chi , no fue simplemente una repetición del patrón cada 41 × 43 = 1763 caracteres para ΔK 1 , sino una secuencia más compleja.
El método de Turing para derivar los ajustes de las levas de las ruedas a partir de una longitud de llave obtenida de una profundidad implicaba un proceso iterativo . Dado que el carácter delta psi era el carácter nulo ' / ' la mitad del tiempo en promedio, la suposición de que ΔK = Δ χ tenía un 50% de posibilidades de ser correcta. El proceso comenzó tratando un carácter ΔK particular como si fuera el Δ χ para esa posición. El supuesto patrón de bits resultante de x y • para cada rueda chi se registró en una hoja de papel que contenía tantas columnas como caracteres había en la clave, y cinco filas que representaban los cinco impulsos de Δ χ . Dado el conocimiento procedente del trabajo de Tutte, de la periodicidad de cada una de las ruedas, esto permitió la propagación de estos valores en las posiciones adecuadas en el resto de la clave.
También se preparó un juego de cinco hojas, una para cada una de las ruedas chi . Estos contenían un conjunto de columnas correspondientes en número a las levas de la rueda chi apropiada , y se denominaban "jaula". Entonces la jaula χ 3 tenía 29 de esas columnas. [64] Las 'conjeturas' sucesivas de los valores de Δ χ produjeron más valores putativos del estado de leva. Estos podían estar de acuerdo o en desacuerdo con los supuestos anteriores, y en estas hojas se hizo un recuento de acuerdos y desacuerdos. Cuando los desacuerdos superaban sustancialmente a los acuerdos, se suponía que el carácter Δ ψ no era el carácter nulo ' / ', por lo que se descartaba el supuesto pertinente. Progresivamente se dedujeron todos los reglajes de levas de las ruedas chi , y de ellos, los reglajes de levas psi y de rueda motora.
A medida que se desarrolló la experiencia con el método, se realizaron mejoras que permitieron su uso con longitudes de clave mucho más cortas que los aproximadamente 500 caracteres originales". [55]
El Testery era la sección de Bletchley Park que realizaba la mayor parte del trabajo necesario para descifrar los mensajes de Tunny. [65] En julio de 1942, el volumen de tráfico estaba aumentando considerablemente. Por ello se creó una nueva sección, dirigida por Ralph Tester (de ahí el nombre). El personal estaba formado principalmente por ex miembros de la Sección de Investigación, [1] e incluía a Peter Ericsson, Peter Hilton , Denis Oswald y Jerry Roberts . [66] Los métodos de Testery eran casi completamente manuales, tanto antes como después de la introducción de métodos automatizados en Newmanry para complementar y acelerar su trabajo. [14] [1]
La primera fase del trabajo del Testery se desarrolló de julio a octubre, siendo el método predominante de descifrado basado en profundidades y profundidades parciales. [67] Sin embargo, después de diez días, el comienzo formulaico de los mensajes fue reemplazado por quatsch sin sentido , lo que hizo que el descifrado fuera más difícil. No obstante, este período fue productivo, aunque cada descifrado llevó un tiempo considerable. Finalmente, en septiembre, se recibió una profundidad que permitió utilizar el método de rotura de ruedas de Turing, "Turingery", lo que permitió comenzar a leer el tráfico actual. Se recopilaron numerosos datos sobre las características estadísticas del lenguaje de los mensajes y se amplió la colección de belenes. [55]
A finales de octubre de 1942, se cerró el enlace experimental original de Tunny y se abrieron dos nuevos enlaces (Codfish y Octopus). Con estos y posteriores enlaces, el sistema QEP reemplazó el sistema indicador de 12 letras para especificar la clave del mensaje. Esto significó que sólo se podían reconocer profundidades completas (a partir de números QEP idénticos), lo que condujo a una reducción considerable del tráfico descifrado.
Una vez que Newmanry entró en funcionamiento en junio de 1943, la naturaleza del trabajo realizado en Testery cambió, y los descifrados y la rotura de ruedas ya no dependieron de las profundidades.
La llamada "máquina británica de atún" era un dispositivo que reproducía exactamente las funciones de las máquinas SZ40/42. Se utilizó para producir el texto claro alemán a partir de una cinta de texto cifrado, después de determinar la configuración de la cámara. [68] El diseño funcional se produjo en Bletchley Park, donde diez Testery Tunnies estaban en uso al final de la guerra. Fue diseñado y construido en el laboratorio de Tommy Flowers en la Estación de Investigación de la Oficina General de Correos en Dollis Hill por Gil Hayward , "Doc" Coombs , Bill Chandler y Sid Broadhurst. [69] Se construyó principalmente a partir de equipos electromecánicos estándar de centrales telefónicas británicas , como relés y uniselectores . La entrada y salida se realizaba mediante teleimpresora con lectura y punzonado de cinta de papel. [70] Estas máquinas se utilizaron tanto en Testery como más tarde en Newmanry. Dorothy Du Boisson , operadora de máquinas y miembro del Servicio Naval Real de Mujeres (Wren), describió que enchufar los ajustes era como operar una central telefónica antigua y que recibió descargas eléctricas en el proceso. [71]
Cuando Hayward invitó a Flowers a probar la primera máquina británica Tunny en Dollis Hill escribiendo la frase de prueba estándar: "Ahora es el momento de que todos los buenos hombres acudan en ayuda del grupo", apreció mucho que el rotor funcionara. se había creado para proporcionar el siguiente resultado de Wordsworth : [72]
Se agregaron características adicionales a los Tunnies británicos para simplificar su operación. Se realizaron más mejoras en las versiones utilizadas en el Newmanry, y el tercer Tunny estaba equipado para producir cintas dechi . [73] [74]
Newmanry fue una sección creada bajo Max Newman en diciembre de 1942 para estudiar la posibilidad de ayudar al trabajo de Testery automatizando partes de los procesos de descifrado de mensajes Tunny . Newman había estado trabajando con Gerry Morgan, jefe de la Sección de Investigación sobre formas de domar a Tunny cuando Bill Tutte se acercó a ellos en noviembre de 1942 con la idea de lo que se conoció como la "entrada 1+2". [75] Se reconoció que esto era factible, pero sólo si se automatizaba.
Newman produjo una especificación funcional de lo que se convertiría en la máquina "Heath Robinson". [75] Reclutó a la Estación de Investigación de la Oficina de Correos en Dollis Hill y al Dr. CE Wynn-Williams en el Establecimiento de Investigación de Telecomunicaciones (TRE) en Malvern para implementar su idea. Los trabajos de diseño de ingeniería comenzaron en enero de 1943 y la primera máquina se entregó en junio. El personal en ese momento estaba formado por Newman, Donald Michie , Jack Good , dos ingenieros y 16 Wrens. Al final de la guerra, Newmanry contenía tres máquinas Robinson, diez computadoras Colossus y varias Tunnies británicas. El personal estaba formado por 26 criptógrafos, 28 ingenieros y 275 Wrens. [76]
La automatización de estos procesos requirió el procesamiento de grandes cantidades de cintas de papel perforadas como aquellas en las que se recibían los mensajes cifrados. La precisión absoluta de estas cintas y su transcripción era esencial, ya que un solo carácter erróneo podía invalidar o corromper una enorme cantidad de trabajo. Jack Good introdujo la máxima "Si no se comprueba, está mal". [77]
WT Tutte desarrolló una forma de explotar la falta de uniformidad de los bigramas (letras adyacentes) en el texto plano alemán utilizando el texto cifrado diferenciado y los componentes clave. Su método se llamó "entrada 1+2" o "ataque doble delta". [78] La esencia de este método era encontrar la configuración inicial del componente chi de la clave probando exhaustivamente todas las posiciones de su combinación con el texto cifrado y buscando evidencia de la falta de uniformidad que reflejaba las características del texto claro original. . [79] [80] El proceso de rotura de la rueda tuvo que haber producido con éxito los ajustes de leva actuales para permitir que se generara la secuencia relevante de caracteres de las ruedas chi . Era totalmente impracticable generar los 22 millones de caracteres de las cinco ruedas chi , por lo que inicialmente se limitó a 41 × 31 = 1271 de las dos primeras.
Dado que para cada uno de los cinco impulsos i :
y por lo tanto
para los dos primeros impulsos:
Calcular un supuesto P 1 ⊕ P 2 de esta manera para cada punto de partida de la secuencia χ 1 ⊕ χ 2 produciría x s y • s con, a largo plazo, una mayor proporción de • s cuando se hubiera elegido el punto de partida correcto. usado. Tutte sabía, sin embargo, que el uso de valores diferenciados (∆) amplificaba este efecto [81] porque cualquier carácter repetido en el texto plano siempre generaría • , y de manera similar ∆ ψ 1 ⊕ ∆ ψ 2 generaría • siempre que las ruedas psi no se movieran y aproximadamente la mitad de las veces que lo hicieron: alrededor del 70% en total.
Tutte analizó un texto cifrado descifrado con la versión diferenciada de la función anterior:
y encontró que generaba • alrededor del 55% del tiempo. [82] Dada la naturaleza de la contribución de las ruedas psi , la alineación de la corriente chi con el texto cifrado que dio el recuento más alto de • s de (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ) fue el que tenía más probabilidades de ser correcto. [83] Esta técnica podría aplicarse a cualquier par de impulsos y, por lo tanto, proporcionó la base de un enfoque automatizado para obtener el dechi ( D) de un texto cifrado, del cual el componente psi podría eliminarse mediante métodos manuales.
Heath Robinson fue la primera máquina producida para automatizar el método 1+2 de Tutte. Le dieron el nombre los Wrens que lo operaban, en honor al caricaturista William Heath Robinson , quien dibujó dispositivos mecánicos inmensamente complicados para tareas simples, similar al caricaturista estadounidense Rube Goldberg .
La especificación funcional de la máquina fue realizada por Max Newman. El diseño de ingeniería principal fue obra de Frank Morrell [84] en la Estación de Investigación de la Oficina de Correos en Dollis Hill en el norte de Londres, con su colega Tommy Flowers diseñando la "Unidad Combinada". El Dr. CE Wynn-Williams del Establecimiento de Investigación de Telecomunicaciones de Malvern produjo los contadores de relés y válvulas electrónicas de alta velocidad. [85] La construcción comenzó en enero de 1943, [86] el prototipo de la máquina estuvo en uso en Bletchley Park en junio. [87]
Las partes principales de la máquina eran:
El prototipo de máquina resultó eficaz a pesar de una serie de graves deficiencias. La mayoría de estos fueron superados progresivamente en el desarrollo de lo que se conoció como el "Viejo Robinson". [88]
Tommy Flowers tenía reservas sobre los dos bucles de cinta sincronizados de Heath Robinson, y su experiencia previa y única con válvulas termoiónicas (tubos de vacío) le llevó a darse cuenta de que se podía producir una máquina mejor utilizando la electrónica. En lugar de leer el flujo de claves desde una segunda cinta de papel perforada, un flujo de claves generado electrónicamente podría permitir un procesamiento mucho más rápido y flexible. La sugerencia de Flowers de que esto podría lograrse con una máquina que fuera enteramente electrónica y contendría entre mil y dos mil válvulas, fue tratada con incredulidad tanto en el Telecommunications Research Establishment como en Bletchley Park, ya que se pensó que sería "demasiado poco confiable para hacer un trabajo útil". Sin embargo, contó con el apoyo del controlador de investigación en Dollis Hill, W. Gordon Radley, [89] e implementó estas ideas produciendo Colossus , la primera máquina informática electrónica y digital del mundo que era programable en absoluto, en el notablemente breve periodo de diez meses. [90] En esto contó con la ayuda de sus colegas de la estación de investigación de la oficina de correos Dollis Hill : Sidney Broadhurst, William Chandler, Allen Coombs y Harry Fensom .
El prototipo Mark 1 Colossus (Colossus I), con sus 1500 válvulas, entró en funcionamiento en Dollis Hill en diciembre de 1943 [2] y entró en pleno funcionamiento en Bletchley Park el 5 de febrero de 1944. [91] Procesó el mensaje a 5000 caracteres por segundo. utilizando el impulso de la lectura de los orificios de la rueda dentada de la cinta para actuar como señal de reloj . Rápidamente se hizo evidente que se trataba de un gran avance en el criptoanálisis de Tunny. Se encargaron más máquinas Colossus y se cancelaron los pedidos de más Robinson. Un Mark 2 Colossus mejorado (Colossus II) contenía 2400 válvulas y funcionó por primera vez en Bletchley Park el 1 de junio de 1944, justo a tiempo para el desembarco de Normandía del día D.
Las partes principales de esta máquina eran: [92]
Las cinco unidades de procesamiento en paralelo permitieron que la "entrada 1+2" de Tutte y otras funciones se ejecutaran a una velocidad efectiva de 25.000 caracteres por segundo mediante el uso de un circuito inventado por Flowers que ahora se llamaría registro de desplazamiento . Donald Michie ideó un método para usar Colossus para ayudar a romper y ajustar las ruedas a principios de 1944. [93] Esto luego se implementó en hardware especial en Colossi posteriores.
En total, diez ordenadores Colossus estaban en uso y un undécimo estaba en servicio al final de la guerra en Europa ( VE-Day ). [94] De los diez, siete se utilizaron para "colocar ruedas" y 3 para "romper ruedas". [95]
Además de los teleimpresores y reperforadores producidos comercialmente, se construyeron otras máquinas para ayudar en la preparación y verificación de cintas en Newmanry y Testery. [96] [97] El complemento aproximado en mayo de 1945 era el siguiente.
Determinar la posición inicial de las ruedas chi ( χ ) requirió primero que la configuración de sus levas se hubiera determinado mediante la "rotura de la rueda". Inicialmente esto se logró mediante el envío de dos mensajes en profundidad .
El número de posiciones iniciales para las dos primeras ruedas, χ 1 y χ 2 fue 41×31 = 1271. El primer paso fue probar todas estas posiciones iniciales con la cinta de mensajes. Esta fue la "entrada 1+2" de Tutte, que implicó calcular (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ) , lo que da un supuesto ( ∆D 1 ⊕ ∆D 2 ), y contar el número de veces esto dio • . Las posiciones iniciales incorrectas darían, en promedio, un recuento de puntos del 50% de la longitud del mensaje. En promedio, el recuento de puntos para un punto de partida correcto sería del 54%, pero inevitablemente había una dispersión considerable de valores en torno a estos promedios. [83]
Tanto Heath Robinson, que se convirtió en lo que se conoció como "Old Robinson", como Colossus fueron diseñados para automatizar este proceso. La teoría estadística permitió derivar medidas de qué tan lejos estaba cualquier recuento del 50% esperado con un punto de partida incorrecto para las ruedas chi . Esta medida de desviación de la aleatoriedad se llamó sigma. Los puntos de partida que dieron un recuento inferior a 2,5 × sigma, denominados "total establecido", no se imprimieron. [105] Lo ideal para una ejecución para establecer χ 1 y χ 2 era que un solo par de valores de prueba produjera un valor sobresaliente para sigma, identificando así las posiciones iniciales de las dos primeras ruedas chi . A continuación se proporciona un ejemplo del resultado de una ejecución de este tipo en un Mark 2 Colossus con sus cinco contadores: a, b, c, d y e.
Con un mensaje de tamaño medio, esto tardaría unos ocho minutos. Sin embargo, al utilizar el paralelismo del Mark 2 Colossus, el número de veces que el mensaje debía leerse se podía reducir en un factor de cinco, de 1271 a 255. [107] Habiendo identificado posibles posiciones iniciales de χ 1 , χ 2 , El siguiente paso fue intentar encontrar las posiciones iniciales para las otras ruedas chi . En el ejemplo anterior, hay un único ajuste de χ 1 = 36 y χ 2 = 21 cuyo valor sigma lo distingue del resto. Este no fue siempre el caso, y Small enumera 36 ejecuciones adicionales diferentes que podrían intentarse de acuerdo con el resultado de la ejecución χ 1 , χ 2 . [108] Al principio, las elecciones en este proceso iterativo las hacía el criptoanalista sentado en la salida de la máquina de escribir y gritando instrucciones a los operadores de Wren. Max Newman ideó un árbol de decisiones y luego encargó a Jack Good y Donald Michie la tarea de idear otros. [109] Estos fueron utilizados por los Wrens sin recurrir a los criptoanalistas si se cumplían ciertos criterios. [110]
En el ejemplo anterior de Small, la siguiente ejecución fue con las dos primeras ruedas chi colocadas en las posiciones iniciales encontradas y tres exploraciones paralelas separadas de las tres ruedas chi restantes . Esta carrera se denominaba "carrera corta" y duraba unos dos minutos. [107]
Entonces, las posiciones iniciales probables para las ruedas chi son: χ 1 = 36, χ 2 = 21, χ 3 = 01, χ 4 = 19, χ 5 = 04. Estas tuvieron que ser verificadas antes del mensaje de- chi ( D ). fue pasado al Probador. Esto implicó que Colossus realizara un recuento de la frecuencia de los 32 caracteres en ΔD . Small describe la verificación del recuento de frecuencia de los caracteres ΔD como la "prueba de fuego", [112] y que prácticamente todos los criptoanalistas y Wren en Newmanry y Testery sabían de memoria el contenido de la siguiente tabla.
Si los puntos de inicio derivados de las ruedas chi pasaron esta prueba, el mensaje deschi - ed se pasó al Testery donde se utilizaron métodos manuales para derivar las configuraciones de psi y motor. Como señaló Small, el trabajo en Newmanry requirió una gran cantidad de ciencia estadística, mientras que el de Testery requirió mucho conocimiento del lenguaje y fue de gran interés como arte. El criptoanalista Jerry Roberts señaló que este trabajo de Testery suponía una carga mayor para el personal que los procesos automatizados en Newmanry. [14]
{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )