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

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.

-
Not every asymmetric system needs those huge keys. Elliptic curves for example only need a key twice as large as those used for symmetric crypto. –  CodesInChaos Feb 4 '13 at 22:30
Short answer: In order to provide comparable levels of security. –  David Schwartz Feb 5 '13 at 10:12

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$.

-
Yes, sorry, that was a mistake on my part overloading $n$ to mean both the bit length of keys as well as the modulus. It's been fixed. –  Stephen Touset Feb 5 '13 at 5:43
@fgrieu I used Wikipedia's article on integer factorization. –  Stephen Touset Feb 5 '13 at 19:50
Edited reply to fix. –  Stephen Touset Feb 6 '13 at 18:58