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,
p
B
and
q
B
, and multiplied them together to get
N
B
. He has kept
p
B
and
q
B
secret, because these make up his private decryption key, but he has published
N
B
, which is equal to 408,508,091. So Alice inserts Bob’s public key
N
B
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
p
B
and
q
B
, 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
p
B
and
q
B
. Bob has kept
p
B
and
q
B
secret, but Eve, like everybody else, knows
N
B
is 408,508,091. Eve then attempts to deduce the values for
p
B
and
q
B
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
N
B
. Although some recipes are faster than others, they all essentially involve checking each prime number to see if it divides into
N
B
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
p
B
and
q
B
. 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 10
65
(this means 1 followed by 65 zeros, or one hundred thousand, million, million, million, million, million, million, million, million, million, million). This would have resulted in a value for
N
that would have been roughly 10
65
× 10
65
, which is 10
130
. 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 10
130
. 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 10
130
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 10
308
, 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 10
130
. 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 10
129
. 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.