Una mente maravillosa llamada Nash pre-descubrió partes de la teoría de complejidad computacional y sus aplicaciones a la criptografía dos décadas antes de su re-descubrimiento posterior.

Curiosa noticia para todos los interesados en la teoría de complejidad computacional y en la criptografía (tema este último que a mi no me ha interesado, al menos hasta hoy).

La NSA (Agencia Nacional de Seguridad de EEUU) desclasificó a finales del mes pasado la correspondencia con ellos de J.F. Nash el famoso matemático cuya biografía dió pie a la oscarizada película Una mente maravillosa. El objeto de la correspondencia es un sistema criptográfico diseñado por Nash. La correspondencia consta de 3 cartas manuscritas que describo a continuación.

1. Primera carta. Sobre papel del MIT, sin fecha y manuscrita. Numerada a mano, de seis páginas. Por la respuesta del la NSA sabemos que fúe recibida por ellos en enero de 1955, es decir en torno a un año antes que la otra famosa carta de Gödel a Von Neumann sobre  el mismo tema. En esta carta  que J. F. Nash envia a la NSA   se adelanta 20 años en la descripción y aplicación de conjeturas  de complejidad computacional a la criptografía.

 En la carta establece la distinción entre problemas finitos resolubles en tiempo polinómico y problemas finitos resolubles en exponencial en el peor caso (base de la teoría de complejidad computacional) y partiendo de esta distinción expresa una conjetura de criptografía (básicamente que hay funciones de cifrado que tienen un tiempo necesariamente exponencial de descifrado para quien no conozca la clave, base de la criptografía contemporánea) que piensa que será muy díficil, sino imposible, de demostrar (se sigue pensando lo mismo, aunque hoy hay investigadores mucho más optimistas sobre esto: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm). En fin, que realmente casi sólo le faltó hablar de los conceptos de reducción entre problemas (concepto que se origina  en la Lógica) y de clase  completa para “fundar” la teoría de complejidad computacional casi en su totalidad.

2. Segunda carta. Sobre papel del MIT, sin fecha y manuscrita también. De dos páginas sin numerar. Ante la notificación por parte de la NSA de que no han recibido su criptosistema,  Nash informa a NSA (Major Grosjean) de que se lo ha enviado vía la Rand Corporation (corporación con la que colaboraba). Les informa que ha discutido su conjetura exponencial descrita en la carta anterior con R.C Blanchfield y A.M. Gleason, personal interno de la NSA y con un tal Prof Huffman que al parecer había estado trabajando en un sistema de parecidas características y consultor de la NSA.  Además se justifica diciendo que no es un cuadra-círculos. Esto hoy puede chocar, pero se debe aclarar que aunque por estas fechas ya había publicado sus famosos trabajos sobre teoría de juegos que datan de entre 1950 y 1954, e incluso su primer teorema de inmersiones de variedades de Riemann, hasta 1994 no recibiría el Nobel de Economía por ellos y por lo tanto sólo era conocido en un círculo muy restringido de especialistas. Esta segunda carta la reciben en la NSA el 18 de enero de 1955.

3. Tercera carta. Nash insiste y les envía la descripción de su criptosistema de nuevo  sobre papel del MIT, manuscrita en texto y gráficos, sin fechar, numerada a mano y de 5 páginas.  Según la descripción uno de los elementos de su  máquina de cifrado o criptosistema, el llamado permutador, se basa en la aplicación de pares de permutaciones  a los dígitos binarios del mensaje que se quiere cifrar.

Comenta que “the key for the enciphering machine is the choice of the (pair of) permutations“… “If there are n storage points in P (se refiere al núnmero de vertices del Digrafo de Cayley del permutador)…then there are [n! 2^(n+1)]^2 possible keys“).

La formula está más o menos clara: una string de n+1 posiciones binarias, tantas cómo vertices (circulos de memoria según la explicación de Nash),  que se pueden permutar de n! maneras (permutación 1) y de n! maneras (por la permutación 2). n! *2^(n+1)* n!*2^(n+1). Aunque en un primer momento pensé que el grafo del permutador es un digrafo de Cayley abeliano, tras un análisis más detallado he visto que no es así, salvo que Nash se equivocase en la representación. A ver si me entero en detalle de en que consiste el sistema y aclaro esto. También intentaré aclarar si el sistema incluye alguna referencia a recorridos hamiltonianos, cómo parece. Aunque todavía no tengo 100% claro el funcionamiento del permutador (y de todo el criptosistema), si que tengo más o menos claro que no tiene nada que ver ni con los digrafos de cayley ni con los recorridos hamiltonianos.

La NSA le contestó finalmente que tras examinar detenidamente su criptosistema y sus posibles usos en aplicaciones militares o de gobierno, han encontrado que los principios que implican su sistema, aunque ingeniosos, no cumplen con los requisitos de seguridad para aplicaciones oficiales.

Un funcionario de la NSA, M.A. Lyons, que revisa toda esta correspondencia en fecha posterior indeterminada, comenta que “Mr. Nash proposes a permuting cipher-text auto-key principle which has many of the desirable features of a good auto-key system; but it affords only limited security and requires a comparatively large amount of equipment“. Relevantes: http://en.wikipedia.org/wiki/Permutation_cipher y http://en.wikipedia.org/wiki/Autokey_cipher.

Un experto actual en criptografía,  Rivest, co-descubridor del famoso sistema de clave pública RSA, lo ha implementado en Python y un experto de complejidad computacional, Nisan,  se pregunta en su blog (a través del cual nos hemos enterado de todo esto) si el moderno criptoanálisis sería capaz de romperlo. Buena pregunta.

4. Finalmente señalar que es bien sabido que Nash era un matemático aficionado a la economía. No quiero ni pensar de que hubiese sido capaz (todavía puede serlo por cierto), sí en vez de aficionarse al campo de  la economía cerrada se hubiese aficionado al campo de la economía abierta, es decir de la economía, comercio y negocios internacionales, mucho más complicados que  en condiciones cerradas, tanto en la teoría cómo en la práctica. Nota: Este último comentario se incluye más  que nada para enlazar el  contenido de este post con los cuatro anteriores…

Nacho R.A.

Enlace: http://courses.csail.mit.edu/6.857/2012/files/H03-Cryptosystem-proposed-by-Nash.pdf


Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: