Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
Asymmetric keys have to be much larger than symmetric keys because 1) there are less asymmetric keys for a given number of bits (key space), and 2) there are patterns within the asymmetric keys themselves.
To compare, consider that the ECRYPT II recommendations on key length suggest a 128-bit symmetric key is as strong as a 3,248-bit asymmetric key, and these equate to a 256-bit Elliptic Curve Diffie-Hellman (ECDH) key. Both key lengths (128-bit and 3,248-bit) are generally recognized as providing long term protection of data (until 2040), but the asymmetric key is much larger.
For further comparison, NSA Suite B Cryptography (unclassified algorithms) specifies both the 128-bit symmetric key space (for encryption) and the 256-bit ECDH key space (for signing and key exchange) as adequate to protect classified data upto Secret.
Typically, symmetric-key algorithms in common use are designed to have security equal to their key length. However, no asymmetric-key algorithms with this property are known. Elliptic curve cryptography comes closest with an effective security of roughly half its key length. (source: Wikipedia)
In a perfect world, the idea is that the only way to break into a network connection or a data store secured with a symmetric cipher is to try all the keys. A 128-bit key space means there are only just a mere 340,282,366,920,938,463,463,374,607,431,768,211,456 possible keys that could be used.
Consider trying to test all these keys for a 128-bit AES encryption using the special AES instructions added to the latest Intel microprocessors. These instructions are designed to be very fast and according to Intel's own data decrypting a block of AES encrypted data would take 5.6 cycles on Intel i7 Processor with 4 cores. Put another way, that processor could try out one key on one block of data in about 1.7 nanoseconds. At that speed it would take it about 1.3 * 10^12 * the age of the universe to check all the keys (you'd probably only have to check half before finding the right one so divide that incredibly long time by two).
So, breaking 128-bit keys by brute force isn't terribly practical. (Breaking 256-bit keys is even less possible.) For symmetric ciphers, keys of these lengths make sense.
Now, unlike a symmetric cryptosystem, asymmetric cryptography works by having two different keys (one for encryption and one for decryption), which are related by some mathematical process.
For example, in the popular RSA scheme used with SSL/TLS the public and private keys consist in part of the product of two large prime numbers, and so making an RSA key starts with picking two random primes. The security of RSA relies (in part) on the fact that it's easy to choose two random prime numbers, but it's very hard to discover what they are when just given their product.
Suppose there are two prime numbers picked at random called p0 and p1. Part of the RSA public (and private) key is called the modulus and it is simply p0 * p1. If an attacker can factor the modulus into p0 and p1 they can break RSA because they can determine the private key. Mathematicians believe that it is very hard to factor a product of two primes and the security of web transactions relies, in part, on that belief. (The "hardness" of integer factorization has not been proven. It's presumed difficult but there's no real formal proof of it.)
Typical RSA key sizes are 1,024 or 2,048 or 4,096 bits. That is the number of bits in the modulus. For each there will be a pair of primes of about 512 bits or 1,024 bits or 2,048 bits depending on the selected key size. Those primes are chosen by some random process (highlighting the importance of cryptographically secure random number generators).
Just as in the case of symmetric keys, attacks on say 2,048-bit RSA are based on trying out all keys of a certain size, but unlike the symmetric key scheme not every 2,048-bit number is an RSA key (because it has to be the product of two primes).
So, although the key space is larger there are actually fewer possible RSA keys for any given number of bits than there are for the same symmetric key size. That's because there are only so many prime numbers of that size and below. The RSA scheme can only use pairs of prime numbers, whereas symmetric schemes can use any number at all of the same size.
Any time there's a pattern in a key it represents a weakness in the cryptosystem. For example, in a perfect world, people would create and memorize completely random passwords. Because they don't, there are patterns in their passwords which can be guessed or broken without having to try every possible one.
RSA keys have a distinctive pattern: they are the product of two prime numbers. That provides the weakness, and it is best exploited by the General Number Field Sieve. In the symmetric key case there are no such patterns: the keys are just large randomly-chosen numbers.
Source: Why some cryptographic keys are much smaller than others
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.
The basic, general reason for this is that all known public key algorithms to date require some form of additional mathematical structure upon both keys, while that symmetric key algorithms can use an arbitrary key, i.e. any sequence of bits, no matter what it is, will work as a key (though there may be reasons to prefer some keys to others, obviously, but the algorithm will function with any arbitrary key).
It is more or less, then, by the very meaning of the goal that if you are going to require keys with more structure, there will be fewer of them for any given bit length, and thus if you want to make similar security, you have to increase the bit length to ensure that you have at least the same number of available keys to choose from. Moreover, the additional structure may make it easier to break the key than pure brute force searches, thus necessitating even more length still to compensate.
For example, consider the RSA algorithm. The key has to be at least a modulus value which is mathematically an actual number that is the product of two similar-sized primes:
$$n := pq$$
An arbitrary string of bits taken as representing a number $n$ will, in general, not factor into two similarly-sized primes, because it can be literally any number at all. While the mathematical structure of the algorithm totally permits the use of more than two primes, if you're choosing the modulus first, then you'd have to factor it because you need the primes to generate the private key, and that is equivalent to breaking the cipher, meaning if you can do it easily, the key has no security, and if you can't, then you can't generate the private key for that choice of $n$. So the only option is to choose the primes first, thus making for fewer keys for any given bit length due to the ones thus excluded from consideration.
And, moreover, it turns out, factorizing numbers when the bit length of $n$ is on the order of length of a typical symmetric key is also so easy that even an ordinary PC can do it, no matter what that $n$ is. To put the factorization out of reach of even the world's biggest supercomputers, thus requires a considerably longer key than even this. But the above argument shows why that, at the very least, the key size absolutely must be larger than symmetric keys.
To add to what was said above, with most symmetric cryptography, you simply can not guess the key - or can't know that you did*. That's because EVERY possible arrangement of N bits is a perfectly legal key, meaning every possible plaintext block will come up.
You try one key and it decrypts to "1". Another key decrypts to "0". With another key, it decrypts as "a". Which is the right key? You have no way of knowing.
Contrast public key crypto such as RSA or DH - when you've factored the number, you know that you have done so - you can know that you've discovered the right key.
ALL possible plaintexts will come up if the key size is the same as the block size. If the key is shorter, still you'll get a huge number of possible plaintexts - generally every key decrypts to some plaintext. Which makes it nearly impossible to know which is the right plaintext.
