Matemáticamente, ¿por qué la máquina Enigma era tan difícil de descifrar?

Question

Matemáticamente, ¿por qué era tan difícil descifrar la máquina Enigma?

En términos sencillos, ¿qué fue exactamente lo que hizo que descifrar la máquina Enigma fuera una tarea tan formidable? Todo lo que he visto sobre la máquina Enigma, desde un artículo general a la información sobre criptoanálisis de la Enigma es bastante extenso, y parece difícil señalar exactamente la dificultad matemática más destacada a la que se enfrentaron los descifradores de códigos, aparte del gran número de configuraciones posibles (159 millones de millones según este Sitio web de Bletchley Park ) que cambiaba cada día. ¿O realmente era esto? Parece que hay mucho más que eso.

Esperaba que alguien con bastantes conocimientos sobre las matemáticas que hay detrás de la Enigma y su ruptura pudiera dar una razón condensada y simplificada de lo que hizo que descifrar esta máquina fuera una empresa tan monumental.

Answer 1

Estoy en total desacuerdo con la otra respuesta, que trivializa las contribuciones de Alan Turing y su grupo, así como de los matemáticos polacos que trabajaron por primera vez en el problema. Por supuesto, el aumento de los números hace que el problema sea más difícil, pero incluso con un ordenador moderno, un ataque de fuerza bruta a los a menudo citados 150 millones de combinaciones (este número en realidad varió a lo largo de la guerra y para diferentes configuraciones de la máquina Enigma) sería una tarea difícil. Como los ordenadores ni siquiera existían al comienzo de la guerra, no había ninguna posibilidad de atacar el problema por la fuerza bruta.

Por lo tanto, hubo que desarrollar nuevos métodos para reducir el número posible de combinaciones. Un ejemplo es Banburismus un método estadístico desarrollado por Alan Turing. Este era un método que permitía excluir muchas posibilidades incluso sin ninguna "cuna" es decir, las partes conocidas del texto plano del mensaje.

La idea básica es que, dadas dos cadenas de lenguaje natural, compartirán muchas más letras en las mismas posiciones que dos cadenas aleatorias. Esto se debe a que ciertas letras son mucho más probables que otras. Por ejemplo, un ejemplo de la página enlazada:

HereisthefirstmessageofapairNothingspecialjustordinaryEnglishtext
BelowitanotherAgainyoucanseethatitismerelyarandomexamplemessage
 -    -                -        -  - -             -       -  -

Aquí tenemos nueve letras coincidentes o superpuestas. Con dos cadenas aleatorias, esperaríamos una media de dos o tres coincidencias para un mensaje de esta longitud.

Una idea crucial fue entonces que esta propiedad se conserva incluso si ambos mensajes se descifran a través de la máquina Enigma. Esto permitió el desarrollo de un ataque que podía descartar muchas combinaciones por motivos estadísticos.

La descripción del método deja claro que los inicios de la teoría de la información, establecidos formalmente por Claude Shannon en su artículo " Una teoría matemática de la comunicación " en 1948, ya están presentes en estas ideas. Decir que sólo era cuestión de construir una máquina lo suficientemente rápida para probar todas las combinaciones es un insulto a estos logros teóricos.

---

Sólo por diversión, aquí hay un poco de matemáticas sobre el problema de la frecuencia de las letras. Digamos que $X_1 \in \{ 1, 2, \ldots, 26 \}$ denota el caso de que una letra del primer mensaje sea A, B, ..., Z, y de forma similar $X_2$ una letra en el segundo mensaje. Como los mensajes son independientes, también lo son estos eventos. Por tanto, dejemos que $p \in \mathbb R^{26}$ denotan el vector $(P(X_1 = 1), \ldots, P(X_1 = 26))$ es decir, las frecuencias de las letras de nuestra lengua.

Entonces la probabilidad de que una posición contenga la misma letra en ambos mensajes es $$P(X_1=X_2) = \sum_{i=1}^{26} P(X_1 = i \land X_2=i) = \sum_{i=1}^{26} P(X_1 = i) P(X_2=i) = \| p \|_{\ell_2}^2.$$ (Aquí asumimos implícitamente que cada letra es independiente de la siguiente, lo que no es del todo cierto. Utilizar las frecuencias de los digramas o trigramas sería más preciso).

Si nuestro "lenguaje" es aleatorio, es decir, $p=(\frac 1{26}, \ldots, \frac 1{26})$ obtenemos que la probabilidad anterior para una letra coincidente es $\frac 1{26}$ . Por lo tanto, para nuestro mensaje de 63 letras, esperaríamos alrededor de $63/26 \approx 2.4$ letras coincidentes.

De hecho, esta es la menor probabilidad posible: ya que las probabilidades en $p$ debe sumar 1, obtenemos de la desigualdad de Cauchy-Schwarz que $$1 = \sum_{i=1}^{26} p_i \le \sqrt{26} \|p\|_{\ell_2},$$ y por lo tanto $$\|p\|_{\ell_2}^2 \ge \frac 1 {26}.$$

Utilizando el frecuencias de letras para el inglés dado en Wikipedia, podemos calcular que para el idioma inglés, tenemos $$\|p\|_{\ell_2}^2 = 0.0655 > 0.0385 = \frac 1 {26}.$$ Supongo que al tener en cuenta los di- y los trigramas, esta cifra aumentaría aún más.

Actualización: Al descargar una versión de texto de "Guerra y Paz" del Proyecto Gutenberg y masajearla en IPython, encontré distribuciones de letras muy similares a las que se dan en Wikipedia, dando como resultado $\|p\|_{\ell_2}^2 \approx 0.0659$ .

A continuación, extraje pares de cadenas de 60 letras al azar del texto y conté el número de coincidencias entre ellas. Repitiendo este experimento 1.000.000 de veces, encontré una probabilidad media de coincidencia de 0,0659 por letra. Así que parece que la simple estimación de primer orden $\|p\|_{\ell_2}^2$ es en realidad una muy buena aproximación a la probabilidad de coincidencia de letras.

Answer 2

En la criptografía informática moderna, los números grandes son uno de los factores más importantes. Por eso el cifrado de 40 bits se consideraba seguridad en 1995, pero hoy (con el cifrado de 512 bits disponible en casi cualquier dispositivo de seguridad) se consideraría una broma.

Mi lectura de la historia del descifrado de Enigma es que los fallos en el uso y la aplicación de Enigma por parte de los alemanes, combinados con una eficaz recopilación de información, fueron los factores más críticos para que los descifradores tuvieran éxito. El algoritmo en sí no tenía mucho que ver, simplemente tenía un gran número de combinaciones.

Como el cubo de Rubik. Es sólo un grupo finito no abeliano, pero es el enorme orden de ese grupo lo que hace que no se pueda simplemente escribir toda la tabla de Cayley y encontrar el número mínimo de operaciones para una solución a partir de ahí.

La razón por la que se construyeron las grandes "bombas" en el cracking de Enigma fue para acelerar el proceso, porque había muchas combinaciones posibles. Lo que nos lleva de nuevo a la criptografía informática moderna, en la que la potencia de cálculo disponible determina el tiempo que se tardaría en descifrar por fuerza bruta una clave de un tamaño determinado, por lo que es fundamental utilizar la clave más larga posible.

Esta cita de Marian Rejewski, uno de los codificadores polacos que trabajó en Enigma, dice básicamente (para mí): "los alemanes aumentaron el número de combinaciones, lo que hace nuestro trabajo mucho más difícil":

Encontramos rápidamente los [cableados] dentro de los [nuevos rotores], pero [su] introducción [...] elevó el número de secuencias posibles de tambores de 6 a 60 [...] y, por lo tanto, también multiplicó por diez el trabajo de encontrar las llaves. Así pues, el cambio fue no cualitativo sino cuantitativo . Habríamos tenido que aumentar notablemente el personal para manejar las bombas, para producir las hojas perforadas (ahora se necesitaban 60 series de 26 hojas cada una, mientras que hasta la reunión del 25 de julio de 1939 sólo teníamos listas dos de esas series) y para manipular las hojas.

(énfasis mío)

Answer 3

La respuesta a la pregunta "Matemáticamente, ¿por qué fue tan fácil descifrar la máquina Enigma?":

El primer punto débil importante fue el hecho de que se utilizó la misma configuración durante todo un día. Siempre hay mensajes que son más fáciles de descifrar y otros más difíciles de descifrar; el uso de la misma configuración durante un día significaba que sólo había que descifrar un mensaje excepcionalmente fácil de descifrar (y probablemente muy poco importante) para descifrar todos los mensajes de un día.

El segundo punto débil importante era el hecho de que, en cada estado, la máquina Enigma producía una permutación Enigma (13 ciclos de longitud 2), lo que la hacía accesible a los ataques matemáticos.

El tercer punto débil importante era el hecho de que el enorme número de configuraciones posibles podía separarse en problemas separados y más fáciles. Era posible descifrar primero las configuraciones del rotor y luego las del tablero por separado. (El mismo error se cometió en el cifrado de DVD, donde un código de 40 bits podía separarse en un código de 25 bits y otro de 16 bits que podían descifrarse por separado).

Answer 4

En cada estado posible, una máquina Enigma produce una permutación de las letras de la A a la Z. Y no cualquier permutación, sino una que intercambia pares de letras, por ejemplo, en un determinado escenario podría intercambiar la A y la Q, la B y la F, la C y la R y así sucesivamente. Una permutación de este tipo, que consiste enteramente en ciclos de longitud 2, se llama "Permutación Enigma".

Después de transmitir una letra, el estado de la máquina cambiaba de forma determinista, por lo que se utilizaba una permutación Enigma diferente. Es importante destacar que se puede suponer que un descifrador de códigos conoce todos los mensajes encriptados, porque se acaban de enviar por radio.

El teorema de Rejewski dice: "El compuesto de dos permutaciones Enigma cualesquiera consiste en ciclos disjuntos en pares de longitudes iguales". Como la longitud total de los ciclos es 26, se pueden tener, por ejemplo, dos ciclos de longitud 1, dos ciclos de longitud 5 y dos ciclos de longitud 7. Otro teorema bastante sencillo dice que una permutación M y una permutación S M S^-1 tienen las mismas características de ciclo.

Durante los primeros años, cada transmisión comenzaba poniendo la máquina en un estado inicial fijo (conocido por el emisor y el receptor, pero no por el descifrador de códigos), luego el emisor elegía un código de tres letras al azar y lo transmitía dos veces, luego el emisor y el receptor utilizaban ese código de tres letras para cambiar la configuración de la máquina. Después, cada mensaje se enviaba con una configuración diferente de la máquina.

Todas las máquinas enviaron las seis primeras letras con las mismas permutaciones P1, P2, P3, P4, P5, P6. Si el emisor transmitió ABC, y el receptor recibe RST XYZ, entonces la permutación P1 intercambia A y R, P4 intercambia A y X. El cracker conoce R y X, pero no A. Pero el cracker sabe que la permutación P1 P4 mapea R a X, porque P1 mapea la conocida R a una desconocida A, y P4 mapea la desconocida A a la conocida X. Si recibe suficientes mensajes, con diferentes letras aleatorias ABC, reúne suficiente información para encontrar la permutación completa P1 P4. Lo mismo para P2 P5 y P3 P6.

Ahora, cada una de estas permutaciones consiste, según el teorema de Rejewski, en ciclos de pares de longitudes iguales, cuyas longitudes suman 26 o las longitudes de una mitad de cada par suman 13. Eso da un patrón; en el ejemplo anterior el patrón sería (1, 5, 7). Y este patrón sólo depende de la configuración inicial del rotor, es independiente del tablero de conexiones (el segundo de los dos teoremas mencionados).

Con los 3 rotores iniciales que podían instalarse en 3! = 6 órdenes, y 26 x 26 x 26 rotaciones iniciales del rotor, había 105.456 configuraciones iniciales posibles, cada una de las cuales produciría 3 patrones para las permutaciones P1P4, P2P5 y P3P6.

Lo que hicieron los matemáticos polacos fue crear un índice: Para cada una de las 105.456 posiciones iniciales que encontraron durante meses trabajan los 3 patrones asociados a cada posición. Y con eso fue fácil encontrar las configuraciones iniciales del rotor para un día después de interceptar unos 100 mensajes. No todas las configuraciones crearon patrones únicos, pero normalmente un patrón sería producido por una o muy pocas configuraciones iniciales. Algunas configuraciones del rotor son malas noticias; por ejemplo, hay 313 configuraciones del rotor que producen tres pares de ciclos de longitud 13.

También se podría descubrir la configuración del tablero de conexiones: Conociendo los ajustes iniciales del rotor, podemos determinar la permutación P1' P4' que se habría producido sin el tablero de enchufe. También tenemos la permutación P1 P4 que se produjo con el plugboard. Estos pueden ser comparados, y tenemos la misma información para P2' P5' contra P2 P5 y P3' P6' contra P3 P6. Esto suele ser suficiente para determinar la configuración del tablero.

Al principio, los polacos podían descifrar los mensajes a mano. Esto dejó de funcionar cuando cambió el método de transmisión (no se transmitían 3 letras dos veces) y cuando se sustituyeron 3 rotores por 5, con 60 posibles opciones de rotores.

Los métodos posteriores se basaban sustancialmente en adivinar mensajes o partes de mensajes. Dado que se utilizaba la misma configuración inicial durante todo un día, si se descifraba un solo mensaje, se descifraban todos los mensajes del día (si no, todos los mensajes del día eran ilegibles). Una buena fuente de mensajes que se podían adivinar eran los informes meteorológicos: Como no eran muy secretos, se transmitían a través del país con un código fácilmente descifrable, por lo que se podían recuperar los informes meteorológicos exactos. Los mismos mensajes exactos se enviaban a los submarinos con el código enigma, por lo que era una buena fuente para conocer los textos de los mensajes.

Más tarde se introdujo un cuarto rotor para los mensajes de alto secreto. Eso habría sido indescifrable en su momento. Excepto que los ajustes de las máquinas de cuatro rotores eran los mismos que los de tres rotores, con otro anillo en 26 posiciones posibles. Así que después de descifrar el código de tres rotores, sólo se necesitaron 26 intentos para descifrar la máquina de cuatro rotores.

Answer 5

Las otras respuestas dan una idea de las técnicas implicadas, pero quiero insistir en una observación muy profunda y confusa del campo del criptoanálisis:

La aplicación iterativa de operaciones muy simples (reversibles) suele ser muy difícil de descifrar.

En esencia, esto significa que se puede tomar una sola operación, por ejemplo

$$x_{n+1}\mapsto a\cdot x_{n}+b \mod k$$

y puede ser muy difícil de encontrar $x_0$ dado $x_{10000}$ si, digamos, $a$ y $b$ son desconocidos. Pero esto es cierto para casi todas las operaciones que se puedan imaginar ( $\mathrm{xor}$ , la cuadratura, las potencias $\mathrm{mod}\ k$ etc.) Véase, por ejemplo, el Algoritmo Blum Blum Shub o Cifras en bloque en general.

El hecho es que funciones unidireccionales o funciones $f$ que son difíciles de invertir, son realmente fáciles de conseguir. Irónicamente, en realidad no sabemos cómo probar que estas funciones son difíciles de invertir, pero son difíciles en la práctica .

Ahora no me malinterpretes: si escribes lo que parece ser un algoritmo criptográfico de clave simétrica válido, lo más probable es que seas vulnerable a algunos ataque que reduce la búsqueda por fuerza bruta en algún orden de magnitud, por lo que idear buenos cripto-sistemas se deja en manos de los expertos. Pero estos ataques no suelen ser teóricamente mejor que la fuerza bruta, en el sentido de que todavía tienen que enumerar algún conjunto (exponencial) de claves (pero quizás mucho menos que el conjunto original de claves secretas).

Así que, en cierto sentido, no es de extrañar que los creadores de Enigma idearan una máquina difícil de descifrar: tomaron esta plantilla básica de aplicaciones repetidas de una transformación relativamente fácil. Lo que sí es sorprendente es que a pesar de esta dificultad inherente, los criptoanalistas polacos e ingleses idearon formas fiables de descifrar este sistema.