Brits Invented Key Encryption Method, Paper Says

Welcome Guest. | Log In| Register | Membership Benefits

December 18, 1997 (2:10 PM EST)

Brits Invented Key Encryption Method, Paper Says

By Douglas Hayward,

LONDON -- An academic paper published this week by an obscure branch of the British secret service has rewritten the history of modern cryptography.

The paper, published Tuesday by a retired officer of the British government's secret Communications-Electronics Security Group, said that public-key encryption was invented secretly in Britain in the late 1960s -- almost 10 years before a description of the technology was first published by pioneer cryptographers Whitfield Diffie and Martin Hellman.

Public-key encryption is one the cornerstones of secure electronic commerce. The technique uses a combination of secret and publicly known algorithms, known as public and private keys.

The technique was first described in April 1976 in a seminal academic paper delivered at a New York conference by Diffie and Hellman, who subsequently received a patent relating to the technique.

But a paper written by James Ellis, a retired cryptographer at the security agency and published Tuesday, said he invented public-key encryption. The technique was subsequently refined by Ellis and his colleagues during the early 1970s in Cold War secrecy.

Ellis died on Nov. 25, just days before his paper was published.

Diffie and Hellman independently rediscovered the technique some seven years after Ellis, according to the paper.

Ellis wrote in his paper that the idea of public-key encryption occurred to him while he was in bed one night, and the proof of the theoretical possibility took only a few minutes. "The unthinkable was actually possible," he wrote. "The only remaining question was, 'Can it be made practicable?' This took a while to answer," Ellis wrote.

Ellis circulated his idea for what he called "non-secret encryption" in a secret memo within the agency in 1970. Subsequently, he and his colleagues developed a full-fledged algorithm that closely resembles the RSA Algorithm, a patented technology developed using the Diffie-Hellman technique.

Because of the weakness of Ellis' number theory, practical implementations were left to others. The first workable idea was put forward by agency cryptographer Clifford Cocks. "This is essentially the RSA Algorithm," Ellis wrote. "The differences between the two algorithms are superficial. Cock's is a special case of RSA."

Although the discovery is controversial, it is backed by leading cryptographers. Professor Dorothy Denning, one of the leading U.S. cryptographers, said Wednesday that she believed Ellis and his colleagues were indeed the inventors of public-key encryption, rather than Diffie and Hellman.

"This does not detract from the significant contributions of Diffie and Hellman or the RSA team, who independently discovered public-key cryptography and brought it into the public domain" Denning said. "This is a case of independent discovery."

Because the agency kept its discoveries secret, it never applied for patents, so the credit and rewards for inventing public-key encryption techniques went to the Americans. "We took independent legal advice at the time and were told such a mathematical method was not patentable under U.K. law," said a spokesman for the British agency.

Still, the agency waited an extraordinary time before trumping its achievements. "There would seem to be little point in waiting an extra 10 or 15 years" following the publication of the Diffie-Hellman article, said Paul Leyland, of Oxford University's computing services department.

"Once public-key cryptography became widely understood and deployed, the Ellis document was likely to be useful only to historians" rather than Britain's foes.