Going to war over prime numbers

As the inventor of public-key encryption prepares to lecture in London, Duncan Campbell reports on revelations from the secret world of spying that raise key questions for both history and mathematics

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 not available even to bomb-makers. The world was less secure as a result.

Soon afterwards, academic mathematicians made the same discoveries independently, publishing them and in some cases registering valuable patent rights.

In the next decade, methods published by the academic community were used by nuclear weapons engineers to instal "permissive action links" to control weapons stockpiles, and to verify arms control treaties.

International commerce as well as military security now stand (or fall) on the same mathematical methods. By early next century, the safety 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 that evolved in the 1970s within the secret and open worlds of mathematics highlights a fundamental debate about "secret" research. Are advances made more quickly, better understood and utilised, or of greater public benefit if they are achieved in secret or in academia?

Next Thursday, the (open) inventor of public key cryptography, 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 open invention of public key cryptography in 1976 with a recent claim that British government cryptographers discovered the same idea six years earlier.

Dr 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. They made routine communication encryption practical and potentially ubiquitous.

It solved the deepest problem faced by previous methods - how to establish a secure channel for sending keys, before messages were sent. It also provided for "authentication" - a digital method whereby a message can mathematically be proven to have come from only one sender.

The "digital signatures" derived from these discoveries can embody an authority to launch nuclear attack or validate an internet order for a case of wine. So did mathematicians working inside intelligence agencies actually beat Diffie, Rivest and their colleagues?

In 1997, Britain's secret signals intelligence agency GCHQ (Government Communications Headquarters) claimed that its staff had invented the idea in the late 1960s. That December, it published on the internet the first of a series of six papers written between 1970 and 1987 that showed an astonishing parallelism of scientific and mathematical research between the academic community and the closed 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 government and armed forces. The papers essentially lay claim to the first invention 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 discovery. He was alerted to the issue in the early 1980s after hearing remarks by the director of GCHQ's American counterpart, the National Security Agency. Admiral Bobby Inman had claimed that NSA discovered public-key methods in the early 1970s, but had classified the method and locked it away.

Admiral Inman's claims have never been 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 Diffie and Ellis. But given the wholesale co-operation that exists between GCHQ and NSA, it is likely that British ideas were shared with American 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.

According to Judith Field, who chairs the British Society for the History of Mathematics, there are many unsatisfactory aspects to the claims that Ellis was secretly ahead of academic work.

The papers published only on the web are incomplete. CESG claims that they are "internal technical papers" that have not been edited. But CESG has been unwilling to provide original copies, leaving itself open to allegations that the electronic versions 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 such as 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 why was the CESG discovery left to stagnate? CESG now makes, and even sells, an email cryptographic system based on public keys called "Cloud Cover", but this owes nothing to the pioneering advances to which it now lays claim.

As soon as the idea of digital signatures appeared in open literature, weapons designers adopted it as a method of verifying arms control treaties.

According to one of the top United States 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 been breached, both ways, as key ideas in number theory moved forward on one side or the other. The Ellis/Diffie case becomes a special case with a highly applied and relevant result.

"If the British found public key encryption in the late 1960s, 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 published. It attributes the first discovery to Ellis in January 1970. His paper identifies a major principle of public key cryptography, the use of "one-way" functions. This makes encoding easy but unauthorised deciphering of the message unfeasible in a reasonable 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 . . . 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, Cocks joined GCHQ. By that November, 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. Two further papers, in 1974 and 1976, foresaw the Diffie and Hellman method. But the author, 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".

An academic researcher at the same point could have turned to the most accomplished colleagues anywhere in the world for support. Williamson could not.

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 its significance, nor had 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.

http://www.cesg.gov.uk/about/nsecret/main.htm