The Prehistory of Public Key Cryptography

In the open literature, Diffie, Hellman, and Merkle are credited with being the inventors of public key cryptography. But there is evidence that assorted intelligence agencies knew of the technique years earlier. (Some discussion of this question can be found in an online N.Y. Times article.)

The British Invention of "Non-Secret Encryption"

The British Communications -- Electronics Security Group (CESG) has recently released some papers discussing their invention of public key cryptography. It is fascinating reading. Briefly, James Ellis came up with the idea in 1970, and proved that it was theoretically possible. In 1973, Clifford Cocks invented a variant on RSA; a few months later, Malcom Williamson invented a Diffie-Hellman analog. Their inspiration, apparently, was a World War II-era paper by an unknown person at Bell Labs.

NSA's Claims

Bobby Inman, when director of NSA, claimed (without substantiation) that NSA had had public key crypto a decade earlier than Diffie and Hellman.

There is evidence to support Inman's claim. The STU-III project -- a certificate-based secure telephone system, with the associated PKI -- apparently began in the mid-70's. Certificates weren't invented in the public sector until 1978. Even without that, it is improbable that NSA would build top secret-rated phones without years of evaluation of a new math trick. (Note: I'm looking for public, citable sources on the age of the STU-III project. The earlist I've found is Whit Diffie's "The First Ten Years of Public-key Cryptography"; he gives 1983 as the starting year. But I have Heard otherwise.)

National Security Action Memorandum 160

The most fascinating thread, though, concerns the relationship of public key cryptograpy to the command and control of nuclear weapons. At the ACM Computer and Communications Security conference in 1993, Whit Diffie organized a Festcolloquium in honor of Gus Simmons, who was retiring. Gus said that he learned of public key crypto the same way many of us did, by reading Martin Gardner's column in Scientific American. Simmons was on his way to Australia to give a talk; he said he was immediately struck by the implications of this technique for nuclear weapons command and control -- his field -- so he tore up his talk and made up a new one on the plane. It seemed clear, at that point, that he had not known of the technique. (An alternative explanation, of course, is that he knew of it but couldn't speak about it until it was rediscovered. I did not get that impression at the time.)

The next speaker was Jim Frazer, who had recently retired from the upper echelons of NSA. In a talk "The Early Days in Nuclear Command and Control", he spoke of National Security Action Memorandum 160 (from June 6, 1962), "Permissive Links for Nuclear Weapons in NATO". Frazer claimed that this memo -- signed by President Kennedy and endorsing a memo from his science advisor, Jerome Weisner -- was the basis for the invention of public key cryptography by NSA. Simmons nodded in vigorous agreement.

When the conference was over, Matt Blaze called up the Kennedy Library in Cambridge, MA, and asked about getting a copy of the memo. They were extremely helpful. It was classified, but the person to whom he spoke initiated a declassification review. It turned out that what was of interest was not so much Kennedy's note as the Weisner memorandum; this, too, was classified, and actually contained some material that was still considered sensitive. But someone scrubbed it; fairly promptly, he received a sanitized copy.

This version sat around for a few years before I finally gotten around to scanning it in and putting it up on the Web. (The Kennedy Library itself has now made available a scanned copy of NSAM 160, but not the Weisner memorandum. Amusingly, for a while the library did not have a copy of NSAM 160 online. It isn't clear to me if that was a classification issue or not. I sent them my links; they promptly corrected their web site.)

An interesting question is just what the requirement is that is best satisfied by public key cryptography. The obvious function -- arming the weapons -- can be satisfied with conventional cryptography. But I think there's more.

Weisner's memorandum says that "this equipment ... would certainly deter unauthorized use by military forces holding the weapons during periods of high tension or military combat". In other words, non-repudiation -- a classic use for public key cryptography -- was important; if a bomb is used, they (or their heirs, or civilization's heirs...) want to know who ordered it. Pending declassification of the rest of the memo, I suspect that this is the crucial seed that led to the invention of public key cryptography at NSA. (I should note that the quoted sentence is right in between the two largest "redacted" sections of the memorandum...)

Here is my scanned copy of NSAM 160. Matt Curtin has converted the scanned images to HTML. You can find both NSAM 160 and the Weisner memorandum on his Web page.

As a footnote, the first PALs (Permissive Action Links) deployed were 5-digit mechanical combination locks. The latest versions, the Categories D and F PALs, feature 6- or 12-digit input, and an automatic "limited try" feature which disables the warhead after too many incorrect tries. But I haven't yet found anything about setting C.R.M.-114 discriminators to "FGD 135", let alone "OPE"...


smb home

02 Sep 09