The Code Book Part 9

The exact details of the mangler function can change, and are determined by a key agreed by sender and receiver. In other words, the same message can be encrypted in a myriad of different ways depending on which key is chosen. The keys used in computer cryptography are simply numbers. Hence, the sender and receiver merely have to agree on a number in order to decide the key. Thereafter, encryption requires the sender to input the key number and the message into Lucifer, which then outputs the ciphertext. Decryption requires the receiver to input the same key number and the ciphertext into Lucifer, which then outputs the original message.

Lucifer was generally held to be one of the strongest commercially available encryption products, and consequently it was used by a variety of organizations. It seemed inevitable that this encryption system would be adopted as the American standard, but once again the NSA interfered with Feistel's work. Lucifer was so strong that it offered the possibility of an encryption standard that was probably beyond the codebreaking capabilities of the NSA; not surprisingly, the NSA did not want to see an encryption standard that they could not break. Hence, it is rumored that the NSA lobbied to weaken one aspect of Lucifer, the number of possible keys, before allowing it to be adopted as the standard. be adopted as the American standard, but once again the NSA interfered with Feistel's work. Lucifer was so strong that it offered the possibility of an encryption standard that was probably beyond the codebreaking capabilities of the NSA; not surprisingly, the NSA did not want to see an encryption standard that they could not break. Hence, it is rumored that the NSA lobbied to weaken one aspect of Lucifer, the number of possible keys, before allowing it to be adopted as the standard.

The number of possible keys is one of the crucial factors determining the strength of any cipher. A crypta.n.a.lyst trying to decipher an encrypted message could attempt to check all possible keys, and the greater the number of possible keys, the longer it will take to find the right one. If there are only 1,000,000 possible keys, a crypta.n.a.lyst could use a powerful computer to find the correct one in a matter of minutes, and thereby decipher an intercepted message. However, if the number of possible keys is large enough, finding the correct key becomes impractical. If Lucifer were to become the encryption standard, then the NSA wanted to ensure that it operated with only a restricted number of keys.

The NSA argued in favor of limiting the number of keys to roughly 100,000,000,000,000,000 (technically referred to as 56 bits, because this number consists of 56 digits when written in binary). It seems that the NSA believed that such a key would provide security within the civilian community, because no civilian organization had a computer powerful enough to check every possible key within a reasonable amount of time. However, the NSA itself, with access to the world's greatest computing resource, would just about be able to break into messages. The 56-bit version of Feistel's Lucifer cipher was officially adopted on November 23, 1976, and was called the Data Encryption Standard (DES). A quarter of a century later, DES remains America's official standard for encryption.

The adoption of DES solved the problem of standardization, encouraging businesses to use cryptography for security. Furthermore, DES was strong enough to guarantee security against attacks from commercial rivals. It was effectively impossible for a company with a civilian computer to break into a DES-encrypted message because the number of possible keys was sufficiently large. Unfortunately, despite standardization and despite the strength of DES, businesses still had to deal with one more major issue, a problem known as key distribution key distribution.

Imagine that a bank wants to send some confidential data to a client via a telephone line, but is worried that there might be somebody tapping the wire. The bank picks a key and uses DES to encrypt the data message. In order to decrypt the message, the client needs not only to have a copy of DES on its computer, but also to know which key was used to encrypt the message. How does the bank inform the client of the key? It cannot send the key via the telephone line, because it suspects that there is an eavesdropper on the line. The only truly secure way to send the key is to hand it over in person, which is clearly a time-consuming task. A less secure but more practical solution is to send the key via a courier. In the 1970s, banks attempted to distribute keys by employing special dispatch riders who had been vetted and who were among the company's most trusted employees. These dispatch riders would race across the world with padlocked briefcases, personally distributing keys to everyone who would receive messages from the bank over the next week. As business networks grew in size, as more messages were sent, and as more keys had to be delivered, the banks found that this distribution process became a horrendous logistical nightmare, and the overhead costs became prohibitive.

The problem of key distribution has plagued cryptographers throughout history. For example, during the Second World War the German High Command had to distribute the monthly book of day keys to all its Enigma operators, which was an enormous logistical problem. Also, Uboats, which tended to spend extended periods away from base, had to somehow obtain a regular supply of keys. In earlier times, users of the Vigenere cipher had to find a way of getting the keyword from the sender to the receiver. No matter how secure a cipher is in theory, in practice it can be undermined by the problem of key distribution.

To some extent, government and the military have been able to deal with the problem of key distribution by throwing money and resources at it. Their messages are so important that they will go to any lengths to ensure secure key distribution. The U.S. Government keys are managed and distributed by CO MS EC, short for Communications Security. In the 1970s, COMSEC was responsible for transporting tons of keys every day. When s.h.i.+ps carrying COMSEC material came into dock, crypto-custodians would march onboard, collect stacks of cards, paper tapes, floppy disks, or whatever other medium the keys might be stored on, and then deliver them to the intended recipients. floppy disks, or whatever other medium the keys might be stored on, and then deliver them to the intended recipients.

Key distribution might seem a mundane issue, but it became the overriding problem for postwar cryptographers. If two parties wanted to communicate securely, they had to rely on a third party to deliver the key, and this became the weakest link in the chain of security. The dilemma for businesses was straightforward-if governments with all their money were struggling to guarantee the secure distribution of keys, then how could civilian companies ever hope to achieve reliable key distribution without bankrupting themselves?

Despite claims that the problem of key distribution was unsolvable, a team of mavericks triumphed against the odds and came up with a brilliant solution in the mid-1970s. They devised an encryption system that appeared to defy all logic. Although computers transformed the implementation of ciphers, the greatest revolution in twentieth-century cryptography has been the development of techniques to overcome the problem of key distribution. Indeed, this breakthrough is considered to be the greatest cryptographic achievement since the invention of the monoalphabetic cipher, over two thousand years ago.

G.o.d Rewards Fools Whitfield Diffie is one of the most ebullient cryptographers of his generation. The mere sight of him creates a striking and somewhat contradictory image. His impeccable suit reflects the fact that for most of the 1990s he has been employed by one of America's giant computer companies-currently his official job t.i.tle is Distinguished Engineer at Sun Microsystems. However, his shoulder-length hair and long white beard betray the fact that his heart is still stuck in the 1960s. He spends much of his time in front of a computer workstation, but he looks as if he would be equally comfortable in a Bombay ashram. Diffie is aware that his dress and personality can have quite an impact on others, and comments that, "People always think that I am taller than I really am, and I'm told it's the Tigger effect-'No matter his weight in pounds, s.h.i.+llings and ounces, he always seems bigger because of the bounces.'"

Diffie was born in 1944, and spent most of his early years in Queens, New York. As a child he became fascinated by mathematics, reading books ranging from New York. As a child he became fascinated by mathematics, reading books ranging from The Chemical Rubber Company Handbook of Mathematical Tables The Chemical Rubber Company Handbook of Mathematical Tables to G.H. Hardy's to G.H. Hardy's Course of Pure Mathematics Course of Pure Mathematics. He went on to study mathematics at the Ma.s.sachusetts Inst.i.tute of Technology, graduating in 1965. He then took a series of jobs related to computer security, and by the early 1970s he had matured into one of the few truly independent security experts, a freethinking cryptographer, not employed by the government or by any of the big corporations. In hindsight, he was the first cypherpunk.

Diffie was particularly interested in the key distribution problem, and he realized that whoever could find a solution would go down in history as one of the all-time great cryptographers. Diffie was so captivated by the problem of key distribution that it became the most important entry in his special notebook ent.i.tled "Problems for an Ambitious Theory of Cryptography." Part of Diffie's motivation came from his vision of a wired world. Back in the 1960s, the U.S. Department of Defense began funding a cutting-edge research organization called the Advanced Research Projects Agency (ARPA), and one of ARPA's front-line projects was to find a way of connecting military computers across vast distances. This would allow a computer that had been damaged to transfer its responsibilities to another one in the network. The main aim was to make the Pentagon's computer infrastructure more robust in the face of nuclear attack, but the network would also allow scientists to send messages to each other, and perform calculations by exploiting the spare capacity of remote computers. The ARPANet was born in 1969, and by the end of the year there were four connected sites. The ARPANet steadily grew in size, and in 1982 it sp.a.w.ned the Internet. At the end of the 1980s, non-academic and nongovernmental users were given access to the Internet, and thereafter the number of users exploded. Today, more than a hundred million people use the Internet to exchange information and send electronic mail messages, or e-mails. problem of key distribution that it became the most important entry in his special notebook ent.i.tled "Problems for an Ambitious Theory of Cryptography." Part of Diffie's motivation came from his vision of a wired world. Back in the 1960s, the U.S. Department of Defense began funding a cutting-edge research organization called the Advanced Research Projects Agency (ARPA), and one of ARPA's front-line projects was to find a way of connecting military computers across vast distances. This would allow a computer that had been damaged to transfer its responsibilities to another one in the network. The main aim was to make the Pentagon's computer infrastructure more robust in the face of nuclear attack, but the network would also allow scientists to send messages to each other, and perform calculations by exploiting the spare capacity of remote computers. The ARPANet was born in 1969, and by the end of the year there were four connected sites. The ARPANet steadily grew in size, and in 1982 it sp.a.w.ned the Internet. At the end of the 1980s, non-academic and nongovernmental users were given access to the Internet, and thereafter the number of users exploded. Today, more than a hundred million people use the Internet to exchange information and send electronic mail messages, or e-mails.

[image]

Figure 62 Whitfield Diffie. ( Whitfield Diffie. (photo credit 6.1) While the ARPANet was still in its infancy, Diffie was farsighted enough to forecast the advent of the information superhighway and the digital revolution. Ordinary people would one day have their own computers, and these computers would be interconnected via phone lines. Diffie believed that if people then used their computers to exchange emails, they deserved the right to encrypt their messages in order to guarantee their privacy. However, encryption required the secure exchange of keys. If governments and large corporations were having trouble coping with key distribution, then the public would find it impossible, and would effectively be deprived of the right to privacy.

Diffie imagined two strangers meeting via the Internet, and wondered how they could send each other an encrypted message. He also considered the scenario of a person wanting to buy a commodity on the Internet. How could that person send an e-mail containing encrypted credit card details so that only the Internet retailer could decipher them? In both cases, it seemed that the two parties needed to share a key, but how could they securely exchange keys? The number of casual contacts and the amount of spontaneous e-mails among the public would be enormous, and this would mean that key distribution would be impractical. Diffie was fearful that the necessity of key distribution would prevent the public from having access to digital privacy, and he became obsessed with the idea of finding a solution to the problem. and the amount of spontaneous e-mails among the public would be enormous, and this would mean that key distribution would be impractical. Diffie was fearful that the necessity of key distribution would prevent the public from having access to digital privacy, and he became obsessed with the idea of finding a solution to the problem.

In 1974, Diffie, still an itinerant cryptographer, paid a visit to IBM's Thomas J. Watson Laboratory, where he had been invited to give a talk. He spoke about various strategies for attacking the key distribution problem, but all his ideas were very tentative, and his audience was skeptical about the prospects for a solution. The only positive response to Diffie's presentation was from Alan Konheim, one of IBM's senior cryptographic experts, who mentioned that someone else had recently visited the laboratory and given a lecture that addressed the issue of key distribution. That speaker was Martin h.e.l.lman, a professor from Stanford University in California. That evening Diffie got in his car and began the 5,000 km journey to the West Coast to meet the only person who seemed to share his obsession. The alliance of Diffie and h.e.l.lman would become one of the most dynamic partners.h.i.+ps in cryptography.

Martin h.e.l.lman was born in 1945 in a Jewish neighborhood in the Bronx, but at the age of four his family moved to a predominantly Irish Catholic neighborhood. According to h.e.l.lman, this permanently changed his att.i.tude to life: "The other kids went to church and they learned that the Jews killed Christ, so I got called 'Christ killer.' I also got beat up. To start with, I wanted to be like the other kids, I wanted a Christmas tree and I wanted Christmas presents. But then I realized that I couldn't be like all the other kids, and in self-defense I adopted an att.i.tude of 'Who would want to be like everybody else?'" h.e.l.lman traces his interest in ciphers to this enduring desire to be different. His colleagues had told him he was crazy to do research in cryptography, because he would be competing with the NSA and their multibillion-dollar budget. How could he hope to discover something that they did not know already? And if he did discover anything, the NSA would cla.s.sify it.

Just as h.e.l.lman was beginning his research, he came across The Codebreakers The Codebreakers by the historian David Kahn. This book was the first detailed discussion of the development of ciphers, and as such it was the perfect primer for a budding cryptographer. by the historian David Kahn. This book was the first detailed discussion of the development of ciphers, and as such it was the perfect primer for a budding cryptographer. The Codebreakers The Codebreakers was h.e.l.lman's only was h.e.l.lman's only research companion, until September 1974, when he received an unexpected phone call from Whitfield Diffie, who had just driven across the Continent to meet him. h.e.l.lman had never heard of Diffie, but grudgingly agreed to a half-hour appointment later that afternoon. By the end of the meeting, h.e.l.lman realized that Diffie was the best-informed person he had ever met. The feeling was mutual. h.e.l.lman recalls: "I'd promised my wife I'd be home to watch the kids, so he came home with me and we had dinner together. He left at around midnight. Our personalities are very different-he is much more counterculture than I am-but eventually the personality clash was very symbiotic. It was just such a breath of fresh air for me. Working in a vacuum had been really hard." research companion, until September 1974, when he received an unexpected phone call from Whitfield Diffie, who had just driven across the Continent to meet him. h.e.l.lman had never heard of Diffie, but grudgingly agreed to a half-hour appointment later that afternoon. By the end of the meeting, h.e.l.lman realized that Diffie was the best-informed person he had ever met. The feeling was mutual. h.e.l.lman recalls: "I'd promised my wife I'd be home to watch the kids, so he came home with me and we had dinner together. He left at around midnight. Our personalities are very different-he is much more counterculture than I am-but eventually the personality clash was very symbiotic. It was just such a breath of fresh air for me. Working in a vacuum had been really hard."

Since h.e.l.lman did not have a great deal of funding, he could not afford to employ his new soulmate as a researcher. Instead, Diffie was enrolled as a graduate student. Together, h.e.l.lman and Diffie began to study the key distribution problem, desperately trying to find an alternative to the tiresome task of physically transporting keys over vast distances. In due course they were joined by Ralph Merkle. Merkle was an intellectual refugee, having emigrated from another research group where the professor had no sympathy for the impossible dream of solving the key distribution problem. Says h.e.l.lman: Ralph, like us, was willing to be a fool. And the way to get to the top of the heap in terms of developing original research is to be a fool, because only fools keep trying. You have idea number 1, you get excited, and it flops. Then you have idea number 2, you get excited, and it flops. Then you have idea number 99, you get excited, and it flops. Only a fool would be excited by the 100th idea, but it might take 100 ideas before one really pays off. Unless you're foolish enough to be continually excited, you won't have the motivation, you won't have the energy to carry it through. G.o.d rewards fools.

The whole problem of key distribution is a cla.s.sic catch-22 situation. If two people want to exchange a secret message over the phone, the sender must encrypt it. To encrypt the secret message the sender must use a key, which is itself a secret, so then there is the problem of transmitting the secret key to the receiver in order to transmit the secret message. In short, before two people can exchange a secret (an encrypted message) they must already share a secret (the key).

When thinking about the problem of key distribution, it is helpful to consider Alice, Bob and Eve, three fictional characters who have become the industry standard for discussions about cryptography. In a typical situation, Alice wants to send a message to Bob, or vice versa, and Eve is trying to eavesdrop. If Alice is sending private messages to Bob, she will encrypt each one before sending it, using a separate key each time. Alice is continually faced with the problem of key distribution because she has to convey the keys to Bob securely, otherwise he cannot decrypt the messages. One way to solve the problem is for Alice and Bob to meet up once a week and exchange enough keys to cover the messages that might be sent during the next seven days. Exchanging keys in person is certainly secure, but it is inconvenient and, if either Alice or Bob is taken ill, the system breaks down. Alternatively, Alice and Bob could hire couriers, which would be less secure and more expensive, but at least they have delegated some of the work. Either way, it seems that the distribution of keys is unavoidable. For two thousand years this was considered to be an axiom of cryptography-an indisputable truth. However, there is a thought experiment that seems to defy the axiom. a week and exchange enough keys to cover the messages that might be sent during the next seven days. Exchanging keys in person is certainly secure, but it is inconvenient and, if either Alice or Bob is taken ill, the system breaks down. Alternatively, Alice and Bob could hire couriers, which would be less secure and more expensive, but at least they have delegated some of the work. Either way, it seems that the distribution of keys is unavoidable. For two thousand years this was considered to be an axiom of cryptography-an indisputable truth. However, there is a thought experiment that seems to defy the axiom.

[image]

Figure 63 Martin h.e.l.lman. ( Martin h.e.l.lman. (photo credit 6.2) Imagine that Alice and Bob live in a country where the postal system is completely immoral, and postal employees will read any unprotected correspondence. One day, Alice wants to send an intensely personal message to Bob. She puts it inside an iron box, closes it and secures it with a padlock and key. She puts the padlocked box in the post and keeps the key. However, when the box reaches Bob, he is unable to open it because he does not have the key. Alice might consider putting the key inside another box, padlocking it and sending it to Bob, but without the key to the second padlock he is unable to open the second box, so he cannot obtain the key that opens the first box. The only way around the problem seems to be for Alice to make a copy of her key and give it to Bob in advance when they meet for coffee. So far, I have just restated the same old problem in a new scenario. Avoiding key distribution seems logically impossible-surely, if Alice wants to lock something in a box so that only Bob can open it, she must give him a copy of the key. Or, in terms of cryptography, if Alice wants to encipher a message so that only Bob can decipher it, she must give him a copy of the key. Key exchange is an inevitable part of encipherment-or is it?

Now picture the following scenario. As before, Alice wants to send an intensely personal message to Bob. Again, she puts her secret message in an iron box, padlocks it and sends it to Bob. When the box arrives, Bob adds his own padlock and sends the box back to Alice. When Alice receives the box, it is now secured by two padlocks. She removes her own padlock, leaving just Bob's padlock to secure the box. Finally she sends the box back to Bob. And here is the crucial difference: Bob can now open the box because it is secured only with his own padlock, to which he alone has the key.

The implications of this little story are enormous. It demonstrates that a secret message can be securely exchanged between two people without necessarily exchanging a key. For the first time we have a suggestion that key exchange might not be an inevitable part of cryptography. We can reinterpret the story in terms of encryption. Alice uses her own key to encrypt a message to Bob, who encrypts it again with his own key and returns it. When Alice receives the doubly encrypted message, she removes her own encryption and returns it to Bob, who can then remove his own encryption and read the message.

It seems that the problem of key distribution might have been solved, because the doubly encrypted scheme requires no exchange of keys. However, there is a fundamental obstacle to implementing a system in which Alice encrypts, Bob encrypts, Alice decrypts and Bob decrypts. The problem is the order in which the encryptions and decryptions are performed. In general, the order of encryption and decryption is crucial, and should obey the maxim "last on, first off." In other words, the last stage of encryption should be the first to be decrypted. In the above scenario, Bob performed the last stage of encryption, so this should have been the first to be decrypted, but it was Alice who removed her encryption first, before Bob removed his. The importance of order is most easily grasped by examining something we do every day. In the morning we put on our socks, and then we put on our shoes, and in the evening we remove our shoes before removing our socks-it is impossible to remove the socks before the shoes. We must obey the maxim "last on, first off."

Some very elementary ciphers, such as the Caesar cipher, are so simple that order does not matter. However, in the 1970s it seemed that any form of strong encryption must always obey the "last on, first off" rule. If a message is encrypted with Alice's key and then with Bob's key, then it must be decrypted with Bob's key before it can be decrypted with Alice's key. Order is crucial even with a monoalphabetic subst.i.tution cipher. Imagine that Alice and Bob have their own keys, as shown on the next page, and let us take a look at what happens when the order is incorrect. Alice uses her key to encrypt a message to Bob, then Bob reencrypts the result using his own key; Alice uses her key to perform a partial decryption, and finally Bob attempts to use his key to perform the full decryption.

[image]

The result is nonsense. However, you can check for yourself that if the decryption order were reversed, and Bob decrypted before Alice, thus obeying the "last on, first off" rule, then the result would have been the original message. But if order is so important, why did the padlock system seem to work in the anecdote about locked boxes? The answer is that order is not important for padlocks. I can apply twenty padlocks to a box and undo them in any order, and at the end the box will open. Unfortunately, encryption systems are far more sensitive than padlocks when it comes to order.

Although the doubly padlocked box approach would not work for real-world cryptography, it inspired Diffie and h.e.l.lman to search for a practical method of circ.u.mventing the key distribution problem. They spent month after month attempting to find a solution. Although every idea ended in failure, they behaved like perfect fools and persevered. Their research concentrated on the examination of various mathematical functions functions. A function is any mathematical operation that turns one number into another number. For example, "doubling" is a type of function, because it turns the number 3 into 6, or the number 9 into 18. Furthermore, we can think of all forms of computer encryption as functions because they turn one number (the plaintext) into another number (the ciphertext).

Most mathematical functions are cla.s.sified as two-way functions because they are easy to do, and easy to undo. For example, "doubling" is a two-way function because it is easy to double a number to generate a new number, and just as easy to undo the function and get from the doubled number back to the original number. For example, if we know that the result of doubling is 26, then it is trivial to reverse the function and deduce that the original number was 13. The easiest way to understand the concept of a two-way function is in terms of an everyday activity. The act of turning on a light switch is a function, because it turns an ordinary lightbulb into an illuminated lightbulb. This function is two-way because if a switch is turned on, it is easy enough to turn it off and return the light-bulb to its original state. is a two-way function because it is easy to double a number to generate a new number, and just as easy to undo the function and get from the doubled number back to the original number. For example, if we know that the result of doubling is 26, then it is trivial to reverse the function and deduce that the original number was 13. The easiest way to understand the concept of a two-way function is in terms of an everyday activity. The act of turning on a light switch is a function, because it turns an ordinary lightbulb into an illuminated lightbulb. This function is two-way because if a switch is turned on, it is easy enough to turn it off and return the light-bulb to its original state.

However, Diffie and h.e.l.lman were not interested in two-way functions. They focused their attention on one-way functions. As the name suggests, a one-way function is easy to do but very difficult to undo. In other words, two-way functions are reversible, but one-way functions are not reversible. Once again, the best way to ill.u.s.trate a one-way function is in terms of an everyday activity. Mixing yellow and blue paint to make green paint is a one-way function because it is easy to mix the paint, but impossible to unmix it. Another one-way function is the cracking of an egg, because it is easy to crack an egg but impossible then to return the egg to its original condition. For this reason, one-way functions are sometimes called Humpty Dumpty functions.

Modular arithmetic, sometimes called clock arithmetic clock arithmetic in schools, is an area of mathematics that is rich in one-way functions. In modular arithmetic, mathematicians consider a finite group of numbers arranged in a loop, rather like the numbers on a clock. For example, in schools, is an area of mathematics that is rich in one-way functions. In modular arithmetic, mathematicians consider a finite group of numbers arranged in a loop, rather like the numbers on a clock. For example, Figure 64 Figure 64 shows a clock for modular 7 (or mod 7), which has only the 7 numbers from 0 to 6. To work out 2 + 3, we start at 2 and move around 3 places to reach 5, which is the same answer as in normal arithmetic. To work out 2 + 6 we start at 2 and move around 6 places, but this time we go around the loop and arrive at 1, which is not the result we would get in normal arithmetic. These results can be expressed as: shows a clock for modular 7 (or mod 7), which has only the 7 numbers from 0 to 6. To work out 2 + 3, we start at 2 and move around 3 places to reach 5, which is the same answer as in normal arithmetic. To work out 2 + 6 we start at 2 and move around 6 places, but this time we go around the loop and arrive at 1, which is not the result we would get in normal arithmetic. These results can be expressed as: 2 + 3 = 5 (mod 7) and 2 + 6 = 1 (mod 7) Modular arithmetic is relatively simple, and in fact we do it every day when we talk about time. If it is 9 o'clock now, and we have a meeting 8 hours from now, we would say that the meeting is at 5 o'clock, not 17 o'clock. We have mentally calculated 9 + 8 in (mod 12). Imagine a clock face, look at 9, and then move around 8 s.p.a.ces, and we end up at 5: 17 o'clock. We have mentally calculated 9 + 8 in (mod 12). Imagine a clock face, look at 9, and then move around 8 s.p.a.ces, and we end up at 5: 9 + 8 = 5 (mod 12) Rather than visualizing clocks, mathematicians often take the shortcut of performing modular calculations according to the following recipe. First, perform the calculation in normal arithmetic. Second, if we want to know the answer in (mod x), we divide the normal answer by x x and note the remainder. This remainder is the answer in (mod x). To find the answer to 11 9 (mod 13), we do the following: and note the remainder. This remainder is the answer in (mod x). To find the answer to 11 9 (mod 13), we do the following: 11 9= 99.

99 13 = 7, remainder 8 11 9= 8 (mod 13) Functions performed in the modular arithmetic environment tend to behave erratically, which in turn sometimes makes them one-way functions. This becomes evident when a simple function in normal arithmetic is compared with the same simple function in modular arithmetic. In the former environment the function will be two-way and easy to reverse; in the latter environment it will be one-way and hard to reverse. As an example, let us take the function 3x. This means take a number x, then multiply 3 by itself x x times in order to get the new number. For example, if times in order to get the new number. For example, if x x = 2, and we perform the function, then: = 2, and we perform the function, then: 3x = 3 = 32 = 3 3 = 9. = 3 3 = 9.

In other words, the function turns 2 into 9. In normal arithmetic, as the value of x x increases so does the result of the function. Hence, if we were given the result of the function it would be relatively easy to work backward increases so does the result of the function. Hence, if we were given the result of the function it would be relatively easy to work backward and deduce the original number. For example, if the result is 81, we can deduce that and deduce the original number. For example, if the result is 81, we can deduce that x x is 4, because 3 is 4, because 34 = 81. If we made a mistake and guessed that = 81. If we made a mistake and guessed that x x is 5, we could work out that 3 is 5, we could work out that 35 = 243, which tells us that our choice of = 243, which tells us that our choice of x x is too big. We would then reduce our choice of is too big. We would then reduce our choice of x x to 4, and we would have the right answer. In short, even when we guess wrongly we can home in on the correct value of x, and thereby reverse the function. to 4, and we would have the right answer. In short, even when we guess wrongly we can home in on the correct value of x, and thereby reverse the function.

[image]

Figure 64 Modular arithmetic is performed on a finite set of numbers, which can be thought of as numbers on a clock face. In this case, we can work out 6 + 5 in modular 7 by starting at 6 and moving around five s.p.a.ces, which brings us to 4. Modular arithmetic is performed on a finite set of numbers, which can be thought of as numbers on a clock face. In this case, we can work out 6 + 5 in modular 7 by starting at 6 and moving around five s.p.a.ces, which brings us to 4.

However, in modular arithmetic this same function does not behave so sensibly. Imagine that we are told that 3x in (mod 7) is 1, and we are asked to find the value of in (mod 7) is 1, and we are asked to find the value of x x. No value springs to mind, because we are generally unfamiliar with modular arithmetic. We could take a guess that x x = 5, and we could work out the result of 3 = 5, and we could work out the result of 35 (mod 7). The answer turns out to be 5, which is too big, because we are looking for an answer of just 1. We might be tempted to reduce the value of (mod 7). The answer turns out to be 5, which is too big, because we are looking for an answer of just 1. We might be tempted to reduce the value of x x and try again. But we would be heading in the wrong direction, because the actual answer is and try again. But we would be heading in the wrong direction, because the actual answer is x x = 6. = 6.

In normal arithmetic we can test numbers and can sense whether we are getting warmer or colder. The environment of modular arithmetic gives no helpful clues, and reversing functions is much harder. Often, the only way to reverse a function in modular arithmetic is to compile a table by calculating the function for many values of x x until the right answer is found. until the right answer is found. Table 25 Table 25 shows the result of calculating several values of the function in both normal arithmetic and modular arithmetic. It clearly demonstrates the erratic behavior of the function when calculated in modular arithmetic. Although drawing up such a table is only a little tedious when we are dealing with relatively small numbers, it would be excruciatingly painful to build a table to deal with a function such as 453 shows the result of calculating several values of the function in both normal arithmetic and modular arithmetic. It clearly demonstrates the erratic behavior of the function when calculated in modular arithmetic. Although drawing up such a table is only a little tedious when we are dealing with relatively small numbers, it would be excruciatingly painful to build a table to deal with a function such as 453x (mod 21,997). This is a cla.s.sic example of a one-way function, because I could pick a value for (mod 21,997). This is a cla.s.sic example of a one-way function, because I could pick a value for x x and calculate the result of the function, but if I gave you a and calculate the result of the function, but if I gave you a result, say 5,787, you would have enormous difficulty in reversing the function and deducing my choice of x. It took me just seconds to do my calculation and generate 5,787, but it would take you hours to draw up the table and work out my choice of result, say 5,787, you would have enormous difficulty in reversing the function and deducing my choice of x. It took me just seconds to do my calculation and generate 5,787, but it would take you hours to draw up the table and work out my choice of x x.

Table 25 Values of the function 3 Values of the function 3x calculated in normal arithmetic (row 2) and modular arithmetic (row 3). The function increases continuously in normal arithmetic, but is highly erratic in modular arithmetic. calculated in normal arithmetic (row 2) and modular arithmetic (row 3). The function increases continuously in normal arithmetic, but is highly erratic in modular arithmetic.

[image]

After two years of focusing on modular arithmetic and one-way functions, h.e.l.lman's foolishness began to pay off. In the spring of 1976 he hit upon a strategy for solving the key exchange problem. In half an hour of frantic scribbling, he proved that Alice and Bob could agree on a key without meeting, thereby disposing of an axiom that had lasted for centuries. h.e.l.lman's idea relied on a one-way function of the form Y Yx (mod (mod P P). Initially, Alice and Bob agree on values for Y Y and and P P. Almost any values are fine, but there are some restrictions, such as Y Y being smaller than being smaller than P P. These values are not secret, so Alice can telephone Bob and suggest that, say, Y Y = 7 and = 7 and P P = 11. Even if the telephone line is insecure and nefarious Eve hears this conversation, it does not matter, as we shall see later. Alice and Bob have now agreed on the one-way function 7 = 11. Even if the telephone line is insecure and nefarious Eve hears this conversation, it does not matter, as we shall see later. Alice and Bob have now agreed on the one-way function 7x (mod 11). At this point they can begin the process of trying to establish a secret key without meeting. Because they work in parallel, I explain their actions in the two columns of (mod 11). At this point they can begin the process of trying to establish a secret key without meeting. Because they work in parallel, I explain their actions in the two columns of Table 26 Table 26.

Having followed the stages in Table 26 Table 26, you will see that, without meeting, Alice and Bob have agreed on the same key, which they can use to encipher a message. For example, they could use their number, 9, as the key for a DES encryption. (DES actually uses much larger numbers as the key, and the exchange process described in Table 26 Table 26 would be performed with much larger numbers, resulting in a suitably large DES key.) By using h.e.l.lman's scheme, Alice and Bob have been able to agree on a key, yet they did not have to meet up and whisper the key to each other. The extraordinary achievement is that the secret key was agreed via an exchange of information on a normal telephone line. But if Eve tapped this line, then surely she also knows the key? would be performed with much larger numbers, resulting in a suitably large DES key.) By using h.e.l.lman's scheme, Alice and Bob have been able to agree on a key, yet they did not have to meet up and whisper the key to each other. The extraordinary achievement is that the secret key was agreed via an exchange of information on a normal telephone line. But if Eve tapped this line, then surely she also knows the key?

Let us examine h.e.l.lman's scheme from Eve's point of view. If she is tapping the line, she knows only the following facts: that the function is 7x (mod 11), that Alice sends = 2 and that Bob sends = 4. In order to find the key, she must either do what Bob does, which is turn into the key by knowing B, or do what Alice does, which is turn into the key by knowing A. However, Eve does not know the value of (mod 11), that Alice sends = 2 and that Bob sends = 4. In order to find the key, she must either do what Bob does, which is turn into the key by knowing B, or do what Alice does, which is turn into the key by knowing A. However, Eve does not know the value of A A or or B B because because Alice and Bob have not exchanged these numbers, and have kept them secret. Eve is stymied. She has only one hope: in theory, she could work out Alice and Bob have not exchanged these numbers, and have kept them secret. Eve is stymied. She has only one hope: in theory, she could work out A A from , because was a consequence of putting from , because was a consequence of putting A A into a function, and Eve knows the function. Or she could work out into a function, and Eve knows the function. Or she could work out B B from , because was a consequence of putting from , because was a consequence of putting B B into a function, and once again Eve knows the function. Unfortunately for Eve, the function is one-way, so whereas it was easy for Alice to turn into a function, and once again Eve knows the function. Unfortunately for Eve, the function is one-way, so whereas it was easy for Alice to turn A A into and for Bob to turn into and for Bob to turn B B into , it is very difficult for Eve to reverse the process, especially if the numbers are very large. into , it is very difficult for Eve to reverse the process, especially if the numbers are very large.

Table 26 The general one-way function is The general one-way function is Y Yx (mod (mod P P). Alice and Bob have chosen values for Y Y and and P P, and hence have agreed on the one-way function 7 7x (mod 11). (mod 11).

[image]

Bob and Alice exchanged just enough information to allow them to establish a key, but this information was insufficient for Eve to work out the key. As an a.n.a.logy for h.e.l.lman's scheme, imagine a cipher that somehow uses color as the key. First, let us a.s.sume that everybody, including Alice, Bob and Eve, has a three-liter pot containing one liter of yellow paint. If Alice and Bob want to agree on a secret key, each of them adds one liter of their own secret color to their own pot. Alice might add a peculiar shade of purple, while Bob might add crimson. Each sends their own mixed pot to the other. Finally, Alice takes Bob's mixture and adds one liter of her own secret color, and Bob takes Alice's mixture and adds one liter of his own secret color. Both pots should now be the same color, because they both contain one liter of yellow, one liter of purple and one liter of crimson. It is the exact color of the doubly contaminated pots that is used as the key. Alice has no idea what color was added by Bob, and Bob has no idea what color was added by Alice, but they have both achieved the same end. Meanwhile, Eve is furious. Even if she intercepts the intermediate pots she cannot work out the color of the final pots, which is the agreed key. She might see the color of the mixed pot containing yellow and Alice's secret color on its way to Bob, and she might see the color of the mixed pot containing yellow and Bob's secret color on its way to Alice, but in order to work out the key she really needs to know Alice and Bob's original secret colors. However, Eve cannot work out Alice and Bob's secret colors by looking at the mixed pots. Even if she takes a sample from one of the mixed paints, she cannot unmix the paint to find out the secret color, because mixing paint is a one-way function.

h.e.l.lman's breakthrough came while he was working at home late one night, so by the time he had finished his calculations it was too late to call Diffie and Merkle. He had to wait until the following morning to reveal his discovery to the only two other people in the world who had believed that a solution to the key distribution problem was even possible. "The muse whispered to me," says h.e.l.lman, "but we all laid the foundations together." Diffie immediately recognized the power of h.e.l.lman's breakthrough: "Marty explained his system of key exchange in all its unnerving simplicity. Listening to him, I realized that the notion had been at the edge of my mind for some time, but had never really broken through." Diffie and Merkle. He had to wait until the following morning to reveal his discovery to the only two other people in the world who had believed that a solution to the key distribution problem was even possible. "The muse whispered to me," says h.e.l.lman, "but we all laid the foundations together." Diffie immediately recognized the power of h.e.l.lman's breakthrough: "Marty explained his system of key exchange in all its unnerving simplicity. Listening to him, I realized that the notion had been at the edge of my mind for some time, but had never really broken through."

The Diffie-h.e.l.lman-Merkle key exchange scheme, as it is known, enables Alice and Bob to establish a secret via public discussion. It is one of the most counterintuitive discoveries in the history of science, and it forced the cryptographic establishment to rewrite the rules of encryption. Diffie, h.e.l.lman and Merkle publicly demonstrated their discovery at the National Computer Conference in June 1976, and astonished the audience of cryptoexperts. The following year they filed for a patent. Henceforth, Alice and Bob no longer had to meet in order to exchange a key. Instead, Alice could just call Bob on the phone, exchange a couple of numbers with him, mutually establish a secret key and then proceed to encrypt.

Although Diffie-h.e.l.lman-Merkle key exchange was a gigantic leap forward, the system was not perfect because it was inherently inconvenient. Imagine that Alice lives in Hawaii, and that she wants to send an e-mail to Bob in Istanbul. Bob is probably asleep, but the joy of e-mail is that Alice can send a message at any time, and it will be waiting on Bob's computer when he wakes up. However, if Alice wants to encrypt her message, then she needs to agree a key with Bob, and in order to perform the key exchange it is preferable for Alice and Bob to be on-line at the same time-establis.h.i.+ng a key requires a mutual exchange of information. In effect, Alice has to wait until Bob wakes up. Alternatively, Alice could transmit her part of the key exchange, and wait 12 hours for Bob's reply, at which point the key is established and Alice can, if she is not asleep herself, encrypt and transmit the message. Either way, h.e.l.lman's key exchange system hinders the spontaneity of e-mail.

h.e.l.lman had shattered one of the tenets of cryptography and proved that Bob and Alice did not have to meet to agree a secret key. Next, somebody merely had to come up with a more efficient scheme for overcoming the problem of key distribution.

The Birth of Public Key Cryptography Mary Fisher has never forgotten the first time that Whitfield Diffie asked her out on a date: "He knew I was a s.p.a.ce buff, so he suggested we go and see a launch. Whit explained that he was leaving that evening to see Skylab take off, and so we drove all night, and we got there at about 3 A.M. The bird was on the path, as they used to say in those days. Whit had press credentials, but I didn't. So when they asked for my identification and asked who I was, Whit said 'My wife.' That was 16 November 1973." They did eventually marry, and during the early years Mary supported her husband during his cryptographic meditations. Diffie was still being employed as a graduate student, which meant that he received only a meager salary. Mary, an archaeologist by training, took a job with British Petroleum in order to make ends meet.

While Martin h.e.l.lman had been developing his method of key exchange, Whitfield Diffie had been working on a completely different approach to solving the problem of key distribution. He often went through long periods of barren contemplation, and on one occasion in 1975 he became so frustrated that he told Mary that he was just a failed scientist who would never amount to anything. He even told her that she ought to find someone else. Mary told him that she had absolute faith in him, and just two weeks later Diffie came up with his truly brilliant idea.

He can still recall how the idea flashed into his mind, and then almost vanished: "I walked downstairs to get a c.o.ke, and almost forgot about the idea. I remembered that I'd been thinking about something interesting, but couldn't quite recall what it was. Then it came back in a real adrenaline rush of excitement. I was actually aware for the first time in my work on cryptography of having discovered something really valuable. Everything that I had discovered in the subject up to this point seemed to me to be mere technicalities." It was midafternoon, and he had to wait a couple of hours before Mary returned. "Whit was waiting at the door," she recalls. "He said he had something to tell me and he had a funny look on his face. I walked in and he said, 'Sit down, please, I want to talk to you. I believe that I have made a great discovery-I know I am the first person to have done this.' The world stood still for me at that moment. I felt like I was living in a Hollywood film."

Diffie had concocted a new type of cipher, one that incorporated a so-called asymmetric key asymmetric key. So far, all the encryption techniques described in this book have been symmetric symmetric, which means that the unscrambling process is simply the opposite of scrambling. For example, the Enigma machine uses a certain key setting to encipher a message, and the receiver uses an identical machine in the same key setting to decipher it. Similarly, DES encipherment uses a key to perform 16 rounds of scrambling, and then DES decipherment uses the same key to perform the 16 rounds in reverse. Both sender and receiver effectively have equivalent knowledge, and they both use the same key to encrypt and decrypt-their relations.h.i.+p is symmetric. On the other hand, in an asymmetric key system, as the name suggests, the encryption key and the decryption key are not identical. In an asymmetric cipher, if Alice knows the encryption key she can encrypt a message, but she cannot decrypt a message. In order to decrypt, Alice must have access to the decryption key. This distinction between the encryption and decryption keys is what makes an asymmetric cipher special.

At this point it is worth stressing that although Diffie had conceived of the general concept of an asymmetric cipher, he did not actually have a specific example of one. However, the mere concept of an asymmetric cipher was revolutionary. If cryptographers could find a genuine working asymmetric cipher, a system that fulfilled Diffie's requirements, then the implications for Alice and Bob would be enormous. Alice could create her own pair of keys: an encryption key and a decryption key. If we a.s.sume that the asymmetric cipher is a form of computer encryption, then Alice's encryption key is a number, and her decryption key is a different number. Alice keeps the decryption key secret, so it is commonly referred to as Alice's private key private key. However, she publishes the encryption key so that everybody has access to it, which is why it is commonly referred to as Alice's public key public key. If Bob wants to send Alice a message, he simply looks up her public key, which would be listed in something akin to a telephone directory. Bob then uses Alice's public key to encrypt the message. He sends the encrypted message to Alice, and when it arrives Alice can decrypt it using her private decryption key. Similarly, if Charlie, Dawn or Edward want to send Alice an encrypted message, they too can look up Alice's public encryption key, and in each case only Alice has access to the private decryption key required to decrypt the messages.

The great advantage of this system is that there is no toing and froing, as there is with Diffie-h.e.l.lmanMerkle key exchange. Bob does not have to wait to get information from Alice before he can encrypt and send a message to her, he merely has to look up her public encryption key. Furthermore, the asymmetric cipher still overcomes the problem of key distribution. Alice does not have to transport the public encryption key securely to Bob: in complete contrast, she can now publicize her public encryption key as widely as possible. She wants the whole world to know her public encryption key so that anybody can use it to send her encrypted messages. At the same time, even if the whole world knows Alice's public key, none of them, including Eve, can decrypt any messages encrypted with it, because knowledge of the public key will not help in decryption. In fact, once Bob has encrypted a message using Alice's public key, even he cannot decrypt it. Only Alice, who possesses the private key, can decrypt the message.

This is the exact opposite of a traditional symmetric cipher, in which Alice has to go to great lengths to transport the encryption key securely to Bob. In a symmetric cipher the encryption key is the same as the decryption key, so Alice and Bob must take enormous precautions to ensure that the key does not fall into Eve's hands. This is the root of the key distribution problem.

Returning to padlock a.n.a.logies, asymmetric cryptography can be thought of in the following way. Anybody can close a padlock simply by clicking it shut, but only the person who has the key can open it. Locking (encryption) is easy, something everybody can do, but unlocking (decryption) can be done only by the owner of the key. The trivial knowledge of knowing how to click the padlock shut does not tell you how to unlock it. Taking the a.n.a.logy further, imagine that Alice designs a padlock and key. She guards the key, but she manufactures thousands of replica padlocks and distributes them to post offices all over the world. If Bob wants to send a message, he puts it in a box, goes to the local post office, asks for an "Alice padlock" and padlocks the box. Now he is unable to unlock the box, but when Alice receives it she can open it with her unique key. The padlock and the process of clicking it shut is equivalent to the public encryption key, because everyone has access to the padlocks, and everyone can use a padlock to seal a message in a box. The padlock's key is equivalent to the private decryption key, because only Alice has it, only she can open the padlock, and only she can gain access to the message in the box. can use a padlock to seal a message in a box. The padlock's key is equivalent to the private decryption key, because only Alice has it, only she can open the padlock, and only she can gain access to the message in the box.

The system seems simple when it is explained in terms of padlocks, but it is far from trivial to find a mathematical function that does the same job, something that can be incorporated into a workable cryptographic system. To turn asymmetric ciphers from a great idea into a practical invention, somebody had to discover an appropriate mathematical function. Diffie envisaged a special type of one-way function, one that could be reversed under exceptional circ.u.mstances. In Diffie's asymmetric system, Bob encrypts the message using the public key, but he is unable to decrypt it-this is essentially a one-way function. However, Alice is able to decrypt the message because she has the private key, a special piece of information that allows her to reverse the function. Once again, padlocks are a good a.n.a.logy-shutting the padlock is a one-way function, because in general it is hard to open the padlock unless you have something special (the key), in which case the function is easily reversed.

Diffie published an outline of his idea in the summer of 1975, whereupon other scientists joined the search for an appropriate one-way function, one that fulfilled the criteria required for an asymmetric cipher. Initially there was great optimism, but by the end of the year n.o.body had been able to find a suitable candidate. As the months pa.s.sed, it seemed increasingly likely that special one-way functions did not exist. It seemed that Diffie's idea worked in theory but not in practice. Nevertheless, by the end of 1976 the team of Diffie, h.e.l.lman and Merkle had revolutionized the world of cryptography. They had persuaded the rest of the world that there was a solution to the key distribution problem, and had created Diffieh.e.l.lmanMerkle key exchange-a workable but imperfect system. They had also proposed the concept of an asymmetric cipher-a perfect but as yet unworkable system. They continued their research at Stanford University, attempting to find a special one-way function that would make asymmetric ciphers a reality. However, they failed to make the discovery. The race to find an asymmetric cipher was won by another trio of researchers, based 5,000 km away on the East Coast of America.

Prime Suspects "I walked into Ron Rivest's office," recalls Leonard Adleman, "and Ron had this paper in his hands. He started saying, 'These Stanford guys have this really blah, blah, blah.' And I remember thinking, 'That's nice, Ron, but I have something else I want to talk about.' I was entirely unaware of the history of cryptography and I was distinctly uninterested in what he was saying." The paper that had made Ron Rivest so excited was by Diffie and h.e.l.lman, and it described the concept of asymmetric ciphers. Eventually Rivest persuaded Adleman that there might be some interesting mathematics in the problem, and together they resolved to try to find a one-way function that fitted the requirements of an asymmetric cipher. They were joined in the hunt by Adi Shamir. All three men were researchers on the eighth floor of the MIT Laboratory for Computer Science.

Rivest, Shamir and Adleman formed a perfect team. Rivest is a computer scientist with a tremendous ability to absorb new ideas and apply them in unlikely places. He always kept up with the latest scientific papers, which inspired him to come up with a whole series of weird and wonderful candidates for the one-way function at the heart of an asymmetric cipher. However, each candidate was flawed in some way. Shamir, another computer scientist, has a lightning intellect and an ability to see through the debris and focus on the core of a problem. He too regularly generated ideas for formulating an asymmetric cipher, but his ideas were also inevitably flawed. Adleman, a mathematician with enormous stamina, rigor and patience, was largely responsible for spotting the flaws in the ideas of Rivest and Shamir, ensuring that they did not waste time following false leads. Rivest and Shamir spent a year coming up with new ideas, and Adleman spent a year shooting them down. The threesome began to lose hope, but they were unaware that this process of continual failure was a necessary part of their research, gently steering them away from sterile mathematical territory and toward more fertile ground. In due course, their efforts were rewarded.

In April 1977, Rivest, Shamir and Adleman spent Pa.s.sover at the house of a student, and had consumed significant amounts of Manischewitz wine before returning to their respective homes some time around midnight. Rivest, unable to sleep, lay on his couch reading a mathematics textbook. He began mulling over the question that had been puzzling him for weeks-is it possible to build an asymmetric cipher? Is it possible to find a one-way function that can be reversed only if the receiver has some special information? Suddenly, the mists began to clear and he had a revelation. He spent the rest of that night formalizing his idea, effectively writing a complete scientific paper before daybreak. Rivest had made a breakthrough, but it had grown out of a yearlong collaboration with Shamir and Adleman, and it would not have been possible without them. Rivest finished off the paper by listing the authors alphabetically; Adleman, Rivest, Shamir. textbook. He began mulling over the question that had been puzzling him for weeks-is it possible to build an asymmetric cipher? Is it possible to find a one-way function that can be reversed only if the receiver has some special information? Suddenly, the mists began to clear and he had a revelation. He spent the rest of that night formalizing his idea, effectively writing a complete scientific paper before daybreak. Rivest had made a breakthrough, but it had grown out of a yearlong collaboration with Shamir and Adleman, and it would not have been possible without them. Rivest finished off the paper by listing the authors alphabetically; Adleman, Rivest, Shamir.

The next morning, Rivest handed the paper to Adleman, who went through his usual process of trying to tear it apart, but this time he could find no faults. His only criticism was with the list of authors. "I told Ron to take my name off the paper," recalls Adleman. "I told him that it was his invention, not mine. But Ron refused and we got into a discussion about it. We agreed that I would go home and contemplate it for one night, and consider what I wanted to do. I went back the next day and suggested to Ron that I be the third author. I recall thinking that this paper would be the least interesting paper that I will ever be on." Adleman could not have been more wrong. The system, dubbed RSA (Rivest, Shamir, Adleman) as opposed to ARS, went on to become the most influential cipher in modern cryptography. (Rivest, Shamir, Adleman) as opposed to ARS, went on to become the most influential cipher in modern cryptography.

[image]

Figure 65 Ronald Rivest, Adi Shamir and Leonard Adleman. ( Ronald Rivest, Adi Shamir and Leonard Adleman. (photo credit 6.3) Before exploring Rivest's idea, here is a quick reminder of what scientists were looking for in order to build an asymmetric cipher: (1) Alice must create a public key, which she would then publish so that Bob (and everybody else) can use it to encrypt messages to her. Because the public key is a one-way function, it must be virtually impossible for anybody to reverse it and decrypt Alice's messages.

(2) However, Alice needs to decrypt the messages being sent to her. She must therefore have a private key, some special piece of information, which allows her to reverse the effect of the public key. Therefore, Alice (and Alice alone) has the power to decrypt any messages sent to her.

At the heart of Rivest's asymmetric cipher is a one-way function based on the sort of modular functions described earlier in the chapter. Rivest's one-way function can be used to encrypt a message-the message, which is effectively a number, is put into the function, and the result is the ciphertext, another number. I shall not describe Rivest's one-way function in detail (for which see Appendix J Appendix J), but I shall explain one particular aspect of it, known simply as N N, because it is N N that makes this one-way function reversible under certain circ.u.mstances, and therefore ideal for use as an asymmetric cipher. that makes this one-way function reversible under certain circ.u.mstances, and therefore ideal for use as an asymmetric cipher.

N is important because it is a flexible component of the one-way function, which means that each person can choose a different value of is important because it is a flexible component of the one-way function, which means that each person can choose a different value of N N, and personalize the one-way function. In order to choose her personal value of N N, Alice picks two prime numbers, p p and and q q, and multiplies them together. A prime number is one that has no divisors except itself and 1. For example, 7 is a prime number because no numbers except 1 and 7 will divide into it without leaving a remainder. Likewise, 13 is a prime number because no numbers except 1 and 13 will divide into it without leaving a remainder. However, 8 is not a prime number, because it can be divided by 2 and 4.

So, Alice