EarthWeb   
HomeAccount InfoLoginSearchMy ITKnowledgeFAQSitemapContact Us
     

   
  All ITKnowledge
  Source Code

  Search Tips
  Advanced Search
   
  

  

[an error occurred while processing this directive]
Previous Table of Contents Next


Example 4.5  (Cont.)

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

i bi z
11 1 12 × 9726 = 9726
10 1 97262 × 9726 = 2659
  9 0 26592 = 5634
  8 1 56342 × 9726 = 9167
  7 1 91672 × 9726 = 4958
  6 1 49582 × 9726 = 7783
  5 0 77832 = 6298
  4 0 62982 = 4629
  3 1 46292 × 9726 = 10185
  2 1 101852 × 9726 = 105
  1 0 1052 = 11025
  0 1 110252 × 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)2). Steps 3 and 4 involve the Euclidean algorithm, so let’s briefly consider its complexity.

Suppose we compute the greatest common divisor of r0 and r1, where r0 > r1. In each iteration of the algorithm, we compute a quotient and remainder, which can be done in time O((log r0)2). 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 fs+2r0, where fi denotes the ith Fibonacci number. Since

it follows that s is O(log r0).

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

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 log2 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.


Previous Table of Contents Next

Copyright © CRC Press LLC

HomeAccount InfoSubscribeLoginSearchMy ITKnowledgeFAQSitemapContact Us
Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.