John Nash's Declassified 1955 Letter To the NSA

An anonymous reader writes "In 1955, John Nash sent an amazing letter (PDF) to the NSA in order to support an encryption design that he suggested. In it, he anticipates computational complexity theory as well as modern cryptography. He also proposes that the security of encryption can be based on computational hardness and makes the distinction between polynomial time and exponential time: 'So a logical way to classify enciphering processes is by the way in which the computation length for the computation of the key increases with increasing length of the key. This is at best exponential and at worst probably at most a relatively small power of r, ar^2 or ar^3, as in substitution ciphers.'"

Comments

Some Links to the NSA site

[Frosty Piss]

Hereâ(TM)s some linkys to the actual NSA website pages that talk about this:

http://www.nsa.gov/public_info/press_room/2012/nash_exhibit.shtml

http://www.nsa.gov/public_info/_files/nash_letters/nash_letters1.pdf

Re:This is impossible

[hcs_$reboot]

So you mean that he was probably tired that day and he wanted to send the letter to the NaSA instead?

Listening to People outside the Norm

[BoRegardless]

I think overtly creative people get to be that way partly because they are not "normal". It is their gift or mindset to be able to see, conjecture and analyze what others can not fathom.

Yet we tend to shy away from anyone who is "not normal". I am glad Mr. Nash has been able to proceed in his career in spite of his problems. I hope his story gives others with problems some inspiration.

Re:Listening to People outside the Norm

[Anonymous Coward]

"Yet we tend to shy away from anyone who is "not normal"."

I believe he was exposed to the invisible realities of evil. Don't watch the movie, read the book, read about his life experiences and about the men with "red" ties.

There is more to the disease than most know. It's a revealing of the puppets behind this reality, they must be run all the way to hell by the power of Yahweh, and they run when you take the power God offers you.

The movie glossed over the interesting elements of his life and his disease.

Open your eyes. "They Live" was not just a movie, it's a warning but laced with subtle occult references if you know where to look, one important note is found as sprayed across a wall and I won't mention it.

The "norm" is an illusion, controlled by your perception being weaned off of and continued drip of CONTROLLED MEDIA everywhere.

Neo's "follow the white rabbit" and the medium used in Jumping Jack Flash movie have a unique tie to them.

Re:Listening to People outside the Norm

[rssrss]

Mr. Nash's creativity and his illness were two different things. There are many people with the same illness that he had, which appeared to be a form of schizophrenia, who have no creative accomplishments, just delusions, illness, and death.

Mr. Nash spent many years in the grip of delusions and manias. He was, after a very long time able to achieve the ability to live with his family, interact with his community, and work on Mathematics.

That he was able to do so speaks well of both his family and his community. Most people with his illness do not. They wind up institutionalized, or, what is worse, homeless, uncared for, subject to substance abuse and other illnesses, and premature death.

Re:Listening to People outside the Norm

[Xtifr]

You forgot: self-diagnosed "Aspie" with an unearned superiority complex.

Ironically, in my experience, the majority of self-diagnosed "Aspies" seem to be perfectly normal people who chose to focus on academics to the exclusion of social skills because they didn't have what it takes to master both. Nevertheless, geeks with social skills are, in my experience, the vast majority. For every John Nash, there are dozens of Richard Feynmans. Asocial geeks tend not to realize this because, well, because they don't get out much. (And because they watch too many Hollywood movies.) :)

Re:Listening to People outside the Norm

[stevedog]

You are right in the sense he should not be "congratulated" for his illness. However, I would take caution before labeling the creativity and the illness as "true and true, but unrelated." By modern criteria, he very well may have had bipolar disorder with psychotic features (he did get diagnosed with schizophrenia, but back then so did everyone else who "acted crazy" -- delusions and psychosis fairly commonly accompany severe bipolar as we diagnose it nowadays). If so, then actually his periods of brilliance would have actually been his (already highly talented) brain building up and progressively overactivating to generate an immense sense of clarity and focus (the common description of the initial stages of mania) prior to devolving into the disorganization, delusions, and often bizarre behaviors of full mania (with or without psychosis, depending on the person).

In fact, this is exactly what makes bipolar so hard to treat -- it is basically like a drug, in that the "highs" can result in great success (and, even independent of the happiness about that success, it causes euphoria as well), but the destruction that occurs as a result of the behavior during those highs (as well as the severely depressed lows that often follow) generally end up tearing a person's world apart. Even so, the person often cannot see this and will completely refuse treatment, because (like a drug) they are basically addicted to their condition, and with the delusions of grandeur that often accompany the disorder further exaggerating (in their own mind) those periods of success... who wouldn't be?

That's why it might be worthwhile to take pause before laughing people like Charlie Sheen off the stage. 10 days after John Nash wrote this letter, once his brain had accelerated just a little bit further and beyond the boundaries of organized thought, Nash may very well have been just as "bi-winning," and merely had it manifest in a slightly different way.

Re:Listening to People outside the Norm

[nobodie]

The history of what happened is more complex. Jimmy Carter tried to relieve some of the problems with the institutions by providing government support for some less needy cases to return home or to live on their own with social workers supporting them and their families. The idea was that it was cheaper to do this than to keep them in an institution, which was true but the other part was that the institutions were not helping the mentally ill to live the best life they could. They were just warehoused because the funds for the institutions were inadequate. So, by helping them live on their own more funds were available for those who remained in the institutions, as well as relieving the crowding.

The program was somewhat successful, but never had time to get the kinks ironed out because Reagan came into office and proposed a budget, which was passed by his pocket congress, that declared that the program was a failure. The people who had been released didn't really need to be institutionalized as was obvious from the fact that they were living outside the institution, and so they could be cut off from the safety net that Carter had set up and taxpayers could reap in the billions in savings from this change.

Obviously there were little savings. Obviously this idea just left mentally ill people with no safety net and they crashed onto the street as homeless people. Obviously this was stupid. I volunteered in homeless shelters that were flooded with these people in the late eighties, it was just heartbreaking because their families had entrusted their care to the state who had dumped them on the street. The families had no clue what to do and the homeless folks, unable to collect benefits, medicine or help just spiralled into deeper insanity.

And the nazi solution (state organized murder) was more vicious?

Hand writing

[CurryCamel]

Reading Nash's letters makes me realize how much better presentation medium powerpoint is.
And also how much junk is made to sound nice, just with a nice presentation.

Re:Hand writing

[El_Muerte_TDS]

And yet his handwriting isn't as awful as Comic Sans.

(Read all of it) Nash gets form letter rejection

[measure]

After Nash invents modern cryptography, explains it quite eloquently in a few pages of hand written notes, and designs and builds an electronic machine that automatically encrypts / decrypts the messages. He is then sent form letter rejection by the government: "It has been found that cryptographic principles involved in your system, although ingenous, do not meet the necessary requirements for official application."

Re:(Read all of it) Nash gets form letter rejectio

[Hentes]

They hint that they have found a weakness in it, but for some reason they don't disclose it. It might be the case that the NSA wanted to keep it secret, just like the British did.

Re:This is impossible

[iggymanz]

maybe that 1950s IC post was by another anti-space nutter AC, you all look alike you know.

Those early mainframes didn't use integrated circuits, it took the space program's Apollo Guidance System (1963 - ) to push that.

Amusing you brought up SAGE, as ICBM are of course part of and intertwined with the story of the space age and space age technology. In fact, I'd say it was downright stupid of your and hurts your arguments terribly.

We all reap the many benefits of the space program, GPS and weather and geoscience and comm satellites to name a few.

Re:(Read all of it) Nash gets form letter rejectio

[interval1066]

Or, they simply wanted to butter him up and keep him quiet because the presiding industrial defence complex entities at the time (Westinghouse, GE, Hughes, Bell Telephone (or later, AT&T), etc.) already had inferior, but completed cryptographic solutions ready to go. How many times has the Fed been handed elegant solutions to problems only to pass them by for fixes given to them by men from the old boy's network?

Re:(Read all of it) Nash gets form letter rejectio

[iluvcapra]

You're right, I can't imagine why they'd work with a vendor with a three-decade track record of on time deliveries and at-cost wartime contracting, when an academic and known schizophrenic with no manufacturing or operational experience was available.

Re:This is impossible

[Eric S. Smith]

Amusing you brought up SAGE, as ICBM are of course part of and intertwined with the story of the space age and space age technology. In fact, I'd say it was downright stupid of your and hurts your arguments terribly.

Well trolled! For those playing along at home, SAGE was for spotting and intercepting bombers.

Communication as a form of intelligence

[johnwbyrd]

As I read the correspondence I tried to put myself in the position of Dr. Campaigne, and tried to figure out whether what Nash was saying made any sense. I confess that Nash's presentational style made me feel as though I was reading what Nash himself referred to as "a crank or circle-squarer". The core of Nash's invention is a squiggly, messy node graph of colored lines demonstrating a manually obfuscated binary function. But the importance of his communication is the importance of P vs. NP functions, which Nash communicated very very obliquely. Nash's Unabomber handwritten font didn't help him either.

I feel bad that I would have made the same mistake that Campaigne did. But I think nearly anyone would have.

Re:(Read all of it) Nash gets form letter rejectio

[FrootLoops]

Actually I was surprised by how much interest the NSA showed. Here was a young (~27) assistant professor of math writing to the government largely out of the blue. Nash himself was relatively insecure in his reputation, at least to this audience:

"I hope my handwriting, etc. do not give the impression I am just a crank or circle-squarer. My position here is Assist. Prof. of math. My best known work is in game theory (reprint sent separately)."

Even though he's insecure, he still chose to hand-write his letters sloppily with relatively poor penmanship and words crossed out. Still, the NSA dutifully corresponded with him and analyzed his machine, concluding

"[it] 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. The principle would not be used alone in its present form and suitable modification or extension is considered unlikely, unless it could be used in conjunction with other good auto-key principles."

The letters certainly don't give me the impression of someone who is serious about making a working cypher machine. He's pretty clearly just dabbling in cryptography because it's a nice mental game for him to play. That doesn't necessarily mean his ideas should be ignored, and (somewhat surprisingly) the NSA didn't ignore them.

Re:(Read all of it) Nash gets form letter rejectio

[FrootLoops]

What about the "crank or circle-squarer" bit? He was afraid of getting put in a crank file. See this article for a fascinating discussion of mathematical cranks, among them angle trisectors and circle-squarers:

"Many mathematics departments do not bother with crank work, throwing it out or putting it in a file labeled 'nuts' or 'crackpots.'"

That he was at all afraid of that outcome implies his insecurity, regardless of his work in game theory (which is of course distinct from cryptography) or his own opinion of it. By the way, Nash hadn't won any major awards by 1955 (as far as I can tell). His Nobel came in the 90's, for instance. He used MIT math department stationary, probably for convenience and also as proof that he was at least somewhat respectable. Conversely, he wasn't not respectable either; his mental problems didn't develop until around 1959. He was just afraid of getting ignored.

Feedback shift register

[Animats]

What Nash seems to be describing is a feedback shift register. This has potential as a cryptosystem, but isn't a very good one. As the NSA pointed out, it "affords only limited security".

When Nash wrote this, Friedman had already developed the theory that allowed general cryptanalysis of rotor-type machines. But that was still highly classified. Friedman, of course, was responsible for breaking the Japanese "Purple" cypher, plus many others. Before Friedman, cryptanalysis was about guessing. After Friedman, it was about number crunching.

Friedman was the head cryptanalyst at NSA at the time. Within NSA, it would have been known that a linear feedback shift register was a weak key generator. So this idea was, properly, rejected. At least NSA looked at it. Friedman's hard line on that subject was "No new encryption system is worth looking at unless it comes from someone who has already broken a very hard one."

The fact that a problem is NP-hard isn't enough to make it a good key generator. The Merkle-Hellman knapsack cryptosystem, the first public-key cryptosystem published, is based on an NP-hard problem. But, like many NP-hard problems, it's only NP-hard in the worst case. The average case is only P-hard. (Linear programming problems, and problems which can be converted to a linear programming problem, are like that.) So that public-key system was cracked.

We still don't have cryptosystems which are provably NP-hard for all cases. Factoring and elliptic curves are as good as it gets, and there's still the possibility that a breakthrough could make factoring easy.

Re:(Read all of it) Nash gets form letter rejectio

[FrootLoops]

I think we actually agree. By "insecure", I meant he was not secure in his reputation with the NSA. He seemed quite confident about the correctness and worth of the ideas he presented. I suppose he may or may not have literally felt fear about getting ignored. Perhaps it's not standard, but to me the phrase "X was afraid of Y" is an idiom that doesn't necessarily imply X feels fear. For instance, take "I'm afraid you'll have to leave" or "He's afraid the door will be locked and he'll have to go around back in the cold."

To be clear, I understand your "translation" of his "1950's politeness". It's so obvious that I didn't feel the need to explicitly agree with you. I only bring it up now since you repeated your translation in different words as if I didn't understand the first version (or the original text).

I don't know why you keep obliquely insulting me ("Your first mistake was..." [you never got to my second mistake, by the way; did you have one?]; "Wow. You really don't understand how academic politeness works?"). It's distracting.