Gates: Jiffy Iffy Crypto

[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.

-----