Cryptography: Theory and Practice:The RSA System and Factoring | Modern Cryptography: Theory and Practice

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

Table of Contents

4.4 Implementing RSA

There are many aspects of the RSA Cryptosystem to discuss, including the details of setting up the cryptosystem, the efficiency of encrypting and decrypting, and security issues. In order to set up the system, Bob follows the steps indicated in Figure 4.3. How Bob carries out these steps will be discussed later in this chapter.

One obvious attack on the cryptosystem is for a cryptanalyst to attempt to factor n. If this can be done, it is a simple manner to compute φ(n) = (p - 1)(q - 1) and then compute the decryption exponent a from b exactly as Bob did. (It has been conjectured that breaking RSA is polynomially equivalent²to factoring n, but this remains unproved.)

²Two problems are said to be polynomially equivalent if the existence of a polynomial-time algorithm for either problem implies the existence of a polynomial-time algorithm for the other problem.

Figure 4.3 Setting up RSA

Hence, if the RSA Cryptosystem is to be secure, it is certainly necessary that n = pq must be large enough that factoring it will be computationally infeasible. Current factoring algorithms are able to factor numbers having up to 130 decimal digits (for more information on factoring, see Section 4.8). Hence, it is recommended that, to be on the safe side, one should choose p and q to each be primes having about 100 digits; then n will have 200 digits. Several hardware implementations of RSA use a modulus which is 512 bits in length. However, a 512-bit modulus corresponds to about 154 decimal digits (since the number of bits in the binary representation of an integer is log₂ 10 times the number of decimal digits), and hence it does not offer good long-term security.

Leaving aside for the moment the question of how to find 100 digit primes, let us look now at the arithmetic operations of encryption and decryption. An encryption (or decryption) involves performing one exponentiation modulo n. Since n is very large, we must use multiprecision arithmetic to perform computations in , and the time required will depend on the number of bits in the binary representation of n.

Suppose n has k bits in its binary representation; i.e., k = [log₂ n] + 1. Using standard “grade-school” arithmetic techniques, it is not difficult to see that an addition of two k-bit integers can be done in time O(k), and a multiplication can be done in time O(k²). Also, a reduction modulo n of an integer having at most 2k bits can be performed in time O(k²) (this amounts to doing long division and retaining the remainder). Now, suppose that (where we are assuming that 0 ≤ x, y ≤ n - 1). Then xy mod n can be computed by first calculating the product xy (which is a 2k-bit integer), and then reducing it modulo n. These two steps can be peformed in time O(k²). We call this computation modular multiplication.

Figure 4.4 The square-and-multiply algorithm to compute x^b mod n

We now consider modular exponentiation, i.e., computation of a function of the form x^c mod n. As noted above, both the encryption and the decryption operations in RSA are modular exponentiations. Computation of x^c mod n can be done using c - 1 modular multiplications; however, this is very inefficient if c is large. Note that c might be as big as φ(n) - 1, which is exponentially large compared to k.

The well-known “square-and-multiply” approach reduces the number of modular multiplications required to compute x^c mod n to at most , where is the number of bits in the binary representation of c. Since , it follows that x^c mod n can be computed in time O(k³). Hence, RSA, encryption and decryption can both be done in polynomial time (as a function of k, which is the number of bits in one plaintext (or ciphertext) character).

Square-and-multiply assumes that the exponent, b say, is represented in binary notation, say

where . The algorithm to compute z = x^b mod n is presented in Figure 4.4. It is easy to count the number of modular multiplications performed by the square-and-multiply algorithm. There are always squarings performed (step 3). The number of modular multiplications in step 4 is equal to the number of 1’s in the binary representation of b, which is an integer between 0 and . Thus, the total number of modular multiplications is at least and at most .

We will illustrate the use of square-and-multiply by returning to Example 4.5.

Table of Contents