Some aspects of public-key encryption

Traditional ("symmetric", "secret-key", or "single-key") cryptosystems are simple.  There is an algorithm that says what calculations to perform and a key (often a number) that controls how those calculations work.  The same key can be used to decrypt or encrypt data. 

Public-key ("asymmetric", "two-key") cryptosystems are different.  They have two keys, one for encryption and one for decryption, and it is not possible to derive one from the other.  So you could keep the encryption key secret but publish your decryption key in a directory, so that you could encrypt messages and everyone could decrypt them and be sure they were from you (digital signatures) or you could keep the decryption key secret and publish the encryption key so that people could send you secret messages even if you have never met them or made arrangements with them.

Public-key encryption was first openly described by Diffie and Hellman in 1976.  It was the biggest advance in cryptology in thirty years.  Two years later, Rivest, Shamir and Adleman published the most famous public-key cryptosystem, the RSA algorithm.

For someone who had just finished at university and who had always had a love of number theory (for its beauty and irrelevance) it seemed the perfect field to go into. Donald Davies of the National Physical Laboratory (who had earlier invented the principle of packet switching on which Internet communications depend) soon heard of our activities and kept a benevolent eye on us: it was through him that I came to attend the Crypto ’81 conference in Santa Barbara, California.

Crypto ’81 was the first major conference on cryptology and it marked a seminal moment in the creation of a new academic discipline. It brought together researchers from many disparate fields and there was a feeling of joy in the air as people who had worked in relative isolation realised that many other people were working in the same field and that their interest in encryption was not frivolous, eccentric, or seditious.

This last was a serious concern in 1981. The relations between governments and the commercial and academic sectors had always been rather uneasy when it came to encryption and for some the invention of apparently unbreakable cryptosystems such as RSA (the public invention, to be precise: a British government scientist had invented the same system more than ten years before but his work was classified and never published) was the last straw. In such an atmosphere the mere holding of Crypto ’81 and the admission of foreigners to it was something of an achievement (though it would have been difficult to exclude Shamir, although he was an Israeli). A number of delegates from government agencies were there, exuding charm and reasonableness and hoping for the same in return, and there were also a surprising number of delegates with home addresses in Maryland who liked to go running together every morning.
Nowadays cryptology is an academic discipline just like any other, but then it was all very new. There had not been much in the way of communication before, so just sitting a number theorist next to someone whose background was in abstract algebra could lead to significant advances.

Leaving aside the wilder fringes of quantum physics, there were three main questions facing the cryptographers of the time. One was the security of DES, the United States Data Encryption Standard. It was obvious that the cipher had been deliberately weakened at the behest of the United States government, to make it 250 times easier to break, but what no-one knew was what else might have been done behind the scenes. The design principles behind DES were classified (although the algorithm itself was of course made public) and people suspected the worst, that the government had designed DES with a "trapdoor" so that it could break it easily while other people without knowledge of the trapdoor could not. A great deal of energy was expended by the leading lights of cryptology on finding this or that suspicious-looking regularity in the way that DES behaved. Many years later it turned out that the government did indeed know of an attack that we did not, and that DES had been specially designed to resist that attack, so that there was no way of revealing the design principles of DES without also telling the world of a new kind of attack on cryptosystems in general. We were being kept in the dark for our own good; but a lot of time was wasted.

I played no part in all this because I didn't really see the point. One symmetric (ie. non-public-key) cipher would end up being used and it didn't really matter that much which. It was public-key encryption that offered unique new possibilities.

The question then was which public-key cryptosystem to choose. Diffie and Hellman's 1977 paper merely postulated the existence of public-key cryptosystems, but by 1981 there were quite a few to choose from. RSA used modular exponentiation, which was simple and flexible but very slow. Another much touted candidate was the knapsack system, which required far less arithmetic for each encryption. It had some disadvantages (it could not be used backwards for doing digital signatures) but my main objection to it was that it was ugly, so I had no interest in defending it and did not feel particularly sad when two to three years later knapsacks in general were comprehensively broken.

A much more elegant alternative was published by Lu and Lee of COMSAT under the title "A Simple and Effective Public-Key Cryptosystem". Donald Davies spotted this article and passed it on to us. We looked at it, and my first Cryptologia paper, "Remarks on Lu and Lee's Cryptosystem", showed how easily it could be broken.

The third problem that urgently needed addressing in 1981 was that of speed. This may sound strange given that we all know that computers are good at doing arithmetic fast, but a single modular exponentiation, the fundamental unit of RSA, could take a million multiplications or more, depending on the size of the numbers involved, making RSA too slow for many practical purposes. Even today, when your computer hesitates for a few seconds before entering a secure web site, this is because RSA is slow.
The obvious thing was to design hardware for doing arithmetic on very large numbers (around 150 digits long). We worked on various designs. FAP-1, which was actually built, featured a multiplier chip designed for military and aerospace operations that got so hot when it was working that one could burn oneself on it. FAP-2, a far more elaborate and faster design, would have had a significant impact on the world's supply of bit-slice processors if it had ever gone into production. It was time for a new approach.

Modular exponentiation can easily be broken down into a series of modular multiplications – multiplying A by B and reducing modulo R (ie. dividing the result by R and taking the remainder) – where A,.B, and R are all large numbers. Multiplication, in turn, is not really problematic: you use essentially the same methods that you would if you were doing long multiplication by hand. The really awkward operation was modulo reduction. Again the obvious method was the binary analogue of primary-school long division, but long division has one snag: you have to know the result of one subtraction before you can decide whether or not the next subtraction needs performing and this, for technical reasons, could slow the whole thing down by a factor of ten.

The solution that I invented was simple, if a little counter-intuitive. If you don't want to wait until you have the exact information you need to make your decision, then don't. Make a guess instead, and make your decision on the basis of that guess. Of course your guess will be wrong sometimes, and this will lead to errors, and these errors will double each time you take another step in your calculation – but it turns out that these errors (which are all multiples of R) can be controlled, and any remaining ones can be tidied away at the end.

It seems absurd but the simulations showed that it always worked. I even managed to prove that the algorithm would work, though not until after the chips themselves had been built.

When you make an invention you have three choices: to publish, to patent, or to build it. Publication brings glory but no money; patenting leaves you open to the wiles of better-funded and more ruthless opponents.  The chips were duly designed and built – in Japan, which was interesting given that the final product would be subject to stringent UK export controls.

We announced FAP4, as it was called, in 1985, and sold quite a few of them.  It was the world's first commercially available public-key chip.

The lack of details in our Crypto ’85 paper has been a source of irritation to the writers of survey articles ever since, and now that enough time has passed and similar algorithms have been published (Brickell's method is a cousin of ours; Montgomery's is on another planet) it will be worth publishing the details.  Someone should manage at least an undergraduate dissertation in comparing our method with Brickell's.

The subsequent history of public-key encryption hardware was greatly influenced by something completely non-cryptographic: the fact that microprocessors have got 1,000 times faster. Twenty years ago some form of hardware accelerator would have been needed on every PC that used encryption, but now the market for such devices is restricted to the specialised computers that have to handle hundreds of web connections at the same time.

Things have changed in other ways in the past two decades.  Cryptology has ceased to be cutting-edge and is the pabulum of innumerable standards committees.  I found my time increasingly taken up with Cardbox, and when I return to cryptographic matters now it is as a user rather than a designer of chips and a breaker of algorithms.

I do not regret this. It is fun to blow on a fire in the early stages, singeing one's eyebrows and getting ash in one's eyes, but once the bonfire is properly alight sitting and watching it burn for hours has limited amusement value.

RSA continues to rule because everyone has implemented it and the patent has now expired. Any new cryptosystem would have to have revolutionary advantages if people are to take the risk of adopting it.

The successor to DES, the Advanced Encryption Standard (AES) was selected in an open competition where all the design criteria were clearly stated and each designer took care to give reasons for every decision, even giving the methods by which "random" data had been obtained. Now it has been adopted and everyone is trying to attack it, because a paper about a new attack on AES is sure to get published. This is open cryptology in action.

Many other themes that were touched on at Crypto ’81 continue to be worked on, often by their original proponents; but my feeling is that the really interesting questions of cryptology now lie in the application of encryption to real-world problems of security, privacy, and control. In 1981 the civilian use of cryptography was seen as a liberating force, with David Chaum even using it to create a form of electronic "cash" that had all the properties of the real thing (checkable, unforgeable) and was guaranteed to work anonymously. Now, as we stand on the threshold of totalitarianism, the talk is of chips to be embedded in banknotes so that even paper money can be tracked to see where it goes and how it is used. Encryption software may be freely available but in the UK its use already brings the risk of a prison sentence. It may be only a matter of time before the use of cryptography is banned altogether and the men in running shorts with home addresses in Maryland can declare victory at last.