by Simon Singh
The next morning, Rivest handed the paper to Adleman, who went through his usual process of trying to tear it apart, but this time he could find no faults. His only criticism was with the list of authors. “I told Ron to take my name off the paper,” recalls Adleman. “I told him that it was his invention, not mine. But Ron refused and we got into a discussion about it. We agreed that I would go home and contemplate it for one night, and consider what I wanted to do. I went back the next day and suggested to Ron that I be the third author. I recall thinking that this paper would be the least interesting paper that I will ever be on.” Adleman could not have been more wrong. The system, dubbed RSA (Rivest, Shamir, Adleman) as opposed to ARS, went on to become the most influential cipher in modern cryptography.
Figure 65 Ronald Rivest, Adi Shamir and Leonard Adleman. (photo credit 6.3)
Before exploring Rivest’s idea, here is a quick reminder of what scientists were looking for in order to build an asymmetric cipher:
(1) Alice must create a public key, which she would then publish so that Bob (and everybody else) can use it to encrypt messages to her. Because the public key is a one-way function, it must be virtually impossible for anybody to reverse it and decrypt Alice’s messages.
(2) However, Alice needs to decrypt the messages being sent to her. She must therefore have a private key, some special piece of information, which allows her to reverse the effect of the public key. Therefore, Alice (and Alice alone) has the power to decrypt any messages sent to her.
At the heart of Rivest’s asymmetric cipher is a one-way function based on the sort of modular functions described earlier in the chapter. Rivest’s one-way function can be used to encrypt a message-the message, which is effectively a number, is put into the function, and the result is the ciphertext, another number. I shall not describe Rivest’s one-way function in detail (for which see Appendix J), but I shall explain one particular aspect of it, known simply as N, because it is N that makes this one-way function reversible under certain circumstances, and therefore ideal for use as an asymmetric cipher.
N is important because it is a flexible component of the one-way function, which means that each person can choose a different value of N, and personalize the one-way function. In order to choose her personal value of N, Alice picks two prime numbers, p and q, and multiplies them together. A prime number is one that has no divisors except itself and 1. For example, 7 is a prime number because no numbers except 1 and 7 will divide into it without leaving a remainder. Likewise, 13 is a prime number because no numbers except 1 and 13 will divide into it without leaving a remainder. However, 8 is not a prime number, because it can be divided by 2 and 4.
So, Alice could choose her prime numbers to be p = 17,159 and q = 10,247. Multiplying these two numbers together gives N = 17,159 × 10,247 = 175,828,273. Alice’s choice of N effectively becomes her public encryption key, and she could print it on her business card, post it on the Internet, or publish it in a public key directory along with everybody else’s value of N. If Bob wants to encrypt a message to Alice, he looks up Alice’s value of N (175,828,273) and then inserts it into the general form of the one-way function, which would also be public knowledge. Bob now has a one-way function tailored with Alice’s public key, so it could be called Alice’s one-way function. To encrypt a message to Alice, he takes Alice’s one-way function, inserts the message, notes down the result and sends it to Alice.
At this point the encrypted message is secure because nobody can decipher it. The message has been encrypted with a one-way function, so reversing the one-way function and decrypting the message is, by definition, very difficult. However, the question remains-how can Alice decrypt the message? In order to read messages sent to her, Alice must have a way of reversing the one-way function. She needs to have access to some special piece of information that allows her to decrypt the message. Fortunately for Alice, Rivest designed the one-way function so that it is reversible to someone who knows the values of p and q, the two prime numbers that are multiplied together to give N. Although Alice has told the world that her value for N is 175,828,273, she has not revealed her values for p and q, so only she has the special information required to decrypt her own messages.
We can think of N as the public key, the information that is available to everybody, the information required to encrypt messages to Alice. Whereas, p and q are the private key, available only to Alice, the information required to decrypt these messages.
The exact details of how p and q can be used to reverse the one-way function are outlined in Appendix J. However, there is one question that must be addressed immediately. If everybody knows N, the public key, then surely people can deduce p and q, the private key, and read Alice’s messages? After all, N was created from p and q. In fact, it turns out that if N is large enough, it is virtually impossible to deduce p and q from N, and this is perhaps the most beautiful and elegant aspect of the RSA asymmetric cipher.
Alice created N by choosing p and q, and then multiplying them together. The fundamental point is that this is in itself a one-way function. To demonstrate the one-way nature of multiplying primes, we can take two prime numbers, such as 9,419 and 1,933, and multiply them together. With a calculator it takes just a few seconds to get the answer, 18,206,927. However, if instead we were given 18,206,927 and asked to find the prime factors (the two numbers that were multiplied to give 18,206,927) it would take us much longer. If you doubt the difficulty of finding prime factors, then consider the following. It took me just ten seconds to generate the number 1,709,023, but it will take you and a calculator the best part of an afternoon to work out the prime factors.
This system of asymmetric cryptography, known as RSA, is said to be a form of public key cryptography. To find out how secure RSA is, we can examine it from Eve’s point of view, and try to break a message from Alice to Bob. To encrypt a message to Bob, Alice must look up Bob’s public key. To create his public key, Bob picked his own prime numbers, pB and qB, and multiplied them together to get NB. He has kept pB and qB secret, because these make up his private decryption key, but he has published NB, which is equal to 408,508,091. So Alice inserts Bob’s public key NB into the general one-way encryption function, and then encrypts her message to him. When the encrypted message arrives, Bob can reverse the function and decrypt it using his values for pB and qB, which make up his private key. Meanwhile, Eve has intercepted the message en route. Her only hope of decrypting the message is to reverse the one-way function, and this is possible only if she knows pB and qB. Bob has kept pB and qB secret, but Eve, like everybody else, knows NB is 408,508,091. Eve then attempts to deduce the values for pB and qB by working out which numbers would need to be multiplied together to get 408,508,091, a process known as factoring.
Factoring is very time-consuming, but exactly how long would it take Eve to find the factors of 408,508,091? There are various recipes for trying to factor NB. Although some recipes are faster than others, they all essentially involve checking each prime number to see if it divides into NB without a remainder. For example, 3 is a prime number, but it is not a factor of 408,508,091 because 3 will not perfectly divide into 408,508,091. So Eve moves on to the next prime number, 5. Similarly, 5 is not a factor, so Eve moves on to the next prime number, and so on. Eventually, Eve arrives at 18,313, the 2,000th prime number, which is indeed a factor of 408,508,091. Having found one factor, it is easy to find the other one, which turns out to be 22,307. If Eve had a calculator and was able to check four primes a minute, then it would have taken her 500 minutes, or more than 8 hours, to find pB and qB. In other words, Eve would be able to work out Bob’s private key in less than a day, and could therefore decipher the intercepted message in less than a day.
This is not a very high level of security, but Bob could have chosen much larger prime numbers and increased the security of his private key. For example, he could have chosen primes that are as big as 1065 (this means 1 followed by 65 zeros, or one hundred thousand, million, millio
n, million, million, million, million, million, million, million, million). This would have resulted in a value for N that would have been roughly 1065 × 1065, which is 10130. A computer could multiply the two primes and generate N in just a second, but if Eve wanted to reverse the process and work out p and q, it would take inordinately longer. Exactly how long depends on the speed of Eve’s computer. Security expert Simson Garfinkel estimated that a 100 MHz Intel Pentium computer with 8 MB of RAM would take roughly 50 years to factor a number as big as 10130. Cryptographers tend to have a paranoid streak and consider worst-case scenarios, such as a worldwide conspiracy to crack their ciphers. So, Garfinkel considered what would happen if a hundred million personal computers (the number sold in 1995) ganged up together. The result is that a number as big as 10130 could be factored in about 15 seconds. Consequently, it is now generally accepted that for genuine security it is necessary to use even larger primes. For important banking transactions, N tends to be at least 10308, which is ten million billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion times bigger than 10130. The combined efforts of a hundred million personal computers would take more than one thousand years to crack such a cipher. With sufficiently large values of p and q, RSA is impregnable.
The only caveat for the security of RSA public key cryptography is that at some time in the future somebody might find a quick way to factor N. It is conceivable that a decade from now, or even tomorrow, somebody will discover a method for rapid factoring, and thereafter RSA will become useless. However, for over two thousand years mathematicians have tried and failed to find a shortcut, and at the moment factoring remains an enormously time-consuming calculation. Most mathematicians believe that factoring is an inherently difficult task, and that there is some mathematical law that forbids any shortcut. If we assume they are right, then RSA seems secure for the foreseeable future.
The great advantage of RSA public key cryptography is that it does away with all the problems associated with traditional ciphers and key exchange. Alice no longer has to worry about securely transporting the key to Bob, or that Eve might intercept the key. In fact, Alice does not care who sees the public key—the more the merrier, because the public key helps only with encryption, not decryption. The only thing that needs to remain secret is the private key used for decryption, and Alice can keep this with her at all times.
RSA was first announced in August 1977, when Martin Gardner wrote an article entitled “A New Kind of Cipher that Would Take Millions of Years to Break” for his “Mathematical Games” column in Scientific American. After explaining how public key cryptography works, Gardner issued a challenge to his readers. He printed a ciphertext and also provided the public key that had been used to encrypt it:
N = 114,381,625,757,888,867,669,235,779,976,146,612,010,218,296, 721,242,362,5 62,561,842,93 5,706,93 5,245,733,897,83 0,597,123,563, 958,705,058,989,075,147,599,290,026,879,543,541.
The challenge was to factor N into p and q, and then use these numbers to decrypt the message. The prize was $100. Gardner did not have space to explain the nitty-gritty of RSA, and instead he asked readers to write to MIT’s Laboratory for Computer Science, who in turn would send back a technical memorandum that had just been prepared. Rivest, Shamir and Adleman were astonished by the three thousand requests they received. However, they did not respond immediately, because they were concerned that public distribution of their idea might jeopardize their chances of getting a patent. When the patent issues were eventually resolved, the trio held a celebratory party at which professors and students consumed pizzas and beer while stuffing envelopes with technical memoranda for the readers of Scientific American.
As for Gardner’s challenge, it would take 17 years before the cipher would be broken. On April 26, 1994, a team of six hundred volunteers announced the factors of N:
q = 3,490,529,510,847,650,949,147,849,619,903,898,133,417,764, 638,493,387,843,990,820,577
p = 32,769,132,993,266,709,549,961,988,190,834,461,413,177, 642,967,992,942,539,798,288,533.
Using these values as the private key, they were able to decipher the message. The message was a series of numbers, but when converted into letters it read “the magic words are squeamish ossifrage.” The factoring problem had been split among the volunteers, who came from countries as far apart as Australia, Britain, America and Venezuela. The volunteers used spare time on their workstations, mainframes and supercomputers, each of them tackling a fraction of the problem. In effect, a network of computers around the world were uniting and working simultaneously in order to meet Gardner’s challenge. Even bearing in mind the mammoth parallel effort, some readers may still be surprised that RSA was broken in such a short time, but it should be noted that Gardner’s challenge used a relatively small value of N–it was only of the order of 10129. Today, users of RSA would pick a much larger value to secure important information. It is now routine to encrypt a message with a sufficiently large value of N so that all the computers on the planet would need longer than the age of the universe to break the cipher.
The Alternative History of Public Key Cryptography
Over the past twenty years, Diffie, Hellman and Merkle have become world-famous as the cryptographers who invented the concept of public key cryptography, while Rivest, Shamir and Adleman have been credited with developing RSA, the most beautiful implementation of public key cryptography. However, a recent announcement means that the history books are having to be rewritten. According to the British Government, public key cryptography was originally invented at the Government Communications Headquarters (GCHQ) in Cheltenham, the top-secret establishment that was formed from the remnants of Bletchley Park after the Second World War. This is a story of remarkable ingenuity, anonymous heroes and a government cover-up that endured for decades.
The story starts in the late 1960s, when the British military began to worry about the problem of key distribution. Looking ahead to the 1970s, senior military officials imagined a scenario in which miniaturization of radios and a reduction in cost meant that every soldier could be in continual radio contact with his officer. The advantages of widespread communication would be enormous, but communications would have to be encrypted, and the problem of distributing keys would be insurmountable. This was an era when the only form of cryptography was symmetric, so an individual key would have to be securely transported to every member of the communications network. Any expansion in communications would eventually be choked by the burden of key distribution. At the beginning of 1969, the military asked James Ellis, one of Britain’s foremost government cryptographers, to look into ways of coping with the key distribution problem.
Ellis was a curious and slightly eccentric character. He proudly boasted of traveling halfway around the world before he was even born—he was conceived in Britain, but was born in Australia. Then, while still a baby, he returned to London and grew up in the East End of the 1920s. At school his primary interest was science, and he went on to study physics at Imperial College before joining the Post Office Research Station at Dollis Hill, where Tommy Flowers had built Colossus, the first codebreaking computer. The cryptographic division at Dollis Hill was eventually absorbed into GCHQ, and so on April 1, 1965, Ellis moved to Cheltenham to join the newly formed Communications–Electronics Security Group (CESG), a special section of GCHQ devoted to ensuring the security of British communications. Because he was involved in issues of national security, Ellis was sworn to secrecy throughout his career. Although his wife and family knew that he worked at GCHQ, they were unaware of his discoveries and had no idea that he was one of the nation’s most distinguished codemakers.
Despite his skills as a codemaker, Ellis was never put in charge of any of the important GCHQ research groups. He was brilliant, but he was also unpredictable, introverted and not a natural team worker. His colleague Richard Walton recalled:
He was a rather quirky worker, and he didn’t
really fit into the day-to-day business of GCHQ. 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 everybody in GCHQ was like him, but we can tolerate a higher proportion of such people than most organizations. We put up with a number of people like him.
Figure 66 James Ellis. (photo credit 6.4)
One of Ellis’s greatest qualities was his breadth of knowledge. He read any scientific journal he could get his hands on, and never threw anything away. For security reasons, GCHQ employees must clear their desks each evening and place everything in locked cabinets, which meant that Ellis’s cabinets were stuffed full with the most obscure publications imaginable. He gained a reputation as a cryptoguru, and if other researchers found themselves with impossible problems, 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 examine the key distribution problem.
The cost of key distribution was already enormous, and would become the limiting factor to any expansion in encryption. Even a reduction of 10 per cent in the cost of key distribution would significantly cut the military’s security budget. However, instead of merely nibbling away at the problem, Ellis immediately looked for a radical and complete solution. “He would always approach a problem by asking, ‘Is this really what we want to do?’ ” says Walton. “James being James, one of the first things he did was to challenge the requirement that it was necessary to share secret data, by which I mean the key. There was no theorem that said you had to have a shared secret. This was something that was challengeable.”