Public Key Cryptography : Key length

Question

While symm. crypt. has around 256 bits of a key, why does public key crypt have a key that is much longer (1000's) ???

Answer 1

Asymmetric cryptography tries to provide some advanced features, namely the asymmetry, the property which allows the public key to be made public, without revealing the private key. This takes structure. We need mathematics. A key for signatures or asymmetric encryption cannot just be a bunch of bits; it must be a mathematical object with very special characteristics.

That mathematical structure can be leveraged for attacks, which forces us to use a lot bigger values. For instance, with RSA, the public key contains a big integer (the "modulus"): this is a composite integer, but factoring it into its prime factors allows for breaking the algorithm. We know some rather efficient factoring algorithm; the General Number Field Sieve will thus defeat a 1024-bit RSA key (a key whose modulus is an integer between 2¹⁰²³ and 2¹⁰²⁴) with an estimated cost around 2⁷⁷. If we want to achieve the same level of robustness with a symmetric key (which is just a sequence of bits, nothing made public) then we just need 78 bits.

The generic attack known as "luck", in which you try all possible bit sequences until the right one is found, has average cost 2^n-1 for a n-bit key. For symmetric cryptography (with a good algorithm), we know no better attack, and any key of 100 bits or more will be safe for decades. With asymmetric cryptography, we have the public key and its structure to work with, allowing for much more efficient (but heavier in mathematics) attacks, which forces us to use much bigger objects (larger keys).