Cryptography: Theory and Practice:The RSA System and Factoring

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


Chapter 4
The RSA System and Factoring

4.1 Introduction to Public-key Cryptography

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:

RSA
The security of RSA is based on the difficulty of factoring large integers. This system is described in Section 4.3.
Merkle-Hellman Knapsack
This and related systems are based on the difficulty of the subset sum problem (which is NP-complete1); however, all of the various knapsack systems have been shown to be insecure (with the exception of the Chor-Rivest Cryptosystem mentioned below). See Chapter 5 for a discussion of this cryptosystem.

1The NP-complete problems are a large class of problems for which no polynomial-time algorithms are known.
McEliece
The McEliece Cryptosystem is based on algebraic coding theory and is still regarded as being secure. It is based on the problem of decoding a linear code (which is also NP-complete). (See Chapter 5.)
ElGamal
The ElGamal Cryptosystem is based on the difficulty of the discrete logarithm problem for finite fields. (See Chapter 5.)
Chor-Rivest
This is also referred to as a “knapsack” type system, but it is still regarded as being secure.
Elliptic Curve
The Elliptic Curve Cryptosystems are modifications of other systems (such as the ElGamal Cryptosystem, for example) that work in the domain of elliptic curves rather than finite fields. The Elliptic Curve Cryptosystems appear to remain secure for smaller keys than other public-key cryptosystems. (See Chapter 5.)

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.

Bob’s 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 Bob’s 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net