|
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.” |
Cliff Cocks |
