John Nash's Declassified 1955 Letter To the NSA 93
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.'"
Some Links to the NSA site (Score:5, Interesting)
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 [nsa.gov]
http://www.nsa.gov/public_info/_files/nash_letters/nash_letters1.pdf [nsa.gov]
Re: (Score:1)
I couldn't find "Hereâ" listed in any trademark office. Can you give a reference that it is a trademarked term?
Re:This is impossible (Score:4, Funny)
Re: (Score:2)
The U.S. space program did make cause many advances in technology. Your linked stupidity and ignorance of the history of technology is amusing. Especially your mentioning of an integrated circuit patent from the Sputnik era with no practical or commericial application whatsoever. You anti-space nutters sure are a piece of work....
Re:This is impossible (Score:4, Informative)
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: (Score:2)
and of course SAGE used vacuum tubes. all down the toilet with the ICBM and the kind of systems NORAD needed for those.
Re:This is impossible (Score:4, Informative)
Well trolled! For those playing along at home, SAGE [wikipedia.org] was for spotting and intercepting bombers.
Re: (Score:2)
that's just the point, the SAGE was obsoleted in purpose by ICBMs, and in architecture by transistors. it's a silly thing to bring up to counter argument that space program did nothing for such systems
Re: (Score:2)
wrong. pro-space includes manned and unmanned space mission. Even if we confine discussion to manned space, the benefits to integrated circuits of the manned space program are used by all the unmanned space applications such as satellite.
And that vacuum tube SAGE computer is yet another thing obsoleted by discrete solid state computers, which were obsoleted by the integrated circuit based ones which had enormous benefit from manned space program, stupid of you to bring that dinosaur up.
Re: (Score:1)
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.
You're missing the point. It's the extravagant spending on manned space travel that annoys anti-space-nutters. I don't think they mind military spending on rockets that happen to go into space.
Re: (Score:1)
I know of no company in "the car industry, or aerospace, or banking" that invented a drink like Tang.
Re: (Score:1)
The technology came FIRST. Then we went to the Moon as the biggest stunt in history. But the technology came FIRST. We had computers before Apollo. If Apollo had never happened, there wouldn't be much different today, I assure you. Englebart would have made his Mother of all Dem
Re: (Score:2)
Re: (Score:1)
Nach
Re: (Score:1)
You seem mad. I see that the comment you're linking in your next post contains you ranting and whining too. Just drop it already, no one cares about your personal crusade against "space nutters".
Re: (Score:1)
You seem mad. I see that the comment you're linking in your next post contains you ranting and whining too. Just drop it already, no one cares about your personal crusade against "space nutters".
I think it's an amusing and useful antidote to the people who think that by landing a man on Mars we will magically transform science, politics and economics.
Re: (Score:2)
Actually that is incorrect, computers were used for fire control on naval ships long before that, they were mechanical analog computers, but computers nonetheless.
See this US Navy training film from 1953 http://youtu.be/_8aH-M3PzM0 [youtu.be]
The need to make them small enough and light enough to put into a spacecraft brought about some major developments, but they existed long before that.
Listening to People outside the Norm (Score:5, Insightful)
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: (Score:1)
To find clever is to lose a little sanity.
Re: (Score:2, Informative)
"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.
Op
Re: (Score:1)
Amen Brother!
Re:Listening to People outside the Norm (Score:5, Insightful)
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: (Score:2)
Being an asocial geek is about half way to passing an Aspberger's test already. Have you actually looked up the criteria lately?
Re: (Score:2)
perfectly normal people who chose to focus on academics to the exclusion of social skills
Nobody is responsible for their personal choices, especially if it's a long-term choice.
Re:Listening to People outside the Norm (Score:5, Insightful)
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: (Score:1)
...
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.
They used to wind up institutionalized. The Reagan administration undid that, so now they just wind up homeless, uncared for, subject to substance abuse and other illnesses.
Re: (Score:2)
To quibble, appropriations come from Congress, not the president. Besides, in the U.S., there is more than one level of government. If the feds drop the ball, states are welcome to pick it up.
Re: (Score:2)
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 becau
Re: (Score:2)
De-institutionalization occurred in the 1950s and 60s, by the time of the Regan administration in the 1980s, it was the norm.
Re: (Score:3, Informative)
Re: (Score:1)
Hand writing (Score:4, Funny)
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: (Score:1, Insightful)
Nash would have used Beamer, not Powerpoint.
Re: (Score:3)
And yet his handwriting isn't as awful as Comic Sans.
Re: (Score:1)
Re: (Score:1)
This just in -- not only does slashcode support only a ridiculously limited set of html entities and some subset of Latin-1 (I think -- it's some ISO-8859 flavor, anyway), it doesn't support UTF-8 at all, so why the fuck would you paste a buttload of UTF-8 into the comment form? I can see using some HTML entity you might expect to work, and not realizing it didn't (there's a preview for a reason, BTW), but that UTF-8 shit is like you're TRYING to piss us all off.
Wait... IHBT with encodings, haven't I. *sigh
Re: (Score:2)
The great thing isn't that it doesn't support it - it's that it doesn't support it so clumsily.
Re: (Score:1)
It supports UTF-8 clumsily (if at all)??!!! I'm going to stop paying my subscription to /.
(Read all of it) Nash gets form letter rejection (Score:5, Funny)
Re:(Read all of it) Nash gets form letter rejectio (Score:4, Insightful)
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 [wikipedia.org].
Re:(Read all of it) Nash gets form letter rejectio (Score:4, Insightful)
Re: (Score:3)
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: (Score:2)
Re: (Score:2)
I suspect the cases are in the thousands.
Ah, well. As long as you have hard numbers, then.
Thanks for being so cavalier with MY money.
You would, of course, be saying the exact same damn thing if the government were spending millions of dollars on elegant-sounding but ultimately impractical or unworkable solutions offered by academic geniuses with no experience in government or project management.
Re: (Score:1)
Ah, well. As long as you have hard numbers, then.
You've never heard the reports of government waste in the media? I find that difficult to believe.
You would, of course, be saying the exact same damn thing if the government were spending millions of dollars on elegant-sounding but ultimately impractical or unworkable solutions offered by academic geniuses with no experience in government or project management.
I find that many government geniuses have no experience in government or project management. Glad you seem to have gotten so lucky.
Re: (Score:2)
Hmm, and totally unrelated, nobody's using Hash127 [cr.yp.to] either ...
Re: (Score:2)
Did he invent modern cryptography?
No. His "machine" (the letters don't imply it was ever built) certainly wasn't the only one of its kind. If anything, the letters might give him some vague claim on the beginnings of computability and/or computational complexity theory, though his "exponential conjecture" isn't really developed enough to earn him much credit for either, IMO.
Is it ironic that around this time the UK was injecting Turing with hormones?
It's certainly coincidental. There are some rumors that Nash was bisexual (inasmuch as he had some sort of maybe-sexual relationship with some men, or was attracted to s
Re:(Read all of it) Nash gets form letter rejectio (Score:5, Interesting)
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: (Score:3)
What about the "crank or circle-squarer" bit? He was afraid of getting put in a crank file. See this article [mst.edu] 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 us
Re: (Score:1)
Wow. You really don't understand how academic politeness works? Yes, he was rightfully worried that his letter would be ignored, because he knew that a handwritten letter without an up-front defense would be ignored automatically.
What he wrote is simply the polite way of saying "do not mistake me for a crank; here are my credentials". The fact that he covered his bases is not evidence that he was insecure; instead, it's evidence that he understood how the letter would be received and wrote the necessary def
Re: (Score:3)
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
Re: (Score:2)
Yup, and in fact I did think of that when I wrote the post above. My main complaint was his sloppy writing style. He could certainly have done a more professional job of writing his letters by hand. Using the ones we have as drafts and copying their corrected contents carefully to new paper would have made a big difference, for instance. Of course these are minor points; I was just pleasantly surprised the NSA gave him the attention he seems to have deserved in spite of his stylistic flaws.
I wonder if he co
Re: (Score:2)
I agree that just because they were handwritten doesn't necessarily indicate a lack of thoughtfulness. He probably wanted to avoid having a secretary type them up to keep them secret. That they're sloppily handwritten does indicate a lack of thoughtfulness, though not necessarily about the key ideas: mostly, his presentation could have been better. Beyond the stylistic issues I mentioned above, there is for instance this sentence:
"Recently a conversation with Prof. Huffman here indicated that he has recently been working on a machine with similar objectives."
A more thoughtful presentation might replace the second "recently" with "latel
Re: (Score:2)
Beyond English department embroidery, there's little to fault with Nash's composition. His argument develops logically, his sentences parse correctly, he sticks to the primary points, and he's clear both about the potential significance and the nature of the mechanics involved.
This parti
Re: (Score:2)
Shortly after pressing submit, I realized that I made light of the difference between adjectives and adverbs when I first commented on the adenoidal Fermions. Like the difference between ovaries and testicles, people tend to insist upon the distinction even when it isn't terribly germane. Either type leads to adenoidal behaviour patterns.
Re: (Score:2)
Hah, that was hilarious, thank you.
While I don't quite agree with you about the quality of his exposition, I also don't see the point of discussing it further since it's such a minor issue. I will if you wish, though.
I'm not sure where "[Nash was] not in any way predictable out-of-house" came from. I'm no Nash expert, but his mental disturbances didn't start until 1959, several years after these letters were written. From the letters, the impression I got was that his ideas simply weren't advanced enough to
you believe the NSA? (Score:2)
dude, they are payed to be secretive. they are the big brother of the CIA. hell they probably used to spy on the CIA.
they probably took his theories and used them (if they didnt already have people who had come to similar conclusions working for them already).
Communication as a form of intelligence (Score:5, Interesting)
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: (Score:1)
Shit, the dude writes and doodles like me. Good thing we use computer keyboards now. Otherwise, they'd haul me away for my writing.
Re: (Score:2)
It didn't look like there was anything new in his paper to me. When he wrote it, the theory of cryptography would have been much further advanced than that, the idea that cryptographic strength can at its best go up exponentially with key length is pretty obvious.
It didn't look like he'd come up with a strong crypto system either; I suspect that the only reason anyone even looked at it was because he was a professor of mathematics and so they would have given him the benefit of the doubt, but the contents w
Feedback shift register (Score:5, Informative)
What Nash seems to be describing is a feedback shift register. [wikipedia.org] 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 [wikipedia.org] 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 [wikipedia.org], 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: (Score:2)
Infinite loop? (Score:1)
I've read the documents and i believe that i understand them but perhaps not. It appears that Nash has forgotten a + or - on one of the permutation rules. No that big of a deal as one should be able to deduce it's value from the other rules. But both values produce an infinite loop. Perhaps a mistake was made else where. It appears that the mechanics are there and are sound (insofar as its level of encryption).
It would have been fun to work through it and perhaps implement it via simple JavaScript or someth
Transcription (Score:1)