# How many random bits are required to create one RSA key?

If we were observing how many bits are taken from a random number source, what is the total number of bits required for creating a 4096 bit key using a current RSA implementation? This means the total of the number of bits for finding the random primes P and Q, and the random number for the OAEP (padding), and any other random bits that might be needed that I'm not yet aware of.

Thanks!

• Key generation does not involve OAEP. OAEP only applies when you encrypt data. – CodesInChaos Nov 14 '17 at 10:51
• You never really need more than 256 bits of entropy you use to seed a CSPRNG. – CodesInChaos Nov 14 '17 at 10:53
• @CodesInChaos Isn't that effectively a 256 bit key then? It's the old underlying entropy input thing. Couldn't you (in extremis) use an 8 bit seed to generate a 32 Kbit RSA key? – Paul Uszak Nov 14 '17 at 11:03
• For that just look at keylength.com. Note that there is a difference between the key size (the size of the modulus for RSA: 4096 in your case), the effective strength in bits (slightly upwards of 128 bits indeed) and the encoded size of an RSA key (depends on the encoding scheme). – Maarten Bodewes Nov 14 '17 at 11:07
• @CodesInChaos 1) if every other part of a hybrid crypto system did offer informational theoretical security then we know the RSA problem is the only attackable part. 2) I am asking about how much randomness a typical implementation might consume. One of the two points people usually bring up about the OTP is how randomness is not cheap. Yep that is another possible consumer of random bits I did not think about! recycling thrown away random bits is another interesting topic, a tiny example math.stackexchange.com/q/2243304/438622 – daniel Nov 14 '17 at 12:06

For creating an RSA key pair you need an undefined number of random bytes from the source. The reason for this is that finding primes is indeterministic and hence it may be required that multiple random large numbers are required. In the end this also depends on the details of the key pair generator used.

However, it is possible to use a well seeded DRBG / PRNG for the key pair generation process. A PRNG is a deterministic or pseudo random number generator; it depends on the entropy of the seeds to generate a computationally random stream of bytes. That is: only the seed is truly random, but to an attacker the output of the PRNG is indistinguishable from random.

If a secure PRNG is used then using 256 bits of seed is all you need; for constrained systems you could even bring this down to 128 bits (at the cost of a lower security margin, of course). So if your system has issues generating large amounts of randomness you could seed your own PRNG and inject it into the RSA key pair generator - if that's possible for your runtime.

OAEP is a padding scheme independent on the key pair generation. That is: the calculations performed for key pair generation do not rely on the calculations performed by OAEP. OAEP may be performed on any secure RSA key pair, as many times as required. As per specification it uses hLen random bytes per usage, which means 32 bytes when SHA-256 is used and 64 bytes for SHA-512.

• I'm not sure how to change my question, but I was after the number of bits after the PRNG if one was used. LIke imagining the random source was either a PRNG or a list of physical coin flips, or anything. Pretty much asking how infeasible is it to use OTP as the symmetric cryptosystem in a hybrid, in terms of random number generation. – daniel Nov 14 '17 at 11:10
• Do you mean just how many bits can be encrypted by OAEP + the randomness introduced into OAEP? – Maarten Bodewes Nov 14 '17 at 11:13
• No I was thinking OAEP would likely be used if you were trying to RSA across a key, that you would later use for a OTP (and would then be something else consuming the output of the RNG). if there is a common RSA implementation that doesn't use OAEP then its a red herring. – daniel Nov 14 '17 at 11:16
• "RSA across a key" doesn't make any sense to me. You mean you want to use the output of RSA/OAEP as key? Then you would have a pretty well distributed output of hLen bytes worth of entropy. There is PKCS#1 v1.5 padding, RSA KEM and OAEP, but I don't understand where you are going with that last sentence either. OK, gotta move, will reply more in evening time. – Maarten Bodewes Nov 14 '17 at 11:20