1
$\begingroup$

Of say 4096 bits as is a default GPG master key.

I can manage the first one or so almost immediately on Ubuntu. It then runs out of entropy when generating several more RSA keys, and I'm forced by GPG into mouse wiggling and keyboard smashing. More entropy is clearly required in those cases than available from /dev/random.

Is there some measure of the total amount of entropy bits needed to make a single 4096 bit RSA key?

Close but not quite is Detecting the amount of entropy used for random number generation. Nor How to generate 1024-bit RSA key as that only calculates the bits in the final key pair. Some sort of combination is probably required to take into account primacy testing.

Improve this question
$\endgroup$
1
  • $\begingroup$ This question is not well-defined enough to answer precisely. How you generate the key matters significantly. If you store a 256-bit secret you can use that to power a CSPRNG to generate any further secret bits. This will give a significantly different answer to your question than pulling all of the bits straight from /dev/random. $\endgroup$
    – Ella Rose
    Jul 2, 2019 at 14:42

1 Answer 1

Reset to default
4
$\begingroup$

Is there some measure of the total amount of entropy bits needed to make a single 4096 bit RSA key?

Well, there are two relevant attacks against RSA:

  • The attacker uses NFS to factor the modulus

  • The attacker scans through the possible entropy inputs that possibly generated the public key, and for each such input, generates the corresponding RSA public key, and see if that's the one he's looking for.

The first attack is estimated to take circa $O(2^{160})$ time; while the second attack will take circa $O(2^k)$ time if we use $k$ bits of entropy, hence if we use $k=160$ bits of entropy, the second attack is no easier for the attacker than the first (which doesn't depend on how much entropy we collect). Note that this rather crude analysis ignores some significant constant factors (the algorithm to turn an entropy sample into an RSA public key isn't cheap); however for this question, it should be good enough.

In addition, if we use our 160 bits of entropy to seed a good CSPRNG, and use the CSPRNG output to generate the actual bits used by the prime searching algorithm, that means that there is no easier entropy-based attack.

So, 160 bits are sufficient, and significantly fewer entropy bits will cut into the security of the RSA key.

Now, that's what is possible; I don't know the algorithm that GPG uses to search for RSA public keys - they may use significantly more.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You should also mention attacks like ROCA against Infineon's RSA key generation, where the evaluation went through as there was plenty of entropy, but in which all the entropy was useless due to structural weaknesses permitting the usage of Coppersmith's attack. $\endgroup$
    – j.p.
    Jul 2, 2019 at 20:49
  • 2
    $\begingroup$ @j.p.: there are a lot of known stupid ways to generate RSA keys; I rather assume that GPG avoids them, and so we only need to deal with the generic attacks... $\endgroup$
    – poncho
    Jul 2, 2019 at 21:12

Your Answer

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

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