6 October 1999
Source: The Code Book, by Simon Singh, Doubleday, 1999; pp. 27992.
See related paper by James Ellis, GCHQ, "The Story of NonSecret Encryption":
http://cryptome.org/jya/ellisdoc.htm
and
http://www.cesg.gov.uk/about/nsecret.htm
See Ross Anderson question of the veracity of the GCHQ/CESG claims made here:
http://cryptome.org/ukpktrue.htm
The Alternative History of PublicKey Cryptography
Over the past twenty years, Diffie, Hellman and Merkle have become world
famous as the cryptographers who invented the concept of publickey cryptography,
while Rivest, Shamir and Adleman have been credited with developing RSA,
the most beautiful implementation of publickey cryptography. However, a
recent announcement means that the history books are having to be rewritten.
According to the British Government, publickey cryptography was originally
invented at the Government Communications Headquarters (GCHQ) in Cheltenham,
the topsecret establishment that was formed from the remnants of Bletchley
Park after the Second World War. This is a story of remarkable ingenuity,
anonymous heroes and a government coverup that endured for decades.
The story starts in the late 1960s, when the British military began to worry
about the problem of key distribution. Looking ahead to the 1970s, senior
military officials imagined a scenario in which miniaturisation of radios
and a reduction in cost meant that every soldier could be in continual radio
contact with his officer. The advantages of widespread communication would
be enormous, but communications would have to be encrypted, and the problem
of distributing keys would be insurmountable. This was an era when the only
form of cryptography was symmetric, so an individual key would have to be
securely transported to every member of the communications network. Any expansion
in communications would eventually be choked by the burden of key distribution.
At the beginning of 1969, the military asked James Ellis, one of Britain's
foremost government cryptographers, to look into ways of coping with the
keydistribution problem.
Ellis was a curious and slightly eccentric character. He proudly boasted
of travelling halfway round the world before he was even born  he was conceived
in Britain, but was born in Australia. Then, while still a baby, he returned
to London and grew up in the East End of the 1920s. At school his primary
interest was science, and he went on to study physics at Imperial College
before joining the Post Office Research Station at Dollis Hill, where Tommy
Flowers had built Colossus, the first codebreaking computer. The cryptographic
division at Dollis Hill was eventually absorbed into GCHQ and so on 1 April
1965 Ellis moved to Cheltenham to join the newly formed
CommunicationsElectronics Security Group (CESG), a special section of GCHQ
devoted to ensuring the security of British communications. Because he was
involved in issues of national security, Ellis was sworn to secrecy throughout
his career. Although his wife and family knew that he worked at GCHQ they
were unaware of his discoveries and had no idea that he was one the nation's
most distinguished codemakers.
Despite his skills as a codemaker, Ellis was never put in charge of any of
the important GCHQ research groups. He was brilliant, but he was also
unpredictable, introverted and not a natural teamworker. His colleague Richard
Walton recalled:
He was a rather quirky worker, and he didn't really fit into the daytoday
business of GCHQ. But in terms of coming up with new ideas he was quite
exceptional. You had to sort through some rubbish sometimes, but he was very
innovative and always willing to challenge the orthodoxy. We would be in
real trouble if everybody in GCHQ was like him, but we can tolerate a higher
proportion of such people than most organisations. We put up with a number
of people like him.
One of Ellis's greatest qualities was his breadth of knowledge. He read any
scientific journal he could get his hands on, and never threw anything away.
For security reasons, GCHQ employees must clear their desks each evening
and place everything in locked cabinets, which meant that Ellis's cabinets
were stuffed full with the most obscure publications imaginable. He gained
a reputation as a cryptoguru, and if other researchers found themselves with
impossible problems, they would knock on his door in the hope that his vast
knowledge and originality would provide a solution. It was probably because
of this reputation that he was asked to examine the keydistribution problem.
The cost of key distribution was already enormous, and would become the limiting
factor to any expansion in encryption. Even a reduction of 10 per cent in
the cost of key distribution would significantly cut the military's security
budget. However, instead of merely nibbling away at the problem, Ellis
immediately looked for a radical and complete solution. 'He would always
approach a problem by asking, "Is this really what we want to do?" ' says
Walton. 'James being James, one of the first things he did was to challenge
the requirement that it was necessary to share secret data, by which I mean
the key. There was no theorem that said you had to have a shared secret.
This was something that was challengeable.'
Ellis began his attack on the problem by searching through his treasure trove
of scientific papers. Many years later, he recorded the moment when he discovered
that key distribution was not an inevitable part of cryptography:
The event which changed this view was the discovery of a wartime Bell Telephone
report by an unknown author describing an ingenious idea for secure telephone
speech. It proposed that the recipient should mask the sender's speech by
adding noise to the line. He could subtract the noise afterwards since he
had added it and therefore knew what it was. The obvious practical disadvantages
of this system prevented it being actually used, but it has some interesting
characteristics. The difference between this and conventional encryption
is that in this case the recipient takes part in the encryption process .
. . So the idea was born.
Noise is the technical term for any signal that impinges on a communication.
Normally it is generated by natural phenomena, and its most irritating feature
is that it is entirely random, which means that removing noise from a message
is very difficult. If a radio system is well designed, then the level of
noise is low and the message is clearly audible, but if the noise level is
high and it swamps the message, there is no way to recover the message. Ellis
was suggesting that the receiver, Alice, deliberately create noise, which
she could measure before adding it to the communication channel that connects
her with Bob. Bob could then send a message to Alice, and if Eve tapped the
communications channel she would be unable to read the message because it
would be swamped in noise. Eve would be unable to disentangle the noise from
the message. The only person who can remove the noise and read the message
is Alice, because she is in the unique position of knowing the exact nature
of the noise, having put it there in the first place. Ellis realised that
security had been achieved without exchanging any key. The key was the noise,
and only Alice needed to know the details of the noise.
In a memorandum, Ellis detailed his thought processes: 'The next question
was the obvious one. Can this be done with ordinary encipherment? Can we
produce a secure encrypted message, readable by the authorised recipient
without any prior secret exchange of the key? This question actually occurred
to me in bed one night, and the proof of the theoretical possibility took
only a few minutes. We had an existence theorem. The unthinkable was actually
possible.' (An existence theorem shows that a particular concept is possible,
but is not concerned with the details of the concept.) In other words, until
this moment, searching for a solution to the keydistribution problem was
like looking for a needle in a haystack, with the possibility that the needle
might not even be there. However, thanks to the existence theorem, Ellis
now knew that the needle was in there somewhere.
Ellis's ideas were very similar to those of Diffie, Hellman and Merkle, except
that he was several years ahead of them. However, nobody knew of Ellis's
work because he was an employee of the British Government and therefore sworn
to secrecy. By the end of 1969, Ellis appears to have reached the same impasse
that the Stanford trio would reach in 1975. He had proved to himself that
publickey cryptography (or nonsecret encryption, as he called it) was possible,
and he had developed the concept of separate publickeys and privatekeys.
He also knew that he needed to find a special oneway function, one that
could be reversed if the receiver had access to a piece of special information.
Unfortunately, Ellis was not a mathematician. He experimented with a few
mathematical functions, but he soon realised that he would be unable to progress
any further on his own.
At this point, Ellis revealed his breakthrough to his bosses. Their reactions
are still classified material, but in an interview Richard Walton was prepared
to paraphrase for me the various memoranda that were exchanged. Sitting with
his briefcase on his lap, the lid shielding the papers from my view, he flicked
through the documents:
I can't show you the papers that I have in here because they still have naughty
words like TOP SECRET stamped all over them. Essentially, James's idea goes
to the top man, who farms it out, in the way that top men do, so that the
experts can have a look at it. They state that what James is saying is perfectly
true. In other words, they can't write this man off as a crank. At the same
time they can't think of a way of implementing his idea in practice. And
so they're impressed by James's ingenuity, but uncertain as to how to take
advantage of it.
For the next three years, GCHQ's brightest minds struggled to find a oneway
function that satisfied Ellis's requirements, but nothing emerged. Then,
in September 1973, a new mathematician joined the team. Clifford Cocks had
recently graduated from Cambridge University, where he had specialised in
number theory, one of the purest forms of mathematics. When he joined GCHQ
he knew very little about encryption and the shadowy world of military and
diplomatic communication, so he was assigned a mentor, Nick Patterson, who
guided him through his first few weeks at GCHQ.
After about six weeks, Patterson told Cocks about 'a really whacky idea'.
He outlined Ellis's theory for publickey cryptography, and explained that
nobody had yet been able to find a mathematical function that fitted the
bill. Patterson was telling Cocks because this was the most titillating
cryptographic idea around, not because he expected him to try to solve it.
However, as Cocks explains, later that day he set to work: 'There was nothing
particular happening, and so I thought I would think about the idea. Because
I had been working in number theory, it was natural to think about oneway
functions, something you could do but not undo. Prime numbers and factoring
was a natural candidate, and that became my starting point.' Cocks was beginning
to formulate what would be known as the RSA asymmetric cipher. Rivest, Shamir
and Adleman discovered their formula for publickey cryptography in 1977,
but four years earlier the young Cambridge graduate was going through exactly
the same thought processes. Cocks recalls: 'From start to finish, it took
me no more than half an hour. I was quite pleased with myself. I thought,
"Ooh, that's nice. I've been given a problem, and I've solved it." '
Cocks did not fully appreciate the significance of his discovery. He was
unaware of the fact that GCHQ's brightest minds had been struggling with
the problem for three years, and had no idea that he had made one of the
most important cryptographic breakthroughs of the century. Cocks's naivety
may have been part of the reason for his success, allowing him to attack
the problem with confidence, rather than timidly prodding at it. Cocks told
his mentor about his discovery, and it was Patterson who then reported it
to the management. Cocks was quite diffident and very much still a rookie,
whereas Patterson fully appreciated the context of the problem and was more
capable of addressing the technical questions that would inevitably arise.
Soon complete strangers started approaching Cocks the wonderkid, and began
to congratulate him. One of the strangers was James Ellis, keen to meet the
man who had turned his dream into a reality. Because Cocks still did not
understand the enormity of his achievement the details of this meeting did
not make a great impact on him, and so now, over two decades later, he has
no memory of Ellis's reaction.
When Cocks did eventually realise what he had done, it struck him that his
discovery might have disappointed G.H. Hardy, one of the great English
mathematicians of the early part of the century. In his The Mathematician's
Apology, written in 1940, Hardy had proudly stated: 'Real mathematics
has no effects on war. No one has yet discovered any warlike purpose to be
served by the theory of numbers.' Real mathematics means pure mathematics,
such as the number theory that was at the heart of Cocks's work. Cocks proved
that Hardy was wrong. The intricacies of number theory could now be used
to help generals plan their battles in complete secrecy. Because his work
had implications for military communications, Cocks, like Ellis, was forbidden
from telling anybody outside GCHQ about what he had done. Working at a topsecret
government establishment meant that he could tell neither his parents nor
his former colleagues at Cambridge University. The only person he could tell
was his wife, Gill, since she was also employed at GCHQ.
Although Cocks's idea was one of GCHQ's most potent secrets, it suffered
from the problem of being ahead of its time. Cocks had discovered a mathematical
function that permitted publickey cryptography, but there was still the
difficulty of implementing the system. Encryption via publickey cryptography
requires much more computer power than encryption via a symmetric cipher
like DES. In the early 1970s, computers were still relatively primitive and
unable to perform the process of publickey encryption within a reasonable
amount of time. Hence, GCHQ were not in a position to exploit publickey
cryptography. Cocks and Ellis had proved that the apparently impossible was
possible, but nobody could find a way of making the possible practical.
At the beginning of the following year, 1974, Cocks explained his work on
publickey cryptography to Malcolm Williamson, who had recently joined GCHQ
as a cryptographer. The men happened to be old friends. They had both attended
Manchester Grammar School, whose school motto is Sapere aude, 'Dare
to be wise'. While at school in 1968, the two boys had represented Britain
at the Mathematical Olympiad in the Soviet Union. After attending Cambridge
University together, they went their separate ways for a couple of years,
but now they were reunited at GCHQ. They had been exchanging mathematical
ideas since the age of eleven, but Cocks's revelation of publickey cryptography
was the most shocking idea that Williamson had ever heard. 'Cliff explained
his idea to me,' recalls Williamson, 'and I really didn't believe it. I was
very suspicious, because this is a very peculiar thing to be able to do.'
Williamson went away, and began trying to prove that Cocks had made a mistake
and that publickey cryptography did not really exist. He probed the mathematics,
searching for an underlying flaw. Publickey cryptography seemed too good
to be true, and Williamson was so determined to find a mistake that he took
the problem home. GCHQ employees are not supposed to take work home, because
everything the do is classified, and the home environment is potentially
vulnerable to espionage. However, the problem was stuck in Williamson's brain,
so he could not avoid thinking about it. Defying orders, he carried his work
back to his house. He spent five hours trying to find a flaw. 'Essentially
I failed,' says Williamson. 'Instead I came up with another solution to the
problem of key distribution.' Williamson was discovering DiffieHellmanMerkle
key exchange, at roughly the same time that Martin Hellman discovered it.
Williamson's initial reaction reflected his cynical disposition: 'This looks
great, I thought to myself. I wonder if I can find a flaw in this one. I
guess I was in a negative mood that day.'
By 1975,James Ellis, Clifford Cocks and Malcolm Williamson had discovered
all the fundamental aspects of publickey cryptography, yet they all had
to remain silent. The three Britons had to sit back and watch as their
discoveries were rediscovered by Diffie, Hellman, Merkle, Rivest, Shamir
and Adleman over the next three years. Curiously, GCHQ discovered RSA before
DiffieHellmanMerkle key exchange, whereas in the outside world,
DiffieHellmanMerkle key exchange came first. The scientific press reported
the breakthroughs at Stanford and MIT, and the researchers who had been allowed
to publish their work in the scientific journals became famous within the
community of cryptographers. A quick look on the Internet with a search engine
turns up 15 web pages mentioning Clifford Cocks, compared to 1,382 pages
that mention Whitfield Diffie. Cocks's attitude is admirably restrained:
'You don't get involved in this business for public recognition.' Wllliamson
is equally dispassionate: 'My reaction was "Okay, that's just the way it
is." Basically, I just got on with the rest of my life.'
Williamson's only qualm is that GCHQ failed to patent publickey cryptography
When Cocks and Williamson first made their breakthroughs, there was agreement
among GCHQ management that patenting was impossible for two reasons. First,
patenting would mean having to reveal the details of their work, which would
have been incompatible with GCHQ's aims. Second, in the early 1970s it was
far from clear that mathematical algorithms could be patented. When Diffie
and Hellman tried to file for a patent in 1976, however, it was evident that
they could be patented. At this point, Williamson was keen to go public and
block Diffie and Hellman's application, but he was overruled by his senior
managers, who were not farsighted enough to see the digital revolution and
the potential of publickey cryptography. By the early 1980s Williamson's
bosses were beginning to regret their decision, as developments in computers
and the embryonic Internet made it clear that RSA and DiffieHellmanMerkle
key exchange would both be enormously successful commercial products. In
1996, RSA Data Security, Inc., the company responsible for RSA products,
was sold for $200 million.
Although the work at GCHQ was still classified, there was one other organisation
that was aware of the breakthroughs that had been achieved in Britain. By
the early 1980s America's National Security Agency knew about the work of
Ellis, Cocks and Williamson, and it is probably via the NSA that Whitfield
Diffie heard a rumour about the British discoveries. In September 1982, Diffie
decided to see if there was any truth in the rumour, and he travelled with
his wife to Cheltenham in order to talk to James Ellis face to face. They
met at a local pub, and very quickly Mary was struck by Ellis's remarkable
character:
We sat around talking, and I suddenly became aware that this was the most
wonderful person you could possibly imagine. The breadth of his mathematical
knowledge is not something I could confidently discuss, but he was a true
gentleman, immensely modest, a person with great generosity of spirit and
gentility. When I say gentility, I don't mean oldfashioned and musty. This
man was a chevalier. He was a good man, a truly good man. He was a
gentle spirit.
Diffie and Ellis discussed various topics, from archaeology to how rats in
the barrel improve the taste of cider, but whenever the conversation drifted
towards cryptography, Ellis gently changed the subject. At the end of Diffie's
visit, as he was ready to drive away, he could no longer resist directly
asking Ellis the question that was really on his mind: 'Tell me about how
you invented publickey cryptography?' There was a long pause. Ellis eventually
whispered: 'Well, I don't know how much I should say. Let me just say that
you people did much more with it than we did.'
Although GCHQ were the first to discover publickey cryptography, this should
not diminish the achievements of the academics who rediscovered it. It was
the academics who were the first to realise the potential of publickey
encryption, and it was they who drove its implementation Furthermore, it
is quite possible that GCHQ would never have revealed their work, thus blocking
a form of encryption that would enable the digital revolution to reach its
full potential. Finally, the discovery by the academics was wholly independent
of GCHQ's discovery, and on an intellectual par with it. The academic environment
is completely isolated from the topsecret domain of classified research,
and academics do not have access to the tools and secret knowledge that may
be hidden in the classified world. On the other hand, government researchers
always have access to the academic literature. One might think of this flow
of information in terms of a oneway function  information flows freely
in one direction, but it is forbidden to send information in the opposite
direction.
When Diffie told Hellman about Ellis, Cocks and Williamson, his attitude
was that the discoveries of the academics should be a footnote in the history
of classified research, and that the discoveries at GCHQ should be a footnote
in the history of academic research. However, at that stage nobody except
GCHQ NSA, Diffie and Hellman knew about the classified research, and so it
could not even be considered as a footnote.
By the mid1980s, the mood at GCHQ was changing, and the management considered
publicly announcing the work of Ellis, Cocks and Williamson The mathematics
of publickey cryptography was already well established in the public domain,
and there seemed to be no reason to remain secretive. In fact, there would
be distinct benefits if the British revealed their groundbreaking work on
publickey cryptography. As Richard Walton recalls:
We flirted with the idea of coming clean in 1984. We began to see advantages
for GCHQ being more publicly acknowledged. It was a time when the government
security market was expanding beyond the traditional military and diplomatic
customer, and we needed to capture the confidence of those who did not
traditionally deal with us. We were in the middle of Thatcherism, and we
were trying to counter a sort of 'government is bad, private is good' ethos.
So, we had the intention of publishing a paper, but that idea was scuppered
by that blighter Peter Wright, who wrote Spycatcher. We were just
warming up senior management to approve this release, when there was all
this hooha about Spycatcher. Then the order of the day was 'heads
down, hats on'.
Peter Wright was a retired British intelligence officer, and the publication
of Spycatcher, his memoirs, was a source of great embarrassment to
the British government. It would be another 13 years before GCHQ eventually
went public  28 years after Ellis's initial breakthrough. In 1997 Clifford
Cocks completed some important unclassified work on RSA, which would have
been of interest to the wider community, and which would not be a security
risk if it were to be published. As a result, he was asked to present a paper
at the Institute of Mathematics and its Applications Conference to be held
in Cirencester. The room would be full of cryptography experts. A handful
of them would know that Cocks, who would be talking about just one aspect
of RSA, was actually its unsung inventor. There was a risk that somebody
might ask an embarrassing question, such as 'Did you invent RSA?' If such
a question arose, what was Cocks supposed to do? According to GCHQ policy
he would have to deny his role in the development of RSA, thus forcing him
to lie about an issue that was totally innocuous. The situation was clearly
ridiculous, and GCHQ decided that it was time to change its policy. Cocks
was given permission to begin his talk by presenting a brief history of GCHQ's
contribution to publickey cryptography.
On 18 December 1997, Cocks delivered his talk. After almost three decades
of secrecy, Ellis, Cocks and Williamson received the acknowledgement they
deserved. Sadly, James Ellis had died just one month earlier on 25 November
1997, at the age of seventythree. Ellis joined the list of British cipher
experts whose contributions would never be recognised during their lifetimes.
Charles Babbage's breaking of the Vigenère cipher was never revealed
during his lifetime, because his work was invaluable to British forces in
the Crimea. Instead, credit for the work went to Friedrich Kasiski. Similarly,
Alan Turing's contribution to the war effort was unparalleled, and yet government
secrecy demanded that his work on Enigma could not be revealed.
In 1987, Ellis wrote a
classified document that
recorded his contribution to publickey cryptography, which included his
thoughts on the secrecy that so often surrounds cryptographic work:
Cryptography is a most unusual science. 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 that
no further benefit can be obtained from continued secrecy.
