Behind the Invention of the Cryptosystem That Revolutionized Tech

A code, or cipher, is a method for converting a message in ordinary language, the plaintext, into a ciphertext that looks like gibberish. The conversion generally relies on a key—a vital item of information that’s kept secret. For example, Julius Caesar is said to have used a cipher in which each letter of the alphabet is moved along three places. The key here is “three.” This type of substitution cipher, in which each letter of the alphabet is transformed into some other letter in a fixed manner, can easily be broken, given an adequate supply of ciphertexts. You just need to know the frequencies with which the letters of the alphabet occur in plaintext. Then you can make a pretty good stab at guessing the code. At first there will be a few errors, but if a section seems to decode as JULFUS CAESAR, you don’t need to be a genius to realize that the F ought to be an I.

Simple and insecure though it may be, the Caesar cipher is a good example of a general principle that, until recently, underlay virtually all code systems: it’s a symmetric cipher, meaning that both the sender and the recipient use essentially the same key. I say “essentially” because they use it in different ways: Julius moves the alphabet three places forward, while the recipient moves it three places back. However, if you know how the key is used to encode a message, you can easily reverse the process to use the same key to decode it. Even very sophisticated and secure ciphers are symmetric. So security demands that the key must be kept secret, from everyone except the sender and the recipient.

As Benjamin Franklin said, “three may keep a secret, if two of them are dead.” In a symmetric cipher, at least two people need to know the key, which in Franklin’s view is one too many. Some time in 1944 or 1945, someone (perhaps Claude Shannon, inventor of information theory) at Bell Labs in the USA suggested protecting voice communication from eavesdroppers by adding random noise to the signal, and then subtracting it again when received. This is also a symmetric method, because the key is the random noise, and subtraction reverses addition. In 1970 James Ellis, an engineer at the UK’s Government Communications Headquarters (GCHQ), formerly GC&CS, wondered whether the noise could be generated mathematically. If so, it was at least conceivable that this could be done not by mere addition of signals, but by some mathematical process that would be very difficult to reverse, even if you knew what it was. Of course, the recipient had to be able to reverse it, but that might be achieved using a second key, known only to the recipient.

Ellis called this idea “non-secret encryption.” Today’s term is “public key cryptosystem.” These phrases mean that the rule for putting a message into code can be revealed to the general public, but without knowledge of the second key, no one would be able to work out how to reverse that procedure and decode the message. The only problem was that Ellis couldn’t devise a suitable encryption method. He wanted what’s now called a trapdoor function: easy to calculate, but hard to reverse, like falling through a trapdoor. But, as always, there had to be some secret second key that let the legitimate recipient reverse the process just as easily, like a hidden ladder that you could use to climb out again.

Enter Clifford Cocks, a British mathematician also at GCHQ. In September of 1973, Cocks had a brainwave. He could realize Ellis’s dream, using the mathematics of prime numbers to create a trapdoor function. Mathematically, multiplying two or more prime numbers together is easy. You can do it by hand with two 50-digit primes, getting a 99- or 100-digit result. The reverse, taking a number with a hundred digits and finding its prime factors, is far harder. The standard school method “try possible factors in turn” is hopeless: there are too many possibilities. Cocks devised a trapdoor function based on the product of two large primes—what you get by multiplying them together. The resulting code is so secure that this product, though not the primes themselves, can even be made public. Decoding requires knowing the two primes separately, and that’s the secret second key. Unless you know those two primes, you’re stuck; knowing their product alone doesn’t help. For instance, suppose I tell you I’ve found two primes whose product is: 1,192,344,277,257,254,936,928,421,267,205,031,305,805,339,598,743,208,059,530,638,398,522,646,841,344,407,246,985,523,336,728,666,069.

Can you find those primes? A really fast supercomputer can do it, but a laptop would struggle. With more digits, even the supercomputer is stumped.

Anyway, Cocks’s background was in number theory, and he devised a way to use such a pair of primes to create a trapdoor function. It was so simple that at first he didn’t even write it down. Later, he put the details in a report to his superiors. But no one could think of a way to use this method, not with the rudimentary computers of the time, so it was classified. It was also passed on to the US National Security Agency. Both organizations did see military potential, because even if the calculations were slow, you could use the public key system to send someone the key to some other entirely different code electronically. That’s the main way this type of cipher is used today, in both military and civilian applications.

Britain’s bureaucrats have a long and undistinguished track record of failing to spot huge money spinners—penicillin, the jet engine, DNA fingerprinting. In this case, though, they can take some consolation from patent law: in order to patent something, you have to give away what it is. At any rate, Cocks’s revolutionary idea was filed away, rather like the scene at the end of Raiders of the Lost Ark, where the box containing the Ark of the Covenant is wheeled away into the depths of a gigantic, anonymous government warehouse, piled to the rafters with boxes that look just the same. Meanwhile, come 1977, the identical method surfaced, reinvented independently and promptly published by three American mathematicians: Ronald Rivest, Adi Shamir, and Leonard Adleman. After them, we now call it the RSA cryptosystem.

Finally, in 1997, the British security services declassified Cocks’s work, which is how we now know he thought of it first.

__________________________________

Excerpted from What’s the Use?: How Mathematics Shapes Everyday Life by Ian Stewart. Copyright © 2021. Available from Basic Books, an imprint of Hachette Book Group, Inc.