0
$\begingroup$

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!

Improve this question
$\endgroup$
14
  • $\begingroup$ Key generation does not involve OAEP. OAEP only applies when you encrypt data. $\endgroup$
    – CodesInChaos
    Commented Nov 14, 2017 at 10:51
  • 1
    $\begingroup$ You never really need more than 256 bits of entropy you use to seed a CSPRNG. $\endgroup$
    – CodesInChaos
    Commented Nov 14, 2017 at 10:53
  • $\begingroup$ @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? $\endgroup$
    – Paul Uszak
    Commented Nov 14, 2017 at 11:03
  • 1
    $\begingroup$ 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). $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 14, 2017 at 11:07
  • 1
    $\begingroup$ @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 $\endgroup$
    – daniel
    Commented Nov 14, 2017 at 12:06

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – daniel
    Commented Nov 14, 2017 at 11:10
  • $\begingroup$ Do you mean just how many bits can be encrypted by OAEP + the randomness introduced into OAEP? $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 14, 2017 at 11:13
  • $\begingroup$ 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. $\endgroup$
    – daniel
    Commented Nov 14, 2017 at 11:16
  • $\begingroup$ "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. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 14, 2017 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.