Parrilla (criptología)

Método de criptología

El método de parrilla ( en polaco : metoda rusztu ), ^[1] en criptología , fue un método utilizado principalmente al principio, antes de la llegada del ciclómetro , por los matemáticos-criptólogos de la Oficina de Cifrado Polaca ( Biuro Szyfrów ) para descifrar los cifrados de la máquina Enigma alemana . ^[2] La máquina de cifrado de rotor Enigma cambia caracteres de texto simple en texto cifrado utilizando una permutación diferente para cada carácter, y así implementa un cifrado de sustitución polialfabética .

Fondo

La marina alemana comenzó a utilizar máquinas Enigma en 1926; se llamaba Funkschlüssel C ("Radio cifra C"). ^[3] Para el 15 de julio de 1928, ^[4] el ejército alemán ( Reichswehr ) había presentado su propia versión de la Enigma: la Enigma G ; una Enigma I revisada (con tablero de conexiones ) apareció en junio de 1930. ^[5] La Enigma I utilizada por el ejército alemán en la década de 1930 era una máquina de 3 rotores. Inicialmente, solo había tres rotores etiquetados I , II y III , pero podían organizarse en cualquier orden cuando se colocaban en la máquina. El criptólogo polaco Marian Rejewski identificó las permutaciones del rotor por L , M y N ; el cifrado producido por los rotores se alteraba a medida que se encriptaba cada carácter. La permutación más a la derecha ( N ) cambiaba con cada carácter. Además, había un tablero de conexiones que realizaba algunas codificaciones adicionales.

El número de posibles cableados de rotor diferentes es:

${\displaystyle 26^{3}=17,536}$

El número de posibles cableados diferentes del reflector es: ^[6]

${\displaystyle {\frac {26!}{2^{13}\,13!}}=7,905,853,580,625}$

Una forma quizás más intuitiva de llegar a esta cifra es considerar que una letra puede conectarse a cualquiera de las 25. Eso deja 24 letras para conectar. La siguiente letra elegida puede conectarse a cualquiera de las 23. Y así sucesivamente.

${\displaystyle 25*23*21*19...*3*1=7,905,853,580,625}$

El número de posibles cableados diferentes del tablero de conexiones (para seis cables) es: ^[7]

${\displaystyle {\frac {26!}{2^{6}\,6!\,14!}}=100,391,791,500}$

Para cifrar o descifrar, el operador realizó las siguientes configuraciones de clave de la máquina: ^[8]

• el orden del rotor ( Walzenlage )
• Ajuste del anillo ( Ringstellung )
• las conexiones del cuadro eléctrico ( Steckerverbindung )
• una posición inicial del rotor ( Grundstellung )

A principios de la década de 1930, los alemanes distribuyeron una lista mensual secreta de todos los ajustes diarios de la máquina. Los alemanes sabían que sería una tontería cifrar el tráfico del día utilizando la misma clave, por lo que cada mensaje tenía su propia "clave de mensaje". Esta clave de mensaje era la posición inicial del rotor elegida por el remitente (por ejemplo, YEK). La clave del mensaje tenía que ser transmitida al operador del destinatario, por lo que los alemanes decidieron cifrarla utilizando la configuración terrestre diaria preestablecida del día ( Grundstellung ). El destinatario utilizaría la configuración diaria de la máquina para todos los mensajes. Establecería la posición inicial del rotor de la Enigma en la configuración terrestre y descifraría la clave del mensaje. A continuación, el destinatario establecería la posición inicial del rotor en la clave del mensaje y descifraría el cuerpo del mensaje.

El sistema Enigma se utilizaba en las comunicaciones por radio, por lo que, en ocasiones, las letras se corrompían durante la transmisión o la recepción. Si el destinatario no tenía la clave del mensaje correcta, no podía descifrar el mensaje. Los alemanes decidieron enviar la clave del mensaje de tres letras dos veces para evitar errores de transmisión. En lugar de cifrar la clave del mensaje "YEK" una vez y enviar la clave cifrada dos veces, los alemanes duplicaron la clave del mensaje a "YEKYEK" ("clave duplicada"), cifraron la clave duplicada con la configuración de tierra y enviaron la clave duplicada cifrada. De este modo, el destinatario podía reconocer una clave de mensaje ilegible y, aun así, descifrar el mensaje. Por ejemplo, si el destinatario recibía y descifraba la clave duplicada como "YEKYEN", podía probar con ambas claves de mensaje "YEK" y "YEN"; una produciría el mensaje deseado y la otra produciría un galimatías.

La clave duplicada cifrada fue un gran error criptográfico porque permitió a los criptoanalistas conocer dos cifras de la misma letra, con tres lugares de diferencia, para cada una de las tres letras. Los descifradores de códigos polacos explotaron este error de muchas maneras. Marian Rejewski utilizó la clave duplicada y algunas claves diarias conocidas obtenidas por un espía, para determinar el cableado de los tres rotores y el reflector. Además, los descifradores de códigos a menudo no elegían claves aleatorias seguras, sino que elegían claves débiles como "AAA", "ABC" y "SSS". Los polacos utilizaron más tarde las claves débiles duplicadas para encontrar las claves diarias desconocidas. El método de la parrilla fue una explotación temprana de la clave duplicada para recuperar parte de los ajustes diarios. El ciclometro y la bomba criptológica fueron explotaciones posteriores de la clave duplicada.

Mensaje de ejemplo

La máquina Enigma era una máquina electromecánica de rotor con un desviador compuesto (de derecha a izquierda) por un tambor de entrada, tres rotores y un reflector. Estuvo disponible comercialmente desde principios de la década de 1920 y fue modificada para su uso por el ejército alemán, que la adoptó más tarde en esa década.

Frode Weierud proporciona el procedimiento, las configuraciones secretas y los resultados que se utilizaron en un manual técnico alemán de 1930. ^{[9] [10]}

Configuración diaria (secreto compartido): Orden de ruedas: II I III Fecha de emisión: 24 13 22 (XMV) Reflector: A Tablero de conexiones: AM, FI, NV, PS, TU, WZ Fecha de inicio: 06 15 12 (FOL)Clave de mensaje elegida por el operador: ABLCifrado que comienza con FOL: PKPJXIMensaje a enviar y grupos de 5 letras de texto claro resultantes: Feindliche Infanteriekolonne beobachtet. Entrada sur de Bärwalde. Finaliza 3 km al este de Neustadt. FÁCIL LLENADO DE ERIEK OLONN EBEOB AQTET XANFA NGSUE DAUSG ANGBA ERWAL DEXEN DEDRE IKMOS TWAER Ciudad de TSNEUMensaje resultante: 1035 – 90 – 341 – PKPJX IGCDS EAHUG WTQGR KVLFG XUCAL XVYMI GMMNM FDXTG NVHVR MMEVO UYFZS LRHDR RXFJW CFHUH MUNZE FRDIS IKBGP MYVXU Z

La primera línea del mensaje no está cifrada. El "1035" es la hora, "90" es el número de caracteres cifrados con la clave del mensaje y "341" es un indicador del sistema que le dice al destinatario cómo se cifró el mensaje (es decir, utilizando Enigma con una determinada clave diaria). Las primeras seis letras del cuerpo ("PKPJXI") son la clave duplicada ("ABLABL") cifrada utilizando la configuración de la clave diaria y comenzando el cifrado en la configuración básica/Grundstellung "FOL". El destinatario descifraría las primeras seis letras para recuperar la clave del mensaje ("ABL"); luego configuraría los rotores de la máquina en "ABL" y descifraría los 90 caracteres restantes. Observe que Enigma no tiene números, puntuación ni diéresis . Los números se deletreaban con todas las letras. La mayoría de los espacios se ignoraban; se utilizaba una "X" para un punto. Las diéresis utilizaban su ortografía alternativa con una "e" al final. Se utilizaron algunas abreviaturas: se utilizó una "Q" para "CH".

Cuando Rejewski comenzó su ataque en 1932, encontró obvio que las primeras seis letras eran la clave duplicada cifrada. ^[11]

Cifrado de claves

La configuración de la clave diaria y la configuración básica permutarán los caracteres de la clave del mensaje de diferentes maneras. Esto se puede demostrar cifrando seis letras iguales para las 26 letras:

AAAAAA -> ¡PUUJJN!BBBBBB -> TKYWXVn.º 1 -> KZMVVYDDDDDD -> XMSRQKEEEEEE -> RYZOLZFFFFFF -> ZXNSTUGGGGGG -> QRQUNTHHHHHH -> SSWYYSIIIIII -> WNOZPLJJJJJJ -> MQVAAXKKKKKK -> CBTTSDLLLLLL -> OWPQEIMMMMMMM -> JDCXUONNNNNN -> YIFPGAOOOOOO -> LPIEZMPPPPPP -> AOLNIWQQQQQQ -> GJGLDRRRRRRR -> EGXDWQSSSSSS -> HHDFKHTTTTTT -> BVKKFGUUUUUU -> VAAGMFVVVVVV -> UTJCCBWWWWWW -> ILHBRPXXXXXX -> DFRMBJAAAAA -> NEBHHCZZZZZZ -> FCEIOE

A partir de esta información, se pueden encontrar las permutaciones para cada una de las seis claves de mensajes. Etiquete cada permutación como ABCDEF . Estas permutaciones son secretas: el enemigo no debería conocerlas.

${\displaystyle {\begin{aligned}A=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {ptkxrzqswmcojylagehbvuidnf}}}&={\texttt {(ap)(bt)(ck)(dx)(er)(fz)(gq)(hs)(iw)(jm)(lo)(ny)(uv)}}\\B=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {ukzmyxrsnqbwdipojghvatlfec}}}&={\texttt {(au)(bk)(cz)(dm)(ey)(fx)(gr)(hs)(in)(jq)(lw)(op)(tv)}}\\C=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {uymsznqwovtpcfilgxdkajhrbe}}}&={\texttt {(au)(by)(cm)(ds)(ez)(fn)(gq)(hw)(io)(jv)(kt)(lp)(rx)}}\\D=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {jwvrosuyzatqxpenldfkgcbmhi}}}&={\texttt {(aj)(bw)(cv)(dr)(eo)(fs)(gu)(hy)(iz)(kt)(lq)(mx)(np)}}\\E=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {jxvqltnypaseugzidwkfmcrbho}}}&={\texttt {(aj)(bx)(cv)(dq)(el)(ft)(gn)(hy)(ip)(ks)(mu)(oz)(rw)}}\\F=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {nvykzutslxdioamwrqhgfbpjce}}}&={\texttt {(an)(bv)(cy)(dk)(ez)(fu)(gt)(hs)(il)(jx)(mo)(pw)(qr)}}\\\end{aligned}}}$

Observe que las permutaciones son productos de 13 transposiciones disjuntas . ^{[ Se necesita más explicación ]} En el caso de la permutación A , no solo cambia "A" por "P", sino que también cambia "P" por "A". Esto permite que la máquina encripte y desencripte mensajes.

Augustin-Louis Cauchy introdujo la notación de dos líneas en 1815 y la notación cíclica en 1844. ^{[12] [13] [14]}

La característica de Rejewski

Rejewski hizo un descubrimiento increíble. Sin conocer la configuración del tablero de conexiones, las posiciones del rotor, la configuración de los anillos o la configuración de la base, pudo encontrar todas las claves de mensajes diarios. Todo lo que necesitaba eran suficientes mensajes y algunos empleados de código que utilizaran claves de mensajes no aleatorias.

La clave del mensaje tiene tres caracteres, por lo que la clave duplicada tiene seis caracteres. Rejewski etiquetó las permutaciones de los caracteres sucesivos de la clave del mensaje como ABCDEF . No sabía cuáles eran esas permutaciones, pero sí sabía que las permutaciones A y D cifraban la misma letra de la clave del mensaje, que B y E cifraban la misma letra y que C y F cifraban la misma letra. Si p _i son las letras de texto simple (desconocidas) de la clave del mensaje y c _i son las letras de texto cifrado correspondientes (conocidas), entonces

${\displaystyle {\begin{aligned}p_{1}&=c_{1}A^{-1}&=p_{4}&=c_{4}D^{-1}\\p_{2}&=c_{2}B^{-1}&=p_{5}&=c_{5}E^{-1}\\p_{3}&=c_{3}C^{-1}&=p_{6}&=c_{6}F^{-1}\\\end{aligned}}}$

Las ecuaciones se pueden multiplicar posteriormente por D , E y F respectivamente para simplificar los lados derechos:

${\displaystyle {\begin{aligned}p_{1}D&=c_{1}A^{-1}D&=p_{4}D&=c_{4}\\p_{2}E&=c_{2}B^{-1}E&=p_{5}E&=c_{5}\\p_{3}F&=c_{3}C^{-1}F&=p_{6}F&=c_{6}\\\end{aligned}}}$

Los valores de texto simple son desconocidos, por lo que esos términos simplemente se eliminan para dejar:

${\displaystyle {\begin{aligned}c_{1}A^{-1}D&=c_{4}\\c_{2}B^{-1}E&=c_{5}\\c_{3}C^{-1}F&=c_{6}\\\end{aligned}}}$

Las ecuaciones anteriores describen un camino a través de las permutaciones. Si c ₁ pasa por el inverso de A , entonces produce p ₁ . Si ese carácter pasa por D , entonces el resultado es c ₄ .

Rejewski también sabía que las permutaciones de Enigma eran inversas entre sí: el cifrado y el descifrado de Enigma eran idénticos. Eso significa que AA = I , donde I es la permutación identidad. En consecuencia, A = A ⁻¹ . Por lo tanto:

${\displaystyle {\begin{aligned}c_{1}AD&=c_{4}\\c_{2}BE&=c_{5}\\c_{3}CF&=c_{6}\\\end{aligned}}}$

Las ecuaciones anteriores muestran la relación entre los caracteres clave duplicados. Aunque Rejewski no conocía las permutaciones individuales ABCDEF , un único mensaje le indicó cómo caracteres específicos fueron permutados por las permutaciones compuestas AD , BE y CF .

A partir de muchos mensajes, Rejewski pudo determinar completamente las permutaciones compuestas. En la práctica, se necesitaban alrededor de 60 mensajes para determinar las permutaciones. ^[15]

Rejewski registró las tres permutaciones con una notación cíclica que llamó característica. Rejewski (1981, p. 217) da un ejemplo:

${\displaystyle {\begin{aligned}AD&={\texttt {(dvpfkxgzyo)(eijmunglht)(bc)(rw)(a)(s)}}\\BE&={\texttt {(blfqveoum)(hjpswizrn)(axt)(cgy)(d)(k)}}\\CF&={\texttt {(abviktjgfcqny)(duzrehlxwpsmo)}}\\\end{aligned}}}$

En esta notación, el primer ciclo de permutación AD asignaría d a v, v a p, p a f, ..., y a o, y o se convertiría en d.

Marks y Weierud dan un ejemplo de Alan Turing que muestra que estos ciclos pueden completarse cuando alguna información está incompleta. ^[16]

Además, las permutaciones de Enigma eran transposiciones simples, lo que significaba que cada permutación ABCDEF solo transponía pares de caracteres. Esos pares de caracteres tenían que provenir de ciclos diferentes de la misma longitud. Además, cualquier emparejamiento entre dos ciclos determinaba todos los demás pares en esos ciclos. En consecuencia, las permutaciones A y D tenían que transponer a y s porque (a) y (s) son los únicos ciclos de longitud uno y solo hay una forma de emparejarlos. Hay dos formas de hacer coincidir (bc) y (rw) porque b debe emparejarse con r o w. De manera similar, hay diez formas de hacer coincidir los ciclos restantes de diez caracteres. En otras palabras, Rejewski ahora sabía que solo había veinte posibilidades para las permutaciones A y D . De manera similar, había 27 candidatos para B y E , y 13 candidatos para C y F . ^[17]

Teclas débiles

En este punto, los polacos aprovecharían las debilidades en la selección de claves de mensajes por parte de los encargados de codificar para determinar cuáles eran las candidatas correctas. Si los polacos podían adivinar correctamente la clave de un mensaje en particular, esa suposición anclaría dos ciclos en cada una de las tres características.

Los polacos interceptaron muchos mensajes; necesitarían unos 60 mensajes en la misma clave diaria para determinar la característica, pero podrían tener muchos más. Al principio, Rejewski había identificado los seis caracteres que componían la clave del mensaje. ^[18] Si los encargados de codificar elegían claves de mensajes al azar, entonces no se esperaría ver mucha correlación en los seis caracteres cifrados. Sin embargo, algunos encargados de codificar eran perezosos. ¿Qué sucedería si, de cien mensajes, hubiera cinco mensajes de cinco estaciones diferentes (es decir, cinco encargados de codificar diferentes) que usaran la misma clave de mensaje "PUUJJN"? ^[19] El hecho de que todos ellos llegaran a la misma clave sugiere que usaban una clave muy simple o muy común. Los polacos llevaban un registro de las diferentes estaciones y de cómo esas estaciones elegían las claves de los mensajes. Al principio, los encargados de codificar a menudo usaban claves simples como "AAA" o "BBB". ^[20]

El resultado final fue que sin conocer la configuración del tablero de conexiones de la Enigma, las posiciones del rotor o la configuración de los anillos, Rejewski determinó cada una de las permutaciones ABCDEF y, por lo tanto, todas las claves de los mensajes del día. ^{[21] [22]}

Inicialmente, Rejewski utilizó el conocimiento de las permutaciones ABCDEF (y un manual obtenido por un espía francés) para determinar el cableado del rotor. Después de aprender el cableado del rotor, los polacos utilizaron las permutaciones para determinar el orden del rotor, las conexiones del tablero de conexiones y los ajustes de los anillos mediante pasos adicionales del método de la rejilla.

Continuando con el ejemplo de 1930

Usando la clave diaria del manual técnico de 1930 mencionado anteriormente, entonces (con suficientes mensajes) Rejewski pudo encontrar las siguientes características:

${\displaystyle {\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{aligned}}}$

Aunque teóricamente existen 7 billones de posibilidades para cada una de las permutaciones ABCDEF , las características anteriores han reducido las permutaciones A y D a solo 13 posibilidades, B y E a solo 30 posibilidades, y C y F a solo 20 posibilidades. La característica para CF tiene dos ciclos singleton, (e) y (z) . ^[23] Esos ciclos singleton deben emparejarse en las permutaciones individuales, por lo que la característica para CF implica que la "E" y la "Z" se intercambian tanto en la permutación C como en la F.

${\displaystyle {\begin{aligned}C&={\texttt {(ez)...}}\\F&={\texttt {(ez)...}}\\\end{aligned}}}$

El emparejamiento de "E" y "Z" se puede comprobar en las permutaciones originales (secretas) dadas arriba.

Rejewski sabría ahora que los indicadores con el patrón "..E..E" eran de una clave de mensaje de "..Z"; de manera similar, un indicador de "..Z..Z" era de una clave de mensaje de "..E". En el tráfico del día, podría encontrar indicadores como "PKZJXZ" o "RYZOLZ"; ¿podría uno de estos indicadores ser la clave de mensaje común (perezosa) "EEE"? La característica limita el número de permutaciones posibles a un número pequeño, y eso permite algunas comprobaciones simples. "PKZJXZ" no puede ser "EEE" porque requiere que "K" y "E" se intercambien en B , pero tanto "K" como "E" son parte del mismo ciclo en BE : (kxtcoigweh) . ^[24] Las letras intercambiables deben provenir de ciclos distintos de la misma longitud. La clave repetitiva también podría confirmarse porque podría descubrir otras claves repetitivas. ^[24]

El indicador "RYZOLZ" es un buen candidato para la clave de mensaje "EEE", y determinaría inmediatamente ambas permutaciones A y D. Por ejemplo, en AD , la clave de mensaje asumida "EEE" requiere que "E" y "R" se intercambien en A y que "E" y "O" se intercambien en D.

${\displaystyle {\begin{aligned}A&={\texttt {(er)...}}\\D&={\texttt {(eo)...}}\\\end{aligned}}}$

Si "E" se intercambia con "R" en A (observe que un carácter proviene del primer ciclo en AD y el otro carácter proviene del segundo ciclo), entonces la letra que sigue a "E" (es decir, "D") se intercambiará con la letra que precede a "R" (es decir, "X").

${\displaystyle {\begin{aligned}A&={\texttt {(er)(dx)...}}\\D&={\texttt {(eo)...}}\\\end{aligned}}}$

Esto se puede continuar para obtener todos los caracteres para ambas permutaciones.

${\displaystyle {\begin{aligned}A&={\texttt {(er)(dx)(jm)(ap)(ny)(hs)(fz)(iw)(bt)(ck)(uv)(gq)(lo)}}\\D&={\texttt {(eo)(lq)(gu)(cv)(kt)(bw)(iz)(fs)(hy)(np)(ag)(mx)(dr)}}\\\end{aligned}}}$

Esta notación característica es equivalente a las expresiones dadas para las permutaciones A y D de 1930 dadas anteriormente, ordenando los ciclos de modo que la letra más antigua sea la primera.

${\displaystyle {\begin{aligned}A&={\texttt {(ap)(bt)(ck)(dx)(er)(fz)(gq)(hs)(iw)(jm)(lo)(ny)(uv)}}\\D&={\texttt {(aj)(bw)(cv)(dr)(eo)(fs)(gu)(hy)(iz)(kt)(lq)(mx)(np)}}\\\end{aligned}}}$

La clave del mensaje adivinado de "EEE" que produce el indicador "RYZOLZ" también determinaría el emparejamiento de los 10 ciclos de longitud en la permutación BE .

${\displaystyle {\begin{aligned}B&={\texttt {(ey)(hs)(kb)(xf)(tv)(cz)(op)(in)(gr)(wl)...}}\\E&={\texttt {(le)(rw)(ng)(pi)(zo)(vc)(ft)(bx)(sk)(yh)...}}\\\end{aligned}}}$

Esto determina la mayor parte de B y E , y solo quedarían tres variaciones posibles de ese par (ujd) y (mqa) . Todavía hay 20 variaciones posibles para C y F. En este punto, los polacos podrían descifrar todas las primeras y cuartas letras de las claves diarias; también podrían descifrar 20 de las 26 letras segunda y quinta. La creencia de los polacos en estas permutaciones podría comprobarse observando otras claves y viendo si eran claves típicas utilizadas por los empleados de códigos.

Con esa información, podrían buscar y encontrar otras claves de mensajes probablemente débiles que determinarían el resto de las permutaciones ABCDEF . Por ejemplo, si los polacos tenían un indicador "TKYWXV", podrían descifrarlo como "BB.BB"; al verificar los ciclos de CF , se revelaría que el indicador es consistente con la clave de mensaje "BBB".

El modelo de Rejewski

Rejewski modeló la máquina como una permutación hecha a partir de permutaciones del tablero de conexiones ( S ), el cableado del teclado/lámparas a los rotores ( H ), los tres rotores ( LMN ) y el reflector ( R ). La permutación para cada posición de la clave duplicada era diferente, pero estaban relacionadas por una permutación P que representaba un solo paso de un rotor ( P es conocida). Rejewski asumió que los rotores izquierdo y medio no se movían mientras se encriptaba la clave duplicada. Las seis letras de la clave duplicada, en consecuencia, se ven en las permutaciones ABCDEF: ^[25]

${\displaystyle {\begin{aligned}A&=SH(P^{1}NP^{-1})LMRM^{-1}L^{-1}(P^{1}N^{-1}P^{-1})H^{-1}S^{-1}\\B&=SH(P^{2}NP^{-2})LMRM^{-1}L^{-1}(P^{2}N^{-1}P^{-2})H^{-1}S^{-1}\\C&=SH(P^{3}NP^{-3})LMRM^{-1}L^{-1}(P^{3}N^{-1}P^{-3})H^{-1}S^{-1}\\D&=SH(P^{4}NP^{-4})LMRM^{-1}L^{-1}(P^{4}N^{-1}P^{-4})H^{-1}S^{-1}\\E&=SH(P^{5}NP^{-5})LMRM^{-1}L^{-1}(P^{5}N^{-1}P^{-5})H^{-1}S^{-1}\\F&=SH(P^{6}NP^{-6})LMRM^{-1}L^{-1}(P^{6}N^{-1}P^{-6})H^{-1}S^{-1}\\\end{aligned}}}$

Rejewski simplificó estas ecuaciones creando Q como un reflector compuesto a partir del reflector real y dos rotores más a la izquierda:

${\displaystyle Q=LMRM^{-1}L^{-1}}$

La sustitución produce:

${\displaystyle {\begin{aligned}A&=SH(P^{1}NP^{-1})Q(P^{1}N^{-1}P^{-1})H^{-1}S^{-1}\\B&=SH(P^{2}NP^{-2})Q(P^{2}N^{-1}P^{-2})H^{-1}S^{-1}\\C&=SH(P^{3}NP^{-3})Q(P^{3}N^{-1}P^{-3})H^{-1}S^{-1}\\D&=SH(P^{4}NP^{-4})Q(P^{4}N^{-1}P^{-4})H^{-1}S^{-1}\\E&=SH(P^{5}NP^{-5})Q(P^{5}N^{-1}P^{-5})H^{-1}S^{-1}\\F&=SH(P^{6}NP^{-6})Q(P^{6}N^{-1}P^{-6})H^{-1}S^{-1}\\\end{aligned}}}$

El resultado son seis ecuaciones con cuatro incógnitas ( SHNQ ). ^[26] Rejewski tenía una máquina Enigma comercial y al principio pensó que H sería la misma. En otras palabras, Rejewski supuso que

${\displaystyle H={\binom {qwertzuioasdfghjkpyxcvbnml}{abcdefghijklmnopqrstuvwxyz}}}$

Más tarde, Rejewski se dio cuenta de que esa suposición era errónea. Rejewski entonces adivinó (correctamente) que H era simplemente la permutación identidad:

${\displaystyle H={\binom {abcdefghijklmnopqrstuvwxyz}{abcdefghijklmnopqrstuvwxyz}}}$

Aún quedan tres incógnitas. Rejewski comenta:

Así pues, tenía un conjunto de seis ecuaciones con tres incógnitas, S, N y Q. Mientras me devanaba los sesos para encontrar la manera de resolver ese conjunto de ecuaciones, el 9 de diciembre de 1932, de forma totalmente inesperada y en el momento más oportuno, me fue entregada una fotocopia de dos tablas de claves diarias de septiembre y octubre de 1932. ^[26]

Tener las claves diarias significaba que ahora se conocía S. Las permutaciones conocidas se movieron al lado izquierdo de las ecuaciones mediante premultiplicación y posmultiplicación.

${\displaystyle {\begin{aligned}H^{-1}S^{-1}ASH&=(P^{1}NP^{-1})Q(P^{1}N^{-1}P^{-1})\\H^{-1}S^{-1}BSH&=(P^{2}NP^{-2})Q(P^{2}N^{-1}P^{-2})\\H^{-1}S^{-1}CSH&=(P^{3}NP^{-3})Q(P^{3}N^{-1}P^{-3})\\H^{-1}S^{-1}DSH&=(P^{4}NP^{-4})Q(P^{4}N^{-1}P^{-4})\\H^{-1}S^{-1}ESH&=(P^{5}NP^{-5})Q(P^{5}N^{-1}P^{-5})\\H^{-1}S^{-1}FSH&=(P^{6}NP^{-6})Q(P^{6}N^{-1}P^{-6})\\\end{aligned}}}$

Las permutaciones P más a la izquierda y más a la derecha del lado derecho (que también eran conocidas) se movieron hacia la izquierda; los resultados recibieron los nombres de variable UVWXYZ :

${\displaystyle {\begin{aligned}U&=P^{-1}H^{-1}S^{-1}ASHP^{1}&=(NP^{-1})Q(P^{1}N^{-1})\\V&=P^{-2}H^{-1}S^{-1}BSHP^{2}&=(NP^{-2})Q(P^{2}N^{-1})\\W&=P^{-3}H^{-1}S^{-1}CSHP^{3}&=(NP^{-3})Q(P^{3}N^{-1})\\X&=P^{-4}H^{-1}S^{-1}DSHP^{4}&=(NP^{-4})Q(P^{4}N^{-1})\\Y&=P^{-5}H^{-1}S^{-1}ESHP^{5}&=(NP^{-5})Q(P^{5}N^{-1})\\Z&=P^{-6}H^{-1}S^{-1}FSHP^{6}&=(NP^{-6})Q(P^{6}N^{-1})\\\end{aligned}}}$

Luego Rejewski multiplicó cada ecuación por la siguiente:

${\displaystyle {\begin{aligned}UV&=(NP^{-1})Q(P^{1}N^{-1})(NP^{-2})Q(P^{2}N^{-1})&=NP^{-1}(QP^{-1}QP)P^{1}N^{-1}\\VW&=(NP^{-2})Q(P^{2}N^{-1})(NP^{-3})Q(P^{3}N^{-1})&=NP^{-2}(QP^{-1}QP)P^{2}N^{-1}\\WX&=(NP^{-3})Q(P^{3}N^{-1})(NP^{-4})Q(P^{4}N^{-1})&=NP^{-3}(QP^{-1}QP)P^{3}N^{-1}\\XY&=(NP^{-4})Q(P^{4}N^{-1})(NP^{-5})Q(P^{5}N^{-1})&=NP^{-4}(QP^{-1}QP)P^{4}N^{-1}\\YZ&=(NP^{-5})Q(P^{5}N^{-1})(NP^{-6})Q(P^{6}N^{-1})&=NP^{-5}(QP^{-1}QP)P^{5}N^{-1}\\\end{aligned}}}$

A continuación, Rejewski eliminó la subexpresión común ( Q P ⁻¹ Q P ) sustituyendo su valor obtenido del producto anterior. ^[27]

${\displaystyle {\begin{aligned}VW&=NP^{-1}N^{-1}(UV)NP^{1}N^{-1}\\WX&=NP^{-1}N^{-1}(VW)NP^{1}N^{-1}\\XY&=NP^{-1}N^{-1}(WX)NP^{1}N^{-1}\\YZ&=NP^{-1}N^{-1}(XY)NP^{1}N^{-1}\\\end{aligned}}}$

El resultado es un conjunto de cuatro ecuaciones con una sola incógnita: NPN ⁻¹ .

Volvamos al ejemplo de 1930

Para el ejemplo de 1930 anterior,

 ABCDEFGHIJKLMNOPQRSTUVWXYZ Un ptkxrzqswmcojylagehbvuidnf B ukzmyxrsnqbwdipojghvatlfec C uymsznqwovtpcfilgxdkajhrbe D jwvrosuyzatqxpenldfkgcbmhi Y jxvqltnypaseugzidwkfmcrbho F nvykzutslxdioamwrqhgfbpjce

se transforman en las permutaciones UVWXYZ :

 ABCDEFGHIJKLMNOPQRSTUVWXYZ U gkvlysarqxbdptumihfnoczjew En gnfmycaxtrzsdbvwujliqophek W uekfbdszrtcyqxvwmigjaopnlh X jelfbdrvsaxctqyungimphzkow Y ltgmwycsvqxadzrujohbpiekfn De mskpiyuteqcravzdjlbhgnxwfo

y luego se multiplica para producir los cinco productos sucesivos:

 ABCDEFGHIJKLMNOPQRSTUVWXYZ UV = azoselgjuhnmwiqdtxcbvfkryp = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = sxdqlkunjihgfeopatyrmvwzbc = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = pbxdefiwgmlonkhztsrajyuqcv = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = qwaytmoihlkgbjfpzcvdusnxre = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = rhuaxfkbnjwmpolgqztsdeicyv = (f)(j)(q)(y)(bh)(st)(arzvexcud)(gkwinolmp)

Ahora el objetivo es encontrar el mapa de preservación de estructura única que transforma UV en VW, VW en WX, WX en XY y XY en YZ. Se encuentra por suscripción de notación de ciclo. ^{[ aclaración necesaria ]} Cuando UV se mapea en VW , el mapa debe coincidir con ciclos de la misma longitud. Eso significa que (a)en UV debe mapearse a uno de (o)(p)(v)(w)en VW . En otras palabras, adebe mapearse a uno de opvw. Estos se pueden probar a su vez.

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o) (p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (f)(j)(q)(y)(bh)(st)(arzvexcud)(gkwinolmp)

Pero adebe asignarse lo mismo oen cada emparejamiento, por lo que también se determinan otras asignaciones de caracteres:

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o) (p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (dembwnjlg) (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (olmpgkwin) (f)(j)(q)(y)(bh)(st)(arzvexcud)

En consecuencia, se descubren y son consistentes las asignaciones de caracteres para sybxzcdq, pzvycxqt, y qzetdyrc. Esas asignaciones se pueden aprovechar:

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p) (w) (ij)(umfkhnelg)(xzcdqasyb) (v)(rt)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (f)(b) (ig)(ohwujmnkl)(pzvycxqta) (d)(e)(rs)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (u)(k)(p) (ih)(dembwnjlg) (x)(sv)(aqzetdyrc)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (f) (j) (hb)(olmpgkwin)(udarzvexc) (q)(y)(st)

Que determina el resto del mapa y suscribe consistentemente:

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p)(v)(w)(tr)(ij)(umfkhnelg)(xzcdqasyb)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (e)(f)(b)(d)(sr)(ig)(ohwujmnkl)(pzvycxqta)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (u)(k)(p)(x)(vs)(ih)(ofmbwnjlg)(tdyrcaqze)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (q)(f)(y)(j)(ts)(hb)(olmpgkwin)(udarzvexc)

El mapa resultante con suscripciones sucesivas:

Mapa resultante: ABCDEFGHIJKLMNOPQRSTUVWXYZ ounkpxvtsrqzcaeflihgybdjwm = (aoepfxjrishtgvbuywdkqlzmcn) UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p)(v)(w)(tr)(ij)(umfkhnelg)(xzcdqasyb) WX = (e)(f)(b)(d)(gi)(sr)(ycxqtapzv)(jmnklohwu) XY = (p)(x)(u)(k)(vs)(hi)(wnjlgofmb)(rcaqzetdy) YZ = (f)(j)(y)(q)(bh)(ts)(darzvexcu)(inolmpgkw)

El mapa nos da NPN ⁻¹ , pero también es conjugado (preserva la estructura). En consecuencia, los 26 valores posibles para N se encuentran suscribiendo P de 26 maneras posibles.

El modelo anterior ignoró la posición del anillo (22) y la posición del fondo (12) del rotor derecho, ambas conocidas porque Rejewski tenía las llaves diarias. La posición del anillo tiene el efecto de contrarrotar el tambor en 21; la posición del fondo lo hace avanzar en 11. En consecuencia, la rotación del rotor es -10, que también es 16.

 ABCDEFGHIJKLMNOPQRSTUVWXYZRecto ounkpxvtsrqzcaeflihgybdjwmGpsquvbyxwortzmcekdafnljih desplazado = (agbpcsdqeufvnzhyixjwlrkomt)Suscríbete a P de diferentes maneras: (abcdefghijklmnopqrstuvwxyz) (bcdefghijklmnopqrstuvwxyza) * cableado real del rotor (cdefghijklmnopqrstuvwxyzab) ... (zabcdefghijklmnopqrstuvwxy)Rotor * ABCDEFGHIJKLMNOPQRSTUVWXYZ bdfhjlcprtxvznyeiwgakmusqo

Parrilla

La parrilla física ^{[ aclaración necesaria ]} se utilizó para determinar tanto el rotor más a la derecha, su posición inicial y las configuraciones del tablero de conexiones.

Sábana bajera

Rejewsky observó que S está cerca de la permutación identidad (a principios de la década de 1930, solo 12 de las 26 letras se vieron afectadas por el tablero de conexiones). Movió todo, excepto Q, al lado izquierdo de las ecuaciones mediante premultiplicación o posmultiplicación. El sistema de ecuaciones resultante es:

${\displaystyle {\begin{aligned}(P^{1}N^{-1}P^{-1})S^{-1}AS(P^{1}NP^{-1})&=Q\\(P^{2}N^{-1}P^{-2})S^{-1}BS(P^{2}NP^{-2})&=Q\\(P^{3}N^{-1}P^{-3})S^{-1}CS(P^{3}NP^{-3})&=Q\\(P^{4}N^{-1}P^{-4})S^{-1}DS(P^{4}NP^{-4})&=Q\\(P^{5}N^{-1}P^{-5})S^{-1}ES(P^{5}NP^{-5})&=Q\\(P^{6}N^{-1}P^{-6})S^{-1}FS(P^{6}NP^{-6})&=Q\\\end{aligned}}}$

En este punto, Q es desconocido, pero es el mismo para cada ecuación. Rejewski no conoce N , pero sabe que es uno de los rotores (I, II y III), y conoce el cableado para cada uno de esos rotores. Solo había tres rotores y 26 posibles rotaciones iniciales. En consecuencia, solo hay 84 valores posibles para N. Rejewski puede observar cada valor posible para ver si la permutación Q es consistente. Si no hubiera steckers ( S fuera la identidad), entonces cada ecuación produciría el mismo Q.

En consecuencia, hizo una hoja inferior para cada rotor posible (tres hojas). Cada hoja inferior constaba de 31 líneas (26 + 5 para hacer seis líneas contiguas). Cada línea contenía la permutación escalonada de un rotor conocido. ^[28] Por ejemplo, una hoja inferior adecuada para el rotor III es,

${\displaystyle {\begin{aligned}P^{0}&NP^{-0}&\ {\texttt {bdfhjlcprtxvznyeiwgakmusqo}}\\P^{1}&NP^{-1}&\ {\texttt {cegikboqswuymxdhvfzjltrpna}}\\P^{2}&NP^{-2}&\ {\texttt {dfhjanprvtxlwcgueyiksqomzb}}\\&...&...\\P^{25}&NP^{-25}&\ {\texttt {pcegikmdqsuywaozfjxhblnvtr}}\\P^{0}&NP^{-0}&\ {\texttt {bdfhjlcprtxvznyeiwgakmusqo}}\\P^{1}&NP^{-1}&\ {\texttt {cegikboqswuymxdhvfzjltrpna}}\\P^{2}&NP^{-2}&\ {\texttt {dfhjanprvtxlwcgueyiksqomzb}}\\P^{3}&NP^{-3}&\ {\texttt {egizmoquswkvbftdxhjrpnlyac}}\\P^{4}&NP^{-4}&\ {\texttt {fhylnptrvjuaescwgiqomkxzbd}}\\\end{aligned}}}$

A principios de la década de 1930, el orden de los rotores era el mismo durante un mes o más, por lo que los polacos generalmente sabían qué rotor estaba en la posición más a la derecha y solo necesitaban usar una hoja inferior. Después del 1 de noviembre de 1936, el orden de los rotores cambiaba todos los días. Los polacos podían usar el método del reloj para determinar el rotor más a la derecha, por lo que la parrilla solo tendría que examinar la hoja inferior de ese rotor. ^[29]

Hoja superior

Para la hoja superior, Rejewski escribió las seis permutaciones A a F.

A: abcdefghijklmnopqrstuvwxyz srwivhnfdolkygjtxbapzecqmu(..abertura......................)...F: abcdefghijklmnopqrstuvwxyz wxofkduihzevqscymtnrglabpj(..abertura......................)

Había seis ranuras para que las permutaciones en la hoja inferior se vieran en el lugar correcto.

La hoja superior se deslizaría entonces por todas las posiciones posibles del rotor N y el criptoanalista buscaría coherencia con alguna permutación desconocida pero constante Q. Si no hay una Q coherente , se prueba con la siguiente posición.

Esto es lo que mostraría la parrilla para las permutaciones anteriores en su alineación constante:

A: abcdefghijklmnopqrstuvwxyz ptkxrzqswmcojylagehbvuidnf17 fpjtvdbzxkmoqsulyacgeiwhnr (visible a través de la ranura)B: abcdefghijklmnopqrstuvwxyz ukzmyxrsnqbwdipojghvatlfec18 oisucaywjlnprtkxzbfdhvgmqe (visible a través de la ranura)C: abcdefghijklmnopqrstuvwxyz ueymsznqwovtpcfilgxdkajhrbe19 hrtbzxvikmoqsjwyaecguflpdn (visible a través de la ranura)D: abcdefghijklmnopqrstuvwxyz jwvrosuyzatqxpenldfkgcbmhi20 qsaywuhjlnprivxzdbftekocmg (visible a través de la ranura)E: abcdefghijklmnopqrstuvwxyz jxvqltnypaseugzidwkfmcrbho21 rzxvtgikmoqhuwycaesdjnblfp (visible a través de la ranura)F: abcdefghijklmnopqrstuvwxyz nvykzutslxdioamwrqhgfbpjce22 ywusfhjlnpgtvxbzdrcimakeoq (visible a través de la ranura)

En la permutación A , el criptoanalista conoce ese (c k)intercambio. Puede ver cómo el rotor III desordenaría esas letras mirando la primera línea (el alfabeto en orden) y la línea visible a través de la ranura. El rotor se asigna ca jy se asigna ka m. Si ignoramos los steckers por el momento, eso significa que la permutación Q intercambiaría (j m). Para que Q sea consistente, debe ser el mismo para las seis permutaciones ABCDEF .

Observa la rejilla cerca de la permutación D para comprobar si su Q también se intercambia (j m). A través de la ranura, busca la letra jy mira en la misma columna dos líneas por encima para encontrar h. Eso nos dice que el rotor, cuando ha avanzado tres posiciones, ahora se asigna ha j. De manera similar, el rotor avanzado se asignará ya m. Observando la permutación D , se intercambia (h y), por lo que las dos pruebas son consistentes.

De manera similar, en la permutación A , el (d x)intercambio y implican que (t h)hay intercambio en Q . Si observamos la permutación E , (e l)el intercambio y también implican que (t h)hay intercambio en Q .

Todas estas pruebas serían coherentes si no hubiera steckers, pero los steckers confunden el asunto al ocultar dichas coincidencias. Si alguna de las letras involucradas en la prueba está steckerizada, entonces no parecerá una coincidencia.

El efecto de la permutación del rotor se puede eliminar para dejar la Q implícita en las permutaciones ABCDEF . El resultado (junto con el valor real de Q ) es:

 -: ABCDEFGHIJKLMNOPQRSTUVWXYZP(R): vyzrilptemqfjsugkdnhoaxwbcPregunta(B): myqvswpontxzaihgcuejrdfkblQ(C): vcbrpmoulxwifzgeydtshakjqnQ(D): kyirhulecmagjqstndopfzxwbvQ(E): vemgbkdtwufzcxrysoqhjainplQ(F): wvlrpqsmjizchtuefdgnobayxkP: vyqrpkstnmfzjiuecdghoaxwbl (el criptoanalista desconoce esta pregunta real)

La mayoría de las letras en una permutación implícita son incorrectas. Un intercambio en una permutación implícita es correcto si dos letras no están steckerizadas. Aproximadamente la mitad de las letras están steckerizadas, por lo que la expectativa es que solo una cuarta parte de las letras en una permutación implícita sean correctas. Varias columnas muestran correlaciones; la columna Atiene tres vcaracteres e (a v)intercambio en la Q real ; la columna Dtiene cuatro rcaracteres e (d r)intercambio en Q. ^[30 ]

Rejewski (1981, p. 222) describe la posibilidad de escribir las seis Q implícitas para las 26 posibles posiciones del rotor. Rejewski afirma: "Si la permutación S fuera realmente la identidad, entonces... para una [posición inicial] particular obtendríamos el mismo valor para todas las expresiones Q y de esta manera encontraríamos la posición del tambor N. Sin embargo, la permutación S existe, por lo que para ninguna [posición inicial] las expresiones Q serán iguales entre sí, pero entre ellas habrá una cierta similitud para una [posición inicial] particular, ya que la permutación S no cambia todas las letras".

Rejewski afirma que escribir todas las Q posibles "sería demasiado laborioso", por lo que desarrolló el método de la rejilla (grid). ^[28] "A continuación, la rejilla se mueve a lo largo del papel en el que están escritas las conexiones del tambor hasta que llega a una posición en la que aparecen algunas similitudes entre las diversas expresiones Q ... De esta manera, la configuración del tambor N y los cambios resultantes de la permutación S se encuentran simultáneamente. Este proceso requiere una concentración considerable ya que las similitudes que mencioné no siempre se manifiestan de manera distinta y pueden pasarse por alto muy fácilmente". ^[28] La referencia no describe qué técnicas se utilizaron. Rejewski afirmó que el método de la rejilla requería pares de letras sin steckers. ^[31]

La permutación A tiene los intercambios (ap)(bt)(ck).... Si asumimos que el intercambio (ap)no está steckerizado, eso implica que Q intercambia (fl). Las otras cinco permutaciones BCDEF se pueden verificar rápidamente para un par no steckerizado que sea consistente con el intercambio de Q(fl) , esencialmente verificando la columna Fpara otras filas con lsin calcular la tabla completa. No se encuentra ninguno, por lo que (ap)tendría al menos un stecker, por lo que se abandona la suposición de que no está steckerizado. Se puede suponer que el siguiente par no está steckerizado. El intercambio (bt)implica que Q intercambia (pg); eso es consistente con (lw)en B , pero esa suposición no funciona porque ty westán steckerizados.

A: b↔t B: l↔w C: k←t D: x→m E: m→u F: j←x ↓ ↓ ↓ ↓ * ↑ ↑ * ↑ * * ↑ por favor, lea esto ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑P: p↔gp↔gp↔gp↔gp↔gp↔gLa suposición (b)(t) no incrustada en S conduce a la suposición (l)(w) no incrustada en S C encuentra stecker (kx) D encuentra stecker (zm) E encuentra stecker (fu) F encuentra (j)

Seguir esas conjeturas conduce en última instancia a una contradicción:

A: f↔z B: m→d C: p←l D: f→s E: p!x F: ↓ ↓ ↑ * * ↑ ↑ * ↑ ↑ umzyrluark  ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑P: e↔qe↔qe↔qe↔qe↔qe↔qLa explotación (fz) en A conduce a un intercambio (eq) en Q B encuentra (dy) steckered C encuentra (pr) steckered D encuentra (como) steckered E encuentra (px) steckered - ¡pero p ya está steckered a r! Error

El tercer intercambio (ck)implica Q intercambios (jm); esta vez la permutación D con un no steckered (hy)sería consistente con Q intercambios (jm).

A: c↔k B: C: D: h↔y E: F: ↓ ↓ ↑ ↑ ckixnjhyuigu ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑Q: j↔mj↔mj↔mj↔mj↔mj↔mLa suposición de (c)(y) no incrustada en S conduce a la suposición de (h)(y) no incrustada en S

En este punto, la suposición es que las letras chkyno están steckerizadas. A partir de esa suposición, todos los steckers se pueden resolver para este problema en particular. Los intercambios conocidos (supuestos) en S se utilizan para encontrar intercambios en Q , y esos intercambios se utilizan para ampliar lo que se sabe sobre S .

Al usar esas letras no stecker como semillas se encuentra (hy)intercambio en E e implica (kf)que está en Q ; de manera similar, (cy)se intercambia en F e implica (uo)que está en Q. Al examinar (uo)las otras permutaciones, (tu)se encuentra un stecker.

A: B: C: D: E: h↔y F: ↓ ↓ jaosivvshywe ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Q: k↔fk↔fk↔fk↔fk↔fk↔fexplotar (hy) en EA: B: C: t←k D: E: F: c↔y * ↑ ↓ ↓ viejoaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑P: u↔ou↔ou↔ou↔ou↔ou↔oexplotar (cy) en F muestra que (tu) están en S

Eso añade letras tua las semillas. Esas letras también eran desconocidas anteriormente, por lo que se puede obtener más información revisando: S también tiene (g)(if)(x).

A: c↔k B: f→x C: D: h↔y E: t→f F: g←t ↓ ↓ ↑ * ↑ ↑ ↑ * * ↑ ckixnjhyuigu ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑Q: j↔mj↔mj↔mj↔mj↔mj↔mSaber (tu) en S conduce a (g)(si) en Sentonces (si) en S se puede utilizar para encontrar (x) en S

Revisar (kf)(uo)en Q brinda más información:

A: B: o←p C: f→n D: n→p E: h↔y F: z→e * ↑ ↑ * ↑ * ↓ ↓ ↑ * jaosivvshywe ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Q: k↔fk↔fk↔fk↔fk↔fk↔fexplotar (si) en S conduce a (nv) en S (nv) en S conduce a stecker (ps) (ps) en S conduce a (o) (wz) en S conduce a (e)A: o→l B: C: t←k D: i→z E: F: c↔y ↑ * * ↑ ↑ * ↓ ↓ viejoaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑P: u↔ou↔ou↔ou↔ou↔ou↔oexplotar (si) en S conduce a stecker (wz) en S (o) en S conduce a (l) en S

Otra revisión explota al máximo (jm):

A: c↔k B: fx C: v→j D: h↔y E: t→f F: g←t ↓ ↓ ↑ * ↑ * ↑ ↑ ↑ * * ↑ ckixnjhyuigu ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑Q: j↔mj↔mj↔mj↔mj↔mj↔mSaber (nv) en S conduce a (j) en S

Ese añadido lo completa aún más:

A: j→m B: o←p C: f→n D: n→p E: h↔y F: z→e ↑ * * ↑ ↑ * ↑ * ↓ ↓ ↑ * jaosivvshywe ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Q: k↔fk↔fk↔fk↔fk↔fk↔fexplotar (j) en S conduce a (am) en SA: o→l B: d←m C: t←k D: i→z E: a↔j F: c↔y ↑ * * ↑ * ↑ ↑ * ↑ ↑ ↓ ↓ viejoaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑P: u↔ou↔ou↔ou↔ou↔ou↔oexplotar (j)(am) en S conduce a (d) en SQ = ( (fk)(jm)(ou)... ) faltan 10 emparejamientosS = ( (am)(c)(d)(fi)(g)(h)(j)(k)(l)(nv)(o)(ps)(tu)(wz)(x)(y)... ) 22 caracteres hasta el momento: falta beqr He encontrado los 6 steckers, por lo que (b)(e)(q)(r)

Ahora se conoce todo S después de examinar 3 intercambios en Q. El resto de Q se puede encontrar fácilmente.

Cuando se encuentra una coincidencia, el criptoanalista aprendería tanto la rotación inicial de N como la permutación del tablero de conexiones ( Stecker ) S. ^[28]

Recuperación de posiciones absolutas del rotor para la clave de mensaje

En este punto, no se conocen las posiciones del rotor para la permutación Q. Es decir, no se conocen las posiciones iniciales (y posiblemente el orden) de los rotores L y M. Los polacos aplicaron fuerza bruta probando todas las posiciones iniciales posibles ( 26 ² = 676 ) de los dos rotores. ^[28] Con tres rotores, saber cuál rotor estaba en la posición N significaba que solo había dos formas posibles de cargar los otros dos rotores.

Más tarde, los polacos elaboraron un catálogo de todas las permutaciones de Q. El catálogo no era muy grande: había seis combinaciones posibles de dos rotores izquierdos con 26 ² = 676 configuraciones iniciales, por lo que el catálogo tenía 4.056 entradas. Después de utilizar la parrilla, los polacos buscaban Q en el catálogo para conocer el orden y las posiciones iniciales de los otros dos rotores. ^[29]

Al principio, los alemanes cambiaban el orden de los rotores con poca frecuencia, por lo que los polacos solían saberlo antes de empezar a trabajar. El orden de los rotores cambiaba cada trimestre hasta el 1 de febrero de 1936. Después, cambiaba cada mes hasta el 1 de noviembre de 1936, cuando se cambiaba a diario. ^[29]

Recuperando la configuración del anillo

El criptoanalista ya conocía el tablero de conexiones, el orden de los rotores y la posición absoluta de los rotores para la clave duplicada, pero no conocía la posición del anillo. También sabía cuál debía ser la posición de la clave del mensaje, pero esa posición era inútil sin conocer la posición del anillo. La posición del anillo podía ser cualquier cosa, y eso significaba que los polacos no sabían cómo posicionar los rotores para el cuerpo del mensaje. Todo el trabajo hasta ese momento se había centrado en explotar la clave duplicada. Para determinar la posición del anillo, la atención se desplazó ahora al mensaje real.

En este caso, los alemanes cometieron otro error. Cada mensaje empezaba normalmente con el texto "ANX", que en alemán significaba "a:", y la "X" significaba espacio. Los polacos también aplicaron la fuerza bruta. Para encontrar los valores que daban "ANX", tuvieron que recorrer hasta 26 ³ = 17.576 configuraciones. Una vez encontrados, el criptoanalista utilizaba la configuración absoluta de los rotores para determinar la configuración del anillo. De este modo, se recuperaba la clave diaria completa.

Más tarde, los polacos perfeccionaron la técnica de búsqueda por fuerza bruta. Examinando algunos mensajes, pudieron determinar la posición del rotor más a la derecha; por lo tanto, sólo habría que probar 676 posiciones de rotor. Rejewski ya no recuerda cómo funcionaba este truco. ^[32]

Rechazar

Marian Rejewski describe el método de la parrilla como "manual y tedioso" ^[2] y, al igual que la posterior bomba criptológica, como "basado... en el hecho de que las conexiones de los enchufes [en el conmutador o "tablero de conexiones" de la Enigma] no cambiaban todas las letras". Sin embargo, a diferencia de la bomba, "el método de la parrilla requería pares de letras sin cambios [en lugar de] sólo letras sin cambios". ^[31]

Inicialmente, el tablero de conexiones solo intercambiaba seis pares de letras, lo que dejaba más de la mitad del alfabeto sin verse afectado por la permutación S. El número de steckers cambió el 1 de agosto de 1936; entonces se podían intercambiar de cinco a ocho pares de letras. ^[33] Los caracteres extra intercambiados redujeron la eficacia del método de la cuadrícula, por lo que los polacos comenzaron a buscar otros métodos. El resultado fue el ciclometro y el catálogo de tarjetas correspondiente; ese método era inmune a los steckers.

El método de la parrilla se aplicó en diciembre de 1938 para trabajar en el cableado de dos rotores Enigma recién introducidos por los alemanes (esto fue posible gracias a que una red del Sicherheitsdienst , si bien había introducido los nuevos tambores IV y V, continuó utilizando el antiguo sistema para cifrar las claves de mensajes individuales). ^[34]

El 15 de septiembre de 1938, la mayoría de las redes alemanas dejaron de cifrar la clave duplicada con una configuración común (la configuración de tierra). Los polacos habían podido aprovechar todos los mensajes de una red utilizando la misma configuración de máquina para cifrar la clave duplicada. Ahora la mayoría de las redes dejaron de hacerlo; en su lugar, el operador elegiría su propia configuración de tierra y la enviaría sin cifrar al destinatario. ^[35] Este cambio frustró el método de la parrilla y el catálogo de tarjetas del ciclómetro. Una red, la red Sicherheitsdienst (SD), continuó utilizando una configuración de tierra común, y esa red se utilizó para aplicar ingeniería inversa a los nuevos rotores (IV y V) que se introdujeron. ^[36] El tráfico de la red SD estaba doblemente codificado, por lo que el método ANX no funcionaría. ^[37] El método de la parrilla a veces fallaba después de que los alemanes aumentaran el número de conexiones del tablero de conexiones a diez el 1 de enero de 1939. Cuando la red SD cambió al nuevo protocolo de clave de mensaje el 1 de julio de 1939, el método de la parrilla (y el método del ciclómetro) ya no eran útiles. ^[36]

A continuación se muestra un ejemplo del procedimiento de mensaje nuevo para un mensaje del 21 de septiembre de 1938. ^[38]

2109 -1750 - 3 TLE - FRX FRX - 1TL -172=HCALN UQKRQ AXPWT WUQTZ KFXZO MJFOY RHYZW VBXYS IWMMV WBLEBDMWUW BTVHM RFLKS DCCEX IYPAH RMPZI OVBBR VLNHZ UPOSY EIPWJTUGYO SLAOX RHKVC HQOSV DTRBP DJEUK SBBXH TYGVH GFICA CVGUVPreguntas frecuentes Preguntas frecuentes

El "3 TLE" (en alemán Teile , partes) indica que es un mensaje de 3 partes; el "1TL" (en alemán Teil , parte) indica que ésta es la primera parte; el "172" indica que hay 172 caracteres en el mensaje (incluida la clave del mensaje). Para este mensaje, la configuración terrestre "FRX" se transmite dos veces en claro; la configuración terrestre debería ser diferente para cada mensaje en la red. En consecuencia, los polacos no pudieron encontrar las sesenta claves de mensaje necesarias cifradas con la misma configuración terrestre. Sin el mismo volumen de mensajes con clave, no pudieron determinar la característica, por lo que no pudieron determinar las permutaciones ABCDEF ni utilizar la rejilla. Para este mensaje, se utilizaron las configuraciones diarias (orden del rotor, tablero de conexiones y configuraciones del anillo) con "FRX" para descifrar los primeros seis caracteres ("HCALN U") para obtener la clave de mensaje duplicada ("AGIAGI").

Para descifrar estos mensajes, los polacos utilizaron otras técnicas para explotar la clave del mensaje duplicado.

Véase también

• Matriz de permutación

Notas

1. Marian Rejewski, Solución matemática del cifrado Enigma, trad. Christopher Kasparek, Cryptologia, vol. 6, número 1, págs. 1–18, 17, enero de 1982
2. Rejewski 1984e, pág. 290
3. Kahn 1991, págs. 39–41, 299.
4. Kahn 1991, págs. 41, 299.
5. Kruh y Deavours 2002, pag. 97.
6. Rejewski 1981, p. 215 Tome la cantidad de maneras de ordenar 26 letras distintas (¡26!) y empareje las letras seleccionadas. Las letras emparejadas se intercambian, por lo que divida por 2 ¹³ para tener en cuenta los dos ordenamientos de cada par. El orden en que se enumeran los pares no importa, por lo que divida por la cantidad de maneras de ordenar los 13 pares (¡13!).
7. Rejewski 1981, pág. 216 Tome el número de maneras de organizar 26 letras distintas y empareje las primeras 12 letras; divida por 2 ⁶ porque los pares se pueden intercambiar (AB es lo mismo que BA), divida por 6! porque el orden de los pares no importa, y divida por 14! porque el orden de los 14 caracteres finales no importa.
8. Lisicki 1979, pag. 68, Bild 1, Beispiel (Ejemplo)
9. "CryptoCellar de Frode Weierud | Mensaje de prueba de Enigma de 1930". Archivado desde el original el 30 de octubre de 2014. Consultado el 7 de octubre de 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, 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 conectores (AM, FI, NV, PS, TU, WZ), active el tablero de conectores y configure las ruedas en la configuración de tierra ("FOL"). Al escribir ABLABL en el cuadro de entrada, debería aparecer PKPJXI como resultado.
11. Rejewski 1981, p. 217, afirmando: "El hecho de que las primeras seis letras de cada mensaje formaran su clave de tres letras, cifrada dos veces, era obvio y no me extenderé en ese asunto".
12. Wussing, Hans (2007), La génesis del concepto de grupo abstracto: una contribución a la historia del origen de la teoría de grupos abstractos, Courier Dover Publications, pág. 94, ISBN 9780486458687Cauchy utilizó su notación de permutación (en la que los arreglos se escriben uno debajo del otro y ambos están encerrados entre paréntesis) por primera vez en 1815.
13. Harkin, Anthony A.; Harkin, Joseph B. (abril de 2004), "Geometría de números complejos generalizados" (PDF) , Mathematics Magazine , 77 (2): 118–129, doi :10.1080/0025570X.2004.11953236, S2CID  7837108en la página 129 implica ambas notaciones utilizadas en 1815.
14. Cauchy, Augustin-Louis (1987), "Augustin Louis Cauchy sobre la teoría de las permutaciones", en Fauvel, John; Gray, Jeremy (eds.), La historia de las matemáticas: un lector, Macmillan Press en asociación con The Open University, págs. 506-507, ISBN 9780333427910
15. Rejewski 1981, pág. ??
16. Marks, Philip; Weierud, Frode (enero de 2000), "Recuperación del cableado de Umkehrwalze A de Enigma" (PDF) , Cryptologia , 24 (1): 55–66, CiteSeerX 10.1.1.622.1584 , doi :10.1080/0161-110091888781, S2CID  4473786 (pagina 3 en PDF)
17. Tuma, Jirí (2003), Grupos de permutación y la solución del cifrado alemán Enigma (PDF) , Frode Weierud, p. 51, archivado desde el original (PDF) el 2014-10-30 , consultado el 2014-09-12
18. Rejewski 1981, pág. ?
19. Lisicki (1979, pp. 72–74) ofrece un ejemplo de tabla con 65 claves de mensajes, pero sólo 40 de ellas eran distintas. Dieciséis claves se repetían al menos una vez. La clave cifrada "SYX SCV" se utilizó cinco veces; correspondía a la clave de mensaje "AAA". La clave cifrada "RJL WPX" se utilizó cuatro veces; correspondía a "BBB".
20. Rejewski (1981, p. 218) afirma: "Cuando supuse por primera vez que habría muchas claves del tipo aaa , bbb , etc., era solo una hipótesis que afortunadamente resultó ser cierta. Se siguieron muy de cerca los gustos cambiantes de los criptógrafos y se descubrieron otras predilecciones".
21. Rejewski 1981, p. 218, donde se afirma: "De este modo, se resolvió uno de los misterios del código Enigma, el secreto de la clave del mensaje. Es interesante que no se necesitara el conocimiento de las posiciones de los tambores ni de las claves diarias (en otras palabras, ninguno de los secretos restantes del código Enigma) para obtener el resultado".
22. Rejewski, Marian (1980), "Una aplicación de la teoría de permutaciones para descifrar el cifrado Enigma" (PDF) , Aplicaciones Mathematicae , 16 (4), archivado desde el original (PDF) el 2014-10-30, De esta manera, un conocimiento preciso de las preferencias de los criptógrafos junto con el teorema sobre el producto de transposiciones nos permite encontrar la única solución real.
23. Más tarde conocida como "hembra".
24. Rejewski 1981, pág. 218
25. Rejewski 1981, p. 219 ecuación 3 con H eliminado
26. Rejewski 1981, pág. 219
27. Rejewski 1981, pág. 220
28. Rejewski 1981, pág. 222
29. Rejewski 1981, pág. 223
30. Uno de los Dintercambios es accidental debido a un doble stecker que asigna un intercambio diferente.
31. Rejewski 1984c, pág. 242
32. Rejewski 1981, p. 223: "... pronto nos dimos cuenta de que si alguna parte del mensaje comenzaba con ANX , varias posiciones del tambor N serían imposibles y ya no deberían considerarse. Como había una docena de mensajes cada día en los que uno podía esperar encontrar las letras ANX al principio, generalmente era posible rechazar, puramente por cálculo, todas las posiciones imposibles del tambor N dejando solo una o dos para considerar. (Ya no recuerdo qué cálculos se tuvieron que realizar y en qué principios teóricos se basaban.)"
33. Rejewski 1981, pág. 224
34. Rejewski 1984d, pág. 268
35. Rejewski 1981, págs. 225-226
36. Rejewski 1981, pág. 227
37. Rejewski 1981, pág. 225
38. [1] Archivado el 30 de octubre de 2014 en Wayback Machine, transcrito de Cryptologia, CA Deavours y Louis Kruh, "The Turing Bombe: Was It Enough?", Cryptologia, Vol. XIV, No.4, octubre de 1990, pp. 331-349, en la página 342.

Referencias

• Kahn, David (1991). Capturando el enigma: la carrera para descifrar los códigos de los submarinos alemanes, 1939-1943 . ISBN 978-0-395-42739-2.
• Kozaczuk, Władysław (1984), Enigma: How the German Machine Cipher was Broken, and how it was Read by the Allies in World War Two, editado y traducido por Christopher Kasparek [una traducción revisada y aumentada de W kręgu enigmy , Varsovia, Książka i Wiedza, 1979, complementada con apéndices de Marian Rejewski], Frederick, MD, Publicaciones Universitarias de América, ISBN 978-0-89093-547-7.
• Kruh, L.; Deavours, C. (2002). "El enigma comercial: comienzos de la criptografía mecánica". Cryptologia . 26 : 1–16. doi :10.1080/0161-110291890731. S2CID  41446859.
• Lisicki, Tadeusz (1979), "Die Leistung des polnischen Entzifferungsdienstes bei der Lösung des Verfahrens der deutschen »Enigma«-Funkschlüsselmachine" [Los métodos que utilizó la Oficina de cifrado polaca para resolver la máquina de cifrado Enigma alemana] (PDF) , en Rohwer, J .; Jäkel, E. (eds.), Die Funkaufklärung und ihre Rolle im Zweiten Weltkrieg [ La radiointeligencia y su papel en la Segunda Guerra Mundial ] (en alemán), Stuttgart: Motorbuch Verlag, págs. 66–81, archivado desde el original (PDF) ) el 19 de octubre de 2014 , consultado el 12 de octubre de 2014
• Rejewski, Marian (julio de 1981), "Cómo los matemáticos polacos descifraron el enigma" (PDF) , Anales de la historia de la informática , 3 (3): 213–234, doi :10.1109/MAHC.1981.10033, S2CID  15748167
• Rejewski, Marian (1984c), Resumen de nuestros métodos para reconstruir ENIGMA y reconstruir claves diarias, y de los esfuerzos alemanes para frustrar esos métodos: Apéndice Cde Kozaczuk 1984, págs. 241–45
• Rejewski, Marian (1984d), Cómo los matemáticos polacos descifraron Enigma: Apéndice Dde Kozaczuk 1984, págs. 246–71
• Rejewski, Marian (1984e), La solución matemática del cifrado Enigma: Apéndice Ede Kozaczuk 1984, págs. 272-291

Enlaces externos

• Contribuciones polacas a la informática, http://chc60.fgcu.edu/EN/HistoryDetail.aspx?c=1 Archivado el 13 de julio de 2014 en Wayback Machine.
• Gaj, Kris; Orlowski, Arkadiusz (mayo de 2003), "Hechos y mitos de Enigma: rompiendo estereotipos", en Biham, Eli (ed.), Avances en criptología — EUROCRYPT 2003: Conferencia internacional sobre la teoría y aplicaciones de técnicas criptográficas, Varsovia, Polonia: Springer-Verlag, págs. 106–122, ISBN 978-3-540-14039-9, LNCS 2656También https://www.iacr.org/archive/eurocrypt2003/26560106/26560106.doc
• Casselman, Bill (noviembre de 2009), Marian Rejewski y la primera incursión en Enigma, columna destacada, American Mathematical Society , consultado el 15 de noviembre de 2014
• Casselman, Bill (diciembre de 2013), El ataque polaco a Enigma II: hojas de Zygalski, Columna destacada, American Mathematical Society , consultado el 15 de noviembre de 2014
• Inteligencia de señales del Eje europeo en la Segunda Guerra Mundial revelada por las investigaciones de "TICOM" y por otros interrogatorios de prisioneros de guerra y material capturado, principalmente alemán: Volumen 2 — Notas sobre criptografía y criptoanálisis de alto nivel alemanes; consulte la página 76: Los suizos cambiaban los cableados de los rotores cada 3 meses, pero los alemanes se dieron cuenta de los cableados porque algunos mensajes se enviaban dos veces durante el cambio trimestral. La empresa que fabricaba los rotores les dijo a los alemanes que los cableados de los rotores eran croatas nuevos.
• Bauer pág. 419