Appendix F: RSA Encryption and Signature Scheme

The name RSA is derived from the inventors of the algorithm, Rivest, Shamir, and Adleman who presented the algorithm in [1]. RSA is an asymmetric system as described in Appendix D, Section D.1, where each user has a private key known only to him. Corresponding to this key is a public one, accessible to anyone . Data processed with one key can be recovered using the other key. At the same time there is no way that an attacker could recover the private key from the public key, a feature that is based on the difficulty of factoring large numbers . Using various operation modes, RSA can be used as an asymmetric encryption algorithm for secret key distribution or as a digital signature scheme.

F.1 Key generation

Each entity creates an RSA public key and the corresponding private key according to the following key generation algorithm:

1. Generate at random two distinct large prime numbers p and q ,of approximately the same size .

2. Compute the modulus as the product of these two primes, n = p * q . Compute the Euler function of the modulus • ( n ) = ( p ˆ’ 1) * ( q ˆ’ 1).

3. Choose the public exponent e , 1 < e < • ( n ), such that the greatest common divisor ( gcd )of e and j( n ) is 1 [i.e., gcd ( e , • ( n )) = 1].

4. Use the extended Euclidian algorithm to compute the unique integer d , referred to as the secret exponent, 1 < d < • ( n ), such that e * d = 1 mod • ( n ).

5. The private key of the entity consists of the pair ( n , d ) and optionally the pair ( p , q ); while the public key of the entity consists of the pair ( n , e ).

Note that the computation of d can be performed with the universal exponent of n , which equals the least common multiple ( lcm )of p ˆ’ 1 and q ˆ’ 1 denoted » ( n ) = lcm ( p ˆ’ 1, q ˆ’ 1) = • ( n ) / gcd( p ˆ’ 1, q ˆ’ 1), using the formula e * d = 1 mod » ( n ). The advantage is that the resulting d is smaller than in the case when d is computed with respect to • ( n ). Since p and q were generated at random, however, it is expected that gcd( p ˆ’ 1, q ˆ’ 1) is small, and correspondingly, the values of the secret exponent computed either way are approximately the same size.

In the key generation algorithm it was euphemistically stated that the primes p and q should be large . Their size is usually correlated to the state of the art in the factorization problem. The factorization of the modulus n implies breaking RSA. Indeed, someone who can successfully factor the modulus n in the primes p and q can easily compute • ( n ), and then applying the extended Euclidian algorithm can compute d from e and • ( n ). The largest published factorization, using the General Number Field Sieve algorithm is that of a 512-bit modulus (about 155 digits), reported in August 1999. Therefore, the bit-length of n is required to be minimum 768 bits, but for a system designed to work for several years a bit-length of at least 1,024 bits is highly recommended. Certainly, the bit-length of the modulus impacts on the performance: the bigger the modulus the slower the RSA operation. When the execution time is a functional constraint, the increase of the modulus' length reflects in a more expensive hardware/software platform of the device performing the RSA operation. If the device performing the RSA operation is a chip card, the presence in the hardware architecture of the chip of a cryptographic coprocessor specialized in long arithmetic operations is a must, which slightly increases the cost of the cards.

It was never proved that breaking RSA necessarily implies factoring the modulus, but there is good evidence that this implication does not hold if the public exponent is small. Some popular values of a few years ago, of a public exponent of value 3 or 17, are no longer recommended. Based on recent results in the area of RSA cryptanalysis [2, 3] the public exponent for RSA must be sufficiently large. The commonly used value 2 ¹⁶ + 1 is still acceptable, but for a higher level of assurance the value of the public exponent should be generated at random on 32 bits or even 64 bits, with odd values.