# Key space: Dense and sparse

I'm taking a cryptography class and I come across these terms dense and sparse key space allt he time. What do they mean?

As far as I can I understand, dense key space means that there are more combinations of the keys in that particular space and sparse the opposite. If yes, assuming I use elliptic key cryptography i.e.

y^2 = x^3 + ax^2 + bx + c,

How is it that elliptic key cryptography is more dense(less sparse) than the RSA cryptography?

Please tell me if I need to be clearer.

-

This "dense key space means that there are more combinations of the keys in that particular space and sparse the opposite" is pretty much it.

Depending on cryptographic algorithm, key space can be less or more sparse. This depends on what primitives and possibly, what hard problems the security of the algorithm is based on.

Symmetric cryptographic algorithms use just one key and use simple algebraic or logical operations. Because these operations generally work with all possible input values, they key spaces can be (and usually are) dense. For many symmetric algorithm, each possible combination of bits of input key space is valid key (maximally dense), for some others bits less.

Public key algorithms use separate public key and private key, with specific semantics: it should be reasonably hard (likely require brute-force search of key space) to discover private key if public key is know. This kind of more complex semantics put more requirements into the operation of the algorithm. Algorithms become more complex, much slower and the key sizes they use become larger. The currently known public key algorithms are based on some problems known to be hard.

For instance, RSA is based on integer factorization problem: it is hard to factor composite number built from two prime numbers to prime numbers that make up the number. This is actually already quite close to the reason why RSA's key space is sparse. The RSA key for common 2048-bit key size is built from two 1024-bit primes. Prime number theorem describes how to estimate number of primes smaller than specify number. Math question How many all prime numbers p with length of bits of p = 1024 bits? answer can be used to estimate how sparse RSA key space is: only $\frac 1 {2ln 2^{1023}}$ out of 1024-bit bit combinations are acceptable prime numbers, and it is required to have two such primes. This means that only around every millionth of number between $2^{2047}$ and $2^{2048}$ is acceptable, which could be considered relatively sparse.

(Note: in RSA also public exponent needs to be chosen. For simplicity I've not considered full RSA key generation here, feel free to refer NIST's FIPS 186-4 standard in case you want more detail).

When considering elliptic curves, important number to consider is prime number n, one of the curve parameters. For most curves, (nearly) any number smaller than n will be acceptable private key. Thus it is easy to see that the key space is considerably denser than RSA.

Note: for EC, some of formats for the public key take twice as much bits to represent than the strength of the curve (or private key). Still, they are significantly denser than RSA of equivalent strength.

## Relation with security

The sparse/dense key space has some relation with strength of the cryptographic algorithm. If only acceptable keys are prime numbers, then possible attackers may skip many of keys with little processing. Thus the strength of the algorithm can be considered to be at most the effective key space, this does not, however, remove any other algebraic reasons why there would be even better (easier) ways to attack the algorithm.

Please, tell me if I need to be clearer.

-
Thank you for the detailed answer! –  P R Oct 22 '13 at 5:48