Cryptography for Mere Mortals #11

An occasional feature, Cryptography for Mere Mortals attempts to provide clear, accessible answers to questions about cryptography for those who are not cryptographers or mathematicians.

Q: Why are asymmetric keys so much longer than symmetric keys?

Typically, symmetric key lengths are fairly short: 128 bits is common, 256 bits is about the longest you’ll see.  Asymmetric keys, by comparison, tend to be much longer: 1024 bits is becoming obsolete in favor of 2048 bits.  The reason is the amount of work needed to break the encryption.

For the ideal symmetric encryption scheme, the best feasible attack is to try all the possible keys in turn until you find the right one.  Since the key is 128 bits (and a bit is either 0 or 1), that means there are a total of 2128 possibilities.  So to be absolutely certain of breaking the cipher, you have to try 2128 keys.

However, for existing asymmetric encryption schemes (RSA, El Gamal, IBE, et al), it turns out there is a more efficient attack.  For example, RSA can be broken by factoring a very large number into two prime factors (the RSA encryption algorithm builds that large number by multiplying two large primes).  But, to work out the prime factors of a number, you don’t have to try all the possible values: you just have to try all the odd prime numbers lower than the square root of the number[1].  It turns out that this same basic concept also holds for the encryption systems based on discrete logarithms, for reasons that are still a mystery to cryptographers.

As an example, let’s take a 6-bit symmetric key and work out the size of asymmetric key that would take the same amount of effort to break.

There are 26 (=64) possible values of the symmetric key, from 000000 to 111111.  To be certain of breaking the cipher, we need to try 64 values.

So, how large a number do we need before it will take us 64 attempts to factor it into two primes?  Or, expressed another way, what is the square of the 64th odd prime number?  The 64th odd prime is 317[2].  3172 is 100,489, which is 1 1000 1000 1000 1001 in binary – a 17-bit value.  So to get the same amount of protection from an asymmetric algorithm as we get from a 6 bit symmetric key, we need a 17-bit asymmetric key.

As the lengths get longer, the prime numbers get further apart, and so the difference between the symmetric and asymmetric key lengths increases.  For example, to get the same protection as a 128-bit symmetric key, you need a 3072-bit asymmetric key.

The 2048-bit asymmetric keys that are becoming the new standard take about the same amount of work to break as a 112-bit symmetric key[3]: the soon-to-be-obsolete 1024-bit keys provide the same key strength as an 80-bit symmetric key[3].  Hence the move to 2048-bit!

 

1 – For those of you paying attention, 2 is indeed a prime number, but we do not have to try it because it is only a factor of even numbers, and the RSA algorithm always uses two large primes, which will always be odd.  Hence the somewhat redundant-looking phrase “odd prime numbers”.

2 – http://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_500_prime_numbers

3 – http://en.wikipedia.org/wiki/Key_size

Leave a Reply

Your email address will not be published. Required fields are marked *