X-RDate: Mon, 22 Dec 1997 09:47:34 +0500 (ESK)
Date: Fri, 19 Dec 1997 09:43:38 +1100 (EST)
From: "<Con Zymaris" <conz@cyber.com.au>
To: best-of-security@cyber.com.au
Subject: BoS: Brits Invented Key Encryption Method, Paper Says
Brits Invented Key Encryption Method, Paper Says
(12/18/97; 5:10 p.m. EST)
By Douglas Hayward, TechWeb <Picture>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 lets large volumes of encrypted material be sent
cheaply and efficiently, using 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, a manager at 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.
