It is easy to multiply the prime numbers 11,927 and 20,903 and get the number 249,310,081, but it is much harder to recover from the product, 249,310,081, the two prime numbers that are its factors. This one-way function, the difficulty of factoring numbers, underlies an ingenious kind of cipher: the most sophisticated encryption system in use today. It takes a long time for even the largest computers to factor a really large product back into its constituent primes. A coding system based on factoring uses two different decoding keys, one to encipher a message and a different but related one to decipher. With only the enciphering key, it’s easy to encode a message, but deciphering it within any practical period of time is nearly impossible. Deciphering requires a separate key, available only to the intended recipient of the message—or, rather, to the recipient’s computer. The enciphering key is based on the product of two huge prime numbers, whereas the deciphering key is based on the primes themselves. A computer can generate a new pair of unique keys in a flash, because it is easy for a computer to generate two large prime numbers and multiply them together. The enciphering key thus created can be made public without appreciable risk, because of the difficulty even another computer would have factoring it to obtain the deciphering key.
The practical application of this encryption will be at the center of the information highway’s security system. The world will become quite reliant on this network, so it is important that security be handled competently. You can think of the information highway as a postal network where everyone has a mailbox that is impervious to tampering and has an unbreakable lock. Each mailbox has a slot that lets anyone slide information in, but only the owner of a mailbox has the key to get information out. (Some governments may insist that each mailbox have a second door with a separate key that the government keeps, but we’ll ignore that political consideration for now and concentrate on the security that software will provide.)
Each user’s computer or other information appliance will use prime numbers to generate an enciphering key, which will be listed publicly, and a corresponding deciphering key, which only the user will know. This is how it will work in practice: I have information I want to send you. My information appliance/computer system looks up your public key and uses it to encrypt the information before sending it. No one can read the message, even though your key is public knowledge, because your public key does not contain the information needed for decryption. You receive the message and your computer decrypts it with a private key that corresponds to your public key.
You want to answer. Your computer looks up my public key and uses it to encrypt your reply. No one else can read the message, even though it was encrypted with a key that is totally public. Only I can read it because only I have the private deciphering key. This is very practical, because no one has to trade keys in advance.
How big do the prime numbers and their products have to be to ensure an effective one-way function?.
The concept of public-key encryption was invented by Whitfield Diffie and Martin Hellman in 1977. Another set of computer scientists, Ron Rivest, Adi Shamir, and Leonard Adelman, soon came up with the notion of using prime factorization as part of what is now known as the RSA cryptosystem, after the initials of their last names. They projected that it would take millions of years to factor a 130-digit number that was the product of two primes, regardless of how much computing power was brought to bear. To prove the point, they challenged the world to find the two factors in this 129-digit number, known to people in the field as RSA 129:
114,381,625,757,888,867,669,235,779,976,146,612,010,218,296, 721,242,362,562,561,842,935,706,935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,29.0,026,879,543,541
They were sure that a message they had encrypted using the number as the public key would be totally secure forever. But they hadn’t anticipated either the full effects of Moore’s Law, as discussed in chapter 2, which has made computers much more powerful, or the success of the personal computer, which has dramatically increased the number of computers and computer users in the world. In 1993 a group of more than 600 academics and hobbyists from around the world began an assault on the 129-digit number, using the Internet to coordinate the work of various computers. In less than a year they factored the number into two primes, one 64 digits long and the other 65. The primes are as follows:
3,490,529,510,847,650,949,147,849,619,903,898,133,417,764,638, 493,387,843,990,820,577
and
32,769,132,993,266,709,549,961,988,190,834,461,413,177,642, 967,992,942,539,798,288,533
And the encoded message says: “The magic words are squeamish and ossifrage.”
One lesson that came out of this challenge is that a 129-digit public key is not long enough if the information being encrypted is really important and sensitive. Another is that no one should get too cocksure about the security of encryption.
Increasing the key just a few digits makes it much more difficult to crack. Mathematicians today believe that a 250-digit-long product of two primes would take millions of years to factor with any foreseeable amount of future computing power. But who really knows. This uncertainty—and the unlikely but conceivable possibility that someone could come up with an easy way of factoring big numbers—means that a software platform for the information highway will have to be designed in such a way that its encryption scheme can be changed readily.
One thing we don’t have to worry about is running out of prime numbers, or the prospect of two computers’ accidentally using the same numbers as keys. There are far more prime numbers of appropriate length than there are atoms in the universe, so the chance of an accidental duplication is vanishingly small.
Key encryption allows more than just privacy. It can also assure the authenticity of a document because a private key can be used to encode a message that only the public key can decode. It works like this: If I have information I want to sign before sending it to you, my computer uses my private key to encipher it. Now the message can be read only if my public key—which you and everyone else knows—is used to decipher it. This message is verifiably from me, because no one else has the private key that could have encrypted it in this way.
My computer takes this enciphered message and enciphers it again, this time using your public key. Then it sends this double-coded message to you across the information highway.
Your computer receives the message and uses your private key to decipher it. This removes the second level of encoding but leaves the level I applied with my private key. Then your computer uses my public key to decipher the message again. Because it really is from me, the message deciphers correctly and you know it is authentic. If even one bit of information was changed, the message would not decode properly and the tampering or communications error would be apparent. This extraordinary security will enable you to transact business with strangers or even people you distrust, because you’ll be able to be sure that digital money is valid and signatures and documents are provably authentic.
Security can be increased further by having time stamps incorporated into encrypted messages. If anyone tries to tinker with the time that a document supposedly was written or sent, the tinkering will be detectable. This will rehabilitate the evidentiary value of photographs and videos, which has been under assault because digital retouching has become so easy to do.