How are the keys used in cryptography generated?

Question

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?

Answer 1

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.

Answer 2

I know they have to be random

Well, kind of. More precisely, they have to be indistinguishable from random.

The goal when choosing a key is that the adversary (the “bad guy”) won't be able to find the key. Since the adversary may know how our system works (Kerckhoffs's principle), we need to find a way to generate keys that don't only depend on a deterministic computation (which the adversary could reproduce). Therefore all keys must depend on something that the adversary does not know. Such a thing is called a “true” random value.

Random values can be generated using various unpredictable physical processes. A device that implements such a process is called a hardware or “true” random number generator (HRNG or TRNG). Pretty much all modern smartphones and PC, and a growing number of embedded devices, include a HRNG.

Once a system has been “seeded” with a true random value, it can use a deterministic calculation called cryptographically secure pseudorandom generator (CSPRNG) (pseudorandom generator for short) to generate a practically infinite stream of random values. These values are random in the sense that an adversary with finite computing power cannot distinguish them from “true” random values. In a cryptographic context, a random generator (RNG) is a CSPRNG seeded by a HRNG.

is that all the properties required?

Each key must be indistinguishable from random, from the point of view of potential adversaries. This can mean that the key is generated randomly (as explained above). But not all keys are generated randomly: some keys are calculated deterministically from a mixture of keys and other inputs. Such processes are called key derivation. HKDF is an example of a key derivation function. A pseudorandom function (PRF) can be a building block for a KDF. For example, when two computers communicate over an encrypted channel, they typically derive the same keys from a shared secret.

“Random”, for a key, means as close as possible to uniformly random among the set of possible keys. What this means depends on the type of key.

Generally, symmetric encryption uses keys that are just an array of bytes, and so generating an $n$-bit key just means generating $n$ random bits and calling that a key. This is true, for example, of block ciphers such as AES and Camellia, of stream ciphers such as Chacha20, of MAC algorithms such as HMAC and Poly1305, etc.

Classical asymmetric encryption uses keys that are numbers with certain properties, and so generating such keys can involve additional calculations. A generic way of generating a key that can be represented by an $n$-bit string is to generate $n$ random bits, check if this represents a valid key, and if not try again. (This assumes that the representation is unique, i.e. that there aren't two identical keys with the same representation.) This approach works well for typical ECC keys, where a private key is a number between $1$ and $2^n - a$ with $a \ll 2^n$, so it works well to generate a random $n$-bit string and interpret it as a number between $0$ and $2^n-1$ and try again if you hit one of the few invalid values. Some other cryptosystems, such as RSA, involve far more complex key generation processes, but even so it uses “generate a random bit-string” and “try again if the value is unsuitable” as building blocks.

Answer 3

It seems there are keys everywhere in cryptography.

And so it seems. I have so many I have to put them on Post-its stuck to my monitors.

But if you need more than can be made by tossing coins, there are machines that can do that. There are things like this, this and this. They spew out randomness ad infinitum.

Why would you need so many keys? Good question. And there are threee reasons:-

1. Clearly if you have to access multiple services, you'll need multiple passwords /keys. IT professionals typically have 100's of passwords /keys. You generally pick the passwords from your life experiences. So my iguana's name features in most of them (Trevor). Spreadsheets are useful for managing this.

2. You don't trust the government that commonplace cryptography hasn't been broken in polynomial time. You might want to roll your keys over every 15 minutes. That's surprisingly only ~0.1 bits/s of entropy which is easily generated with minimal resources.

3. You don't trust the government that commonplace cryptography hasn't been broken in polynomial time. And so (as diplomatic services do [why?]) you use one time pads. That requires a truly random key symbol for every plaintext symbol you send. This statistically is no different than point 2.

are they more than just random numbers?

No. They're just random numbers with a uniform distribution. But, there is the concept of Kolgomorov complexity. That means the source of the numbers is not deterministic. It is universally unique. Again, easily achieved but requires some thinking. \dev\urandom is deterministic so can't be used for point 3.

---

Also see quantum key distribution which facilitates the secure exchange of keys between multiple parties.