John Nash's letter to the NSA from 1955
The US National Security Agency declassified the amazing letters that famous mathematician John Nash sent them in 1955.
John Nash proposed a completely revolutionary idea for those times: to use the complexity theory of calculations in cryptography. If you read the letter dated January 18, 1955, it is admirable how Nash’s analysis of computational complexity and cryptographic resistance turned out to be prophetic. It is on these principles that modern cryptography is based . The first work in this field was published only in 1975.
Scanned copies of John Nash handwritten letters
')
At one time, the authorities did not show interest in the work of the eccentric professor of mathematics. Or, which is also possible, Nash’s ideas were used secretly from him.
In his letter, John Nash develops ideas of communication theory in Claude Shannon's secret systems (1949), without mentioning it, but goes much further. He proposes to base the security of cryptosystems on computational complexity - exactly on the principle that in 1975 two decades later formed the basis of modern cryptography. Next, Nash clearly describes the difference between polynomial time and exponential time, which is the basis of the theory of computational complexity. This principle was first described in 1965 , although we are talking about it in Gödel's famous letter to von Neumann from 1956 , but not in relation to cryptography.
John Nash:
In another place, he, apparently, speaks of a one-sided function , although there were, of course, no such terms yet:
The mathematician well understands the importance of his hypothesis for practical cryptography, because the use of new methods will put an end to the eternal “game” of encrypters and code crackers.
Actually, the way it happened.
It is also interesting that John Nash speaks openly about using methods whose theoretical basis he cannot prove (P = NP). Moreover, he says directly in the letter that he “does not expect his proof,” which is unusual for a mathematician.
The 1994 Nobel Prize winner John Nash is known to the general public for the Mind Games biopic.
PS Professor of Computer Science, an American cryptographer Ronald Rivest made the Nash cryptosystem in Python .
via Turing's Invisible Hand
John Nash proposed a completely revolutionary idea for those times: to use the complexity theory of calculations in cryptography. If you read the letter dated January 18, 1955, it is admirable how Nash’s analysis of computational complexity and cryptographic resistance turned out to be prophetic. It is on these principles that modern cryptography is based . The first work in this field was published only in 1975.
Scanned copies of John Nash handwritten letters
')
At one time, the authorities did not show interest in the work of the eccentric professor of mathematics. Or, which is also possible, Nash’s ideas were used secretly from him.
In his letter, John Nash develops ideas of communication theory in Claude Shannon's secret systems (1949), without mentioning it, but goes much further. He proposes to base the security of cryptosystems on computational complexity - exactly on the principle that in 1975 two decades later formed the basis of modern cryptography. Next, Nash clearly describes the difference between polynomial time and exponential time, which is the basis of the theory of computational complexity. This principle was first described in 1965 , although we are talking about it in Gödel's famous letter to von Neumann from 1956 , but not in relation to cryptography.
John Nash:
“So a logical way to classify encryption processes will be by the way that the complexity of computing a key increases with increasing key length. It is at best exponential, and at worst, probably at least a relatively small degree of ar 2 or ar 3 , in substitution ciphers. ”
In another place, he, apparently, speaks of a one-sided function , although there were, of course, no such terms yet:
"My general hypothesis is as follows: for almost all quite complex types of encryption, especially where the instructions given by different parts of the key are valid, the complex interaction of instructions with each other in determining their effect on the final result of encryption increases the average complexity of the key calculation exponentially with a key length ".
The mathematician well understands the importance of his hypothesis for practical cryptography, because the use of new methods will put an end to the eternal “game” of encrypters and code crackers.
“The importance of this general hypothesis, assuming its truth, is easily visible. It means that it is quite possible to create ciphers that will be virtually unbreakable. As the complexity of the cipher increases, the game for breaking ciphers between skillful teams and others will become history. ”
Actually, the way it happened.
It is also interesting that John Nash speaks openly about using methods whose theoretical basis he cannot prove (P = NP). Moreover, he says directly in the letter that he “does not expect his proof,” which is unusual for a mathematician.
The 1994 Nobel Prize winner John Nash is known to the general public for the Mind Games biopic.
PS Professor of Computer Science, an American cryptographer Ronald Rivest made the Nash cryptosystem in Python .
via Turing's Invisible Hand
Source: https://habr.com/ru/post/138500/
All Articles