6
$\begingroup$

Creating a 2048bits RSA keypair I figured that doing this using

  • openssl takes as an input 32bytes of "randomness" from /dev/urandom
  • pgp (openPGP) takes as input 300 bytes of "randomness" from /dev/random

My questions is. Does the number of randomness influence the cryptographic qualities of the resulting keypairs?

$\endgroup$

1 Answer 1

8
$\begingroup$

The difference is inconsequential in this context.

If you do some "processing" (e.g. generating a RSA key pair) using a deterministic and publicly known algorithm (e.g. OpenSSL's code) where the only parameter which is not known to the attacker is a random $n$-bit seed (e.g. $n$ = 256 for 32 bytes from /dev/urandom), then there is a theoretical possibility of an attack by exhaustive search on the seed: the attacker tries to guess your private key by trying out all possible seed values, until he finds one which yields your actual public key when fed to the deterministic key pair generation algorithm. The cost of that exhaustive search is, on average, $2^{n-1}$ tries. When $n$ grows, this cost soon becomes too prohibitive to be envisioned by the attacker.

Indeed, a 2048-bit RSA key can also (and still theoretically) be broken through integer factorization. How the cost of integer factorization relates to the cost of exhaustive search is not an easy question, because the involved algorithms have quite distinct characteristics (exhaustive search uses almost no RAM and is easy to make parallel, while integer factorization gobbles gigabytes or more of RAM and some parts of it are very hostile to parallel computing). You may peruse this site for various estimates from different groups of smart people. Bottom-line is that a 2048-bit RSA key can be deemed "as strong" as a symmetric key in the 100 to 115-bit range (which translates to an uncertainty by a factor of more than 30000, which shows how fuzzy these estimates are).

From this, we can conclude that any seed length beyond 115 bits is overkill: as long as the seed is "really random" (i.e. completely unknown to the attacker) and its length is at least 115 bits, then exhaustive search on the seed is not worth the effort for the attacker, since integer factorization will be easier (2048-bit integer factorization is not doable with existing technology anyway, but neither is a 100-bit exhaustive search). OpenSSL's 256 bits are thus total overkill with a wide margin; GnuPG's whooping 2400 bits even more so.

Then there is the recurrent debate about /dev/urandom vs /dev/random. To make things short, neither is "stronger" than the other (despite widespread myths), but /dev/random may imply usability issues (blocking at inopportune times) which can turn into actual security issues, so its use is discouraged. In that sense, OpenSSL does the Right Thing, and GnuPG errs. See this page for a well-explained summary of why /dev/urandom should be preferred.

$\endgroup$
2
  • $\begingroup$ fantastic answer, which really helped me to understand why with a good estimation the difference of 256 vs 2400 bits does rather not impact the safety. I really learned here! thank you much! $\endgroup$ Commented Mar 16, 2014 at 17:58
  • $\begingroup$ @humanityANDpeace If you think this answer answered your question, please use the check mark button beside it to mark it as "accepted". $\endgroup$ Commented Mar 19, 2014 at 12:25

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.