> More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the key space is very dense, which reduces the key size for an "equivalent" encryption strength.

This isn't correct.

The reason RSA (and classic DH) keys are gigantic is because index calculus techniques yield efficient attacks on systems based on finite fields. We need big keys to make them impractical.

EC systems are not susceptible to these attacks because the points on a curve comprise only a group and not a field. Counterintuitively (to me, at least!), they're safer because they have less structure.

On the question of whether it's intuitive or not: NP-complete problems tend to have fairly little structure. A problem like boolean satisfiability has basically no structure: all you have is a soup of clauses. The "tricky" problems that have solutions in P get their solutions from clever exploitation of structure.

At least, that's how it becomes more intuitive to me.

The structure of a problem specifies it; an unstructured problem is less well-specified, and that makes it intuitively more difficult to approach.

E.g. summation of a column of decimal numbers is a highly structured problem that's very easy to solve. Parsing the speech of yelling drunkards is not so structured, and much harder to solve.

And now my new crypto startup will be the first to market this with YDAAS (Yelling Drunkards As A Service).

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!

[0] https://www.yubico.com/2015/02/big-debate-2048-4096-yubicos-...

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.