11

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 256-bit keys?

  • 2
    to the OP - the update is for clarity: DSA is not used for the key itself, but for signing the key. Most other implementations use El-Gamal in conjunction with DSA to do encryption and signing. – Rory Alsop Jun 2 '14 at 8:43
  • 1
    Closed the newer one as a duplicate of the older one, and merged the answers. Traven, you may wish to review to see if one of the merged answers is more applicable - you can change the check mark if so. – Rory Alsop Feb 4 '15 at 11:26
7

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

enter image description here

Image Source

  • This is a nice, concise graphic - can you link the source? – cslstr Feb 3 '15 at 17:49
  • @cslstr Couldn't find it again, changed it to a new one. Prettier with a link to the source. – RoraΖ Feb 3 '15 at 18:39
21

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:

  1. Any sequence of 128 bits is a potential key, so there are 2128 of them.
  2. There is no internal structure to these 128 bits.

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:

  1. The public key is encoded as n bits, but not all sequences of n bits are a valid public key.
  2. To break the key, one needs to unravel the internal structure. This can be done a lot more efficiently than the ham-fisted, Neanderthal-level, brutal enumeration of possible private keys until luck happens.

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.

  • 2
    Since this is a common misunderstanding, I want to clarify that the fact that not every bitstring of the desired length is a valid RSA key is not responsible for the low security in relation to the key size. The number of public keys, even for easily breakable 512 bit RSA, is far beyond what brute-force can break. – CodesInChaos Feb 3 '15 at 18:46
9

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.

7

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.