Going to War over Prime Numbers
Revelations from the secret world of spying raise academic questions for both
history and mathematics
Duncan Campbell
Twenty five years ago, saving the world from a nuclear
holocaust might have depended on the ability or inability of mathematicians to
factorise the products of very large prime numbers. But the fundamental theories
needed, although secretly discovered by and known to mathematicians inside
intelligence organisations at the time, were just not available even to
bomb-makers. The world was less secure as a result.
Soon afterwards, academic mathematicians made the same
discoveries on parallel timescales, publishing them and in some cases
registering valuable patent rights. Within the decade following, the methods
published openly by the academic community had been used extensively by nuclear
weapons engineers to install "permissive action links" to keep control of
weapons stockpiles, and to reliably verify arms control treaties.
International commerce as well as military security now stands
(or falls) on the same mathematical methods. By early next century, the safety
of tens of billions of pounds worth of international trade will depend on the
same systems and on a clutch of propositions in number theory.
The astonishing similarity of timescale and techniques which
evolved during the 1970s within the secret and open worlds of mathematics
highlights a fundamental and longstanding debate about "secret" scientific
research. The questions are whether advances are made more quickly, better
understood and utilised, or of greater public benefit if they are achieved in
secret or in academia.
Next week in London the (open) inventor of public key
cryptography, Dr Whitfield Diffie, a "distinguished engineer" with Sun
Microsystems, California, will be lecturing to the British Society for the
History of Mathematics at University College, London. He will compare his own
open invention of "public key cryptography" in 1976 with a recent claim that
British government cryptographers discovered the same idea six years
earlier.
Diffie and colleague Martin Hellman first published the idea in
a landmark paper, "New directions in cryptography" in November 1976. Over the
next two years, a second group of mathematicians - Rivest, Shamir and Adelman
(RSA) - published the first practical technique for implementing public key
cryptography.
These inventions began a revolution in applied mathematics and
communications engineering. It made routine communication encryption practical
and potentially ubiquitous. It solved the deepest problem faced by all previous
methods - how to establish a secure channel for sending keys, before any
messages were sent. It also provided for "authentication" - a digital method
whereby a message can mathematically be proven to have come from only one
possible sender. The applications of "digital signatures" derived from these
discoveries can embody an authority to launch nuclear attack just as easily as
they can validate an Internet order for a case of wine So did mathematicians
working secretly inside intelligence agencies actually beat Diffie, Rivest and
their colleagues?
In 1997, with no prior warning, Britain's long-time secret
signals intelligence agency GCHQ (Government Communications Headquarters)
emerged from the shadows and claimed that its staff had invented the idea in the
late 1960s. On 16 December 1997, they published (on the Internet) the first of a
series of 6 papers written between 1970 and 1987 which, if authentic and
complete, showed an astonishing "parallelism" of scientific and mathematical
research between the academic community and the closed, ultra secretive world of
"Sigint".**
British mathematicians James Ellis, Cliff Cocks and Malcolm
Williamson were all employees of the government Communications-Electronic
Security group, whose primary job as part of GCHQ was to provide secure codes
for the British government and armed forces. Although there were differences of
approach and of emphasis, the GCHQ papers together essentially lay claim to the
first invention both of the public key idea and of its "RSA" implementation. The
most obvious difference was the title the different groups gave their work,
which Ellis and co-workers called "Non Secret Encryption".
Dr Diffie will say next week that he accepts the claim to
parallel invention of his own discovery. He was first alerted to the issue in
the early 1980s after hearing remarks by the director of GCHQ's American
counterpart, the National Security Agency. NSA director Admiral Bobby Inman had
claimed in a speech that NSA had discovered public-key methods "in the early
seventies", but had then classified the method and locked it away from view.
Admiral Inman's claims have never been verified or
substantiated. And it would be even more remarkable if a third group of NSA
staff had come up with the same idea on the same timescale as both Diffie and
Ellis. But given the wholesale co-operation that exists between GCHQ and NSA, it
is likely that British ideas were shared with US colleagues. Both organisations
circulate highly classified technical journals to their staff, so as to allow
their large teams of mathematicians, engineers, linguists and scientists to
share ideas within the closed community in which they work. Inman may have been
incompletely briefed.
According to Dr Judith Field, who chairs the British Society
for the History of Mathematics, there are many unsatisfactory aspects to the
claims now being advanced that Ellis and his team was secretly ahead of academic
work. The papers CESG have published are incomplete. They give no indication as
to where they were originally published, or to whom. CESG claims that they are
"internal technical papers" which apart from converting to HTML format (for the
internet) "have not otherwise been edited". But CESG has so far been unwilling
to provide copies of the papers as originally published, leaving themselves open
to allegations that the electronic versions found only on their World Wide Web
site may have been altered.
This is "thoroughly unsatisfactory" from an historical point of
view, says Dr Field. Authentic documents are needed to make sure that their
terms, dates and presentation have not been "improved" or adjusted.
Nevertheless, leading cryptographers like Dr Diffie have long been aware of some
of Ellis's work and accept that his claim is in substance likely to be correct.
But the careful selection of papers made by CESG obscures many
fundamental issues. Most critically, why was the CESG discovery never exploited
but left to stagnate? Although CESG now makes - and even sells - an e-mail
cryptographic systems based on public keys called "Cloud Cover", this owes
nothing to the pioneering advances which it now claims were its own.
As soon as the idea of digital signatures appeared in the open
literature, weapons designers realised that it could provide a method of
verifying arms control treaties, using "black boxes" installed at test sites.
According to one of the top US verification systems designers, the first he
heard of the idea was when he read about it in Scientific American - at
the same time as everyone else. He started work immediately. By 1986, the RSA
algorithm was inside US "black boxes" buried around the Soviet Kazakhstan test
site, helping lead to the end of the Cold War.
According to Bruce Schneier, a leading open cryptographer, "the
Ellis case is a useful tool to examine the interplay between the idea of a
"secret" mathematics inside the walls of the spooks, and the open maths outside.
I have heard many anecdotes about how the walls seem to have had to been
breached, both ways, as key ideas in number theory moved forward on one side on
the other. The Ellis/Diffie case becomes a special case with a highly applied
and relevant result".
Schneier asks "If the British found public-key encryption in
the late 1960s sixties, as well as essentially the RSA algorithm a few years
later, the question arises - did they keep it to themselves, perhaps delaying
the end of the Cold War?"
Part of the answer may lie in the limited material CESG has now
published. They attribute the first discovery to Ellis in January 1970. His
paper identifies a major principle of public key cryptography, the use of
so-called "one way" functions. This makes encoding easy but deciphering the
message infeasible in a reasonable, finite time.
After he retired in 1987, Ellis wrote a classified review of
his early work. He explained how the basic idea had come to him "in bed one
night".
"Cryptography is a most unusual science", he observed. Most
professional scientists aim to be the first to publish their work, because it is
through dissemination that the work realises its value. In contrast, the fullest
value of cryptography is realised by minimising the information available to
potential adversaries. Thus professional cryptographers normally work in closed
communities to provide sufficient professional interaction to ensure quality
while maintaining secrecy from outsiders. Revelation of these secrets is
normally only sanctioned in the interests of historical accuracy after it has
been demonstrated clearly that no further benefit can be obtained from continued
secrecy".
"The proof of the theoretical possibility took only a few
minutes", he added. "We had an existence theorem. The unthinkable was actually
possible".
Ellis's paper was declassified and published in 1997, shortly
after he died. The papers were published partly in tribute and partly to enable
his colleague, Cliff Cocks to lay claim to have been the original inventor of
the "RSA" method.
Back in 1973 and just down from King's College Cambridge with a
first in maths, Cliff Cocks joined GCHQ in Cheltenham. By November the same
year, he had published a short paper on "non secret encryption". In essence, he
described the system that Rivest revealed to the world five years later. Then
two further CESG papers, in 1974 and 1976, foresaw the Diffie and Hellman
method. But the author of these papers, Malcolm Williamson, pointed hesitantly
to the flaws of working in a small and closed community.
"I find myself in an embarrassing position", he wrote, " as I
have come to doubt the whole theory of non-secret encryption. I have no proof
that the method is genuinely secure. This may be no more serious than the
analogous fact that there is no proof that any of our ordinary encryption
methods are genuinely secure but the fact does still worry me". He went on to
say that he needed help from "someone who knows more number theory than myself"
and that he did not sufficiently understand "computational complexity".
If that help was ever forthcoming, the evidence is still locked
away behind GCHQ's fences. An academic researcher reaching the same point could
have turned to the most accomplished colleagues anywhere in the world for
support. Williamson could not. No-one could reassure him that the idea was not
built on air.
There the CESG story ends. Within two years of Williamson's
last paper, Diffie, Rivest and colleagues had published. Fame, fortune, history
and acclaim belong to them. Even in the secret military world to which the
Cheltenham team was supposed to contribute, the idea was apparently lost until
rediscovered and published. It seems that, while Ellis and colleagues may have
discovered the mathematics, they never understood the significance of what they
had, nor had the confidence to develop it.
The proposition by the late James Ellis that "the fullest value
of cryptography is realised by minimising the information available" thus fails.
Although this was the authentic view of his secrecy-obsessed generation, the
world has moved on. The industrial importance and success of academic
cryptography is now fundamental to the open society.
[from the Times Higher Education Supplement, 22 April 1999]
quotes  
curiosities
inexplicable secrets of creation
home
contact
|