Generating RSA keys

Keys for the RSA algorithm are generated using a simple process. The following is a small worked-through example:

1. First, select two prime numbers p and q: p = 3; q = 11

2. Next, calculate the public modulus: n = p · q = 33

3. Calculate the temporary variable z for use during key generation: z = (p − 1) · (q − 1)

4. Calculate a public key e which satisfies the conditions e < z and gcd (z, e) = 1 (that is, the greatest common denominator of z and e is 1). Since there are several numbers that meet these conditions, select one of them: e = 7

5. Calculate a private key d that satisfies the condition (d · e) mod z = 1: d = 3 This completes the computation of the keys. The public and private keys can now be tested for

encryption and decryption using the RSA algorithm, as illustrated in the following numeric example:

1. Use the number ‘4’ as the plaintext x (x < n): x = 4

2. Encrypt the text: y = 47 mod 33 = 16

2. The result of the calculation is the ciphertext y: y = 16

3 Decrypt the ciphertext: x = 163 mod 33 = 4

The result of decrypting the ciphertext is again the original plaintext, as expected.

In actual practice, key generation is more laborious, since it is very difficult to test large numbers to determine if they are prime. The well-known sieve of Eratosthenes cannot be used here, since it requires prior knowledge of all prime numbers smaller than the number being tested. This is practically impossible for numbers as large as 512 bits. Consequently, probabilistic tests are used to determine the likelihood that the selected number is a prime number. The Miller–Rabin test and the Solovay–Strassen test11 are typical examples of such tests. To avoid having to use these time-consuming tests more than necessary, randomly generated candidate numbers are first tested to see if they have any small prime factors. If the randomly generated number can be exactly divided by a small prime number, such as 2, 3, 5 or 7, it obviously cannot be a prime number. Once it has been determined that the number to be tested does not have any small prime factors, a prime number test such as the Miller–Rabin test can be used. The principle of this test is illustrated in Figure 4.31 and described in detail in the appendix of the IEEE 1363 standard. The algorithms for generating RSA keys have a special feature, which is that the time required to generate a key pair (a public key together with a private key) is only statistically predictable. This means that it is only possible to say that there is a certain probability that key generation will take a given amount of time. A definitive statement such as ‘. . . will take x seconds’ is not possible, due to the need to run the prime number test on the random number. The time required to perform this test is not deterministically predictable.

The DSS algorithm

In mid-1991, the NIST (US National Institute of Standards and Technology) published the design of a cryptographic algorithm for adding signatures to messages. This algorithm, which has since been standardized in the US (FIPS 186), has been named the Digital Signature Algorithm (DSA), and the standard that describes it is called the Digital Signature Standard (DSS). The DSA and RSA algorithms are the two most widely used procedures for generating digital signatures. The DSA algorithm is a modification of the El Gamal procedure. The background for the standardization of this algorithm is that a procedure was wanted that could be used to generate signatures but not to encrypt data. For this reason, the DSA algorithm is more complicated than the RSA algorithm. However, it has been shown that it is possible to encrypt data using this algorithm [Simmons 98].

In contrast to the RSA algorithm, the security of the DSS algorithm does not depend on the problem of factoring large numbers, but rather on the discrete logarithm problem. The

expression y = ax mod p can be computed quickly, even with large numbers. However, the reverse process, which is calculating the value of x for given values of y, a and p, requires a very large amount of computational effort. With all signature algorithms, the message to be signed must first be reduced to a predefined length using a hash algorithm. The NIST therefore published a suitable algorithm for use with the DSS algorithm. This is named SHA-1 (Secure Hash Algorithm).13 This variant of the MD5 hash algorithm generates a 160-bit hash value from a message of any arbitrary length. Computations for the DSS algorithm, like those for the RSA algorithm, are performed using only integers.

To compute a signature with the DSA algorithm, the following global values must first be determined:

p (public): prime number with a length of 512 to 1024 bits, evenly divisible by 64

q (public): 160-bit prime factor of (p – 1)

g (public): g = h(p–1)/q

where h is an integer satisfying the conditions h < p –1 and g > 1

The private key x must satisfy the following condition:

x < q

The public key y is computed as follows:

y = gx mod p

Once all of the necessary keys and numbers have been determined, the message m can be signed as follows:

Generate a random number k, where k < q: k

Compute the hash value of m: H(m)

Calculate r : r = (gk mod p) mod q

Calculate s: s = k–1 (H(m) + x · r ) mod q

The two values r and s are the digital signature of the message. With the DSS algorithm, the signature consists of two numbers, instead of only one number as with the RSA algorithm.

The signature is verified as follows:

Calculate w: w = s–1 mod q

Calculate u1: u1 = (H(m) · w) mod q

Calculate u2: u2 = (r · w) mod q

Calculate v: v = ((gu1 · yu2) mod p) mod q

If the condition v = s is satisfied, the message m has not been altered and the digital signature is authentic.

In practice, the RSA algorithm has achieved more widespread use than the DSS algorithm, which up to now has seen only very limited use. The original idea of standardizing a signature algorithm that cannot be used for encryption, which led to the DSS algorithm, has largely come to nothing. The complexity of this algorithm also discourages its widespread use. Nonetheless, for many institutions the fact that the standard exists and the political pressure to generate signatures using the DSS and SHS represent strong arguments in its favor.

Using elliptic curves as asymmetric cryptographic algorithms

In addition to the two well-known asymmetric cryptographic algorithms, RSA and DSA, there is a third type of cryptography that is used for digital signatures and key exchanges in the realm of smart cards. It is based on elliptic curves (EC). In 1985,Victor Miller and NealKoblitz independently proposed the use of elliptic curves for constructing asymmetric cryptographic algorithms. The properties of elliptic curves are well suited to such applications, and in the course of the following years, practical cryptographic systems based on these proposals were developed. In general, they are usually referred to as elliptic curve cryptosystems (ECC). Elliptic curves are sets of smooth curves that satisfy the equation y2 = x3 +ax+b within a finite three-dimensional space. No point is allowed to be a singularity. This means, for instance, that 4a2 +27b2 = 0. In the realm of cryptography, the finite spaces GF(p), GF(2n) and GF(pn) are used, where p is a prime number and n is a positive integer greater than 1. The mathematics of cryptographic systems based on elliptic curves are relatively difficult. For this reason, you are referred to the book by Alfred Menezes on the subject [Menezes 93]. The very comprehensive IEEE 1363 public-key cryptography standard and the ISO/IEC 15946 series of standards dealing with elliptic curves also provide good synopses of elliptic curves and other asymmetric cryptographic techniques. The major advantages of asymmetric cryptographic systems based on elliptic curves are that they require much less computational capacity than systems such as RSA (for instance), and that the same level of cryptographic strength can be attained with significantly shorter keys. For example, roughly the same amount of computation is required to break an ECC algorithm with a 160-bit key as an RSA algorithm with a 1024-bit key. Similarly, an ECC algorithm with a 256-bit key corresponds to an RSA algorithm with a 2048-bit key, while an ECC algorithm with a 320-bit key roughly corresponds to an RSA algorithm with a 5120-bit key. This cryptographic strength and the relatively small size of the keys are precisely the reasons why ECC systems are found in the realm of smart cards. The arithmetic processing components of modern-day smart card microcontrollers generally support ECC, which means that a relatively high computational speed is available. As with the RSA algorithm, the key length is an important characteristic of these asymmetric cryptographic algorithms. Interestingly enough, cryptographic systems based on elliptic curves require so little processing capacity that they can even be implemented in microcontrollers lacking coprocessors. Some typical times for generating and verifying signatures are shown in Table 4.16. An 8-bit microcontroller clocked at 3.5 MHz without a coprocessor requires approximately one second to generate a 160-bit ECC key pair using a look-up table approximately 10 kB in size. This time can be reduced to 200 ns using a coprocessor. One factor limiting the use of elliptic curves for asymmetric cryptographic algorithms is that they are regarded as a relatively new discovery in the cryptographic world, even though they have been known for a long time. It will no doubt take some time until the use of ECC systems becomes commonplace in the cautious world of cryptographers and smart card application designers, despite the fact that cryptographic systems based on elliptic curves presently offer the highest level of security per bit relative to all other asymmetric methods.