Turingery [1] o método de Turing [2] (llamado en broma Turingismo por Peter Ericsson, Peter Hilton y Donald Michie [3] ) fue un método manual de descifrado de códigos ideado en julio de 1942 [4] por el matemático y criptoanalista Alan Turing en el gobierno británico. Escuela de códigos y cifrados en Bletchley Park durante la Segunda Guerra Mundial . [5] [6] Fue utilizado en el criptoanálisis del cifrado de Lorenz producido por las máquinas de cifrado de flujo de rotor de teleimpresor SZ40 y SZ42 , una de las máquinas Geheimschreiber (escritoras secretas) de los alemanes . Los británicos denominaron en código el tráfico no Morse "Fish" , y el de esta máquina "Tunny" (otra palabra para el atún ).
Leer un mensaje de Tunny requería, en primer lugar, que se conociera la estructura lógica del sistema, en segundo lugar, que se derivara el patrón de levas activas en las ruedas que cambiaba periódicamente y, en tercer lugar, que se conocieran las posiciones iniciales de las ruedas codificadoras para este mensaje (la clave del mensaje ). establecido. [7] La estructura lógica de Tunny había sido elaborada por William Tutte y sus colegas [8] durante varios meses hasta enero de 1942. [9] Derivar la clave del mensaje se llamó "escenario" en Bletchley Park, pero era la derivación de los patrones de levas, que se conocían como "rotura de ruedas", eran el objetivo de Turingery.
Los errores del operador alemán al transmitir más de un mensaje con la misma clave, produciendo una "profundidad" , permitieron la derivación de esa clave. Se aplicó Turingery a dicho flujo clave para derivar la configuración de la cámara. [10]
El funcionamiento lógico del sistema Tunny se resolvió mucho antes de que los criptoanalistas de Bletchley Park vieran una de las máquinas, lo que sólo ocurrió en 1945, poco antes de la victoria aliada en Europa. [11]
Las máquinas SZ eran máquinas de cifrado con rotor de 12 ruedas que implementaban un cifrado de flujo Vernam . Estaban conectados en línea a teleimpresores Lorenz estándar. Los caracteres del mensaje se codificaron en el Alfabeto Telegráfico Internacional N° 2 (ITA2) de 5 bits . Los caracteres de texto cifrado de salida se generaron combinando un flujo de claves pseudoaleatorio carácter por carácter con los caracteres de entrada utilizando la función " exclusiva o " (XOR), simbolizada como " " en notación matemática. La relación entre el texto plano , el texto cifrado y la clave criptográfica es entonces:
De manera similar, para descifrar, el texto cifrado se combinó con la misma clave para obtener el texto sin formato:
Esto produce la reciprocidad esencial para permitir que se utilice la misma máquina con las mismas configuraciones tanto para cifrar como para descifrar.
Cada uno de los cinco bits de la clave para cada carácter fue generado por las ruedas correspondientes en dos partes de la máquina. Éstas se denominaron ruedas chi ( ) y ruedas psi ( ). Todas las ruedas de chi se movían en una posición para cada personaje. Las ruedas psi también se movían todas juntas, pero no después de cada personaje. Su movimiento estaba controlado por las dos ruedas mu ( ) o "motoras". [13]
Por tanto, el flujo de claves generado por las máquinas SZ tenía un componente chi y un componente psi que se combinaban con la función XOR. Entonces, la clave que se combinó con el texto sin formato para cifrar (o con el texto cifrado para descifrar) se puede representar de la siguiente manera. [13]
Simbólicamente:
Cada una de las doce ruedas tenía una serie de levas (o "pasadores") a su alrededor. Estas levas podrían colocarse en una posición elevada o bajada. En la posición elevada generaron una "marca", escrita en Bletchley Park como " × " y equivalente a un dígito binario 1, y en la posición baja generaron un "espacio", escrito como " · " y equivalente a un dígito binario 0. La cantidad de levas en cada rueda era igual a la cantidad de impulsos necesarios para que completaran una rotación completa. Todos estos números son coprimos entre sí, lo que da el mayor tiempo posible antes de que se repita el patrón. Con un total de 501 levas, esto equivale a 2.501, lo que equivale aproximadamente a 10.151 , un número astronómicamente grande . [14] Sin embargo, si los cinco impulsos se consideran de forma independiente, los números son mucho más manejables. El producto del período de rotación de cualquier par de ruedas chi da números entre 41×31=1271 y 26×23=598.
El criptoanálisis a menudo implica encontrar patrones de algún tipo que proporcionen una manera de eliminar una variedad de posibilidades clave. En Bletchley Park, la combinación XOR de los valores de dos letras adyacentes en la clave o el texto cifrado se llamó diferencia (simbolizada por la letra griega delta ) porque XOR es lo mismo que la resta de módulo 2 (sin "pedir prestado") y, dicho sea de paso, , adición de módulo 2 (sin "carry"). Así, para los caracteres de la clave (K), la diferencia se obtuvo de la siguiente manera, donde el subrayado indica el carácter siguiente:
(Lo mismo ocurre con el texto plano, el texto cifrado y los dos componentes de la clave).
La relación entre ellos se aplica cuando están diferenciados. Por ejemplo, además de:
Es el caso que:
Si el texto plano está representado por P y el texto cifrado por Z, también se cumple lo siguiente:
Y:
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 (" ····· " o 00000), o, en la terminología de Bletchley Park, " / ". Cuando se aplica XOR con cualquier carácter, este carácter nulo no tiene ningún efecto, por lo que en estas circunstancias, . Los caracteres repetidos en el texto claro eran más frecuentes, tanto por las características del alemán (EE, TT, LL y SS son relativamente comunes) [15] como porque los telegrafistas repetían con frecuencia los caracteres de desplazamiento de cifras y letras [16] como su pérdida en un mensaje telegráfico ordinario podría dar lugar a galimatías . [17]
Para citar el Informe General sobre Tunny:
Turingery introdujo el principio de que la clave diferenciada en uno, ahora llamada , podría proporcionar información que no se puede 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. [1]
Además de aplicar la diferenciación a los caracteres completos de 5 bits del código ITA2 , también se aplicó a los impulsos individuales (bits). Entonces, para el primer impulso, eso fue cifrado por ruedas y diferenciado en uno:
Y para el segundo impulso:
Etcétera.
También vale la pena señalar que la periodicidad de las ruedas chi y psi para cada impulso (41 y 43 respectivamente para el primero) se refleja en su patrón de . 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 , sino una secuencia más compleja.
En julio de 1942, Turing pasó unas semanas en la Sección de Investigación. [18] Se había interesado en el problema de separar a Tunny de las llaves que se habían obtenido de las profundidades . [3] En julio, desarrolló el método de derivar la configuración de la leva a partir de una longitud de clave. [1] Implicaba un proceso iterativo , casi de prueba y error. Se basó en el hecho de que cuando el carácter psi diferenciado es el carácter nulo (" ····· " o 00000), / , realizar XOR con cualquier otro carácter no lo cambia. Así, el carácter clave delta da el carácter de las cinco ruedas chi (es decir, ).
Dado que el carácter delta psi era el carácter nulo la mitad del tiempo en promedio, una suposición que tenía un 50% de posibilidades de ser correcta. El proceso comenzaba tratando a un personaje en particular como el Δ para esa posición. El supuesto patrón de bits resultante de × y · para cada rueda chi se registró en una hoja de papel que contenía tantas columnas como caracteres en la clave, y cinco filas que representaban los cinco impulsos del . 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 tenía 29 de esas columnas. [19] Las sucesivas "conjeturas" de valores produjeron más valores putativos de 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 ajustes de levas de las ruedas chi , y de ellos los ajustes de levas de 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. [1]
