The Code Book (49 page)

Williamson went away, and began trying to prove that Cocks had made a mistake and that public key cryptography did not really exist. He probed the mathematics, searching for an underlying flaw. Public key 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 they 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 Diffie–Hellman–Merkle 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.”

Figure 68
Malcolm Williamson. (
photo credit 6.6
)

By 1975, James Ellis, Clifford Cocks and Malcolm Williamson had discovered all the fundamental aspects of public key 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 Diffie–Hellman–Merkle key exchange, whereas in the outside world, Diffie–Hellman–Merkle 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.” Williamson 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.”

Figure 69
Malcolm Williamson (second from left) and Clifford Cocks (extreme right) arriving for the 1968 Mathematical Olympiad.

Williamson’s only qualm is that GCHQ failed to patent public key 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 public key 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 Diffie-Hellman-Merkle 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 organization 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 rumor about the British discoveries. In September 1982, Diffie decided to see if there was any truth in the rumor, and he traveled 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 old-fashioned 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 toward 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 public key 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 public key cryptography, this should not diminish the achievements of the academics who rediscovered it. It was the academics who were the first to realize the potential of public key 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 top-secret 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 one-way 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 mid-1980s, the mood at GCHQ was changing, and the management considered publicly announcing the work of Ellis, Cocks and Williamson. The mathematics of public key 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 public key 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 hoo-ha 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 public key cryptography.

On December 18, 1997, Cocks delivered his talk. After almost three decades of secrecy, Ellis, Cocks and Williamson received the acknowledgment they deserved. Sadly, James Ellis had died just one month earlier on November 25, 1997, at the age of seventy-three. Ellis joined the list of British cipher experts whose contributions would never be recognized 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 public key 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 realizes its value. In contrast, the fullest value of cryptography is realized by minimizing 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.

7 Pretty Good Privacy

Just as Whit Diffie predicted in the early 1970s, we are now entering the Information Age, a postindustrial era in which information is the most valuable commodity. The exchange of digital information has become an integral part of our society. Already, tens of millions of e-mails are sent each day, and electronic mail will soon become more popular than conventional mail. The Internet, still in its infancy, has provided the infrastructure for the digital marketplace, and e-commerce is thriving. Money is flowing through cyberspace, and it is estimated that every day half the world’s Gross Domestic Product travels through the Society for Worldwide Interbank Financial Telecommunications network. In the future, democracies that favor referenda will begin to have on-line voting, and governments will use the Internet to help administer their countries, offering facilities such as on-line tax declarations.

However, the success of the Information Age depends on the ability to protect information as it flows around the world, and this relies on the power of cryptography. Encryption can be seen as providing the locks and keys of the Information Age. For two thousand years encryption has been of importance only to governments and the military, but today it also has a role to play in facilitating business, and tomorrow ordinary people will rely on cryptography in order to protect their privacy. Fortunately, just as the Information Age is taking off, we have access to extraordinarily strong encryption. The development of public key cryptography, particularly the RSA cipher, has given today’s cryptographers a clear advantage in their continual power struggle against cryptanalysts. If the value of
N
is large enough, then finding
p
and
q
takes Eve an unreasonable amount of time, and RSA encryption is therefore effectively unbreakable. Most important of all, public key cryptography is not weakened by any key distribution problems. In short, RSA guarantees almost unbreakable locks for our most precious pieces of information.