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?
$\begingroup$
$\endgroup$
12
-
$\begingroup$ To factorize it, you have to find the numbers from 2 to N/2 that divide N, not just see if there is one. $\endgroup$– user991May 14, 2012 at 10:12
-
$\begingroup$ @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? $\endgroup$– AshwinMay 14, 2012 at 10:15
-
$\begingroup$ @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. $\endgroup$– mikeazoMay 14, 2012 at 11:16
-
$\begingroup$ @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$). $\endgroup$– mikeazoMay 14, 2012 at 11:18
-
$\begingroup$ 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. $\endgroup$– Paŭlo EbermannMay 14, 2012 at 11:24
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ so you are saying that breaking a 1024 bit rsa key is less difficult than breaking a 128 bit symmetric key $\endgroup$– AshwinMay 15, 2012 at 0:37
-
3$\begingroup$ yes ${}{}{}{}\:$ $\endgroup$– user991May 15, 2012 at 0:55
$\begingroup$
$\endgroup$
2
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
-
$\begingroup$ Does this mean that 80-bit symmetric keys are not secure anymore (or will be insecure soon)? $\endgroup$ May 16, 2012 at 22:13
-
1$\begingroup$ @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. $\endgroup$ May 19, 2012 at 13:38