7.6 Generating an RSA Key Pair

7.6.1 Problem

You want to use RSA to encrypt data, and you need to generate a public key and its corresponding private key.

7.6.2 Solution

Use a cryptography library's built-in functionality to generate an RSA key pair. Here we'll describe the OpenSSL API. If you insist on implementing RSA yourself (generally a bad idea), see the following discussion.

7.6.3 Discussion

Be sure to see Recipe 7.1 and Recipe 7.2 for general-purpose guidance on using public key cryptography.

The OpenSSL library provides a function, RSA_generate_key( ), that generates a {public key, private key} pair, which is stored in an RSA object. The signature for this function is:

RSA *RSA_generate_key(int bits, unsigned long exp, void (*cb)(int, int, void), 
                      void *cb_arg);

This function has the following arguments:

bits: Size of the key to be generated, in bits. This must be a multiple of 16, and at a bare minimum it should be at least 1,024. 2,048 is a common value, and 4,096 is used occasionally. The more bits in the number, the more secure and the slower operations will be. We recommend 2,048 bits for general-purpose use.
exp: Fixed exponent to be used with the key pair. This value is typically 3, 17, or 65,537, and it can vary depending on the exact context in which you're using RSA. For example, public key certificates encode the public exponent within them, and it is almost universally one of these three values. These numbers are common because it's fast to multiply other numbers with these numbers, particularly in hardware. This number is stored in the RSA object, and it is used for both encryption and decryption operations.
cb: Callback function; when called, it allows for monitoring the progress of generating a prime. It is passed directly to the function's internal call to BN_generate_prime( ), as discussed in Recipe 7.4.
cb_arg: Application-specific argument that is passed directly to the callback function, if one is specified.

If you need to generate an "n-bit" key manually, you can do so as follows:

Choose two random primes p and q, both of length n/2, using the techniques discussed in Recipe 7.5. Ideally, both primes will have their two most significant bits set to ensure that the public key (derived from these primes) is exactly n bits long.
Compute n, the product of p and q. This is the public key.
Compute d, the inverse of the chosen exponent, modulo (p - 1) x (q - 1). This is generally done using the extended Euclidean algorithm, which is outside the scope of this book. See the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. Van Oorschot, and Scott A. Vanstone for a good discussion of the extended Euclidean algorithm.
Optionally, precompute some values that will significantly speed up private key operations (decryption and signing): d mod (p - 1), d mod (q - 1), and the inverse of q mod p (again using the extended Euclidean algorithm).

Here's an example, using the OpenSSL BIGNUM library, of computing all the values you need for a key, given two primes p and q:

#include <openssl/bn.h>
   
typedef struct {
  BIGNUM        *n;
  unsigned long e; /* This number should generally be small. */
} RSA_PUBKEY;
   
typedef struct {
  BIGNUM *n;  
  BIGNUM *d;  /* The actual private key. */
   
  /* These aren't necessary, but speed things up if used. If you do use them,
     you don't need to keep n or d around. */
  BIGNUM *p;
  BIGNUM *q;
  BIGNUM *dP, *dQ, *qInv;
} RSA_PRIVATE;
   
void spc_keypair_from_primes(BIGNUM *p, BIGNUM *q, unsigned long e, 
                             RSA_PUBKEY *pubkey, RSA_PRIVATE *privkey)
{
  BN_CTX *x = BN_CTX_new(  );
  BIGNUM p_minus_1, q_minus_1, one, tmp, bn_e;
   
  pubkey->n  = privkey->n = BN_new(  );
  privkey->d = BN_new(  );
  pubkey->e  = e;
  privkey->p = p;
  privkey->q = q;
   
  BN_mul(pubkey->n, p, q, x);
  BN_init(&p_minus_1);
  BN_init(&q_minus_1);
  BN_init(&one);
  BN_init(&tmp);
  BN_init(&bn_e);
  BN_set_word(&bn_e, e);
  BN_one(&one);
  BN_sub(&p_minus_1, p, &one);
  BN_sub(&q_minus_1, q, &one);
  BN_mul(&tmp, &p_minus_1, &q_minus_1, x);
  BN_mod_inverse(privkey->d, &bn_e, &tmp, x);
   
  /* Compute extra values. */
  privkey->dP   = BN_new(  );
  privkey->dQ   = BN_new(  );
  privkey->qInv = BN_new(  );
   
  BN_mod(privkey->dP, privkey->d, &p_minus_1, x);
  BN_mod(privkey->dQ, privkey->d, &q_minus_1, x);
  BN_mod_inverse(privkey->qInv, q, p, x);
}

7.6.4 See Also

Recipe 7.1, Recipe 7.2, Recipe 7.5

[ Team LiB ]