Turingery

La turingería ^{[ 1 ]} o método de Turing ^{[ 2 ]} (llamado jocosamente Turingismo por Peter Ericsson, Peter Hilton y Donald Michie ^{[ 3 ]} ) fue un método manual de descifrado ideado en julio de 1942 ^{[ 4 ]} por el matemático y criptoanalista Alan Turing en la Escuela de Códigos y Cifrado del Gobierno Británico en Bletchley Park durante la Segunda Guerra Mundial . ^{[ 5 ] [ 6 ]} Fue para uso en el criptoanálisis del cifrado de Lorenz producido por las máquinas de cifrado de flujo de rotor de teleimpresora SZ40 y SZ42 , una de las máquinas Geheimschreiber (escritor secreto) alemanas . Los británicos denominaron en clave al tráfico que no era Morse "Fish" y al de esta máquina "Tunny" (otra palabra para el pez atún ).

Para leer un mensaje de Tunny, primero era necesario conocer la estructura lógica del sistema; segundo, derivar el patrón de levas activas en las ruedas que cambiaba periódicamente; y tercero, establecer las posiciones iniciales de las ruedas descifradoras para este mensaje, la clave del mensaje . ^{[ 7 ]} La estructura lógica de Tunny había sido desarrollada por William Tutte y sus colegas ^{[ 8 ]} durante varios meses, hasta enero de 1942. ^{[ 9 ]} En Bletchley Park, derivar la clave del mensaje se denominaba "ajuste", pero el objetivo de Turingery era la derivación de los patrones de levas, conocida como "rotura de ruedas".

Los errores de los operadores alemanes al transmitir más de un mensaje con la misma clave, produciendo una "profundidad" , permitieron derivar dicha clave. Se aplicó la técnica de Turing a dicha secuencia de claves para derivar los ajustes de la leva. ^{[ 10 ]}

El funcionamiento lógico del sistema Tunny se había desarrollado mucho antes de que los criptoanalistas de Bletchley Park vieran una de las máquinas, lo que no ocurrió hasta 1945, poco antes de la victoria aliada en Europa. ^{[ 11 ]}

Las máquinas SZ eran máquinas de cifrado de rotor de 12 ruedas que implementaban un cifrado de flujo Vernam . Estaban conectadas en línea a teletipos Lorenz estándar. Los caracteres del mensaje estaban codificados en el Alfabeto Telegráfico Internacional n.° 2 (ITA2) de 5 bits . Los caracteres del texto cifrado de salida se generaban combinando una secuencia de clave pseudoaleatoria carácter por carácter con los caracteres de entrada utilizando la función " o exclusivo " (XOR), simbolizada como "${\displaystyle \oplus }$" en notación matemática. La relación entre el texto plano , el texto cifrado y la clave criptográfica es entonces:

${\displaystyle \mathrm {texto cifrado} =\mathrm {texto sin formato} \oplus \mathrm {clave} }$

De manera similar, para descifrar, el texto cifrado se combinó con la misma clave para obtener el texto plano:

${\displaystyle \mathrm {texto sin formato} =\mathrm {texto cifrado} \oplus \mathrm {clave} }$

Esto genera la reciprocidad esencial que permite utilizar la misma máquina con la misma configuración 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. Estas fueron denominadas chi (${\displaystyle \chi }$) ruedas y la psi (${\displaystyle \psi }$) ruedas. Las ruedas chi se movían todas 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 era controlado por las dos mu (${\displaystyle \mu }$) o ruedas "motorizadas". ^{[ 12 ]}

La secuencia de claves generada por las máquinas SZ tenía, por lo tanto, un componente chi y un componente psi que se combinaban con la función XOR. Así, la clave que se combinaba con el texto plano para cifrar —o con el texto cifrado para descifrar— se puede representar de la siguiente manera. ^{[ 12 ]}

${\displaystyle \mathrm {key} ={\textit {chi}}\mathrm {{\mbox{-}}key} \oplus {\textit {psi}}\mathrm {{\mbox{-}}key} }$

Simbólicamente:

${\displaystyle K=\chi \oplus \psi }$

Cada una de las doce ruedas tenía una serie de levas (o "pasadores") a su alrededor. Estas levas podían colocarse en una posición elevada o bajada. En la posición elevada generaban una "marca", escrita en Bletchley Park como " × " y equivalente al dígito binario 1, y en la posición baja generaban un "espacio", escrito como " · " y equivalente al dígito binario 0. El número de levas en cada rueda era igual al número de impulsos necesarios para que completaran una rotación completa. Estos números son todos coprimos entre sí, lo que da el tiempo máximo posible antes de que el patrón se repita. Con un total de 501 levas, esto equivale a 2 ⁵⁰¹ , que es aproximadamente 10 ¹⁵¹ , un número astronómicamente grande . ^{[ 13 ]} Sin embargo, si se consideran los cinco impulsos 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 forma de eliminar una serie de posibilidades de clave. En Bletchley Park, la combinación XOR de los valores de dos letras adyacentes en la clave o el texto cifrado se llamaba diferencia (simbolizada por la letra griega delta).${\displaystyle \Delta }$) porque XOR es lo mismo que la resta módulo 2 (sin "préstamo") y, incidentalmente, la suma módulo 2 (sin "acarreo"). Entonces, para los caracteres en la clave (K), la diferencia${\displaystyle \Delta K}$se obtuvo de la siguiente manera, donde el subrayado indica el carácter siguiente:

${\displaystyle \Delta K=K\oplus {\underline {K}}}$

(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 se diferencian. Por ejemplo, además de:

${\displaystyle K=\chi \oplus \psi }$

Es cierto que:

${\displaystyle \Delta K=\Delta \chi \oplus \Delta \psi }$

Si el texto plano está representado por P y el texto cifrado por Z, también se cumplen las siguientes condiciones:

${\displaystyle \Delta Z=\Delta P\oplus \Delta \chi \oplus \Delta \psi }$

Y:

${\displaystyle \Delta P=\Delta Z\oplus \Delta \chi \oplus \Delta \psi }$

La razón por la que la diferenciación proporcionó una forma de acceder a Tunny fue que, aunque la distribución de frecuencia de los caracteres en el texto cifrado no se podía distinguir de una secuencia aleatoria, lo mismo no ocurría con una versión del texto cifrado de la que se había eliminado el elemento chi de la clave. Esto se debe a que, cuando el texto plano contenía un carácter repetido y las ruedas psi no se movían, el carácter psi diferenciado (${\displaystyle \Delta \psi }$) sería el carácter nulo (" ····· " o 00000), o, en la terminología de Bletchley Park, " / ". Cuando se combina mediante XOR con cualquier carácter, este carácter nulo no tiene efecto, por lo que en estas circunstancias,${\displaystyle \Delta \chi =\Delta K}$Los caracteres repetidos en el texto plano 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 cambio de cifras y letras ^{[ 16 ]} , ya que su pérdida en un mensaje telegráfico ordinario podía dar lugar a galimatías . ^{[ 17 ]}

Para citar el Informe General sobre el Atún:

Turingy introdujo el principio de que la clave difería en uno, ahora llamada ${\displaystyle \Delta K}$podría proporcionar información inalcanzable con una clave ordinaria.${\displaystyle \Delta }$El principio iba a ser la base fundamental de casi todos los métodos estadísticos de rotura y ajuste de ruedas. ^{[ 1 ]}

En julio de 1942, Turing pasó algunas semanas en la Sección de Investigación. ^{[ 18 ]} Se había interesado en el problema de romper Tunny a partir de las llaves que se habían obtenido de las profundidades . ^{[ 3 ]} En julio, desarrolló el método de derivar los ajustes de leva a partir de una longitud de llave. ^{[ 1 ]} Implicaba un proceso iterativo , casi de ensayo y error. Se basaba en el hecho de que cuando el carácter psi diferenciado es el carácter nulo (" ····· " o 00000), / , entonces al aplicarle XOR con cualquier otro carácter no se modifica. Por lo tanto, el carácter de llave delta es el mismo que el de las cinco ruedas chi (es decir, ${\displaystyle \Delta \chi =\Delta K}$).

Dado que el carácter delta psi era el carácter nulo la mitad del tiempo en promedio (porque las ruedas psi se movían solo el 50% del tiempo), se asume que${\displaystyle \Delta K=\Delta \chi }$tenía un 50% de probabilidad de ser correcto. El proceso comenzó tratando un caso particular.${\displaystyle \Delta K}$el personaje como el Δ${\displaystyle \chi }$para esa posición. El patrón de bits putativo resultante 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 bits de la${\displaystyle \Delta \chi }$. Dado el conocimiento derivado del trabajo de Tutte sobre la periodicidad de cada una de las ruedas, esto permitió la propagación de estos valores en las posiciones apropiadas en el resto de la tonalidad.

También se preparó un conjunto de cinco hojas, una para cada una de las ruedas chi . Estas contenían un conjunto de columnas que correspondían en número a las levas de la rueda chi correspondiente , y se denominaban "jaula". Así pues,${\displaystyle \chi _{3}}$La jaula tenía 29 columnas de ese tipo. ^{[ 19 ]} Sucesivas 'conjeturas' de${\displaystyle \Delta \chi }$Los valores luego produjeron otros valores putativos del estado de la cámara. Estos podían coincidir o no con las suposiciones previas, y se realizó un recuento de coincidencias y discrepancias en estas hojas. Cuando las discrepancias superaron sustancialmente a las coincidencias, se asumió que${\displaystyle \Delta \psi }$El carácter no era el carácter nulo " / ", por lo que se descartó la suposición correspondiente. Progresivamente, se dedujeron todos los ajustes de leva de las ruedas chi , y a partir de ellos los ajustes de leva de psi y de la rueda del motor.

A medida que se desarrolló la experiencia con el método, se hicieron mejoras que permitieron usarlo con longitudes de clave mucho más cortas que los 500 caracteres originales. ^{[ 1 ]}

• Banburismo
• Criptoanálisis diferencial

• Carter, Frank, Bletchley Park Technical Papers: Colossus and the Breaking of the Lorenz Cipher (PDF) , archivado del original (PDF) el 8 de mayo de 2012 , consultado el 28 de enero de 2011.
• Churchhouse, Robert (2002), Códigos y cifrados: Julio César, Enigma e Internet , Cambridge: Cambridge University Press, ISBN 978-0-521-00890-7
• Copeland, Jack (2006), «Turingery», en Copeland, B. Jack (ed.), Colossus: The Secrets of Bletchley Park's Codebreaking Computers , Oxford: Oxford University Press, ISBN 978-0-19-284055-4
• Good, Jack (1993), "Enigma and Fish", en Hinsley, FH ; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
• Good, Jack ; Michie, Donald ; Timms, Geoffrey (1945), Informe general sobre el atún: con énfasis en los métodos estadísticos , Oficina de Registros Públicos del Reino Unido HW 25/4 y HW 25/5 , consultado el 15 de septiembre de 2010.Esa versión es una copia facsímil, pero existe una transcripción de gran parte de este documento en formato '.pdf' en: Sale, Tony (2001), Parte del "Informe general sobre Tunny", la historia de Newmanry, formateada por Tony Sale (PDF) , consultado el 20 de septiembre de 2010.y una transcripción web de la Parte 1 en: Ellsbury, Graham, Informe general sobre el atún con énfasis en los métodos estadísticos , consultado el 3 de noviembre de 2010.
• Escuela de Códigos y Cifrados del Gobierno (1944), Diccionario Criptográfico de Bletchley Park de 1944 formateado por Tony Sale (PDF) , consultado el 7 de octubre de 2010.
• Hodges, Andrew (1992), Alan Turing: El enigma , Londres: Vintage , ISBN 978-0-09-911641-7
• Newman, Max (c. 1944), "Apéndice 7: Δ${\displaystyle \chi }$-Método", en Copeland, B. Jack (ed.), Colossus: The Secrets of Bletchley Park's Codebreaking Computers , Oxford: Oxford University Press, ISBN 978-0-19-284055-4{{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda )
• Sale, Tony (s.f.), "El cifrado de Lorenz y cómo Bletchley Park lo descifró" , odesandciphers.org.uk , consultado el 21 de octubre de 2010.
• Tutte, William T. (2006), "Mi trabajo en Bletchley Park", en Copeland, B Jack (ed.), Colossus: Los secretos de las computadoras descifradoras de códigos de Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-284055-4
• Tutte, WT (19 de junio de 1998), Fish and I (PDF) , archivado del original (PDF) el 10 de julio de 2007 , consultado el 7 de octubre de 2010.Transcripción de una conferencia impartida por el profesor Tutte en la Universidad de Waterloo.