![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
4.4 Implementing RSAThere 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 equivalent2to factoring n, but this remains unproved.)
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 log2 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 Suppose n has k bits in its binary representation; i.e., k = [log2 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(k2). Also, a reduction modulo n of an integer having at most 2k bits can be performed in time O(k2) (this amounts to doing long division and retaining the remainder). Now, suppose that
We now consider modular exponentiation, i.e., computation of a function of the form xc mod n. As noted above, both the encryption and the decryption operations in RSA are modular exponentiations. Computation of xc 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 xc mod n to at most Square-and-multiply assumes that the exponent, b say, is represented in binary notation, say where We will illustrate the use of square-and-multiply by returning to Example 4.5.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |