This is something which I have been wondering and trying to find an answer for, but yet to come even remotely to one.
Why do you need a
4096-bit DSA/El-Gamal key when AES uses only
Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.Sign up to join this community
This comes down to algorithm design.
Symmetric algorithms are designed to be as simple and quick as possible (for cryptography anyway), and retain a high level of security. A symmetric AES key with 256-bits yields 256 bits of work. Which is currently enough bits of security. Asymmetric cryptography require that the key sizes be larger to provide equivalent levels of security (in bits).
A symmetric key is just a bunch of bits. When you have a 128-bit symmetric key, you have 128 bits, with the two following important characteristics:
These two characteristics mean that (barring some weakness in the encryption algorithm that uses these key), if you want to break such a key, you have no choice but to try out all potential keys until you get lucky and hit the right one, with an average cost of 2127 trials.
With asymmetric algorithms, things don't go that way. To get the "asymmetry", you cannot just throw together operations and key bits into a big tangled mess, like symmetric algorithms do; you need mathematics. Structure. So the public key will be an encoded mathematical object with a lot of internal structure:
In RSA parlance, the public key is a pair of integers: the modulus and the public exponent. The public exponent is normally very short. The "key length" is traditionally the length (in bits) of the modulus, where the mathematical structure hides: the modulus is a big composite integer, and the hidden structure is the knowledge of the two (or more) prime factors of the modulus. We know of integer factorization algorithms that can factor a n-bit modulus in a lot less than 2n-1 trials.
The net consequence is that asymmetric keys are "larger than their strength": the mathematical structure needs room.
Another consequence is that the "strength" achieved by an asymmetric key depends on the key type: for instance, ECDSA keys internally use elliptic curves, which has extremely little to do with integer factorization. So it is usually estimated that you get "128-bit strength" with a 256-bit curve.
It just so happens, by some freak coincidence (well, mostly), that algorithms based on discrete logarithm modulo a big prime (Diffie-Hellman, DSA, ElGamal -- not the elliptic curve variants) offer a strength which is roughly similar to that of RSA for a modulus of the same size. From there comes a traditional (and confusing) habit of talking about "asymmetric key strength" as if it was a generic property of the "key size" regardless of the actual key type and algorithm. This is a wrong but widespread notion.
For details on key strength estimates, see this site.
Homo neanderthalensis, who, for some authors, should be called Homo sapiens neanderthalensis, was apparently able of abstract thought and left traces of mysticism (e.g. burial rites) and a few pieces of art (not a lot, though). However, he was still an "hunter-gatherer" and when you spend your days trying to stick a spear in a big animal so that you do not starve, you tend to apply practical, no-nonsense solutions to everyday problems. You don't get mathematicians until you have both agriculture and cities of sufficient size to support such people that do not directly contribute to today's evening meal.
A symmetric key is actually considered secure for the forseeable future at 128 bits. While RSA requires 2048-bit keys for 112-bit security, ECC only requires 256-bit for 128-bit security.
In all cases, length of the key is utterly irrelevant. What's important is what sort of attacks are possible. With a symmetric key, it's essentially a random string of whatever its length is; the attacker has no constraints other than the length of the key. This means that brute force is a general search problem, which takes a very, very long time to do on even 2^128 possible keys.
For asymmetric keys, there are two factors. First, very few appropriate-length strings are valid RSA keys. That means that 2048 bits leaves you with many fewer possibilities to check out than if it was a symmetric key of similar length. Furthermore, you'd be an idiot to randomly brute-force: you have a public key, and know what relationship it has with the private key. You can instead use a sophisticated and maximally efficient algorithm to try to get the private key (e.g. you can try factoring an RSA key). With elliptic curve cryptography, these have much lower impact on security than with RSA, which is the main advantage of ECC -- ECC requires around twice as long a key as a similar symmetric algorithm, while RSA, DH, and other problems over finite fields require much longer keys for similar levels of security.
The difference is in the nature of the keys. AES is a symmetric cypher where every 256-bit number is a valid key. This give you a huge range of numbers to choose from. DSA, on the other hand, is a signature algorithm based on public-key cryptography, and there are some strong mathematical constraints on the values involved, which makes guessing the private key easier. This means that a much longer key is needed to ensure security.