Guidelines for cryptographic key generation

Question

I was wondering whether you know can point me to some general (basic) principles/guidelines one should follow for generating cryptographic keys? I have looked at NIST 800-133, but was hoping for some principles a bit more general and less technical.

Specifically I’m thinking of asymmetric key pair for use of RSA and symmetric key for use of HMAC. For example, I assume that the key should have some randomness to it.

Thank you.

Answer 1

As for the randomness it is simply sufficient to have a cryptographically secure PRNG to generate the HMAC key and RSA key pair. You should make sure that the PRNG is a well known algorithm and well seeded, and you should perform self tests during startup. Having a malfunctioning or incorrectly seeded PRNG is one of the most common reason for vulnerable keys.

• The HMAC key simply consists of random bits. You can directly use the output of your random number generator.

• The RSA key pair generator requires a random input to find the random primes of half the key size. This generator will likely use a high number of random bits.

With regards to key lengths take a look at keylength.com.

• Make sure your hash algorithm used within the HMAC construction is of the same size as the key size.
• It is strongly recommended to only choose 8-bit multiples for the RSA key size in order to reduce compatibility issues.

---

RSA-specific notes:

• It is best to choose a public exponent in advance, 0x010001 (65537), the fourth prime of Fermat is a popular - and often the default - choice.
• Key sizes of the form $2^x$ or possibly $2^x + 2^{x-1}$ are highly recommended (e.g. 2.048, 3.072, 4.096, 8.192, 16.384 bit keys).
• There is technically no need to go for ANSI X9.31 key generation (now practically replaced by FIPS 186-4 with appendix B.3); however, if a private key must run on yet unspecified hardware (as long-term root keys should), it is prudent to use primes with $2^{(n-1)/2}<p<2^{n/2}$ where $n$ is the public modulus size (one of the requirements of these standards).
• RSA private keys should contain CRT parameters so as to make it straightforward to speed up RSA private key operations.
• Beware that an RSA private exponent may be smaller in size - even in bytes - compared to the modulus, this is no reason to worry (unless it is much smaller).
• Beware that RSA key generation can take a long time compared to other cryptosystems, including asymmetric; and this time varies widely and without firm upper bound from one key to another. This is a classic issue for mass production of devices with internal key generation, or when defining a maximum delay for supervising software.

---

For optimum assurance you should use a FIPS or Common Criteria validated software and hardware component (HSM, smart card) for key generation, key storage and key usage. Beware that computer memory may not always be secure. Key generation is the easy part, correct key management is much harder.

Answer 2

Efficient RSA key generation algorithms can be found in http://dx.doi.org/10.1007/11894063_13