The Roots of Cybersecurity Owe A Great Deal to James Ellis, Clifford Cocks and Malcolm Williamson
The Roots of Cybersecurity Owe A Great Deal to James Ellis, Clifford Cocks and Malcolm Williamson
In memory of James Ellis, RIP.
We all know about the work of Alan Turing, but I’d like to outline three of the greats in cryptography who, at the time, did not receive the praise they deserved: James Ellis, Clifford Cocks and Malcolm Williamson. Each of them worked at GCHQ, and where Clifford Cocks discovered public key encryption, independently from Ron Rivest, in 1973, and Malcolm Williamson discovered the key exchange method used by the Diffie-Hellman method several years before Whitfield Diffie and Martin Hellman published their classic paper [here]:
The eventual declassification of their work was in 1997 and to honour them, the Institute of Electrical and Electronics Engineers (IEEE), in 2010, awarded them the 100th IEEE Milestone Award for their contributions to cryptography. To show the significance of the award, other winners included contributions to the first transatlantic telephone cable and the first transatlantic satellite TV communication.
Ellis based his idea on a paper about a research paper where random noise could be added to a voice signal and then extracted at the other end. He started at GCHQ in September 1973, and outlined his ideas of Clifford Cocks, who went home and give it a think, and returned with the RSA public key concept. The technique was immediately classified, as it created risks in getting into the hands of adversaries.
Cocks and Ellis then outlined their ideas to Malcolm Williamson, who also working at GCHQ, and who then tried to address the problem of key distribution. His contribution was the creation of a method known as Diffie–Hellman key exchange. Again, as with the discovery of public key, the work was classified.
With the publication of the Diffie-Hellman method in 1976, and then the RSA method, the trio approached GCHQ in order to inform others that they had independently discovered the methods, for which their request was turned down.
At the time, only GCHQ and the NSA knew of the UK discovery. Rumours, though, about the earlier discovery spread, possibly through the NSA, and Whitfield Diffie eventually travelled to meet James Ellis. On what they made of the discovery James outlined to Whitfield:
“Well, I don’t know how much I should say. Let me just say that you people made much more of it than we did.”
Unfortunately, James Ellis died on 25 November 1997, just one month before the public announcement. Then, on 18 December 1997, Clifford Cocks delivered a public lecture on the contribution that Ellis, Cocks and Williamson had made, and whose work had been kept secret for over three decades.
Key Exchange
The Whitefield Diffie and Martin Hellman’s paper focused on solving a problem where Bob and Alice could openly communicate, with Eve listening, and for them to end up with the same encryption key.
So how does key exchange work? First Bob and Alice agree on two values (G and N), where N must be a prime number. Let’s go for:
G=4 and N=7 (which is prime)
Next Bob thinks of a random number … say 3 (and we’ll call it x).
Next Alice thinks of a random number … say 4 (and we’ll call it y).
Bob then calculates G to the power of his random number and takes a mod of N:
Bob’s Value = 4³ mod 7 = 64 mod 7 = 1
Alice then calculates G to the power of her random number and takes a mod of N:
Alice’s Value = 4⁴ mod 7 = 256 mod 7 = 4
They then swap them over, and Bob then calculates the key with:
Key(Bob) = (Alice’s Value)^x mod N = 4³ mod 7 = 1
and Alice does the same with her values:
Key(Alice) = (Bob’s Value)^y mod N = 1⁴ mod 7 = 1
and they both end up with the same key. …. magic! An outline of the calculation is here.
A presentation on this is here.
Just to make sure it all works, here’s some other examples:
- x=3, y=4, G=4 and N=7. Try
- x=6, y=15, G=5 and N=23. Try
- x=5, y=7, G=10 and N=541. Try
- x=7, y=7, G=5 and N=11. Try
- x=7, y=9, G=8 and N=13. Try
Public key
Let’s now look at the second contribution: public key. For this I have two values d and e, and I share e and a prime number n. If you want to send me a message (m) you calculate the cipher with:
Cipher = m^e mod (n)
and you send it to me, and I just basically raise your Cipher to the power of d, and I get the original message back again:
Message = Cipher^d mod (n)
To determine the keys (e and d), we first take two prime numbers named p and q, and calculate n and Phi(n):
n= p * q
Phi(n) = (p-1) * (q-1)
Now we must select a value of e, so that there is no common factor in Phi. Finally we select a value so that:
(e * d) mod n = Phi(n) +1
Magic!
For example if we select p =7 and q = 11, we get:
n=77
Phi(n) = 60
Now, gcd(e,Phi)=1 — where gcd is the greatest common denominator — so Phi(n) has factors of 2, 3, 4, 5, 6, 10.., so we must avoid these. Let’s select 9 … no that doesn’t work as it has a factor of 3. Let’s select 13:
e=13
Now we must compute:
(e * d) mod (Phi(n)) = 1
(13 * d) mod 77 = 61
If we try some values:
d (13*d) mod 77
1 13
2 26
3 39
4 52
….
35 35
36 48
37 1
So we have a value of 37 for d.
Our public key is (e,n) or (13,77) and the decryption key is (d,n) or (37,77).
Let’s take a message of 5. The cipher is:
Cipher = 5¹³ mod 77 = 26
and let’s decrypt:
Message = 26³⁷ mod 77 = 5
Yipeeee!!!!!!!!!!!!!!!!!!!!!!!!!!!! [Try it here]
If you want to try a few more they are [here].
Conclusion
So along with the greats of Ron Rivest, Whitfield Diffie, Martin Hellman, Ralph Merkle, Adi Shamir and Leonard Adleman, stand James Ellis, Clifford Cocks and Malcolm Williamson, and who have build the foundation of security on the Internet. In a world dominated by companies investing million in research, it is good to see that it is humans and not money that makes the difference in creating the ideas which change the world.
While the US based researchers were often protected by academic freedom to publish, James Ellis, Clifford Cocks and Malcolm Williamson were constrained, understandably, by national defence concerns. Unfortunately James did not get the chance to see a public recognition for his work, but the other two did.
The US researchers, though, did not get things all there own way, especially from pressure from individuals in the NSA. More details [here].