How much stronger is RSA-2048 compared to RSA-1024? It is hard to imagine very big numbers. So what would be your way to explain the difference to someone who doesn't know much about cryptography?
$\begingroup$
$\endgroup$
8
-
1$\begingroup$ RSA-1024: no men will be able to decrypt it before the whole universe colapses. RSA-2048: even Chuck Norris won't be able to decrypt it before the universe colapses... $\endgroup$– woliveirajrCommented Jul 1, 2013 at 16:37
-
1$\begingroup$ ...assuming the problem of factoring semiprimes is actually as difficult as we think it is. $\endgroup$– Stephen TousetCommented Jul 1, 2013 at 16:55
-
9$\begingroup$ @woliveirajr RSA-1024 is far weaker than that. AFAIK it's currently borderline feasible to break it for state level adversaries with a few billion to spend. If it's not breakable now, 10 years from now it should be. $\endgroup$– CodesInChaosCommented Jul 1, 2013 at 16:59
-
$\begingroup$ @CodesInChaos is correct. RSA-768 was factored 4 years ago, which means semiprimes up to about 820 bits are vulnerable today. Faster hardware, etc. There's a chart somewhere that shows exactly how many bits are safe as a function of the year... Let me see if I can dig it up and make an edit. $\endgroup$– pg1989Commented Jul 1, 2013 at 18:29
-
$\begingroup$ I heard that they could factor RSA-1024 bit in a year, with just a milion dollar computer. That why you need at least 2048 bit nowadays. $\endgroup$– user27296Commented Jul 1, 2013 at 20:50
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
5
You can use the complexity of the GNFS, the fastest known general-purpose factoring algorithm, to estimate the strength (in bits) of an RSA key size.
Referencing the table linked above, a 1024-bit key has approximately 80 bits of strength, while a 2048-bit key has approximately 112 bits. Thus, it takes approximately 2112/280 = 232 times as long to factor a 2048-bit key. In other words, it takes around four billion times longer to factor a 2048-bit key.
Thus, if you were able to magically factor a 1024-bit key in 10 seconds (which is totally unrealistic in every way possible, I may add), then it would take around 1,200 years to factor a 2048-bit key (note: this is not adjusted for Moore's law). Of course, it took around two years and a massive collaborative effort just to factor a 768-bit key, so factoring a 1024-bit key takes far, far longer than 10 seconds. But this is just to demonstrate the point: 2048-bit keys are much more secure.
If you do want to adjust for Moore's law and the ever-faster pace of computing, you can use this approximation by fgrieu. If you solve the equation for when a 2048-bit key is expected to be factored (keeping in mind that this is a rough approximation), you arrive at the year... 2048. So somewhere around 2040-2050, if that linear approximation holds true, we expect 2048-bit keys to be feasibly factored. In comparison, you can see that the 1024-bit key is expected to be factorable sometime around 2015-2020.
-
1$\begingroup$ Someone who does not understand encryption, will not understand anything about GNFS either... You forgot to explain why we can't just say that $2^{2048} = 2^{1024}·2^{1024}$ is $2^{1024}$ times harder than $2^{1024}$. I heard that you could factor $1024$-bit RSA in a year with a milion dollar computer. $\endgroup$ Commented Jul 1, 2013 at 20:53
-
1$\begingroup$ @user27296 I edited your comment to use MathJax formatting instead of HTML (which doesn't work in comments). I used
$2^{1024}$, for example. $\endgroup$ Commented Jul 2, 2013 at 7:28 -
$\begingroup$ @user27296 it's implicit in Reid's answer. It's not $2^{1024}$ times harder because GNFS can attack it faster than simple brute force. It's $2^{32}$ times harder, as mentioned. $\endgroup$– ConradoCommented Jul 3, 2013 at 11:56
-
$\begingroup$ @user27296: The first link in the answer contains more info about specifics. I agree that someone who doesn't know much about cryptography or number theory probably wouldn't know what the GNFS was, but honestly, to know how much stronger a 2048-bit key is, you don't really need to know the details and reasons. Anyway, I provided links that go into more detail both in this answer and my other (linked) answer in case anyone was curious. $\endgroup$– ReidCommented Jul 3, 2013 at 18:16
-
5$\begingroup$ Now that it's almost the end of 2020 I'd like an update on this. 😉 $\endgroup$ Commented Sep 5, 2020 at 1:23