Unsung Heroes of Cryptography

The Sunday Telegraph

Cryptography, the science of secrecy, is a secret science. For two thousand years, cryptographers have conducted their research behind closed doors, and therefore these codemakers and codebreakers have had to accept that they will never gain any immediate recognition for their ingenious and heroic efforts. For example, Charles Babbage, the Victorian polymath and computer pioneer, broke the Vigenère cipher, but he received no credit. It seems that the British government hushed up his breakthrough, because they wanted to exploit it in order to read enemy messages during the Crimean War.

The Bletchley Park codebreakers had to wait until the 1970s before their contribution to the war effort was declassified, by which time many of the leading figures had already died. Many years after the death of Alastair Denniston, Bletchley’s first director, his daughter received a letter from one of his colleagues:

“Your father was a great man in whose debt all English-speaking people will remain for a very long time, if not forever. That so few should know exactly what he did is the sad part.”

Alan Turing, nowadays the most famous Bletchley codebreaker, committed suicide in 1954, having received no public recognition for cracking the German Enigma code, an achievement which had saved countless lives.

In America, the situation was no different. In the Pacific campaign, the Navajo provided US Marines with an unbreakable code, a combination of their own language and special code words, the latter being used for military terms that had no obvious translation within the Navajo lexicon. The Navajo language has no link with any European or Asian language, and consequently the Japanese had no hope of deciphering it. According to Major General Howard Conner: “Without the Navajos, the Marines would never have taken Iwo Jima.” Their contribution was not acknowledged until 1968, when the Navajo code was declassified.

Although modern encryption is a much more public affair, because of its relevance to individuals and businesses, there is still a large amount of clandestine cryptography, and there are cryptographers whose brilliance continues to be shrouded in government secrecy. However, while writing “The Code Book”, I was fortunate in being able to interview a pair of GCHQ cryptographers, whose research had been classified for the last a quarter of a century, but who had now been given permission to reveal a hitherto hidden history.

As well being intelligence gathering agency, GCHQ is also responsible for safe-guarding british government communications. The story starts in 1965, when James Ellis joined the Communications-Electronics Security Group, GCHQ’s cryptographic division. He was brilliant, but he was also unpredictable, and introverted. His colleague Richard Walton recalls that:

“He was a rather quirky worker, and he didn’t really fit into the day to day business of CESG. 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 everyone in GCHQ was like him, but equally we need some people with his flair and originality.”

One of Ellis’s greatest qualities was his breadth of knowledge. He became known as a cryptoguru, and if other researchers found themselves with impossible problems, then 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 investigate the greatest problem in secret communication, the so-called key-distribution problem.

To explain the key-distribution problem, cryptographers often talk about three characters, Alice, Bob and Eve. Typically, Alice wants to send a personal message to Bob, but Eve the Eavesdropper is trying to intercept the message. Naturally Alice wants to protect the message by scrambling it, but in order for this to work, Bob has to be able to unscramble the message, which means that he needs to know the recipe that Alice used to scramble the message in the first place. Alice has to somehow get the scrambling recipe, known as the key, to Bob without it falling into the hands of Eve.

In the 1970’s, everybody using secret codes, from banks to the military, wanted to find a way around the key distribution problem. Essentially, the only solution was for Alice to send the key to Bob via a trusted courier, so that she could use the key to encrypt a message at a later date. Banks employed specially vetted dispatch riders, who would race across the country with padlocked briefcases, personally distributing keys to everyone that the bank would communicate with over the next week. The distribution of US government keys is the responsibility of COMSEC, short for Communications Security, which would transport tons of keys around the world every day. When ships carrying COMSEC material came into dock, cryptocustodians would march on board, collect stacks of cards, paper tapes, floppy disks, or whatever other medium the keys might be stored on, and then deliver them to the intended recipient.

Key distribution might seem like a mundane issue, but it was the greatest problem in cryptography. It was the weakest link in the chain of security, because there was always the risk of a courier selling keys to the enemy. Also, as communication networks grew in size, the problem also grew, and it became clear that key distribution was turning into a logistical nightmare, making secure communication prohibitively expensive. However, finding a solution seemed to be impossible. If Alice wants to share a secret with Bob, namely the message, then she must first agree another secret with him, namely the key. The only way to send the key securely is to deliver it in person or via a courier. In which case, Alice might as well deliver the message in person or via a courier. The cryptographic community accepted that the key-distribution problem was unavoidable, but Ellis was not so pessimistic.

The best ways to understand Ellis’s solution to the problem is to think about encryption in terms of locking a message inside a box. Alice puts her message in a box, puts a padlock on the box, and then sends it to Bob. Unfortunately, he cannot open the padlock and get to the message in the box unless he has a copy of Alice’s key, and we run into the key-distribution problem again. Alice cannot securely send Bob a message unless she has already sent him the key.

In 1969, Ellis turned the problem on its head, and solved it by suggesting that the receiver, not the sender, should play the crucial role in encryption. He pictured a scenario in which Bob designed a padlock and a key. Although Bob would make only one copy of the key, which he would keep with him at all times, he would manufacture hundreds of padlocks, and distribute them to post offices all over the world. Then, if Alice wants to send a message to Bob, she would simply go to her local post office, ask for one of Bob’s padlocks, and then put the message in a box locked using Bob’s padlock. Alice, and anybody else, can easily lock Bob’s padlock shut, but only Bob has the key required to open the padlock. The key never leaves Bob, and so the key-distribution problem no longer exists.

To make his idea work in practice, Ellis had to develop a mathematical padlock, a virtual analogue of the metal padlock. Unfortunately, neither he, nor anyone else at GCHQ, could provide the necessary mathematics. Three years later, however, a pair of Cambridge graduates, Clifford Cocks and Malcolm Williamson, invented two separate techniques for implementing Ellis’s idea. After learning about Ellis’s proposition, each of them took less than an hour to come up with their respective mathematical implementations. Together, Ellis, Cocks and Wiliamson had made the greatest breakthrough in twentieth century cryptography, but they could tell nobody about they had done. Public-key cryptography, as their invention would later be called, was classified top secret.

Not only were the GCHQ threesome denied the glory of discovering public-key cryptography, they also had to watch in silence as American researchers independently solved the key-distribution problem in the mid-1970s. Whitfield Diffie and Martin Hellman at Stanford University and Ronald Rivest, Adi Shamir and Leonard Adleman at MIT were not bound by any government restrictions, they published their work, and immediately became cryptographic superstars.

Over the last twenty years, public-key cryptography has played a crucial role in enabling Internet commerce, because it has been used to guarantee the security of financial transactions. It has been equally important in providing the tools necessary for individuals to encrypt e-mails, and in the future it will play an increasingly important role in ensuring personal privacy in the Information Age. The American cryptographers have been credited with the discovery that has shaped the digital revolution, and indeed they deserve to be praised, but the tragedy has been that the British cryptographers have been ignored because their research was conducted behind the closed doors of GCHQ.

By the mid-1980s, the whole world knew about the solution to the key-distribution problem, and so there was really nothing to be lost in GCHQ revealing the contribution of Ellis, Cocks and Williamson. In fact, there were distinct advantages in going public. The ethos of Thatcherism meant that GCHQ was expanding its services beyond the traditional military and diplomatic customer, and an announcement claiming credit for the greatest cryptographic invention in history would certainly have boosted its reputation among potential customers. However, just as GCHQ were about to go public in 1987, retired British intelligence officer Peter Wright published his controversial memoirs, ‘Spycatcher’, which was sufficiently embarrassing to engender an increased sense of caution, which in turn meant that the work of Ellis, Cocks and Williamson remained classified.

It would take another decade before GCHQ would eventually be ready to go public – 28 years after Ellis’s initial breakthrough. In the summer of 1997, GCHQ decided that it was ready to reveal the hidden history of public-key cryptography. Clifford Cocks was planning to attend a conference later in the year, on 18 December, and he was given the honour to making the announcement. At last, Clifford Cocks and Graham Williamson would get the credit they deserved. But sadly, James Ellis, aged 73, died just one month before the conference.

In 1987, Ellis wrote an internal GCHQ memorandum, which has recently been declassified. It not only documents his contribution to public-key cryptography, but also includes 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. Revelation of 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.”