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

Example 4.5 (Cont.)

Recall that n = 11413, and the public encryption exponent is b = 3533. Alice encrypts the plaintext 9726 by computing 9726³⁵³³ mod 11413, using the square-and multiply algorithm, as follows:

i	b_i	z
11	1	1² × 9726 = 9726
10	1	9726² × 9726 = 2659
9	0	2659² = 5634
8	1	5634² × 9726 = 9167
7	1	9167² × 9726 = 4958
6	1	4958² × 9726 = 7783
5	0	7783² = 6298
4	0	6298² = 4629
3	1	4629² × 9726 = 10185
2	1	10185² × 9726 = 105
1	0	105² = 11025
0	1	11025² × 9726 = 5761

Hence, as stated earlier, the ciphertext is 5761.

It should be emphasized that the most efficient current hardware implementations of RSA achieve encryption rates of about 600 Kbits per second (using a 512 bit modulus n), as compared to 1 Gbit per second for DES. Stated another way, RSA, is roughly 1500 times slower than DES.

At this point we have discussed the encryption and decryption operations for RSA. In terms of setting up RSA, the generation of the primes p and q (Step 1) will be discussed in the next section. Step 2 is straightforward and can be done in time O((log n)²). Steps 3 and 4 involve the Euclidean algorithm, so let’s briefly consider its complexity.

Suppose we compute the greatest common divisor of r₀ and r₁, where r₀ > r₁. In each iteration of the algorithm, we compute a quotient and remainder, which can be done in time O((log r₀)²). If we can obtain an upper bound on the number of iterations, then we will have a bound on the complexity of the algorithm. There is a well-known result, known as Lamé’s Theorem, that provides such a bound. It asserts that if s is the number of iterations, then f_s+2 ≤ r₀, where f_i denotes the ith Fibonacci number. Since

it follows that s is O(log r₀).

This shows that the running time of the Euclidean algorithm is O((log n)³). (Actually, a more careful analysis can be used to show that the running time is, in fact, O((log n)²).)

4.5 Probabilistic Primality Testing

In setting up the RSA Cryptosystem, it is necessary to generate large (e.g., 80 digit) “random primes.” In practice, the way this is done is to generate large random numbers, and then test them for primality using a probabilistic polynomialtime Monte Carlo algorithm such as the Solovay-Strassen or Miller-Rabin algorithm, both of which we will present in this section. These algorithms are fast (i.e., an integer n can be tested in time that is polynomial in log₂ n, the number of bits in the binary representation of n), but there is a possibility that the algorithm may claim that n is prime when it is not. However, by running the algorithm enough times, the error probability can be reduced below any desired threshold. (We will discuss this in more detail a bit later.)

The other pertinent question is how many random integers (of a specified size) will need to be tested until we find one that is prime. A famous result in number theory, called the Prime number theorem, states that the number of primes not exceeding N is approximately N/ln N. Hence, if p is chosen at random, the probability that it is prime is about 1/ln p. For a 512 bit modulus, we have . That is, on average, of 177 random integers p of the appropriate size, one will be prime (of course, if we restrict our attention to odd integers, the probability doubles, to about 2/177). So it is indeed practical to generate sufficiently large random numbers that are “probably prime,” and hence it is practical to set up the RSA Cryptosystem. We proceed to describe how this is done.

A decision problem is a problem in which a question is to be answered “yes” or “no.” A probabilistic algorithm is any algorithm that uses random numbers (in contrast, an algorithm that does not use random numbers is called a deterministic algorithm). The following definitions pertain to probabilistic algorithms for decision problems.

Table of Contents