 |
Prime Pursuits
|
Ivars Peterson
A young child learning to count can get to 20 by counting fingers and
toes. Higher numbers take on meaning as the child's experience grows.
Mathematicians also find meaning in numbers. They start with patterns or
relationships displayed by relatively small counting numbers and try to find
out whether the patterns hold for ever larger ones. On such a foundation,
they have built the discipline known as number theory. In recent years, number
theory has come out of its mathematical closet to play a crucial role in
public affairs. The playful work of long-ago mathematicians turns out to
have key applications in cryptography and computer security systems.
HEADS OR TAILS?
Alice lives in New York City, and Bob lives in Los Angeles. They are recently
divorced and communicate, when they do at all, only by telephone. Now they
have to decide who should get an antique table that they have just jointly
inherited. They agree to toss a coin. But neither one would like to choose,
say, "heads" and then hear the other person exclaim over the telephone, "Here
goes . . . I'm flipping the coin . . . you
lose!" Somehow, Alice and Bob must find a way of tossing the coin
without suspecting each other of cheating.
The dilemma confronting Alice and Bob is related to a problem that many computer
users face. In the high-tech world of electronic mail and telephone-linked
computers, methods are needed to guarantee that secret messages arrive intact,
that funds are transferred correctly, and that contracts and agreements are
properly signed. Otherwise, electronic letters are as open as postcards,
and a person may be tempted to lie or cheat to gain an advantage over a rival.
One ingenious scheme for remote coin tosses blends the capabilities of modern,
high-speed computers with some basic mathematics rooted in ancient Greece.
In essence, this particular algorithm converts a call of "heads" or "tails"
into the problem of factoring a large number.
To win, the caller must find the two smaller numbers that the coin flipper
multiplied together to generate the large number. This coin-toss algorithm
not only provides Alice and Bob with a way to settle their dispute but also
suggests protocols for ensuring the fairness of computer- aided business
transactions, such as signing contracts and sending certified mail.
At the heart of the coin-toss algorithm is a procedure called the oblivious
transfer, originally devised by Harvard University's Michael Rabin. The
transfer is somewhat like a simple game played with a locked box requiring
two different keys. A sender transfers the locked box to a recipient, who
finds one key that partially unlocks the box. The sender has both keys and,
without seeing what the recipient has done, must now pass on one of the two
keys. Depending on which key is sent, the recipient will either succeed or
fail in opening the box. Although the sender's choice controls the outcome,
the sender never knows which choice to make to guarantee a certain result.
The oblivious transfer depends on two crucial mathematical ideas. First,
mathematicians and computer scientists know several quick ways to determine
whether a large number of, say, 60 digits, is a prime number, that is, evenly
divisible only by itself and by the number 1. A properly programmed microcomputer
can do this in a matter of seconds. Second, mathematicians believe that factoring
a 120-digit or larger composite number, especially when the number is the
product of just two roughly equal primes, can take years, even on the fastest
available computers. The claim that factoring is intrinsically "hard" has
not yet been proved, but mathematicians have assembled convincing evidence
to support their belief. The security of Rabin's transfer hinges on the
difficulty of factoring large numbers.
As in many modern cryptographic systems for sending secret messages, modular arithmetic plays an important role in the oblivious transfer. It's the kind of arithmetic that people use every day when they think about clocks and time. Adding 12 hours to the time shown on a clock face brings the clock's hands (or digits) right back to where they were at the start. Moreover, as far as the clock is concerned, adding 14, 26, or 38 hours is the same as adding just 2 hours.
In modular arithmetic, only remainders left over after division of one integer
by another are saved. In the clock example, dividing 12 into 14, 26, or 38
produces a remainder of 2. Any other numbers that happen to come up during
the computation are tossed out. More formally, given two integers, a
and n, the remainder of a divided by n is written as
a(mod n) and described as "a modulo n." In this
arithmetic system, 7(mod 5) is 2; 13(mod 5) is 3, and so on. A negative number,
-a, is treated in the same way as (n - a) (mod n). Thus,
-2(mod 5) is the same as (5 - 2) (mod 5) or 3(mod 5), which equals 3.
Modular arithmetic is a handy key for locking up secrets. Its advantage is
that it affords a kind of one-way trapdoor: what goes in doesn't easily get
out again. Computing something like "14 modulo 12" is straightforward. The
answer is 2. The reverse process is trickier. If the remainder happens
to be 2 modulo 12 (or 2), then the original number could have been 2, 14,
26, or any one of innumerable other possibilities.
Here's how the oblivious transfer would work in the case of a remote
coin toss Alice and Bob use their linked
personal computers to perform the toss. Normally, the computers would deal
with 60- and 120-digit or larger numbers and probably go through the procedure
in less time than it takes someone to read this example. However, to make
sure that most of this chapter isn't taken up by lengthy strings of digits,
Alice selects much smaller numbers than those a computer would handle.
Alice, in New York, starts the coin toss by selecting two prime numbers,
7 and 13. She multiplies the numbers together and sends the product, 91,
to Bob. She keeps the numbers 7 and 13 secret. Bob wins the toss if he can
factor 91, that is, find 7 and 13. Suppose that Bob, in Los Angeles, can't
factor 91. First, he can check whether Alice is cheating. She could have
sent a number that can't be factored, but Bob's computer has efficient tests
to show whether the number is a prime or a power of a prime. Once his computer
finishes checking for primality, Bob randomly selects an integer, say 11,
that falls between 1 and 91. The integer may, by chance, turn out to be a
factor of 91, and therefore he wins the toss immediately. However, the chances
of this happening with a 120- digit number are incredibly small. So Bob squares
11 to get 121. In the modular arithmetic step, he divides 121 by 91 and finds
that the remainder is 30. Bob sends this remainder to Alice. He keeps the
number 11 secret.
Alice knows the original number, 91, and she looks for all numbers less than
91 that generate a remainder of 30 when squared then divided into her number.
In this case, she can do it by trial and error, but mathematicians use a
faster method based on the Chinese remainder theorem, which provides a handy
way to reconstruct integers from certain remainders. She finds two pairs:
±11 and ±24. She can send either 11 or 24 to Bob. One of the numbers
is Bob's number, but Alice doesn't know which one of the two is his.
If Alice sends the number 11, Bob would have no new information and would
lose the toss because he wouldn't be able to factor 91. But Alice happens
to send him 24. Bob adds his own number, 11, to 24 and gets 35. The greatest
common divisor of 35 and 91 is 7. This number, 7, will automatically be a
factor of 91. Interestingly, the greatest common divisor of 91 and the difference
of 24 and 11 gives the other factor, 13. Now Bob can factor Alice's number,
and he wins the coin toss. Finding the greatest common divisor is an application
of Euclid's algorithm, one of the earliest known tools of number theory.
The algorithm allows one to find, in a systematic way, the greatest common
divisor of two integers without having to factor the two numbers.
The oblivious transfer also makes an appearance in a protocol for sending
certified mail. The protocol was developed by Manuel Blum of the University
of California at Berkeley. The usual problem with certified mail sent from
one computer to another is that although senders get a record that the message
was received, they don't get confirmation of the message's content. This
allows the possibility of tampering and the appearance of deliberate or
accidental errors in the received message.
In this case, the sender, Alice, embeds her message in the digits of 10 large
numbers she sends to Bob for factoring. The numbers, each of which is a product
of two large primes, are constructed so that Bob must factor all 10 In order
to read the full message. As in the coin-toss example, Bob picks a number
at random and runs through the oblivious transfer. Depending on Alice's response,
he may or may not be able to factor the first number. Then he goes on to
the second number, runs through the algorithm, and so on, until he has tried
all 10. After completing this first stage, Bob is likely to be able to factor
some but not all of the numbers. In fact, because he has a 50 percent chance
of factoring each number, he will, on the average end up with 5 of the 10
numbers needed. Bob then repeats the procedure, running through all of Alice's
numbers in the same order as before but with new random guesses. He continues
through these stages until he has enough information to find the factors
of all 10 numbers. This usually takes about three or four passes through
Alice's list.
Eventually, Bob has the information to find and decipher Alice's message,
and Alice has a record of Bob's trial guesses. The collection of Bob's requests
constitutes her receipt. If Bob were to deny receiving the message, a judge
could determine from the transaction record that Alice provided enough
information for Bob to factor the numbers and that Bob must have received
the message she sent. A simple variation on Blum's certified-mall scheme,
with some additional safeguards, can ensure that contracts are signed
simultaneously in different parts of the world. Traditionally, businessmen,
diplomats, or generals have gathered in one place to sign contracts, agreements,
or treaties. Because they don't trust each other, they want to see that the
correct signatures are affixed at the appropriate time. Without a protocol
and if the parties to a contract are in different places, someone may be
tempted to cheat. All kinds of rituals and ceremonies have evolved over centuries
to make sure that no person or country gains an advantage because of delays
in signing a document.
A form of electronic signature is already familiar to people who use a bank's
teller machines. To withdraw or deposit money, the customer must have a coded
card and be able to enter a secret identification number. That combination
constitutes the signing of a document permitting the transaction.
Blum's protocol is a more sophisticated and secure version of a bank's automated
transaction system. Each person involved in the deal would send a copy of
the contract to the other person, in the same way that each person would
send certified mail by computer. Each person, then, also receives a receipt,
which can be interpreted as a signature. The contract would include a clause
stating that the contract is valid only if the participants have in their
hands (or more likely stored in their computers) both contract copies and
receipts. Only if the transaction is completed by both sides will the contract
be valid.
We have described protocols of only two of many schemes proposed to reduce
the risk of fraud when people use computers. Some schemes begin as simple
games like mental poker or tossing a coin and evolve into elaborate protocols
for electronic signatures or exchanging secret messages. These protocols
often employ fundamental mathematical ideas that were discovered centuries
ago without computers or applications in mind.
