Why does the recommended key size between symmetric and assymetric encryption differ greatly?

Question

In various articles it is mentioned that for secure communications, the recommended key sizes are 128-bit key size for symmetric encryption (which makes it $2^{128}$ possible keys?) and 2048-bit key size for asymmetric encryption ($2^{2048}$ possible keys?).

Why do they differ so greatly? It seems like I am missing a very big part of the equation.

Answer 1

Symmetric encryption and asymmetric encryption algorithms are built upon vastly different mathematical constructs.

In typical symmetric encryption algorithms, the key is quite literally just a random number in $\left[0 .. 2^n\right]$, where $n$ is the key length. The strength of the key is based upon its resistance to brute-force attacks, where an attacker would need to perform an attack with complexity $O\left(2^n\right)$ to correctly guess the key.

Asymmetric algorithms, on the other hand, use a different kind of key. For example, an RSA modulus is of the form $m = pq$, where $m$ is the modulus, and $p$ and $q$ are two large, distinct, randomly-chosen prime numbers of roughly equal sizes. The strength of the key is based upon the modulus' resistance to factorization into its prime components. An attacker using a general field number sieve would need to conduct an attack with complexity $O\left(\exp\left(\left(\left(\frac{64}{9} + o\left(1\right)\right) \cdot n\right)^\frac{1}{3}\left(\log n\right)^\frac{2}{3}\right)\right)$ to factor the modulus (and thus break the private key), given a modulus of bit-length $n$.

Answer 2

The tl:dr answer to your question is that there's no known reason why public keys have to be longer than symmetric keys for a given security parameter but we just haven't worked out how to do it yet.

It might be possible to prove that all public key systems can be broken appreciably faster than exhaustive search but this has not been done as far as I know.

We need to draw a distinction between the size of the key and the number of keys. For RSA the modulus may be 2048 bits long but only about two out of a million numbers of that size would be usable moduli. Additionally, it's possible to come up with an RSA scheme were more than a half of the high bits of the modulus are fixed by convention so the amount of information that needs to be distributed is halved.