How are the keys used in cryptography generated?

It seems there are keys everywhere in cryptography. From things like HMAC to encryption (both asymmetric and symmetric).

The bit I do not totally understand now is how are cryptographic keys generated? I know they have to be random, but is that all the properties required?

Do the method of generation also differ depending on the use case? For example does the generation method differ for keys used in HMAC versus keys used as part of a signature?

Doing some googling I have come across a couple of terms which is related to keys and random numbers. Eg, PRNG, RNG, HKDF, VRF, PRPs, PRFs etc.

The problem is, it is difficult to consolidate all these information to succinctly answer the questions I have about cryptographic keys. How are they generated? What mechanism come to play in key generation, are they more than just random numbers? and do certain use cases call for certain ways of generating these keys?


Cryptographic keys should generally be generated secretly and uniformly at random in the cryptosystem's key domain; that is in the set of valid keys for the cryptosystem. What makes a key valid depends on the cryptosystem and often parameters (typically including key size).

In some cryptosystems, including most symmetric ones, the set of valid keys is simply the set of bitstrings the size of the key, e.g. 192-bit for AES-192.

Things are more complex in asymmetric cryptography. One reason is that it's it's generated a key pair, comprising a secret private key, and a matching public key. Another reason is that there are typically some mathematical constraints. For example, in the relatively simple case of ECDSA, a valid private key in an integer $d$ in range $[1,n-1]$ where $n$ is the order of the generator $G$ of the elliptic curve group, and the matching public key is then obtained as the elliptic curve point $Q:=d\,G$. Things are more complex for RSA.

With the key domain defined, there remains to explain how it's generated a uniformly random key. The simplest is fair coin toss, repeated as necessary (e.g. 192 times for AES-192). Should we need to generate an integer in a range $[a,b]$, there are various methods to do this from fair coin toss. The simplest is to generate $\left\lceil\log_2(b-a+1)\right\rceil$ bits by fair coin toss, assemble the bits into an integer $x$ per big-endian binary convention, compute $y=a+x$, use that if $y\le b$, otherwise repeat the procedure.

This method can be automated using a cryptographically strong random number generator, such as /dev/urandom in most unix flavors.

There are substitutes where instead it's used a key derivation function, to compute the key from another key, or sometime from a memorable passphrase.

External Links

External links referenced by this document: