February 01, 1998
The Secret Story of Nonsecret EncryptionBruce Schneier
GCHQ, the British equivalent of the U.S. NSA, released a document on December 17, 1997, claiming to have invented public-key cryptography several years before it was discovered by the research community. According to the paper, GCHQ discovered both RSA and Diffie-Hellman, then kept their discoveries secret.
Bruce is a DDJ contributing editor, president of Counterpane Systems, a consulting firm specializing in cryptography and computer security, and the designer of the Blowfish algorithm. He is the author of Applied Cryptography (John Wiley & Sons, 1994 & 1996), and can be reached at schneier@counterpane.com.
GCHQ, the British equivalent of the U.S. NSA, released a document on December 17, 1997, claiming to have invented public-key cryptography several years before it was discovered by the research community. 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 receiver-the receiver does all the work. (This is essentially what echo-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 U.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 cryptographic 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 public-key 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 signatures. 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 their superiors. 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 non-secret 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 public-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 by 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 first 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.
This op/ed was published in the News and Views section of the April 1998 issue of Dr. Dobb's Journal.
Related web sites
These op/eds do not necessarily reflect the opinions of the author's employer or of Dr. Dobb's Journal. If you have comments, questions, or would like to contribute your own opinions, please contact us at
|
 |
|||||||||||||||||
|
|
|
more
