John Nash, un criptógrafo maravilloso

El nombre de John Forbes Nash no le es conocido a mucha gente.  Pero mencionen la película Una Mente Maravillosa, que narra su vida, y verá como la cosa cambia.  Nash fue un genio de las matemáticas.  Especialmente conocidos son sus trabajos sobre la teoría de juegos, que a pesar de su nombre es un campo de estudios muy serio, ya que describe las relaciones humanas, económicas y sociales.  Si algún día alguien desarrolla las matemáticas de la psicohistoria de Asimov, hará bien en comenzar por la obra de Nash.  Precisamente por su trabajo en teoría de juegos, Nash fue galardonado con el premio Nobel de Economía en 1994.

En Una Mente Maravillosa, Nash (interpretado por Russell Crowe) trabaja para la inteligencia norteamericana.  O al menos, eso es lo que él se creía, ya que todo era un producto de su mente: Nash sufría de esquizofrenia. Lo que no sabíamos hasta ahora es que, en su momento, Nash intentó entrar en el campo de la criptografía.  Unas cartas que escribió a la Agencia de Seguridad Nacional norteamericana (NSA) han sido recientemente desclasificadas.  La propia NSA, quizá buscando publicidad, ha abierto una exhibición sobre Nash en su Museo Criptológico.

Nash escribió algunas cartas de motu propio, es decir, nadie le consultó sobre el tema.  La correspondencia data de 1955, algunos años antes de que sus problemas mentales comenzaran a manifestarse.  Aun así, la carta es, digámoslo así, algo rara.  Está escrita a mano, en papel con el membrete del Departamento de Matemáticas del MIT, y pedía que no le tomasen por un "profesor chiflado" sólo porque no estaba mecanografiada.

En principio, Nash se refiere al cifrado mediante una función matemática que dependa de r dígitos binarios y de un conjunto de bits relativos al texto llano.  En principio (afirma, subrayado) un enemigo que conozca r bits cifrados podría calcular la clave.  Eso me parece una afirmación algo atrevida, pero no seré yo quien se atreva a contradecir al genio.  Lo que afirma Nash es que, si el proceso de calcular la clave es demasiado largo, tendríamos un sistema de cifrado seguro a efectos prácticos.

Es decir, Nash está sugiriendo algo que ahora se usa en criptografía de clave pública: usar un problema matemático cuya resolución, aunque posible en la práctica, lleve demasiado tiempo.  Afirma a continuación que se podría clasificar los sistemas de cifrado en virtud de su complejidad matemática, es decir, por cómo aumenta la dificultad de recuperar la clave cuando aumentamos el tamaño de ésta.  Lo ideal sería un sistema cuya resistencia aumentara exponencialmente con la clave.  Un ejemplo podría ser el PIN de una tarjeta de crédito: poner un dígito más aumentaría en diez su resistencia frente a ataques de fuerza bruta.

Nash se atreve a afirmar que, cuando los sistemas de cifrado alcance un nive de complejidad exponencial, el criptoanálisis se convertiría en una cosa del pasado; cosa que él mismo reconoce que no puede demostrar.  Y en este punto es donde la cosa se pone interesante, ya que pasa a decir que:

Creo que la máquina de cifrado y descifrado que he inventado e hice transmitir a la N.S.A. por medio de [la corporación] RAND tiene esta propiedad de "irrompible."

Si eso es cierto, eso significa que hubo contacto previo entre la NSA y Nash, hasta el punto de que éste trabajó en una máquina de cifrado, al menos sobre el papel.  En efecto, la carta de respuesta de la NSA incluye una referencia a una interesante discusión [de algunos técnicos de la NSA] con usted hará cuatro años.  Eso era 1951, el año en que Nash escribía "Non-cooperative games" en la revista Annals of Mathematics, en la cúspide de su carrera.  Como anécdota, hay que decir que Nash incluyó una copia de ese artículo en su carta a la NSA, con objeto de que sirviera de "carta de presentación." La documentación interna de la NSA lo refleja así: El autor también incluyó un interesante panfleto sobre Juegos No-Cooperativos, escrito por el Sr. Nash, para nuestra información.

La descripción del sistema criptográfico de Nash aparece en la documentación que la NSA acaba de hacer público es, a mis ojos, un galimatías.  Eso no significa que sea un mal sistema, sino que yo no lo entiendo.  Para ser más correcto, no sé si el sistema que describe es criptográficamente resistente.  El criptoanalista Ronald Rivest (la R de RSA) recientemente publicó el algoritmo de Nash como ejercicio para sus alumnos.  Si le interesa, aquí tiene una copia en Python.  Según Rivest, es un sistema de flujo (stream cypher).  Si funciona bien, sería muy interesante, ya que es muy difícil hacer un algoritmo de cifrado en flujo que carezca de debilidades.  El propio Rivest, no obstante, advierte a sus alumnos -y a nosotros, de paso- que esta tarea es problema abierto ... ni nosotros mismos sabemos la respuesta a la pregunta.

Por supuesto, la pregunta a que se refiere es: ¿funciona el sistema de Nash?   Porque hay un problema: la NSA lo rechazó.  En una carta al autor, se le informa de que los principios criptográficos de su sistema, aunque ingeniosos, no cumplen los requisitos de seguridad necesarios para aplicaciones oficiales.  En un memorandum interno de la NSA (no enviado a Nash, por supuesto), se detalla algo más sobre el sistema de cifrado de Nash: solamente proporciona una seguridad limitada, y requiere una cantidad de equipo comparativamente grande. El principio no se usaría por sí mismo en su forma actual y se considera improbable que haya modificaciones o extensiones adecuadas, a menos que pudiera ser usado en conjunción con otros principios de auto-clave.  La referencia a auto-clave (auto-key) es un sistema mediante el cual el propio mensaje también hace de clave.

Visto lo visto, y considerando la capacidad intelectual que tenía John Nash, estoy deseando que los criptoanalistas profesionales se pongan a destripar este sistema de cifrado. Si hace casi setenta años Nash ya bosquejaba los inicios de la criptografía basada en la complejidad computacional, quién otras sorpresas nos esperan.  ¿Una mente maravillosa?  Puedes apostar a que sí.