The Secret Story of Nonsecret Encryption
GCHQ, the British equivalent of the U.S. NSA, released a document on December 1 1997, claiming to have invented publickey cryptography several years before it was discovered by the research community (http://www.cesg.gov.uk/ellisint.htm). According to the paper, GCHQ discovered both RSA and Diffie-Hellman, then kept their discoveries secret.
James Ellis the author of the paper (who died a few days before the paper’s release), wrote that he was inspired by an unknown Bell Telephone labs researcher during World War II. This researcher had the idea that a receiver could inject noise onto a communications circuit and effectively drown out any signal. An eavesdropper would only hear the noise, but the receiver could subtract the noise and recover the signal. The interesting idea here is that the sender doesn’t have to know any encryption “key” to send a secret message to the receiverthe receiver does all the work. (This is essentially what ech(>cancelling modems do; they scream at each other along the same line, and subtract out their own signal when they listen for the other.) This was promptly classified by the Li.S. government.
Fast forward to.the U.K. in 1960. Intrigued by this idea, James Ellis wrote a classified paper providing an existence proof of “nonsecret encryption.” It’s a thoroughly impractical scheme, with large tables and other precomputer crypto,graphic ideas, but there it was.
In 1973, C.C. Cocks (another British spook) published a classified paper where he described what was essentially RSA. And in 1974, M. J. Williamson invented another classified algorithm, remarkably similar to Diffie-Hellman.
Experts believe that the GCHQ claims are valid, and that the mathematics of publickey cryptography were discovered within the intelligence community several years before they were discovered by academic cryptographers. But while they may have discovered the mathematics, it is clear that they never understood its significance.
Public-key cryptography is not used to encrypt data directly. It is used for key exchange, key distribution, and digital sig natures. Its primary benefit is that it allows people who have no preexisting security arrangement to exchange messages securely, or for. a sender to authenticate a message to a random receiver.
The military world is a fixed hierarchy. Key distribution works through the chain of command, and units trust theirsuperiors. Soldiers don’t need to communicate with people they don’t have preexisting arrangements with: those people are either civilians or the enemy. The problems that are immediately obvious to someone trying to secure the nutty world of business and personal communications just didn’t occur to those trying to secure a military.
So the British didn’t envision their nonsecret encryption as a solution to the key management problem, and the notion of digital signatures didn’t occur to them. It took Ralph Merkle, Martin Hellman, and Whitfield Diffie to invent puli)c-key cryptography, and Ron Rivest, Adi Shamir, and Len Adelman to invent RSA. (The British claim they did not invent knapsack encryption) or the El Gamal algorithm before it was published in the academic community.)
This announcement hy GCHQ doesn’t mean we’re going to start calling RSA “Cocks” and Diffie-Hellman “Williamson,” but it is an interesting footnote to the history of modern cryptography. And we still don’t know if the NSA developed public-key cryptography before learning about it from the British or the press, as they have sometimes claimed. But we do know that the Fast military device that used public-key cryptography, the STU-III, was not built until the 1980s, long after the academic community expounded on the technology.
Categories: Computer and Information Security