Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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... –  woliveirajr Jul 1 '13 at 16:37
    
...assuming the problem of factoring semiprimes is actually as difficult as we think it is. –  Stephen Touset Jul 1 '13 at 16:55
4  
@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. –  CodesInChaos Jul 1 '13 at 16:59
    
@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. –  pg1989 Jul 1 '13 at 18:29
    
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. –  user27296 Jul 1 '13 at 20:50
show 2 more comments

1 Answer 1

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.

share|improve this answer
1  
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. –  user27296 Jul 1 '13 at 20:53
1  
@user27296 I edited your comment to use MathJax formatting instead of HTML (which doesn't work in comments). I used $2^{1024}$, for example. –  Paŭlo Ebermann Jul 2 '13 at 7:28
    
@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. –  Conrado PLG Jul 3 '13 at 11:56
    
@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. –  Reid Jul 3 '13 at 18:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.