Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
In the classical model of cryptography that we have been studying up until now, Alice and Bob secretly choose the key K. K then gives rise to an encryption rule eK and a decryption rule dK. In the cryptosystems we have seen so far, dK is either the same as eK, or easily derived from it (for example, DES decryption is identical to encryption, but the key schedule is reversed). Cryptosystems of this type are known as private-key systems, since exposure of eK renders the system insecure.
One drawback of a private-key system is that it requires the prior communication of the key K between Alice and Bob, using a secure channel, before any ciphertext is transmitted. In practice, this may be very difficult to achieve. For example, suppose Alice and Bob live far away from each other and they decide that they want to communicate electronically, using e-mail. In a situation such as this, Alice and Bob may not have access to a reasonable secure channel.
The idea behind a public-key system is that it might be possible to find a cryptosystem where it is computationally infeasible to determine dK given eK. If so, then the encryption rule eK could be made public by publishing it in a directory (hence the term public-key system). The advantage of a public-key system is that Alice (or anyone else) can send an encrypted message to Bob (without the prior communication of a secret key) by using the public encryption rule eK. Bob will be the only person that can decrypt the ciphertext, using his secret decryption rule dK.
Consider the following analogy: Alice places an object in a metal box, and then locks it with a combination lock left there by Bob. Bob is the only person who can open the box since only he knows the combination.
The idea of a public-key system was due to Diffie and Hellman in 1976. The first realization of a public-key system came in 1977 by Rivest, Shamir, and Adleman, who invented the well-known RSA Cryptosystem which we study in this chapter. Since then, several public-key systems have been proposed, whose security rests on different computational problems. Of these, the most important are the following:
1The NP-complete problems are a large class of problems for which no polynomial-time algorithms are known.
One very important observation is that a public-key cryptosystem can never provide unconditional security. This is because an opponent, on observing a ciphertext y, can encrypt each possible plaintext in turn using the public encryption rule eK until he finds the unique x such that y = eK(x). This x is the decryption of y. Consequently, we study the computational security of public-key systems.
It is helpful conceptually to think of a public-key system in terms of an abstraction called a trapdoor one-way function. We informally define this notion now.
Bobs public encryption function, eK, should be easy to compute. We have just noted that computing the inverse function (i.e., decrypting) should be hard (for anyone other than Bob). This property of being easy to compute but hard to invert is often called the one-way property. Thus, we desire that eK be an (injective) one-way function.
One-way functions play a central role in cryptography; they are important for constructing public-key cryptosystems and in various other contexts. Unfortunately, although there are many functions that are believed to be one-way, there currently do not exist functions that can be proved to be one-way.
Here is an example of a function which is believed to be one-way. Suppose n is the product of two large primes p and q, and let b be a positive integer. Then define to be
(For a suitable choice of b and n, this is in fact the RSA encryption function; we will have much more to say about it later.)
If we are to construct a public-key cryptosystem, then it is not sufficient to find a one-way function. We do not want eK to be a one-way function from Bobs point of view, since he wants to be able to decrypt messages that he receives in an efficient way. Thus, it is necessary that Bob possesses a trapdoor, which consists of secret information that permits easy inversion of eK. That is, Bob can decrypt efficiently because he has some extra secret knowledge about K. So, we say that a function is a trapdoor one-way function if it is a one-way function, but it becomes easy to invert with the knowledge of a certain trapdoor.
We will see in Section 4.3 how to find a trapdoor for the function f defined above. This will lead to the RSA Cryptosystem.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC