← Back to context

Comment by wolf550e

7 years ago

RSA-2048 is only about 112 bits of security because index calculus methods of breaking RSA-2048 (and DHE-2048) have an algorithm with ~2^112 steps to break it, not because of the amount of entropy used to generate the key [4].

An RSA-2048 keypair is generated by taking a CSPRNG like the one I proposed, generating 1024 bit numbers, checking them for being a prime number using Miller Rabin [1] until the chance of the number not being prime is below 2^-128 (generating new candidate primes if the current one turns out to be not prime), and then doing it all over again for the other prime. The two 1024 bit probably-primes "p" and "q" are the private key, their product "n" (with the public exponent e=65537) is the public key. Most systems precalculate some derived values used to speed up operations and store them with p and q, but you don't have to [2][3].

The RNG I proposed is absolutely good enough to generate RSA key pairs. There is no benefit to using "true hardware randomness" for generating candidate primes, after the initial pool of 256 bits of entropy has been generated.

1 - https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...

2 - https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generat...

3 - https://tools.ietf.org/html/rfc8017#section-3.2

4 - https://crypto.stackexchange.com/a/8692/24949