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.

Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing prime keys up to $2^{2048}$?

I understand this would take an immense amount of time to do, but it would only be done once. Obviously, computing such an index would take a considerable amount of time and would have to be done with someone having the right amount of resource. Given the public key, you would be able to look up what the two primes are, and hence retrieve the private key instantly.

Breaking an 256 AES would then be easier, as AES keys are often generated using the RSA private key.

Would it be possible to build such an index? How long would that take in permutations and perhaps with the fastest computer in the world?

share|improve this question
1  
To put things in perspective, there are about $2^{265}atoms in the known universe. –  BlueRaja - Danny Pflughoeft Oct 21 '11 at 20:19
    
@BlueRaja-DannyPflughoeft - I demand a recount! :) –  Chad Oct 21 '11 at 20:43
    
Why are we counting atoms? An electron or proton is not an atom and much smaller... right? –  Hamidam Oct 24 '11 at 9:55
add comment

5 Answers

up vote 11 down vote accepted

Let's assume for an instant that you could build a large table of all primes. Then... what ? How would you use it ? What would you look up ?

If you "just" scan the table and try to divide the number to factor by each prime, then this is known as trial division; there is no need to store the primes (they can be regenerated on-the-fly; that's the division which is expensive). Yet this is an highly inefficient factorization algorithm. We know much better factorization algorithms (which nonetheless utterly fail at making the slightest scratch on the surface of a 2048-bit RSA modulus).

Of course, the list of 1024-bit primes is so large that storing it, or even simply generating each prime, is ludicrously infeasible. There are about $2^{1014}$ such primes; that's close to $10^{308}$. Suppose you are an omnipotent but severely bored deity, and you decide to store these primes, using a storage device which uses the size of an hydrogen atom for each prime (we, as humans, can certainly not store that much information in so small a space, but hey, that's a piece of cake for an omnipotent God). The known universe has an approximate volume of $10^{79}$ m3. The volume of an hydrogen atom is close to $10^{-30}$ m3. So our eccentric divinity can pack about $10^{109}$ values in the whole Universe. He would still need $10^{199}$ complete Universes to store them all. $10^{199}$ is a mind-boggling number (if your mind is not boggled by it, then it must already be much more boggled by something else). It is ten billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions. In other words, a lot. And we are still talking about complete Universes packed with atom-sized integers.

share|improve this answer
    
Great answer! That clarified it :) –  Hamidam Oct 21 '11 at 16:14
    
Are these long scale or short scale billions? (Short scale, if I counted right.) –  Paŭlo Ebermann Oct 23 '11 at 21:56
    
Short scale. Usually I try to use British English ("colour", "centre"...) but for numbers I follow American usage, so that our American friends do not misunderstand. –  Thomas Pornin Oct 24 '11 at 0:48
    
I just read this answer again and I love the way to talk! "Suppose you are an omnipotent but severely bored deity" ... you are a philosopher for sure :) –  Hamidam Aug 2 '13 at 21:52
add comment

Whether it's feasible or not depends on multiple factors:

  • The amount of compute power you can throw at the problem
  • The time you're willing to wait
  • Other practicalities (life-span of your staff, lease on the building, money, etc)

I don't think it's desirable, however. While it would be nice to have a list of all possible keys, it's much more likely that flaws in the implementation would provide a gateway to the plaintext.

Also, see http://xkcd.com/538/.

share|improve this answer
2  
You should add also the factors "size of the universe" (to get a storage big enough) and "expected lifespan of the universe" to your list if you take a look at fgrieu's answer. This said, the xkcd is nice, of course. –  j.p. Oct 21 '11 at 12:32
add comment

No, it is not at all feasible to build an index of prime factors to break RSA.

Even if we consider 384-bit RSA, which was in use but breakable two decades ago, the index would need to include a sizable portion of the 160 to 192-bit primes, so that the smallest factor of the modulus has a chance to be in the index. Per the Prime number theorem there are in the order of $2^{185}$ of such primes. The biggest data storage system in existence has a capacity of about $2^{60}$ bits, so if each prime used only one bit, the odds that the right prime is present is about $2^{-125}$.

share|improve this answer
add comment

How long would that take in permutations and perhaps with the fastest computer in the world?

Given the analysis by @fgrieu using the prime number theorem, we know there are roughly $2^{185}$ possible prime numbers which could be used to construct a $384$-bit RSA key pair. Thus there are $2^{185^2}$ possible RSA key pairs (since it takes two primes to make up the key). Let's assume that generating the primes takes no time and that you can generate $10^{30}$ key pairs a second. To estimate the time it would take to create all key pairs, you'd do $2^{185^2}/10^{30}$ to get the number of seconds. Change this then to something a little easier to comprehend (centuries in this case), and it would take approximately $7.63\cdot 10^{71}$ centuries to create all the key pairs.

Now, just to show how difficult it is, let's assume you can do $10^{100}$ key pairs per second. It would still take $7625$ years to create the index.

So, even limiting ourselves to $384$-bit RSA, there currently isn't enough storage to store all possible key pairs and it would take over seven centuries to create the index. I don't even want to know what it would take for $2048$-bit RSA.

share|improve this answer
add comment

There are close to $2.27\cdot10^{613}$ primes smaller than $2^{2048}$.

There are close to $9.4\cdot10^{79}$ atoms in the observable universe.

Even if you could compute all those prime numbers, you wouldn't have any place to store them...

share|improve this answer
    
Why are we counting atoms? An electron or proton is not an atom and much smaller... right? –  Hamidam Oct 24 '11 at 9:56
1  
@Hamidam: My point is that there are $2.42\cdot10^{533}$ times as many primes smaller than $2^{2048}$ than there are atoms in the observable universe. Unless we can store $2.42\cdot10^{533}$ bits of data in a single atom, it doesn't really matter what we're counting. The largest atom known to mankind is an isotope of Ununoctium that consists of 530 subatomic particles: 118 protons, 118 electrons and 294 neutrons. –  Dennis Oct 24 '11 at 10:58
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.