John Nash's Letter to the NSA

It seems he considered how a handwritten letter might be perceived.

In all seriousness, this pdf basically unreadable. It would be nice if there was a readable version available to the general public. If there is one, please let me know because this is very interesting.

So I wrote an Enigma Machine simulator for it [1] which used BASE64 to encrypt (or decrypt) messages. And in the process of doing research for that article I discovered the patent for the 'rotor' used in enigma [2] which was filed in Oct 10th, 1944 but didn't issue until Oct 12th, 1976! Talk about your submarine patent! But the other interesting thing about 1976 is that the DES encryption standard was announced in November of that year.

I don't doubt for a minute that Nash's work was influential on the thinking at least of the development of that standard.

[1] http://www.javaworld.com/javaworld/jw-08-1998/jw-08-indepth....

[2] http://www.google.com/patents/US3984922

I have to admit, I'm reading Rivest's source code and I don't completely grok the encryption scheme yet, but it seems to me that it works like this. Here's the problem: you've got this very pretty conjecture which says "give me just 26 cards, there are about 2^88 permutations of them, and choosing one at random produces a much larger set of possibilities than we could guess in the forseeable future with brute-force techniques." He then provide a cipher which takes a shuffled deck and 26 spots in memory, and uses the red half and the black half to provide a random pathway for the bits through this network, since at each step there is an incoming bit which tells which way you shuffle. (And I gather that also some of the cards may basically be flipped upside down when storing the key, which means "flip the bit as you transmit it.")

It's perfectly valid as an observation, and a nice conjecture, although I'm a little bit concerned in many ways about the design, since it still seems like it only has 2^26 state leaked pretty straightforwardly one bit at a time from two different locations. But maybe he's correct.

Still there's something technologically missing. This is a very simple algorithm for modern computers with their array lookups, and I suppose the military had all the budget they needed to build large machines which can actually push around these bits, but that sort of mixing network would have been really difficult to implement mechanically. In a world where computers were too expensive to distribute to every ship's captain, I could see the NSA being much less interested in this sort of physically pushing bits around a complicated network via pathways that won't be known until run-time.

[1] http://courses.csail.mit.edu/6.857/2012/files/H03-Cryptosyst...

[2] http://en.wikipedia.org/wiki/Stream_cipher

But they also could have shelved it for years until someone had a use for it, the same as Hedy Lamarr's frequency hopping patent. (Granted, they probably modified it slightly so they didn't have to give him any credit)

But maybe there's a bunch of documents that are still secret.