How much entropy do you need for a secure certificate generation?

Question

So in OpenSSL you have the -engine tag for inputting your own entropy as a source for generating whatever.

1. So if you wanted to generate a 2048-bit RSA certificate how much entropy would you need for it to be secure?
2. Is 1 truly random byte or even one bit of entropy enough for generating a secure certificate?
3. Do you need more entropy for bigger certificates?
4. Is the entropy used raw or is it mixed with something else (in the case of openssl -engine)?

Answer 1

The answer to "how much entropy" is always "128 bits".

The tricky point is that the term "entropy" is very often misused. In general terms, the situation is the following:

• A computer is a deterministic machine. From knowledge of its complete state (contents of disk, RAM and CPU registers) at a time $T$, one can compute its behaviour and state at any time $T' > T$, as long as no new unknown information is injected. Conceptually, this is about simulating the machine.

• The attacker's goal is to try to recover the state at the time of key generation, in order to be able to simulate the key generation process and thus obtain the private key. However, the attacker does not know everything about the state, so he will have to "guess", i.e. to try possible values for the information he lacks. This is known as "brute force".

• "That which the attacker does not know" can be quantified into the notion of "entropy": we will say that the state has an entropy of $n$ bits if the best possible brute force strategy will require, on average, $2^{n-1}$ tries before hitting the right one.

  Note that this notion does not require that the unknown information is exactly a sequence of uniformly random bits. The definition is such that if the attacker knows everything except $n$ bits, which are (from the point of view of the attacker) exactly random, uniform, and independent of each other, then the entropy is $n$ bits. In a more practical setup, the "entropy bits" come from measures of physical events (e.g. precise timing of interrupts originating from the hardware); these measure will be encoded over a lot more than $n$ bits. This is not that much a problem since we can always somehow "concentrate" entropy bits by hashing all them together.

If the attacker-unknown data is a single byte, then the attacker will just have to try at most $256$ possible values (and on average $128$) to recover the private key. This is the same as saying that 8 bits cannot contain more than 8 bits of entropy (and may contain less if the attacker has some partial knowledge of the byte, e.g. he knows whether some values are more probable than other).

The amount of needed entropy is basically: "enough to make brute force stupidly expensive". "128 bits" are the traditional value for "way too much" (it's the new tradition; twenty years ago, we would have used 80 bits, but the relentless advances in technology and economics make an $2^{80}$ computation task less ludicrous than what it used to be). If your private key is generated with a cryptographically secure PRNG which is itself seeded with attacker-unknown data that cumulate at least 128 bits of entropy, then, by definition, brute-forcing that entropy is unfeasible (the attacker won't be able to try more than a negligibly small fraction of the space of possible values), and the job is done.

Note that an attacker gets to choose between trying to brute-force the generation seed, and trying to unravel the private key from the public key using its mathematical structure (e.g. trying to factorize the modulus, in the case of RSA keys). He will use the strategy that is easiest for him. In that sense, you "just" need enough entropy to make mathematical breaks easier than PRNG seed brute-force. In practice you inject enough entropy to make brute-forcing unfeasible, and you use asymmetric keys such that mathematically breaking them is not feasible either (e.g. with RSA, use 2048 bits or more).

Some people argue that if quantum computers ever come to fruition, then, in some sense (and with a lot of usually unspoken caveats), an attacker with a quantum computer could quantum-brute-force an $n$-bit PRNG seed with cost $2^{n/2}$ only (with a variant of Grover's algorithm); thus, "256 bits" would be needed to protect against that. On the other hand, a working quantum computer would break through the mathematics of a RSA, DSA, DH or elliptic curve key with extreme efficiency, making the point moot: as long as you use RSA, you are making the bet that quantum computers do not exist (and, for now, this is not that bad a bet).

Answer 2

I feel like this is a trap, but don't you need 2 random prime numbers that are a 1024 bits long? So how much random data you consume depends on how you pick those primes, maybe without any optimization you use 1024 bits, pick a random number, then add 1 continuously until it passes your primality test, then use this as your P or Q.