Desclasificada una «profética» carta sobre criptografía de John Nash a la NSA

La National Secutiry Agency (NSA) de Estados Unidos ha desclasificado una carta que les envió John Nash (sí, el matemático Premio Nobel de Economía en 1994 en cuya vida se basa la película Una mente maravillosa) de la que se desprende que Nash fue un adelantado a su tiempo en lo que se refiere a la criptografía, anticipándose en algunos aspectos en un par de décadas a las ideas que terminaron imponiéndose en este campo.

En la carta (bueno, en realidad las cartas, porque hay más de una), que puede descargarse en pdf en este enlace, Nash comenta que ha enviado a la NSA una máquina de cifrado de su propia invención y realiza lo que él llama «algunas observaciones» sobre un relevante principio de cifrado general, y particularmente sobre su máquina, ya que piensa que en la NSA no lo están teniendo en cuenta. Textualmente:

In this letter I make some remarks on a general principle relevant to enciphering in general and to my machine in particular. This principle is quite important to me and I have some reason to believe you may not be fully aware of it.

Y a partir de ahí realiza un análisis sorprendentemente profético en el que anticipa lo que más tarde se denominó teoría de la complejidad computacional, adelantándose así a la criptografía moderna. Propone que la seguridad en la encriptación se basa en la dureza del cálculo (unos 20 años antes de que la criptografía se centrara en ello) y más adelante habla explícitamente de la distinción entre tiempo polinómico y tiempo exponencial:

Consider an enciphering process with a finite «key» operating on binary messages. […]

[…] But this does not consider how easy or difficult for the enemy to make the computation determining the key. If this computation, although possible in principle, were sufficiently long at best then the process could still be secure in a practical sense.

Quizás uno de los momentos álgidos de la carta es la conjetura sobre la seguridad de una familia de sistemas de cifrados que realiza Nash:

Now my general conjeture is as follows: For almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean key computation length increases exponentially with the length of the key, or, in other words, with the information content of the key.

Vamos, algo así como que el tiempo de cálculo de una clave crece de forma exponencial en función de la información contenida en la propia clave. Según Nash, esto supone que sería factible diseñar claves irrompibles en la práctica, aunque él mismo reconoce que no puede probar dicha conjetura.

Y muchas cosas más. Os recomiendo que le echéis un vistazo a la carta completa, ya que estáis ante un documento histórico, una prueba de que Nash fue un adelantado en criptografía que anticipó las líneas que siguió este campo un par de décadas después. Una prueba más de la grandeza de este gran matemático.

Vía Turing’s Invisible Hand y visto en @MathUpdate, cuenta de Twitter que ya estáis tardando en seguir si todavía no lo hacéis.