Very informative, thanks for the detailed response. To be clear, was my statement incorrect in terms of the "16%" quotation (from [0], which I now realize I misquoted in my private notes), or in the claim that the RSA key space density is low due to the dependency on prime numbers?
My private notes include a claim (original source uncited, sadly) that because the prime density from 1..n decreases (approximately) as `1/ln(n)`, then the corresponding effective key space density for RSA decreases at a related rate, which was what led to the corresponding reduction in the "equivalent" key size. If my notes on this are complete bunk I'd love to hear it. (Even a simple 'yes' would suffice and I'll revisit the subject.) Ta!
It's true that the space of valid RSA keys is sparse relative to size, but this isn't why we need big keys. As a counterexample, classic DH keys are also big (or they can be), even though the space of valid keys is dense.
We need big keys (or rather big fields) due to index calculus. This is a family of algorithms used to factor integers and compute discrete logarithms in finite fields. The fact that index calculus is (thus far) inapplicable to elliptic curve groups is the primary motivation for ECC.
My private notes include a claim (original source uncited, sadly) that because the prime density from 1..n decreases (approximately) as `1/ln(n)`, then the corresponding effective key space density for RSA decreases at a related rate, which was what led to the corresponding reduction in the "equivalent" key size. If my notes on this are complete bunk I'd love to hear it. (Even a simple 'yes' would suffice and I'll revisit the subject.) Ta!
[0] https://www.yubico.com/2015/02/big-debate-2048-4096-yubicos-...