William Thomas Tutte (14 de mayo de 1917 - 2 de mayo de 2002) fue un descifrador de códigos y matemático inglés y canadiense. Durante la Segunda Guerra Mundial, hizo un avance brillante y fundamental en el criptoanálisis del cifrado de Lorenz, un importante sistema de encriptación de la Alemania nazi que se utilizó para comunicaciones de alto secreto dentro del Alto Mando de la Wehrmacht. La naturaleza estratégica de la información de alto nivel obtenida a partir del avance crucial de Tutte, específicamente en el descifrado masivo de los mensajes codificados con el sistema de Lorenz, contribuyó en gran medida, y quizás incluso de manera decisiva, a la derrota de la Alemania nazi. También obtuvo resultados matemáticos significativos, incluido el trabajo de base en los campos de la teoría de grafos y la de matroides.
La investigación de Tutte en el campo de la teoría de grafos demostró ser de notable importancia. En un momento en que esta disciplina era todavía un tema incipiente, comenzó el estudio de los matroides y los convirtió en una teoría ampliando el trabajo que Hassler Whitney había desarrollado por primera vez a mediados de la década de 1930. Aunque las contribuciones de Tutte han influido en la teoría de grafos moderna y muchos de sus teoremas se han utilizado para seguir avanzando en el campo, la mayor parte de su terminología no estaba de acuerdo con su uso convencional y, por lo tanto, no es utilizada por los teóricos de grafos en la actualidad. "Tutte hizo avanzar la teoría de grafos a partir de un tema contenido en un único texto (el de D. Kőnig) hacia su estado actual trabajando de forma extremadamente activa".
Primeros años Tutte nació en Newmarket, en Suffolk. Era el último hijo de William John Tutte (1873-1944), jardinero, y de la ama de llaves Annie Newell (1881-1956). Ambos padres trabajaban en la propiedad de los establos de Fitzroy House, donde Tutte nació. La familia pasó algún tiempo en Buckinghamshire, el Condado de Durham y Yorkshire antes de regresar a Newmarket, donde asistió en la localidad de Cheveley a una escuela primaria regida por la Iglesia de Inglaterra. En 1927, con diez años de edad, obtuvo una beca para asistir a la Escuela secundaria para niños de Cambridge y su Condado, donde ingresó en 1928.
En 1935 ganó una beca para estudiar ciencias naturales en el Trinity College de Cambridge, donde se especializó en química y se graduó con honores de primera clase en 1938. Continuó con la química física como estudiante graduado, pero se decidió por el estudio de las matemáticas a finales de 1940. Como estudiante, junto con tres de sus amigos, se convirtió en uno de los primeros en resolver el problema de la cuadratura del cuadrado y el primero en resolver el problema sin un subrectángulo cuadrado. Juntos, los cuatro crearon el seudónimo de Blanche Descartes, bajo el que Tutte publicó ocasionalmente algunos de sus trabajos durante años.
Segunda Guerra Mundial
Poco después del estallido de la Segunda Guerra Mundial, el tutor de Tutte, Patrick Duff, lo recomendó para trabajar durante la guerra en Escuela de Códigos y Cifrados del Gobierno en Bletchley Park (BP). Fue entrevistado y enviado a un curso de capacitación en Londres antes de ir a Bletchley Park, donde se unió a la Sección de Investigación. Al principio, trabajó en el cifrado Hagelin, que estaba siendo utilizado por la Marina italiana. Esta era una máquina de cifrado de rotores que estaba disponible comercialmente, por lo que se conocía la mecánica del cifrado, y para descifrar los mensajes solo requería averiguar cómo estaba configurada la máquina.
En el verano de 1941 fue transferido para trabajar en un proyecto llamado Fish. La información de inteligencia había revelado que los alemanes llamaron a los sistemas de transmisión mediante teleimpresoras inalámbricas "Sägefisch" (pez sierra). Esto llevó a los británicos a denominar Fish al sistema de cifrado alemán. El apodo Tunny (atún) se usó para el primer sistema de enlace que no empleaba el código Morse, y posteriormente se usó para las máquinas Lorenz SZ y para las comunicaciones que cifraban.
Las comunicaciones telegráficas utilizaban el Alfabeto Telegráfico Internacional n.º 2 (ITA2) de 5 bits. No se sabía nada sobre el mecanismo de cifrado, aparte de que los mensajes estaban precedidos por un indicador de 12 letras, lo que implicaba una máquina de cifrado de rotor de 12 ruedas. El primer paso, por lo tanto, tenía que ser diagnosticar la máquina estableciendo la estructura lógica y por lo tanto su funcionamiento. Tutte desempeñó un papel fundamental en este logro, y no fue hasta poco antes de la victoria aliada en Europa en 1945 cuando Bletchley Park pudo disponer de una máquina de cifrado Tunny Lorenz. Los avances de Tutte llevaron finalmente al descifrado masivo de mensajes cifrados con el sistema Tunny entre el Alto Mando Alemán (OKW) en Berlín y sus mandos militares en toda la Europa ocupada y contribuyeron, quizás de manera decisiva, a la derrota de Alemania.
Diagnóstico de la máquina de cifrado El 31 de agosto de 1941 se enviaron dos versiones del mismo mensaje utilizando claves idénticas, lo que constituía una situación de vulnerabilidad denominada en criptografía "profundidad". Esto permitió a John Tiltman, el veterano y notablemente talentoso criptoanalista de Bletchley Park, deducir que se trataba de un cifrado de Vernam, que usa la función disyunción exclusiva (XOR) (simbolizada por "⊕"), y extraer los dos mensajes y, por lo tanto, obtener la clave de oscurecimiento. Después de un período infructuoso durante el cual los criptoanalistas de la Sección de Investigación intentaron averiguar cómo funcionaba la máquina Tunny, esta y algunas otras claves fueron entregadas a Tutte, a quien se le pidió que "viera qué podía hacer con ellas".
derecha|miniaturadeimagen|280px|La máquina de Lorenz SZ42 sin sus cubiertas (Museo de Bletchley Park)
En su curso de capacitación, a Tutte se le había enseñado la técnica del examen de Kasiski, consistente en escribir una clave en papel cuadriculado, comenzando una nueva fila después de un número definido de caracteres que se sospechaba que era la frecuencia de repetición de la clave. Si este número era correcto, las columnas de la matriz mostrarían más repeticiones de secuencias de caracteres que el azar por sí solo. Tutte sabía que los indicadores de la máquina Tunny usaban 25 letras (excluyendo la J) para 11 de las posiciones, pero solo 23 letras para la otra. Por lo tanto, probó la técnica de Kasiski en el primer impulso de los caracteres clave, utilizando una repetición de 25 × 23 = 575. No observó un gran número de repeticiones de columna con este período, pero sí observó el fenómeno en diagonal. Por lo tanto, volvió a intentarlo con 574, que mostró repeticiones en las columnas. Reconociendo que los factores primos de este número son 2, 7 y 41, lo intentó de nuevo con un período de 41 y "obtuvo un rectángulo de puntos y cruces que estaba repleto de repeticiones".
Estaba claro, sin embargo, que el primer impulso de la tecla era más complicado que el producido por una sola rueda de 41 impulsos de tecla. Tutte llamó a este componente de la clave (chi1). Supuso que había otro componente, que aplicaba una disyunción exclusiva, que no siempre cambiaba con cada nuevo carácter, y que este era el producto de una rueda que llamó (psi1). Lo mismo se aplicó para cada uno de los cinco impulsos Entonces, para un solo carácter, la clave K completa constaba de dos componentes:En Bletchley Park, los impulsos de marca se representaban con x y los impulsos de espacio con • . Por ejemplo, la letra "H" se codificaría como ••x•x. La deducción de Tutte de los componentes chi y psi fue posible por el hecho de que era más probable que los puntos fueran seguidos por puntos, y que las cruces tenían más probabilidades de ser seguidas por cruces. Esto fue producto de una debilidad en la configuración de clave alemana, que luego eliminaron. Una vez que Tutte hizo este avance, el resto de la Sección de Investigación se unió para estudiar los otros impulsos, y se estableció que las cinco ruedas chi avanzaban con cada nuevo carácter y que las cinco ruedas psi se movían juntas bajo el control de dos ruedas mu o "motor". Durante los siguientes dos meses, Tutte y otros miembros de la Sección de Investigación trabajaron en la estructura lógica completa de la máquina, con su conjunto de ruedas con levas que podrían estar en una posición (elevada) que agregaba una x al flujo de caracteres del teclado, o en la posición alternativa que se agregaba en •.
Deducir el funcionamiento de la máquina Tunny de esta manera fue un logro criptoanalítico verdaderamente notable que, en la mención del nombramiento de Tutte como Oficial de la Orden de Canadá, se describió como "una de las mayores hazañas intelectuales de la Segunda Guerra Mundial".
Método estadístico de Tutte Para descifrar un mensaje de Tunny se requería conocimiento no solo del funcionamiento lógico de la máquina, sino también de las posiciones de inicio de cada rotor para el mensaje en particular. Se estaba buscando un proceso que manipulara el texto cifrado o la clave para producir una distribución de frecuencia de caracteres que se apartara de la uniformidad que el proceso de cifrado pretendía lograr. Mientras estaba adscrito a la Sección de Investigación en julio de 1942, Alan Turing descubrió que la combinación XOR de los valores de caracteres sucesivos en un flujo de texto cifrado y clave enfatizaba cualquier desviación de una distribución uniforme. La corriente resultante (simbolizada por la letra griega "delta" Δ) se denominó diferencia porque XOR es lo mismo que la resta de módulo 2.
La razón por la que esto proporcionó una forma de acceder a Tunny fue que, aunque la distribución de frecuencia de los caracteres en el texto cifrado no podía distinguirse de un flujo aleatorio, no ocurría lo mismo con una versión del texto cifrado a partir de la cual se había extraído el elemento chi de la clave. Este fue el caso porque donde el texto sin formato contenía un carácter repetido y las ruedas psi no se habían movido, el carácter psi diferenciado () sería el carácter nulo (' / ' en Bletchley Park). Cuando se usa XOR con cualquier carácter, este carácter no tiene efecto. Los caracteres repetidos en el texto sin formato eran más frecuentes debido a las características del alemán (los pares de letras repetidas EE, TT, LL y SS son relativamente comunes), y porque los telegrafistas repetían con frecuencia los caracteres de cambio de cifras y letras,Newman c. 1944 p. 387 dado que su pérdida en un mensaje telegráfico ordinario podría dar lugar a un galimatías.
Citando el Informe General sobre Tunny:
Tutte aprovechó esta amplificación de la falta de uniformidad en los valores diferenciados y en noviembre de 1942 había hallado una forma de descubrir los puntos de partida de las ruedas de la máquina Tunny que se conoció como el "Método estadístico". La esencia de este método era encontrar la configuración inicial del componente chi de la clave probando exhaustivamente todas las posiciones de su combinación con el texto cifrado y buscando evidencia de la falta de uniformidad que reflejaba las características del texto original sin formato. in 44. Hand Statistical Methods: Setting – Statistical Methods Debido a que cualquier carácter repetido en el texto sin formato siempre generaría •, y de manera similar generaría • cada vez que las ruedas psi no se movieran, y aproximadamente la mitad de las veces cuando lo hicieran, lo que suponía alrededor del 70% en general.