Interesting People mailing list archives
IP: Gates: Jiffy Iffy Crypto
From: Dave Farber <farber () central cis upenn edu>
Date: Mon, 04 Dec 1995 15:30:21 -0500
Date: Sat, 25 Nov 1995 16:06:40 +0100 To: cypherpunks () toad com From: nobody () replay com (Anonymous)
From "The Road Ahead," by Bill Gates, with Nathan
Myhrvold and Peter Rinearson, Viking, 1995. [Paths to the Highway, pp. 106-111] Governments have long understood the importance of keeping information private, for both economic and military reasons. The need to make personal, commercial, military, or diplomatic messages secure (or to break into them) has attracted powerful intellects through the generations. It is very satisfying to break an encoded message. Charles Babbage, who made dramatic advances in the art of code breaking in the mid-1800s, wrote: "Deciphering is, in my opinion, one of the most fascinating of arts, and I fear I have wasted upon it more time than it deserves." I discovered its fascination as a kid when, like kids everywhere, a bunch of us played with simple ciphers. We would encode messages by substituting one letter of the alphabet for another. If a friend sent me a cipher that began "ULFW NZXX," it would be fairly easy to guess that this represented "DEAR BILL," and that U stood for D, and L for E, and so forth. With those seven letters it wasn't hard to unravel the rest of the cipher fairly quickly. Past wars have been won or lost because the most powerful governments on earth didn't have the cryptological power any interested junior high school student with a personal computer can harness today. Soon any child old enough to use a computer will be able to transmit encoded messages that no government on earth will find easy to decipher. This is one of the profound implications of the spread of fantastic computing power. When you send a message across the information highway it will be "signed" by your computer or other information appliance with a digital signature that only you are capable of applying, and it will be encrypted so that only the intended recipient will be able to decipher it. You'll send a message, which could be information of any kind, including voice, video, or digital money. The recipient will be able to be almost positive that the message is really from you, that it was sent at exactly the indicated time, that it has not been tampered with in the slightest, and that others cannot decipher it. The mechanism that will make this possible is based on mathematical principles, including what are called "one-way functions" and "public-key encryption." These are quite advanced concepts, so I'm only going to touch on them. Keep in mind that regardless of how complicated the system is technically, it will be extremely easy for you to use. You'll just tell your information appliance what you want it to do and it will seem to happen effortlessly. A one-way function is something that is much easier to do than undo. Breaking a pane of glass is a one-way function, but not one useful for encoding. The sort of one-way function required for cryptography is one that is easy to undo if you know an extra piece of information and very diffficult to undo without that information. There are a number of such one-way functions in mathematics. One involves prime numbers. Kids learn about prime numbers in school. A prime number cannot be divided evenly by any number except 1 and itself. Among the first dozen numbers, the primes are 2, 3, 5, 7, and 11. The numbers 4, 6, 8, and 10 are not prime because 2 divides into each of them evenly. The number 9 is not prime because 3 divides into it evenly. There are an infinite number of prime numbers, and there is no known pattern to them except that they are prime. When you multiply two prime numbers together, you get a number that can be divided evenly only by those same two primes. For example, only 5 and 7 can be divided evenly into 35. Finding the primes is called "factoring" the number. 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,290, 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. My description of public-key encryption oversimplifies the technical details of the system. For one thing, because it is relatively slow, it will not be the only form of encipherment used on the highway. But publickey encryption will be the way that documents are signed, authenticity is established, and the keys to other kinds of encryption are distributed securely. [Critical Issues, pp. 265-66, 270-71] This versatility will be the strength of the network, but it will also mean we will become reliant on it. Reliance can be dangerous. During the New York City blackouts in 1965 and 1977, millions of people were in trouble -- at least for a few hours -- because of their dependence on electricity. They counted on electric power for light, heat, transport, and security. When electricity failed, people were trapped in elevators, traffic lights stopped working, and electric water pumps quit. Anything really useful is missed when you lose it. A complete failure of the information highway is worth worrying about. Because the system will be thoroughly decentralized, any single outage is unlikely to have a widespread effect. If an individual server fails, it will be replaced and its data restored. But the system could be susceptible to assault. As the system becomes more important, we will have to design in more redundancy. One area of vulnerability is the system's reliance on cryptography -- the mathematical locks that keep information safe. None of the protection systems that exist today, whether steeringwheel locks or steel vaults, are completely fail-safe. The best we can do is make it as difficult as possible for somebody to break in. Despite popular opinions to the contrary, computer security has a very good record. Computers are capable of protecting information in such a way that even the smartest hackers can't get at it readily unless someone entrusted with information makes a mistake. Sloppiness is the main reason computer security gets breached. On the information highway there will be mistakes, and too much information will get passed along. Someone will issue digital concert tickets that prove to be forgeable, and too many people will show up. Whenever this sort of thing happens, the system will have to be reworked and laws may have to be revised. Because both the system's privacy and the security of digital money depend on encryption, a breakthrough in mathematics or computer science that defeats the cryptographic system could be a disaster. The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers. Any person or organization possessing this power could counterfeit money, penetrate any personal, corporate, or governmental file, and possibly even undermine the security of nations, which is why we have to be so careful in designing the system. We have to ensure that if any particular encryption technique proves fallible, there is a way to make an immediate transition to an alternate technique. There's a little bit of inventing still to be done before we have that perfected. It is particularly hard to guarantee security for information you want kept private for a decade or more. [Good section on privacy protection elided] At the same time technology is making it easier to create video records, it is also making it possible to keep all your personal documents and messages totally private. Encryption-technology software, which anyone can download from the Internet, can transform a PC into a virtually unbreakable code machine. As the highway is deployed, security services will be applied to all forms of digital information -- phone calls, files, databases, you name it. As long as you protect the password, the information stored on your computer can be held under the strongest lock and key that has ever existed. This allows for the greatest degree of information privacy any individual has ever had. Many in government are opposed to this encryption capability, because it reduces their ability to gather information. Unfortunately for them, the technology can't be stopped. The National Security Agency is a part of the U.S. government defense and intelligence community that protects this country's secret communications and decrypts foreign communications to gather intelligence data. The NSA does not want software containing advanced encryption capabilities to be sent outside the United States. However, this software is already available throughout the world, and any computer can run it. No policy decision will be able to restore the tapping capabilities governments had in the past. Today's legislation that prevents the export of software with good encryption capability could harm U.S. software and hardware companies. The restrictions give foreign companies an advantage over U.S. competitors. American companies almost unanimously agree that the current encryption export restrictions don't work. -----
Current thread:
- IP: Gates: Jiffy Iffy Crypto Dave Farber (Dec 04)