Slashdot Mirror
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.'"
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
If you want news from today, you have to come back tomorrow.
So you mean that he was probably tired that day and he wanted to send the letter to the NaSA instead?
Slashdot, fix the reply notifications... You won't get away with it...
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.
Think I'm making stuff up?
http://science.slashdot.org/comments.pl?sid=2659839&cid=38967079
Space Nutters are insane crackpots with a completely lunatic vision of history. How will they explain that people were already interested in computers way before Sputnik?
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.
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....
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 hear Big Daddy Cool wrote a classified letter to the WWF in 1995.
I have to say, some random person on slashdot making an incorrect statement about the benefits of the US's space program is definitely something worth being hung up on for two weeks. Please keep making these posts.
Not any more than the car industry, or aerospace, or banking. Yet I never hear anyone thanking banks for buying the first commercial mainframe systems. There was ALREADY an incredibly advanced technological base to draw from because of WWII and the Cold War.
Do you think the SAGE computer system, with its large graphics display and light pen input to control weapons systems came from aliens? Or from intelligent humans? None of this had anything to do with space
http://en.wikipedia.org/wiki/Semi_Automatic_Ground_Environment
So, please explain how we were able to build a large, graphics driven computer system before NASA even existed? Is it possible, just possible, that smart people exist, and that they are naturally drawn to tech and math and creating new things? And that there doesn't need to be more than that?
"Especially your mentioning of an integrated circuit patent from the Sputnik era with no practical or commericial application whatsoever. "
Are you on drugs? When or where did I mention any such thing? You're insane, delusional and incapable of advancing a rational thought. Go back to drooling over your space propaganda.
NASA invented Teflon! FALSE! NASA invented Velcro! FALSE! NASA invented Tang! FALSE! NASA invented the IC! FALSE! NASA invented the computer! FALSE!
NASA invented a kind of bolt only useful to a particular type of rocket! WHO GIVES A SHIT?
Lies, distortions and wishful thinking is all you space lovers have.
+1, lolwut?
GENERATION O98346: The first time you see this, copy it into your sig and remove a random number from the generation. T
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."
Yes. we think you're making stuff up -- because you are!
That comment doesn't say we have computers because of the space program, it says "The space program gave us the integrated circuit." -- not true either, but much nearer the truth. If the "space nutters" really believed the sort of incredible straw men you're propping up, there'd be a lot less of them.
At this point, while I'd like rational discussions of space programs without the "nuttery" (most of which is simply ill-informed and/or not thought out, distinct from crackpot lunacy because it can often be corrected with rational discussion), you retards are far more annoying -- for fuck's sake, they only post their rubbish in at least vaguely space-related articles.
There's a glowing radioactive strip in my arm I'm sure is pregnant with meaning; I hope this newly revealed information will allow me to decode it.
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.
Some really great and true points are made in this... but wtf?
Also... could you spend a little time and fix your damned formatting? It's a fucking pain in the ass to read, and I end up more pissed off at you than the people that I should be pissed off according to your pastings (which I am also pissed off at, and rightly so, as you point out, but shit...)
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 Demos, the '70s hackers would have happened anyways, etc...
The sheer amount of people working on computers in the '50s alone garantees this.
It's just intensly annoying to read the same lies over and over again.
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.
and of course SAGE used vacuum tubes. all down the toilet with the ICBM and the kind of systems NORAD needed for those.
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* IHL, HAND.
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?
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
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.
Don't blame me, I voted for Baltar.
Well trolled! For those playing along at home, SAGE was for spotting and intercepting bombers.
Mind the Gap
You're completely glossing over my point; how many times has the government spent millions on massive, bloated, unworkable solutions after they get handed an elegant solution? I suspect the cases are in the thousands. Thanks for being so cavalier with MY money.
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
Did he invent modern cryptography? I just skimmed the machine description but how much different is it from the Engima (built 10-20 years before 1950)?
He did get to the crux of his letter eloquently. I wonder what he would have come up with if he worked with another genius on it. Is it ironic that around this time the UK was injecting Turing with hormones?
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.
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.
~Idarubicin
The moral of the story is, if you ever develop some new scheme that will be of interest to the government, and particularly its secret agencies, send full details to anyone and everyone else.
Particularly in these times of the Western Autumn.
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.
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.
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
You obviously did your research, and...you can see clearly now. : )
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
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.
Troll?
Computer development got it's start determining ballistic trajectories, hitting the preferred target.
u.s navy vintage fire control computers
http://www.youtube.com/watch?v=_8aH-M3PzM0&lr=1
How a 1950s ballistic computer worked
http://boingboing.net/2010/05/19/how-a-1950s-ballisti.html
very simple demonstration that looks like it would be easier to use a slide rule.
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).
Your first mistake: you misunderstood 1950s formal pleasantry with insecurity.
"My best known work is in game theory." roughly translates to "I'm a well-known badass in this other field, so you'd be an idiot to ignore me."
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.
It may have been handwritten for secrecy reasons, given the national security implications Nash thought the work had. He might not have wanted to send it through the MIT typing staff. That was the era before computers and TeX, remember. ~~~~
Hmm, and totally unrelated, nobody's using Hash127 either ...
- Michael T. Babcock (Yes, I blog)
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.
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 could type--or, more generally, if academics and particularly mathematicians generally had that skill in the mid 50's.
(I don't think TeX would have been much more helpful than a standard word processor to him since there were so few equations, and typesetting them would be extremely simple. I'd use some other program like OmniGraffle to generate the diagrams.)
So... this new letter shows that Nash had what amounts to a new set of tactics for picking up girls at a bar, right?
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 defense in polite terms. That defense worked, and it wasn't ignored.
You say fear and insecurity. I say realism and politeness. He was confident in his ideas, but he knew he had not yet earned "stop everything; we just received a letter from the esteemed Dr. Nash" status with the NSA, so he offered proof that he deserved to be heard. If you think that's fear and insecurity, then you've got a thing or two to learn about approaching three letter agencies.
Before October 1, 1958, NASA was NACA, National Advisory Committee for Aeronautics.
What 1950s IC post? You loons are retarded. I linked to a slashdot post of some pants-on-head retard who thinks we only have computers and ICs because of manned space exploration. That statement was so idiotic that even OTHER people had to correct it.
"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."
Yes, SAGE came FIRST. We didn't wait for the Russians to beat us into space to develop this massive computer. Exactly. Glad we agree. Developing this system didn't require anyone to go into space at all.
"We all reap the many benefits of the space program, GPS and weather and geoscience and comm satellites to name a few."
None of which require manned space stunts, all of which is now firmly DECADES in the PAST. It's all done and over. Yet the geeks keep pushing for manned space "exploration" with religious fervor and intensity, and of course the Space Nutter lies like "we only have computers because of manned space exploration".
Clear now? Is it sinking in yet?
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
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.
Parts of Nash's dissertation was also handwritten, so I don't t think that should be any indication of a lack of thoughtfulness.
Yes, but Nash has always been ahead of his time...
Slashdot, fix the reply notifications... You won't get away with it...
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 something, but my attention span is too short tonight to determine where the mistake is, perhaps in the morning. . .
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.
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 "lately" or similar. His description of his exponential conjecture could also have used a second draft. As an example, he says "n is the maximum span of the 'memory' of the process" when in fact he (probably accidentally) put n+1 x_k's in his function, so the 'memory' would be n+1, not n.
(Just so I don't give the wrong idea, I found the letters fascinating. That I found flaws in them is not terribly important.)
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 some men), though he allowed his wife to deny it in a 60 Minutes interview. There's some discussion of the issue in the book A Beautiful Mind was based on.
While it's a bit off topic, I hope for a day where society doesn't care about a person's sexuality, and where I stop keeping a mental list of the non-heterosexual celebrities I know of. Until that day comes, thank you Anderson Cooper, Ellen Degeneres, Wanda Sykes, Alan Turing, ....
Pathetic Space Nutter.
The great thing isn't that it doesn't support it - it's that it doesn't support it so clumsily.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
I know of no company in "the car industry, or aerospace, or banking" that invented a drink like Tang.
Nach
It supports UTF-8 clumsily (if at all)??!!! I'm going to stop paying my subscription to /.
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 particular English department suggestion made me laugh out loud. How is it that adjectives became spin one-half particles? There are two distinct recent events in his sentence (the work and the discussion about the work). You suggest his presentation is weak because the cognitive Boson (recentness) wasn't recast as Fermionic when appending the -ly affix. When writing to the NSA, which is notorious for using seven levels of Fraktur script to distinguish algebraic levels, one presumes they can't keep two verb instances straight in a simple English sentence.
In high school I was given a composition exercise to write a paragraph on camera assembly. We were given the steps as a mishmash. It was an exercise in achieved logical order.
My solution: ...
The A goes into the B.
The B goes into the C.
The C goes into the D.
QED.
I varied the "goes into" part appropriately. In fact, I wrote very nice sentences. What I did not vary was beginning every sentence with "The". My English teacher was so annoyed with my stylistic uniformity he docked me severely. I could only raise my eyebrows and file his feedback in my Twilight Zone folder. We weren't given any objective function on the benefits of faux variation of form upon correct assembly, yet we were expected to engage in the art of embroidery nevertheless.
Nash made a pretty good start there. If he had received a one sentence answer (with or without confounding word repetitions) explaining that the class of LFSR ciphers (or whatever refined class is most suitable) are known to have a weak of the following nature, expressed perhaps with a supplemental equation or three, it would have been very interesting to read Nash's next response.
The next NSA response (if they were willing to engage in such a dialog) would likely have been "you're still on the right track, but the bar is higher yet".
One needs to realize that Nash is precisely the person the NSA doesn't wish to encourage to clear any bars for which they do not yet know the solution, as he was not of the right temperament to nurture in house, and not in any way predictable out-of-house.
Pedantic interjection: Oh look, I did something terrible and inconsistent with my compound adverbial prepositions in my previous sentence. Here I'm using my hyphens as instruction prefetch markers to the front-end sentence parser ("in house" hardly needs a hint as situated).
If I were in the NSA, however, I would use a regular hyphen where it appears as a prefetch hint, and a Fractur hyphen when used in a capacity that maps into the semantic parse tree. That place is packed with pedants. If you don't keep your levels straight, conversation degenerates and no ciphers are broken.
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.
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.
To have a right to do a thing is not at all the same as to be right in doing it
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.
To have a right to do a thing is not at all the same as to be right in doing it
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 merit him further time, rather than him being unsuitable for being in-or-out-of-house with the NSA.
Another comment talked about people with self-diagnosed Aspergergers sysndrome.
It appears I have it as I write software for a living and like listening to techno which is HIGHLY repetitive music (even if FABULOUSLY composed/performed).
Anyway the post mention John Nash and Richard Feynman -- an introvert and an extrovert who were both geniuses but had two diametrically opposed 'methods' for interacting with other people.
In my case, I pretty much have NO patience for 'socializing'. I see it pretty much as a waste of time...like push-based advertising.
Just give me specs and $$$ so I can churn out the code you want, thank you very much, full stop!
Interacting with other people in this manner makes me a 'black box' which I don't mind.
Until that day comes, thank you Anderson Cooper, Ellen Degeneres, Wanda Sykes, Alan Turing, ....
Niel Patrick Harris
I've made a full transcript of the declassified PDF: http://www.gwern.net/docs/1955-nash