[sdevlin]

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.