Hi,
Recently I came across a good puzzle. It says "what is lowest possible number which when divided by 2,3,5,7,9 and 11 leaves remainder 1,2,3,4,5 and 6 respectively".
In this puzzle method and approach is more important than answer.
Give it a shot.
Agry
Tuesday, September 25, 2007
Tuesday, September 18, 2007
The Code Book by Simon Singh - Concepts
Recently I read this book and I was really amazed by the concepts of cryptography. Frankly speaking I never thought that this field of mathematics can be so interesting. This particular post describes concepts used in Modern cryptography. Since Julius Caesar, who is supposed to be the first one who used encryption, all the cryptic algorithms faced the problem of Key Distribution i.e. how to send key, used for encryption, to the desired receiver.
Bob, Alice and Eve
Problem of key distribution can be described with the help of 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.
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 en-cipherment 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. 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 this system. The problem is the order in which the encryptions and decryptions are performed, which 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."
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. Although the doubly padlocked box approach would not work for real-world cryptography, it inspired Diffie and Hellman to search for a practical method of circumventing the key distribution problem.
Their research concentrated on the examination of various mathematical functions. Most mathematical functions are classified 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. However, Diffie and Hellman 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 illustrate a one-way function is in terms of an everyday activity. Cracking of an egg is a one-way function, 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 dock 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. 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. 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 and note the remainder. This remainder is the answer in (mod x). To find the answer to 11x9 (mod 13), we do the following:
11 x 9=99 à 99 /13= 7, remainder 8
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 times in order to get the new number. For example, if x = 2, and we perform the function, then:
3^ = 32 = 3x3 = 9.
Hence, if we were given the result of the function it would be relatively easy to work back- ward and deduce the original number. 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 x. No value springs to mind, because we are generally unfamiliar with modular arithmetic. We could take a guess that x= 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 x and try again. But we would be heading in the wrong direction, because the actual answer is x= 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 until the right answer is found. It is a classic example of a one-way function, because I could pick a value for x 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 x.
After two years of focusing on modular arithmetic and one-way functions, Hellman'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. Hellman's idea relied on a one-way function of the form Yx (mod P). Initially, Alice and Bob agree on values for Y and P. Almost any values are fine, but there are some restrictions, such as Y being smaller than P. These values are not secret, so Alice can telephone Bob and suggest that, say, Y= 7 and 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 lx (mod 11). At this point they can begin the process of trying to establish a secret key without meeting. By using Hellman'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 Hellman's scheme from Eve's point of view.
If she is tapping the line, she knows only the following facts: that the function is lx (mod 11), that Alice sends a = 2 and that Bob sends b = 4. In order to find the key, she must either do what Bob does, which is turn a into the key by knowing b, or do what Alice does, which is turn b into the key by knowing A. However, Eve does not know the value of A or B 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 A from a, because ‘a’ was a consequence of putting A into a function, and Eve knows the function. Or she could work out B from b, because 3 was a consequence of putting 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 A into ‘a’ and for Bob to turn B into ‘b’, it is very difficult for Eve to reverse the process, especially if the numbers are very large. 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 analogy for Hellman's scheme, imagine a cipher that somehow uses color as the key. First, let us assume 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. The Diffie-Hellman-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. 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-Hellman-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 email 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--establishing 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, Hellman's key exchange system hinders the spontaneity of email.
The Birth of Public Key Cryptography
So far, all the encryption techniques discovered have been 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. Both sender and receiver effectively have equivalent knowledge, and they both use the same key to encrypt and decrypt-their relationship 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 assume 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. 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. 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 wants 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-Hellman-Merkle 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 analogies, 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 dene 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 analogy 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 every one 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 circumstances. 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 analogy-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 nobody had been able to find a suitable candidate. As the months passed, 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, Hellman 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 Diffie-Hellman-Merkle 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.
In April 1977, Rivest, Shamir and Adleman spent Passover 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? 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.
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, but I shall explain one particular aspect of it, known simply as N, because it is N that makes this one-way function reversible under certain circumstances, 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 N, and personalizes the one-way function.
In order to choose her personal value of N, Alice picks two prime numbers, p and q, and multiplies them together. So, Alice could choose her prime numbers to be p = 17,159 and q = 10,247. Multiplying these two numbers together gives N = 17,159 * 10,247 = 175,828,273. Alice's choice of N effectively becomes her public encryption key, and she could print it on her business card, post it on the
Internet, or publish it in a public key directory along with everybody else's value of N. If Bob wants to encrypt a message to Alice, he looks up Alice's value of N (175,828,273) and then inserts it into the general form of the one-way function, which would also be public knowledge. Bob now has a one-way function tailored with Alice's public key, so it could be called Alice's one-way function. To encrypt a message to Alice, he takes Alice's one-way function, inserts the message, notes down the result and sends it to Alice. At this point the encrypted message is secure because nobody can decipher it. The message has been encrypted with a one-way function, so reversing the one-way function and decrypting the message is, by definition, very difficult. However, the question remains-how can Alice decrypt the message?
In order to read messages sent to her, Alice must have a way of reversing the one-way function. She needs to have access to some special piece of information that allows her to decrypt the message. Fortunately for Alice, Rivest designed the one-way function so that it is reversible to someone who knows the values off and q, the two prime numbers that are multiplied together to give N. Although
Alice has told the world that her value for N is 175,828,273, she has not revealed her values for p and q, so only she has the special information required to decrypt her own messages. We can think of N as the public key, the information that is available to everybody, the information required to encrypt messages to Alice. Whereas, p and q is the private key, available only to Alice, the information required to decrypt these messages. The exact details of how p and q can be used to reverse the one-way function are outlined in Appendix J. However, there is one question that must be addressed immediately. If everybody knows N, the public key, and then surely people can deduce p and q, the private key, and read Alice's messages? After all, N was created from p and q. In fact, it turns out that if
N is large enough, it is virtually impossible to deduce p and q from N, and this is perhaps the most beautiful and elegant aspect of the RSA asymmetric cipher.
Alice created N by choosing p and q, and then multiplying them together. The fundamental point is that this is in itself a one-way function. To demonstrate the one-way nature of multiplying primes, we can take two prime numbers, such as 9,419 and 1,933, and multiply them together. With a calculator it takes just a few seconds to get the answer, 18,206,927. However, if instead we were given 18,206,927 and asked to find the prime factors (the two numbers that were multiplied to give 18,206,927) it would take us much longer. If you doubt the difficulty of finding prime factors, then consider the following. It took me just ten seconds to generate the number 1,709,023, but it will take you and a calculator the best part of an afternoon to work out the prime factors. This system of asymmetric cryptography, known as RSA, is said to be a form of public key cryptography. To find out how secure RSA is, we can examine it from Eve's point of view, and try to break a message from Alice to Bob. To encrypt a message to Bob, Alice must look up Bob's public key. To create his public key, Bob picked his own prime numbers, pB and qB, and multiplied them together to get NB. He has kept pB and qB secret, because these make up his private decryption key, but he has published NB, which is equal to 408,508,091. So Alice inserts Bob's public key NB into the general one-way encryption function, and then encrypts her message to him. When the encrypted message arrives, Bob can reverse the function and decrypt it using his values for pB and qB, which make up his private key.
Meanwhile, Eve has intercepted the message en route. Her only hope of decrypting the message is to reverse the one-way function, and this is possible only if she knows pB and qB. Bob has kept pB and qB secret, but Eve, like everybody else, knows NB is 408,508,091. Eve then attempts to deduce the values for pB and qB by working out which numbers would need to be multiplied together to get 408,508,091, a process known as factoring. Factoring is very time-consuming, but exactly how long would it take Eve to find the factors of 408,508,091? There are various recipes for trying to factor NB. Although some recipes are faster than others, they all essentially involve checking each prime number to see if it divides into NB without a remainder. For example, 3 is a prime number, but it is not a factor of 408,508,091 because 3 will not perfectly divide into 408,508,091. So Eve moves on to the next prime number, 5. Similarly, 5 is not a factor, so Eve moves on to the next prime number, and so on. Eventually, Eve arrives at 18,313, the 2,000th prime number, which is indeed a factor of 408,508,091. Having found one factor, it is easy to find the other one, which turns out to be 22,307. If Eve had a calculator and was able to check four primes a minute, then it would have taken her 500 minutes, or more than 8 hours, to find pB and qB. This is not a very high level of security, but Bob could have chosen much larger prime numbers and increased the security of his private key. For example, he could have chosen primes that are as big as 10^5. This would have resulted in a value for N that would have been roughly 1065 x 1065, which is 10130. A computer could multiply the two primes and generate N in just a second, but if Eve wanted to reverse the process and work out p and q, it would take inordinately longer. Exactly how long depends on the speed of Eve's computer. Security expert Sim-son Garfmkel estimated that a 100 MHz Intel Pentium computer with 8 MB of RAM would take roughly 50 years to factor a number as big as 10130.
Cryptographers tend to have a paranoid streak and consider worst-case scenarios, such as a worldwide conspiracy to crack their ciphers. So, Garfinkel considered what would happen if a hundred million personal computers (the number sold in 1995) ganged up together. The result is that a number as big as 10130 could be factored in about 15 seconds. Consequently, it is now generally accepted that for genuine security it is necessary to use even larger primes. For important banking transactions, N tends to be at least 10308.
The combined efforts of a hundred million personal computers would take more than one thousand years to crack such a cipher. With Sufficiently large values off and q, RSA is impregnable. The only caveat for the security of RSA public key cryptography is that at some time in the future somebody might find a quick way to factor N. It is conceivable that a decade from now, or even tomorrow, somebody will discover a method for rapid factoring, and thereafter RSA will become useless. However, for over two thousand years mathematicians have tried and failed to find a shortcut, and at the moment factoring remains an enormously time-consuming calculation. Most mathematicians believe that factoring is an inherently difficult task, and that there is some mathematical law that forbids any shortcut.
PGP and Digital signature
Today, electronic mail is gradually replacing conventional paper mail, and is soon to be the norm for everyone, not the novelty it is today. Unlike paper mail, email messages are just too easy to intercept and scan for interesting keywords. This can be done easily, routinely, automatically, and undetectably on a grand scale. This is analogous to driftnet fishing-making a quantitative and qualitative Orwellian difference to the health of democracy. The difference between ordinary and digital mail can be illustrated by imagining that Alice wants to send out invitations to her birthday party, and that Eve, who has not been invited, wants to know the time and place
of the party. If Alice uses the traditional method of posting letters, then it is very difficult for Eve to intercept one of the invitations. To start with, Eve does not know where Alice's invitations entered the postal system, because Alice could use any postbox in the city. Her only hope for intercepting one of the invitations is to somehow identify the address of one of Alice's friends, and infiltrate the local sorting office. She then has to check each and every letter manually. If she does manage to find a letter from Alice, she will have to steam it open in order to get the information she wants, and then return it to its original condition to avoid any suspicion of tampering. In comparison, Eve's task is made considerably easier if Alice sends her invitations by e-mail. As the messages leave Alice's computer, they will go to a local server, a main entry point for the Internet; if Eve is clever enough, she can hack into that local server without leaving her home. The invitations will carry Alice's e-mail address, and it would be a trivial matter to set up an electronic sieve that looks for e-mails containing Alice's address. Once an invitation has been found, there is no envelope to open, and so no problem in reading it. Furthermore, the invitation can be sent on its way without it showing any sign of having been intercepted. Alice would be oblivious to what was going on. However, there is a way to prevent Eve from reading Alice's e-mails, namely encryption.
If Alice wants to use RSA to encrypt a message to Bob, she looks up his public key and then applies RSA's one-way function to the message. Conversely, Bob decrypts the ciphertext by using his private key to reverse RSA's one-way function. Both processes require considerable mathematical manipulation, so encryption and decryption can, if the message is long, take several minutes on a personal computer. If Alice is sending a hundred messages a day, she cannot afford to spend several minutes encrypting each one. To speed up encryption and decryption, Zimmermann employed a neat trick that used asymmetric RSA encryption in tandem with old-fashioned symmetric encryption. Traditional symmetric encryption can be just as secure as asymmetric encryption, and it is much quicker to perform, but symmetric encryption suffers from the problem of having to distribute the key, which has to be securely transported from the sender to the receiver. This is where RSA comes to the rescue, because RSA can be used to encrypt the symmetric key.
Zimmermann pictured the following scenario. If Alice wants to send an encrypted message to Bob, she begins by encrypting it with a symmetric cipher. Zimmermann suggested using a cipher known as IDEA, which is similar to DES. To encrypt with IDEA, Alice needs to choose a key, but for Bob to decrypt the message Alice somehow has to get the key to Bob. Alice overcomes this problem by looking up Bob's RSA public key, and then uses it to encrypt the IDEA key. So, Alice ends up sending two things to Bob: the message encrypted with the symmetric IDEA cipher and the IDEA key encrypted with the asymmetric RSA cipher. At the other end, Bob uses his RSA private key to decrypt the IDEA key, and then uses the IDEA key to decrypt the message. This might seem convoluted, but the advantage is that the message, which might contain a large amount of information, is being encrypted with a quick symmetric cipher, and only the symmetric IDEA key, which consists of a relatively small amount of information, is being encrypted with a slow asymmetric cipher. Zimmermann planned to have this combination of RSA and IDEA within the PGP product, but the user-friendly interface would mean that the user would not have to get involved in the nuts and bolts of what was going on. Having largely solved the speed problem, Zimmermann also incorporated a series of handy features into PGP. For example, before using the RSA component of PGP, Alice needs to generate her own private key and public key. Key generation is not trivial, because it requires finding a pair of giant primes. However, Alice only has to wiggle her mouse in an erratic manner, and the PGP program will go ahead and create her private key and public key--the mouse movements introduce a random factor which PGP utilizes to ensure that every user has their own distinct pair of primes, and therefore their own unique private key and public key. Thereafter Alice merely has to publicize her public key.
Another helpful aspect of PGP is its facility for digitally signing an email. Ordinarily e-mail does not carry a signature, which means that it is impossible to verify the true author of an electronic message. For example, if Alice uses e-mail to send a love letter to Bob, she normally encrypts it with his public key, and when he receives it he decrypts it with his private key. Bob is initially flattered, but how can he be sure that the love letter is really from Alice? Perhaps the malevolent Eve wrote the email and typed Alice's name at the bottom. Without the reassurance of a handwritten ink signature, there is no obvious way to verify the authorship. In order to develop trust on the Internet, it is essential that there is some form of reliable digital signature. The PGP digital signature is based on a principle that was first developed by Whitfield Diffie and Martin Hellman. When they proposed the idea of separate public keys and private keys, they realized that, in addition to solving the key distribution problem, their invention would also provide a natural mechanism for generating e-mail signatures. Now we now that the public key is for encrypting and the private key for decrypting. In fact the process can be swapped around, so that the private key is used for encrypting and the public key is used for decrypting. This mode of encryption is usually ignored because it offers no security. If Alice uses her private key to encrypt a message to Bob, then everybody can decrypt it because everybody has Alice's public key. However, this mode of operation does verify authorship, because if Bob can decrypt a message using Alice's public key, then it must have been encrypted using her private key--only Alice has access to her private key, so the message must have been sent by Alice. In effect, if Alice wants to send a love letter to Bob, she has two options. Either she encrypts the message with Bob's public key to guarantee privacy, or she encrypts it with her own private key to guarantee authorship. However, if she combines both options she can guarantee privacy and authorship.
There are quicker ways to achieve this, but here is one way in which Alice might send her love letter. She starts by encrypting the message using her private key, then she encrypts the resulting ciphertext using Bob's public key. We can picture the message surrounded by a fragile inner shell, which represents encryption by Alice's private key, and a strong outer shell, which represents encryption by Bob's public key. The resulting ciphertext can only be deciphered by Bob, because only he has access to the private key necessary to crack the strong outer shell. Having deciphered the outer shell, Bob can then easily decipher the inner shell using Alice's public key-the inner shell is not meant to protect the message, but it does prove that the message came from Alice, and not an impostor. Now To send a message to Bob, Alice would simply write her e-mail and select the PGP option from a menu on her computer screen. Next she would type in Bob's name, then PGP would find Bob's public key and automatically perform all the encryption. At the same time PGP would do the necessary jiggery-pokery required to digitally sign the message. Upon receiving the encrypted message, Bob would select the PGP option, and PGP would decrypt the message and verify the author.
Nothing in PGP was original-Diffie and Hellman had already thought of digital signatures and other cryptographers had used a combination of symmetric and asymmetric ciphers to speed up encryption—but Zimmermann was the first to put everything together in one easy-to-use encryption product, which was efficient enough to run on a moderately sized personal computer. At the moment, a purchase on the Internet can be secured by public key cryptography. Alice visits a company's Web site and selects an item. She then fills in an order form which asks her for her name, address and credit card details. Alice then uses the company's public key to encrypt the order form. The encrypted order form is transmitted to the company, who are the only people able to decrypt it, because only they have the private key necessary for decryption. All of this is done automatically by Alice's Web browser (e.g., Netscape or Explorer) in conjunction with the company's computer. As usual, the security of the encryption depends on the size of the key. The cost of the equipment required to decipher Alice's credit card details is vastly greater than the typical credit card limit, so such an attack is not cost-effective. However, as the amount of money flowing around the Internet increases, it will eventually become profitable for criminals to decipher credit card details. In short, if Internet commerce is to thrive, consumers around the world must have proper security, and businesses will not tolerate crippled encryption.
However, one aspect of future encryption policy seems certain, namely the necessity for certification authorities. If Alice wants to send a secure e-mail to a new friend, Zak, she needs Zak's public key. She might ask Zak to send his public key to her in the mail. Unfortunately, there is then the risk that Eve will intercept Zak's letter to Alice, destroy it and forge a new letter, which actually includes her own public key instead of Zak's. Alice may then send a sensitive e-mail to Zak, but she will unknowingly have encrypted it with Eve's public key. If Eve can intercept this e-mail, she can then easily decipher it and read it. In other words, one of the problems with public key cryptography is being sure that you have the genuine public key of the person with whom you wish to communicate. Certification authorities are organizations that will verify that a public key does indeed correspond to a particular person. A verification authority might request a face-to-face meeting with Zak as a way of ensuring that they have correctly catalogued his public key. If Alice trusts the certification authority, she can obtain from it Zak's public key, and be confident that the key is valid. I have explained how Alice could securely buy products from the Internet by using a company's public key to encrypt the order form. In fact, she would do this only if the public key had been validated by a certification authority.
In 1998, the market leader in certification was Verisign, which has grown into a $30 million company in just four years.
--> Mishra
Bob, Alice and Eve
Problem of key distribution can be described with the help of 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.
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 en-cipherment 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. 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 this system. The problem is the order in which the encryptions and decryptions are performed, which 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."
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. Although the doubly padlocked box approach would not work for real-world cryptography, it inspired Diffie and Hellman to search for a practical method of circumventing the key distribution problem.
Their research concentrated on the examination of various mathematical functions. Most mathematical functions are classified 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. However, Diffie and Hellman 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 illustrate a one-way function is in terms of an everyday activity. Cracking of an egg is a one-way function, 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 dock 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. 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. 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 and note the remainder. This remainder is the answer in (mod x). To find the answer to 11x9 (mod 13), we do the following:
11 x 9=99 à 99 /13= 7, remainder 8
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 times in order to get the new number. For example, if x = 2, and we perform the function, then:
3^ = 32 = 3x3 = 9.
Hence, if we were given the result of the function it would be relatively easy to work back- ward and deduce the original number. 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 x. No value springs to mind, because we are generally unfamiliar with modular arithmetic. We could take a guess that x= 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 x and try again. But we would be heading in the wrong direction, because the actual answer is x= 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 until the right answer is found. It is a classic example of a one-way function, because I could pick a value for x 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 x.
After two years of focusing on modular arithmetic and one-way functions, Hellman'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. Hellman's idea relied on a one-way function of the form Yx (mod P). Initially, Alice and Bob agree on values for Y and P. Almost any values are fine, but there are some restrictions, such as Y being smaller than P. These values are not secret, so Alice can telephone Bob and suggest that, say, Y= 7 and 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 lx (mod 11). At this point they can begin the process of trying to establish a secret key without meeting. By using Hellman'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 Hellman's scheme from Eve's point of view.
If she is tapping the line, she knows only the following facts: that the function is lx (mod 11), that Alice sends a = 2 and that Bob sends b = 4. In order to find the key, she must either do what Bob does, which is turn a into the key by knowing b, or do what Alice does, which is turn b into the key by knowing A. However, Eve does not know the value of A or B 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 A from a, because ‘a’ was a consequence of putting A into a function, and Eve knows the function. Or she could work out B from b, because 3 was a consequence of putting 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 A into ‘a’ and for Bob to turn B into ‘b’, it is very difficult for Eve to reverse the process, especially if the numbers are very large. 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 analogy for Hellman's scheme, imagine a cipher that somehow uses color as the key. First, let us assume 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. The Diffie-Hellman-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. 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-Hellman-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 email 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--establishing 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, Hellman's key exchange system hinders the spontaneity of email.
The Birth of Public Key Cryptography
So far, all the encryption techniques discovered have been 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. Both sender and receiver effectively have equivalent knowledge, and they both use the same key to encrypt and decrypt-their relationship 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 assume 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. 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. 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 wants 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-Hellman-Merkle 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 analogies, 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 dene 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 analogy 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 every one 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 circumstances. 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 analogy-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 nobody had been able to find a suitable candidate. As the months passed, 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, Hellman 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 Diffie-Hellman-Merkle 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.
In April 1977, Rivest, Shamir and Adleman spent Passover 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? 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.
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, but I shall explain one particular aspect of it, known simply as N, because it is N that makes this one-way function reversible under certain circumstances, 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 N, and personalizes the one-way function.
In order to choose her personal value of N, Alice picks two prime numbers, p and q, and multiplies them together. So, Alice could choose her prime numbers to be p = 17,159 and q = 10,247. Multiplying these two numbers together gives N = 17,159 * 10,247 = 175,828,273. Alice's choice of N effectively becomes her public encryption key, and she could print it on her business card, post it on the
Internet, or publish it in a public key directory along with everybody else's value of N. If Bob wants to encrypt a message to Alice, he looks up Alice's value of N (175,828,273) and then inserts it into the general form of the one-way function, which would also be public knowledge. Bob now has a one-way function tailored with Alice's public key, so it could be called Alice's one-way function. To encrypt a message to Alice, he takes Alice's one-way function, inserts the message, notes down the result and sends it to Alice. At this point the encrypted message is secure because nobody can decipher it. The message has been encrypted with a one-way function, so reversing the one-way function and decrypting the message is, by definition, very difficult. However, the question remains-how can Alice decrypt the message?
In order to read messages sent to her, Alice must have a way of reversing the one-way function. She needs to have access to some special piece of information that allows her to decrypt the message. Fortunately for Alice, Rivest designed the one-way function so that it is reversible to someone who knows the values off and q, the two prime numbers that are multiplied together to give N. Although
Alice has told the world that her value for N is 175,828,273, she has not revealed her values for p and q, so only she has the special information required to decrypt her own messages. We can think of N as the public key, the information that is available to everybody, the information required to encrypt messages to Alice. Whereas, p and q is the private key, available only to Alice, the information required to decrypt these messages. The exact details of how p and q can be used to reverse the one-way function are outlined in Appendix J. However, there is one question that must be addressed immediately. If everybody knows N, the public key, and then surely people can deduce p and q, the private key, and read Alice's messages? After all, N was created from p and q. In fact, it turns out that if
N is large enough, it is virtually impossible to deduce p and q from N, and this is perhaps the most beautiful and elegant aspect of the RSA asymmetric cipher.
Alice created N by choosing p and q, and then multiplying them together. The fundamental point is that this is in itself a one-way function. To demonstrate the one-way nature of multiplying primes, we can take two prime numbers, such as 9,419 and 1,933, and multiply them together. With a calculator it takes just a few seconds to get the answer, 18,206,927. However, if instead we were given 18,206,927 and asked to find the prime factors (the two numbers that were multiplied to give 18,206,927) it would take us much longer. If you doubt the difficulty of finding prime factors, then consider the following. It took me just ten seconds to generate the number 1,709,023, but it will take you and a calculator the best part of an afternoon to work out the prime factors. This system of asymmetric cryptography, known as RSA, is said to be a form of public key cryptography. To find out how secure RSA is, we can examine it from Eve's point of view, and try to break a message from Alice to Bob. To encrypt a message to Bob, Alice must look up Bob's public key. To create his public key, Bob picked his own prime numbers, pB and qB, and multiplied them together to get NB. He has kept pB and qB secret, because these make up his private decryption key, but he has published NB, which is equal to 408,508,091. So Alice inserts Bob's public key NB into the general one-way encryption function, and then encrypts her message to him. When the encrypted message arrives, Bob can reverse the function and decrypt it using his values for pB and qB, which make up his private key.
Meanwhile, Eve has intercepted the message en route. Her only hope of decrypting the message is to reverse the one-way function, and this is possible only if she knows pB and qB. Bob has kept pB and qB secret, but Eve, like everybody else, knows NB is 408,508,091. Eve then attempts to deduce the values for pB and qB by working out which numbers would need to be multiplied together to get 408,508,091, a process known as factoring. Factoring is very time-consuming, but exactly how long would it take Eve to find the factors of 408,508,091? There are various recipes for trying to factor NB. Although some recipes are faster than others, they all essentially involve checking each prime number to see if it divides into NB without a remainder. For example, 3 is a prime number, but it is not a factor of 408,508,091 because 3 will not perfectly divide into 408,508,091. So Eve moves on to the next prime number, 5. Similarly, 5 is not a factor, so Eve moves on to the next prime number, and so on. Eventually, Eve arrives at 18,313, the 2,000th prime number, which is indeed a factor of 408,508,091. Having found one factor, it is easy to find the other one, which turns out to be 22,307. If Eve had a calculator and was able to check four primes a minute, then it would have taken her 500 minutes, or more than 8 hours, to find pB and qB. This is not a very high level of security, but Bob could have chosen much larger prime numbers and increased the security of his private key. For example, he could have chosen primes that are as big as 10^5. This would have resulted in a value for N that would have been roughly 1065 x 1065, which is 10130. A computer could multiply the two primes and generate N in just a second, but if Eve wanted to reverse the process and work out p and q, it would take inordinately longer. Exactly how long depends on the speed of Eve's computer. Security expert Sim-son Garfmkel estimated that a 100 MHz Intel Pentium computer with 8 MB of RAM would take roughly 50 years to factor a number as big as 10130.
Cryptographers tend to have a paranoid streak and consider worst-case scenarios, such as a worldwide conspiracy to crack their ciphers. So, Garfinkel considered what would happen if a hundred million personal computers (the number sold in 1995) ganged up together. The result is that a number as big as 10130 could be factored in about 15 seconds. Consequently, it is now generally accepted that for genuine security it is necessary to use even larger primes. For important banking transactions, N tends to be at least 10308.
The combined efforts of a hundred million personal computers would take more than one thousand years to crack such a cipher. With Sufficiently large values off and q, RSA is impregnable. The only caveat for the security of RSA public key cryptography is that at some time in the future somebody might find a quick way to factor N. It is conceivable that a decade from now, or even tomorrow, somebody will discover a method for rapid factoring, and thereafter RSA will become useless. However, for over two thousand years mathematicians have tried and failed to find a shortcut, and at the moment factoring remains an enormously time-consuming calculation. Most mathematicians believe that factoring is an inherently difficult task, and that there is some mathematical law that forbids any shortcut.
PGP and Digital signature
Today, electronic mail is gradually replacing conventional paper mail, and is soon to be the norm for everyone, not the novelty it is today. Unlike paper mail, email messages are just too easy to intercept and scan for interesting keywords. This can be done easily, routinely, automatically, and undetectably on a grand scale. This is analogous to driftnet fishing-making a quantitative and qualitative Orwellian difference to the health of democracy. The difference between ordinary and digital mail can be illustrated by imagining that Alice wants to send out invitations to her birthday party, and that Eve, who has not been invited, wants to know the time and place
of the party. If Alice uses the traditional method of posting letters, then it is very difficult for Eve to intercept one of the invitations. To start with, Eve does not know where Alice's invitations entered the postal system, because Alice could use any postbox in the city. Her only hope for intercepting one of the invitations is to somehow identify the address of one of Alice's friends, and infiltrate the local sorting office. She then has to check each and every letter manually. If she does manage to find a letter from Alice, she will have to steam it open in order to get the information she wants, and then return it to its original condition to avoid any suspicion of tampering. In comparison, Eve's task is made considerably easier if Alice sends her invitations by e-mail. As the messages leave Alice's computer, they will go to a local server, a main entry point for the Internet; if Eve is clever enough, she can hack into that local server without leaving her home. The invitations will carry Alice's e-mail address, and it would be a trivial matter to set up an electronic sieve that looks for e-mails containing Alice's address. Once an invitation has been found, there is no envelope to open, and so no problem in reading it. Furthermore, the invitation can be sent on its way without it showing any sign of having been intercepted. Alice would be oblivious to what was going on. However, there is a way to prevent Eve from reading Alice's e-mails, namely encryption.
If Alice wants to use RSA to encrypt a message to Bob, she looks up his public key and then applies RSA's one-way function to the message. Conversely, Bob decrypts the ciphertext by using his private key to reverse RSA's one-way function. Both processes require considerable mathematical manipulation, so encryption and decryption can, if the message is long, take several minutes on a personal computer. If Alice is sending a hundred messages a day, she cannot afford to spend several minutes encrypting each one. To speed up encryption and decryption, Zimmermann employed a neat trick that used asymmetric RSA encryption in tandem with old-fashioned symmetric encryption. Traditional symmetric encryption can be just as secure as asymmetric encryption, and it is much quicker to perform, but symmetric encryption suffers from the problem of having to distribute the key, which has to be securely transported from the sender to the receiver. This is where RSA comes to the rescue, because RSA can be used to encrypt the symmetric key.
Zimmermann pictured the following scenario. If Alice wants to send an encrypted message to Bob, she begins by encrypting it with a symmetric cipher. Zimmermann suggested using a cipher known as IDEA, which is similar to DES. To encrypt with IDEA, Alice needs to choose a key, but for Bob to decrypt the message Alice somehow has to get the key to Bob. Alice overcomes this problem by looking up Bob's RSA public key, and then uses it to encrypt the IDEA key. So, Alice ends up sending two things to Bob: the message encrypted with the symmetric IDEA cipher and the IDEA key encrypted with the asymmetric RSA cipher. At the other end, Bob uses his RSA private key to decrypt the IDEA key, and then uses the IDEA key to decrypt the message. This might seem convoluted, but the advantage is that the message, which might contain a large amount of information, is being encrypted with a quick symmetric cipher, and only the symmetric IDEA key, which consists of a relatively small amount of information, is being encrypted with a slow asymmetric cipher. Zimmermann planned to have this combination of RSA and IDEA within the PGP product, but the user-friendly interface would mean that the user would not have to get involved in the nuts and bolts of what was going on. Having largely solved the speed problem, Zimmermann also incorporated a series of handy features into PGP. For example, before using the RSA component of PGP, Alice needs to generate her own private key and public key. Key generation is not trivial, because it requires finding a pair of giant primes. However, Alice only has to wiggle her mouse in an erratic manner, and the PGP program will go ahead and create her private key and public key--the mouse movements introduce a random factor which PGP utilizes to ensure that every user has their own distinct pair of primes, and therefore their own unique private key and public key. Thereafter Alice merely has to publicize her public key.
Another helpful aspect of PGP is its facility for digitally signing an email. Ordinarily e-mail does not carry a signature, which means that it is impossible to verify the true author of an electronic message. For example, if Alice uses e-mail to send a love letter to Bob, she normally encrypts it with his public key, and when he receives it he decrypts it with his private key. Bob is initially flattered, but how can he be sure that the love letter is really from Alice? Perhaps the malevolent Eve wrote the email and typed Alice's name at the bottom. Without the reassurance of a handwritten ink signature, there is no obvious way to verify the authorship. In order to develop trust on the Internet, it is essential that there is some form of reliable digital signature. The PGP digital signature is based on a principle that was first developed by Whitfield Diffie and Martin Hellman. When they proposed the idea of separate public keys and private keys, they realized that, in addition to solving the key distribution problem, their invention would also provide a natural mechanism for generating e-mail signatures. Now we now that the public key is for encrypting and the private key for decrypting. In fact the process can be swapped around, so that the private key is used for encrypting and the public key is used for decrypting. This mode of encryption is usually ignored because it offers no security. If Alice uses her private key to encrypt a message to Bob, then everybody can decrypt it because everybody has Alice's public key. However, this mode of operation does verify authorship, because if Bob can decrypt a message using Alice's public key, then it must have been encrypted using her private key--only Alice has access to her private key, so the message must have been sent by Alice. In effect, if Alice wants to send a love letter to Bob, she has two options. Either she encrypts the message with Bob's public key to guarantee privacy, or she encrypts it with her own private key to guarantee authorship. However, if she combines both options she can guarantee privacy and authorship.
There are quicker ways to achieve this, but here is one way in which Alice might send her love letter. She starts by encrypting the message using her private key, then she encrypts the resulting ciphertext using Bob's public key. We can picture the message surrounded by a fragile inner shell, which represents encryption by Alice's private key, and a strong outer shell, which represents encryption by Bob's public key. The resulting ciphertext can only be deciphered by Bob, because only he has access to the private key necessary to crack the strong outer shell. Having deciphered the outer shell, Bob can then easily decipher the inner shell using Alice's public key-the inner shell is not meant to protect the message, but it does prove that the message came from Alice, and not an impostor. Now To send a message to Bob, Alice would simply write her e-mail and select the PGP option from a menu on her computer screen. Next she would type in Bob's name, then PGP would find Bob's public key and automatically perform all the encryption. At the same time PGP would do the necessary jiggery-pokery required to digitally sign the message. Upon receiving the encrypted message, Bob would select the PGP option, and PGP would decrypt the message and verify the author.
Nothing in PGP was original-Diffie and Hellman had already thought of digital signatures and other cryptographers had used a combination of symmetric and asymmetric ciphers to speed up encryption—but Zimmermann was the first to put everything together in one easy-to-use encryption product, which was efficient enough to run on a moderately sized personal computer. At the moment, a purchase on the Internet can be secured by public key cryptography. Alice visits a company's Web site and selects an item. She then fills in an order form which asks her for her name, address and credit card details. Alice then uses the company's public key to encrypt the order form. The encrypted order form is transmitted to the company, who are the only people able to decrypt it, because only they have the private key necessary for decryption. All of this is done automatically by Alice's Web browser (e.g., Netscape or Explorer) in conjunction with the company's computer. As usual, the security of the encryption depends on the size of the key. The cost of the equipment required to decipher Alice's credit card details is vastly greater than the typical credit card limit, so such an attack is not cost-effective. However, as the amount of money flowing around the Internet increases, it will eventually become profitable for criminals to decipher credit card details. In short, if Internet commerce is to thrive, consumers around the world must have proper security, and businesses will not tolerate crippled encryption.
However, one aspect of future encryption policy seems certain, namely the necessity for certification authorities. If Alice wants to send a secure e-mail to a new friend, Zak, she needs Zak's public key. She might ask Zak to send his public key to her in the mail. Unfortunately, there is then the risk that Eve will intercept Zak's letter to Alice, destroy it and forge a new letter, which actually includes her own public key instead of Zak's. Alice may then send a sensitive e-mail to Zak, but she will unknowingly have encrypted it with Eve's public key. If Eve can intercept this e-mail, she can then easily decipher it and read it. In other words, one of the problems with public key cryptography is being sure that you have the genuine public key of the person with whom you wish to communicate. Certification authorities are organizations that will verify that a public key does indeed correspond to a particular person. A verification authority might request a face-to-face meeting with Zak as a way of ensuring that they have correctly catalogued his public key. If Alice trusts the certification authority, she can obtain from it Zak's public key, and be confident that the key is valid. I have explained how Alice could securely buy products from the Internet by using a company's public key to encrypt the order form. In fact, she would do this only if the public key had been validated by a certification authority.
In 1998, the market leader in certification was Verisign, which has grown into a $30 million company in just four years.
--> Mishra
Thursday, September 6, 2007
Vietnam War
First movie which I saw, based on Vietnam War, was ‘Rambo II’. But at that time I hardly knew anything about VW, and I was too much fascinated by Rambo, the great. After that I saw Rambo I, and I got an idea that it was not just a war and what terrible things it did to people, on both the sides. Then after quite some time I watched ‘Full Metal Jacket’, by great Stanley, and this movie gave me quite a information on what Vietnam war was, what it did to merican soldiers and how so many of them had almost lost their mental balance. I really liked the movie, mainly the first half, depicting funny and not-so funny incidences at military training camp, that training officer, his marching song, that poor fat fellow and many more. Second half was not that entertaining and more of an eye opener. It showed the effects of war on the psyche of soldiers, Vietnamese people and on that God-forsaken country.
Next movie was ‘The Deer Hunter’. Quite a long movie, almost 3 hours, but worth watching. It shows the life of Deniro and Christopher Walken, who are real close friends, enjoying their time in US of A, and then they went to VW, and how their lives were changed irreversibly. First hour shows the life of a group of friends, who work in a factory and enjoy their lives. Their unique hobby is deer hunting, and Deniro is really good at it. Then in next hour shows their VW stay and how each of them went through it. Last one hour showed that what VW did to soldier’s psyche. Walken lost control of his life and never recovered.
Platoon was the next. This one shows two entirely different army captains, fighting in VW, but with completely different view. One just wants to kill each and every Charlie and the other who just wants to end the war. Between the is a rookie, who is really confused as to who is right and who is wrong. In all a really good movie.
Next movie was ‘The Deer Hunter’. Quite a long movie, almost 3 hours, but worth watching. It shows the life of Deniro and Christopher Walken, who are real close friends, enjoying their time in US of A, and then they went to VW, and how their lives were changed irreversibly. First hour shows the life of a group of friends, who work in a factory and enjoy their lives. Their unique hobby is deer hunting, and Deniro is really good at it. Then in next hour shows their VW stay and how each of them went through it. Last one hour showed that what VW did to soldier’s psyche. Walken lost control of his life and never recovered.
Platoon was the next. This one shows two entirely different army captains, fighting in VW, but with completely different view. One just wants to kill each and every Charlie and the other who just wants to end the war. Between the is a rookie, who is really confused as to who is right and who is wrong. In all a really good movie.
After this I watched, greatest of them all, ‘Apocalypse Now’. It had mix of all of the above ones. It shows the methods used by American army in VW, frustration of American soldiers and the after effect of this.
-- Mishra
Subscribe to:
Posts (Atom)