Difficulty of breaking RSA for a given key size

Is it true that breaking a 1024-bit RSA key is as difficult as breaking a 128 bit symmetric key (e.g. AES)? I know that breaking a RSA key is equivalent to factoring the modulus $N$. To factor it, you have to see if any number between $2$ and $N/2$ divides $N$, right? But that would still be much greater than $2^{128}$ trials (which is the worst-case scenario for cracking a 128 bit AES key). Then, how is breaking a 128-bit AES key the same as a 1024-bit RSA key?

-
To factorize it, you have to find the numbers from 2 to N/2 that divide N, not just see if there is one. –  Ricky Demer May 14 '12 at 10:12
@RickyDemer : You are right about that. So then you see the complexity increases even further. Then how is 1024 bit rsa key equivalent to 128 bit des key? –  Ashwin May 14 '12 at 10:15
@Ashwin, you are looking at the worst case, which is not what an actual attacker would do. There are algorithms which run faster that are used for factoring. When someone comes up with a symmetric key equivalent, they use these faster algorithms to help in the process. –  mikeazo May 14 '12 at 11:16
@Ashwin: Note that breaking RSA is not equivalent to factoring. Factoring the modulus just happens to be the fastest way to do it currently. Also, DES does not have 128-bit keys. And factoring by trial division would require you to divide the modulus by every odd prime between $3$ and $\sqrt{N}$ (not $N/2$). –  mikeazo May 14 '12 at 11:18
There are no 128 bit DES keys. DES has keys of size 64 bits, of which only 56 bits are actually used. There is triple-DES, which has keys of size 128 (effective 112) or 192 (effective 168) bits. –  Paŭlo Ebermann May 14 '12 at 11:24

No. Breaking a 1024 bit RSA key is not as difficult as breaking a 128 bit symmetric key. The consensus is that it is considerably less difficult, perhaps more comparable to breaking a 80-bit symmetric key, which is $2^{48}$ times less difficult than breaking a 128-bit key; that's a lot less difficult (a hundred million million times less difficult).

The reason is that breaking a 1024 bit RSA key can be attempted using an integer factorization algorithm, without exhaustively trying divisors. For the state of the art, see this article on the current factorization record.

-
so you are saying that breaking a 1024 bit rsa key is less difficult than breaking a 128 bit symmetric key –  Ashwin May 15 '12 at 0:37
yes ${}{}{}{}\:$ –  Ricky Demer May 15 '12 at 0:55

No, According to NIST, an RSA (or integer DSA, Elgamal, DH, etc.) key of 3072 bits is equivalent to 128 bits of symmetric key.

By their measure, 1024-bit public keys are considered to be equivalent to 80-bit symmetric keys. 2048-bit keys are equivalent to 112 bits symmetric.

One can debate the equivalence (and I do when I'm in a contrary mood), but it's a reasonable one.

Note that this means that you should have retired your 1024-bit key at the end of 2010, but if you hold your nose, you can keep it through 2013.

Jon

-
Does this mean that 80-bit symmetric keys are not secure anymore (or will be insecure soon)? –  Paŭlo Ebermann May 16 '12 at 22:13
@PaŭloEbermann: Yes. Since 2005, NIST has advised that 80-bit symmetric keys should be phased out by 2010. Presumably, that's the basis for Jon's conclusion. –  David Schwartz May 19 '12 at 13:38