Hispanopedia Wiki
Articulo de referencia

Reloj (criptografía)

En criptografía , el reloj era un método ideado por el matemático y criptólogo polaco Jerzy Różycki , en la Oficina de Cifrado del Estado Mayor polaco , para facilitar el descif...

Hispanopedia WikiContenido en espanolLectura gratuita

En criptografía , el reloj era un método ideado por el matemático y criptólogo polaco Jerzy Różycki , en la Oficina de Cifrado del Estado Mayor polaco , para facilitar el descifrado de los cifrados alemanes de Enigma .

El método determinó el rotor más a la derecha en la máquina Enigma alemana aprovechando las diferentes posiciones de giro. Para los polacos, conocer el rotor más a la derecha redujo el espacio de búsqueda del orden de los rotores en un factor de 3 (el número de rotores).

Posteriormente, los británicos mejoraron el método, lo que les permitió utilizar su limitado número de bombas de forma más eficaz (los británicos se enfrentaban a entre 5 y 8 rotores).

Método

Este método a veces permitía determinar cuál de los rotores de la máquina Enigma se encontraba en el extremo derecho, es decir, en la posición en la que el rotor siempre giraba con cada pulsación de una tecla. [ 1 ] El método del reloj fue desarrollado por Jerzy Różycki entre 1933 y 1935. [ 2 ]

El método de la parrilla de Marian Rejewski permitía determinar el rotor derecho, pero implicaba probar cada permutación posible del rotor (en aquel momento había tres) en cada una de sus 26 rotaciones iniciales posibles. Las pruebas del método de la parrilla también se complicaban por la configuración del tablero de conexiones. En cambio, el método del reloj implicaba pruebas sencillas que no se veían afectadas por el tablero de conexiones. [ 3 ]

A principios de la década de 1930, determinar el orden de los rotores no suponía una carga significativa, ya que los alemanes utilizaban el mismo orden durante tres meses seguidos. El orden de los rotores se determinaba una sola vez y se mantenía durante los tres meses siguientes. El 1 de febrero de 1936, los alemanes cambiaban el orden de los rotores mensualmente. El 1 de noviembre de 1936, lo cambiaban diariamente. [ 4 ]

El método del "reloj" de Różycki fue posteriormente desarrollado por el criptólogo británico Alan Turing en Bletchley Park, en el marco del desarrollo de una técnica criptológica denominada " Banburismus ". [ 5 ]

Fondo

La Oficina de Cifrado recibió interceptaciones de radio alemanas cifradas por la máquina Enigma. Con unos 60 mensajes, la Oficina pudo determinar la estructura característica de Marian Rejewski para la codificación de la clave del mensaje. [ 6 ] Aprovechando las deficientes claves de los mensajes, la Oficina pudo determinar la codificación de la clave del mensaje. En ese punto, los criptoanalistas podrían conocer solo las claves de los mensajes y su texto cifrado. Podrían desconocer otros secretos de la clave diaria, como la configuración del panel de conexiones, la configuración de los anillos, el orden de los rotores o la configuración inicial. Con tan poca información y algo de suerte, los polacos aún pudieron determinar cuál era el rotor más a la derecha.

En el tráfico diario, puede haber alrededor de una docena de pares de mensajes cuya clave de mensaje comienza con las mismas dos letras. [ 7 ] Eso significa que los rotores izquierdo y central están en la misma posición.

Existen dos maneras de alinear los textos cifrados del par de mensajes. [ 8 ] Se prueban ambas alineaciones; una de ellas utiliza una sustitución polialfabética idéntica. A partir de esto, el criptoanalista puede determinar que el cambio de rotor se produjo dentro de un rango específico de letras.

Los rotores tenían diferentes posiciones de giro. Los británicos usaban la regla mnemotécnica "Royal Flags Wave Kings Above" (Las banderas reales ondean sobre los reyes), lo que significaba que el rotor I giraba en la posición R, el rotor II en la F, el rotor III en la W, el rotor IV en la K y todos los demás rotores en la A.

Si los pares de mensajes cooperaban, los polacos podrían reducir la ventana donde ocurre el cambio de rotor para incluir solo uno. Un par de mensajes podría indicar que el cambio ocurrió en la ventana de B a U; esto significaría que los rotores I (R), II (F) y IV (K) eran viables. Un segundo par de mensajes podría generar una ventana de M a C; esto significaría que los rotores I (R), III (W) y V+ (A) eran viables. Solo el rotor I satisface ambos pares de mensajes, por lo que el rotor I es el rotor derecho.

Configuración de la máquina

La máquina de cifrado Enigma dependía de que los usuarios compartieran algunos secretos. Aquí están las configuraciones diarias secretas de un manual de Enigma de 1930: [ 9 ] [ 10 ]

Configuración diaria (clave secreta compartida): Orden del rotor: II I III Ringstellung : 24 13 22 (XMV) Reflector: A Panel de conexiones: AM, FI, NV, PS, TU, WZ Grundstellung: 06 15 12 (FOL)

La configuración diaria indicaba a los operadores de códigos cómo configurar la máquina para el intercambio de mensajes. Inicialmente, la máquina tenía tres rotores que podían disponerse en cualquier orden (orden de rueda u orden de rotor). [ 11 ] Cada rotor tenía un anillo con números o letras, y ese anillo podía estar en cualquiera de las 26 posiciones. Un panel de conexiones permitía intercambiar caracteres adicionales.

Para cada mensaje, el operador elegía una clave de tres letras para cifrar el cuerpo del mensaje. La intención era que esta clave fuera aleatoria, y usar una clave aleatoria para cada mensaje era una buena práctica de seguridad. La clave debía comunicarse al destinatario para que este pudiera descifrar el mensaje.

En lugar de enviar las claves de mensaje en texto plano, estas se cifraban con la configuración básica (Grundstellung). En un grave error de procedimiento, los alemanes cifraron la clave de mensaje dos veces. Si la clave era "ABL", cifraban la clave duplicada como "ABLABL" y enviaban el resultado ("PKPJXI"). El envío doble de la clave permitía recuperar las claves distorsionadas durante la transmisión, pero el error criptográfico radicaba en cifrar la clave duplicada en lugar de enviar la clave cifrada dos veces (por ejemplo, "PKPPKP"). Esta clave duplicada proporcionó a los polacos una vulnerabilidad. Si existía un tráfico de mensajes suficiente con la misma clave diaria (unos 70 mensajes) y los operadores de código utilizaban claves débiles (como "CCC" o "WER"), los polacos podían usar el método de características de Rejewski para determinar todas las claves de mensaje del día. Sorprendentemente, los polacos descifraron las claves de los mensajes sin aprender los secretos sustanciales de la configuración diaria de la máquina: la configuración del panel de conexiones, el orden del rotor, las posiciones del rotor o la configuración del anillo.

Los polacos tuvieron que utilizar otras técnicas para obtener los secretos restantes; el método del reloj ayudó a determinar el orden de los rotores.

Rotores Enigma. La muesca de inversión se puede ver en el rotor izquierdo cerca del número 13. La marca del rotor derecho cerca del centro indica que es el rotor II.

Los diferentes rotores tienen diferentes posiciones de rotación.

El método del reloj aprovechó que los tres rotores (I, II, III) tenían diferentes posiciones de giro . El rotor más a la derecha se movía a medida que se cifraba cada carácter. En una posición determinada del anillo, cifrar el carácter también provocaba que el siguiente rotor a la izquierda se moviera una posición (un giro). La posición del anillo que hacía que el siguiente rotor se moviera era diferente para cada rotor: el rotor I avanzaba en la transición QR ("royal"); el rotor II avanzaba en EF ("flags"); el rotor III avanzaba en VW ("wave"). [ 12 ] Si se podía detectar el giro, entonces se podía identificar el rotor más a la derecha.

Los polacos, debido a que descifraron la clave del mensaje, conocían las posiciones de los anillos para cada mensaje porque las posiciones de los anillos eran la clave del mensaje. [ 13 ]

Con suficiente tráfico, los polacos encontrarían claves de mensajes que comenzaran con los mismos dos caracteres. Digamos que los polacos recibieron mensajes con las claves "AAA" y "AAT".

Clave de mensaje AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Clave de mensaje AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX

Índice de coincidencia

Utilizando el índice de coincidencia en un mensaje suficientemente largo, los polacos pudieron determinar dónde coinciden los ajustes del rotor. Esta determinación es estadística, pero también sutil. Aprovecha la frecuencia no uniforme de las letras en un idioma. Consideremos dos oraciones con sus letras alineadas. Si las letras tuvieran la misma frecuencia, una letra en la primera oración coincidiría con la letra en la misma posición de la segunda oración con una probabilidad de 1/26 (0,038). En los idiomas naturales, caracteres como la "e" son mucho más probables, por lo que la probabilidad de coincidencia es mucho mayor. He aquí un caso en el que hay seis coincidencias en los primeros 28 caracteres (muchas más que las 1,73 coincidencias esperadas por cada 26 caracteres):

SOSTENIMOS QUE LA VERDAD SEA EVIDENTE POR SÍ MISMA CUANDO EN EL CURSO DE LOS ACONTECIMIENTOS HUMANOS * *** * *

El índice de coincidencia también se cumple si las dos cadenas que se comparan están cifradas con la misma clave polialfabética; si los caracteres son iguales, entonces sus cifrados también lo son. Por el contrario, si las cadenas están cifradas con una clave polialfabética diferente, se aleatorizarán y el índice de coincidencia mostrará solo coincidencias aleatorias (1 de cada 26 caracteres coincidirá).

Si las dos cadenas son lo suficientemente largas (por ejemplo, 260 caracteres), el índice de coincidencia indicará si las cadenas se cifraron con la misma clave polialfabética (es decir, con la misma configuración de rotor).

Posición y coincidencia del rotor

Para llevar el índice de coincidencia al extremo, los dos mensajes de ejemplo anteriores consisten únicamente en la letra "A", por lo que las coincidencias se producen en cada posición que comparte la misma posición del rotor (algo que no ocurriría con mensajes normales). Esto permite que la coincidencia sea claramente evidente incluso en un mensaje corto. En la práctica, se necesitan mensajes largos para obtener una buena indicación estadística.

Los polacos buscaron en el tráfico diario un par de mensajes cuyas claves comenzaran con las mismas dos letras. Ejemplos de pares de claves serían ("UIB", "UIW") o ("GCE", "GCX"). La probabilidad de que las dos primeras letras de la clave de un mensaje coincidan con la clave de otro mensaje es pequeña ( 1/(26×26)=1/676 ), pero encontrar dicho par en un conjunto de mensajes puede ser probable; encontrar tal coincidencia es un ejemplo del problema del cumpleaños .

Los polacos querían que las dos primeras letras coincidieran porque eso significaba que los rotores izquierdo y central giraban a la misma velocidad y producirían la misma permutación. También podían alinear los dos mensajes para tener en cuenta la diferencia en la tercera letra de la clave. Dado el par de ejemplo ("AAA", "AAT") mencionado anteriormente, los polacos sabían que había dos maneras posibles de alinear los mensajes para que compartieran una clave común (rotaciones de rotor comunes). Los dos casos reflejan si el cambio de sentido (movimiento del rotor central) ocurre entre "A" y "T" o entre "T" y "A".

 EN Posición del rotor derecho: ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ Clave de mensaje AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Clave de mensaje AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Coincidencia: =============================== Conclusión: la misma clave, por lo que no hay rotación en AT. 
 ejército de reserva Posición del rotor derecho: TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRS Clave de mensaje AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Clave de mensaje AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Coincidencia: Conclusión: clave diferente, por lo que hay rotación en TA

El rotor central girará en diferentes posiciones según cuál se encuentre en la posición más a la derecha (rápida). Los puntos de cambio para los rotores I, II y III se indican con los números 1, 2 y 3. La posición del rotor central se da suponiendo que el rotor derecho sea I, II o III.

Clave de mensaje AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG rotación 2 1 3 2 1 3 Derecha ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY Medio(I) AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCC Medio (II) AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCC Medio(III) AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC Clave de mensaje AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX rotación 3 2 1 3 Correcto TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY Medio(I) AAAAAAAAAAAAAAAAAAAAAAABBBBBBBB Medio(II) AAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB Medio(III) AAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC

Para que se produzcan coincidencias basadas en el lenguaje, los tres rotores deben estar sincronizados. De lo contrario, el texto plano se desordenaría aleatoriamente y las propiedades del lenguaje no se manifestarían. Al observar la región donde se produce la coincidencia, se pueden hacer algunas observaciones. Si el rotor I estuviera a la derecha, el rotor central nunca coincidiría y el índice de coincidencia no indicaría ninguna coincidencia. Si el rotor II estuviera a la derecha, el rotor central tampoco coincidiría. El rotor III muestra una concordancia completa. Por lo tanto, el rotor situado más a la derecha sería el rotor III.

En este punto, los polacos sabrían que el rotor derecho es el III y que el orden de los rotores es (I, II, III) o (II, I, III). Aunque conocían la clave de mensaje, desconocían la configuración de los anillos, por lo que no sabían las posiciones absolutas de los rotores. Tampoco conocían la configuración del panel de conexiones. Los polacos podrían usar otros métodos para obtener esa información, pero estos se simplificarían al conocer el rotor derecho.

Utilidad

Al principio, el método del reloj no era muy importante. En 1932, los alemanes mantuvieron el mismo orden de rotores durante tres meses seguidos. El 1 de febrero de 1936, los alemanes cambiaron el orden de los rotores cada mes. Los cambios diarios en el orden de las ruedas comenzaron el 1 de noviembre de 1936. [ 14 ]

En octubre de 1936, los alemanes aumentaron el número de bujías de seis a ocho, lo que complicó el método de la rejilla. Los polacos desarrollaron el ciclometro y el catálogo de fichas. Aunque el nuevo método no estuvo listo hasta un año después, permitió identificar el orden completo del rotor (no solo el rotor derecho) con poco esfuerzo. [ 15 ] Desafortunadamente, el catálogo quedó inservible el 2 de noviembre de 1937 cuando los alemanes cambiaron el reflector; fue necesario elaborar un nuevo catálogo.

El 15 de septiembre de 1938, los alemanes cambiaron sus procedimientos de modo que los mensajes en una red no usaran la misma Grundstellung . [ 16 ] El cambio complicaría el método del reloj porque la clave del mensaje ya no se conocía fácilmente.

Los criptógrafos británicos extendieron el método del reloj; véase Banburismus . Los mensajes de la Enigma naval alemana utilizaban la misma Grundstellung , y los criptógrafos británicos podían determinar las claves de los mensajes cifrados. Si todas las claves cifradas coincidían excepto la última letra, tendrían las mismas posiciones de rotor, salvo el rotor derecho. El problema era que los británicos no comparaban las claves de los mensajes en texto plano (como los polacos), sino las claves de los mensajes cifrados, por lo que la última letra de la clave del mensaje cifrado no seguía un orden natural "ABCDE...WXYZ", sino un orden arbitrario. En lugar de fijarse en solo dos desplazamientos, los británicos tenían que examinar todos los desplazamientos posibles e inferir suficiente del orden de la tercera rueda antes de poder determinar el rotor correcto. Adivinar correctamente el último rotor podía ahorrarles a los británicos mucho tiempo valioso en la máquina Bombe.

Notas

  1. ↑ Rejewski 1984 , pág. 290 
  2. ↑ Rejewski 1981 , p. 223, afirma: "Durante este período, Różycki desarrolló un procedimiento que denominó el método del reloj . En muchos casos, nos permitió determinar cuál de los tres tambores, I, II o III, era el tambor N en un día determinado; es decir, qué tambor estaba en el lado derecho de la máquina". 
  3. ↑ Rejewski 1981 , p. 227, afirma: «A veces sabíamos qué tambor estaba en la posición N como resultado del método del reloj, pero el método de la cuadrícula, el único que podíamos aplicar ahora a la red SD, a veces fallaba. Fallaba porque el 1 de enero de 1939, los alemanes volvieron a aumentar el número de pares de letras modificadas por la permutación S de siete a diez». 
  4. ↑ Rejewski 1981 , pág. 223 
  5. ↑ Bueno 1993 , pág. 155 
  6. ↑ Rejewski 1981 , p. 218 afirma: "Se necesitaba un número suficiente de mensajes del mismo día, alrededor de 60 especímenes, para establecer la estructura característica AD, BE, CF". 
  7. ↑ Rejewski 1981 , p. 223 afirma: "Teniendo a nuestra disposición una cantidad suficiente de material cifrado, solemos encontrar una docena de pares de mensajes tales que en cada par las dos primeras letras de sus claves son idénticas, mientras que las terceras letras son diferentes". 
  8. ↑ Rejewski 1981 , pág. 223 
  9. ↑ "CryptoCellar de Frode Weierud | Mensaje de prueba de Enigma de 1930" . Archivado del original el 30/10/2014 . Consultado el 07/10/2014 ., citando 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Instrucciones para el uso de claves en la máquina Cypher 'Enigma I'"]
  10. ↑ Se puede comprobar con un simulador. Por ejemplo, http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Seleccione Enigma I, elija el reflector A (en ese momento, los alemanes solo tenían un reflector), configure el orden de las ruedas (II, I, III), configure los anillos (24, 13, 22), configure los enchufes (AM, FI, NV, PS, TU, WZ), active el panel de conexiones y configure las ruedas en la posición de tierra ("FOL"). Al escribir ABLABL en el cuadro de entrada debería producirse PKPJXI como resultado.
  11. ↑ Más adelante habría más de tres rotores posibles.
  12. ↑ Los británicos usaban una regla mnemotécnica para recordar las posiciones de relevo: "Royal Flags Wave Kings Above" (Las banderas reales ondean a los reyes en lo alto).
  13. ↑ Las posiciones de los anillos son las que se muestran en las ventanas; no son la Ringstellung (configuración de los anillos).
  14. ↑ Rejewski 1981 , pág. 223 
  15. ↑ Rejewski 1981 , págs. 224–225 
  16. ↑ Rejewski 1981 , pág. 225 

Referencias

  • Kozaczuk, Władysław (1984), Kasparek, Christopher (ed.), Enigma: Cómo se descifró el cifrado alemán y cómo lo leyeron los aliados en la Segunda Guerra Mundial , Frederick, Maryland: University Publications of America, ISBN 978-0-89093-547-7Una traducción revisada y aumentada de W kręgu enigmy , Varsovia , Książka i Wiedza, 1979, complementada con apéndices de Marian Rejewski
  • Rejewski, Marian (julio de 1981), "Cómo los matemáticos polacos descifraron el enigma", Annals of the History of Computing , 3 (3), IEEE: 213–234 , doi : 10.1109/MAHC.1981.10033 , S2CID 15748167 
  • Rejewski, Marian (1984), «La solución matemática del cifrado Enigma», en Kasparek, Christopher (ed.), Enigma: Cómo se descifró el cifrado de máquina alemán y cómo lo leyeron los aliados en la Segunda Guerra Mundial , pp.  Apéndice E: 272–291, ISBN 978-0-89093-547-7
  • Good, Jack (1993), «Enigma and Fish», en Hinsley, FH ; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park , Oxford: Oxford University Press, pp. 149–166 , ISBN  978-0-19-280132-6