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

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.