I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic.

I understand that many security experts out there might get angry just by the discussion of these things, but I hope you can spare me :)

My Questions:

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.

Given the public key, you would be able to look up what the two primes are, and hence retrieve the private key instantly.

When I consider who might break such a code, I am primarily thinking about NSA and other Governments that might have spent years in research and have the resources and interest in doing so.

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 ?

I hope we can have a nice chat about this. We are just discussion theory here. I hope you can offer me some insight on this topic.


  • $\begingroup$ What do you mean by by performing every permutation of existing prime keys? (Also, you're completely off with the comment about AES keys. AES keys are often transmitted using RSA, but generation is something completely different). $\endgroup$ Oct 21, 2011 at 10:00
  • 6
    $\begingroup$ Since, by some estimates, there are only about $10^{80} \ll 2^{2048}$ atoms in the observable universe, there seem to be some practical problems with building such an index. $\endgroup$
    – cardinal
    Oct 21, 2011 at 10:02
  • 3
    $\begingroup$ And if somehow you managed to build it, you have a heckuva job trying to search it. $\endgroup$ Oct 21, 2011 at 10:11
  • 3
    $\begingroup$ Gerry pointed out that searching that table would take time. I would say that "it depends". If the index is sorted, then a binary search would take only a couple thousand steps. The downside is, of course, that as most of that index would necessarily be several million lightyears away, you need a little bit of patience retrieving a single entry of that table. $\endgroup$ Oct 21, 2011 at 10:50
  • $\begingroup$ @PeterTaylor yes you are right about the generation. I think I meant that if private key is broken then one would be able to get hold of the aes key. $\endgroup$
    – mjs
    Oct 21, 2011 at 11:29

2 Answers 2


The prime numbers used in RSA keys are randomly generated, freshly for every new RSA key. If an RSA key pair is generated properly, then each of its two prime numbers will be unique -- never before generated in the history of humankind (with a probability that is close enough to $1$ to make no difference). This is because there are more than $2.5 \times 10^{305}$ primes less than $2^{1024}$. Which kind of spoils your idea of building a table...

  • $\begingroup$ In other words, the key to breaking the randomly generated keys is to convince people to use your specialized random number generator :) $\endgroup$ Jul 25, 2014 at 10:01
  • $\begingroup$ @HagenvonEitzen: You are about ten years behind the times! Everybody knows now that the RNG is the most important component of an RSA key generation algorithm. $\endgroup$
    – TonyK
    Jul 25, 2014 at 19:58
  • $\begingroup$ Well, it seem that RSA themselves didn't know (or were financially persuaded not to know) that fact for a while ... $\endgroup$ Jul 28, 2014 at 17:57
  • 1
    $\begingroup$ There are ~$2.53274 × 10^{305}$ primes less than $2^{1024}$ $\endgroup$
    – Waffle
    Jan 28, 2015 at 18:25
  • $\begingroup$ @Waffle: Thanks for spotting that! I corrected it. $\endgroup$
    – TonyK
    Jan 28, 2015 at 19:38

A 2048-bit key consists of two 1024-bit primes, of which there are $\pi(2^{1024})-\pi(2^{1023})\approx1.26691\cdot10^{305}$ (all digits shown are exact, the next digit is between 5 and 8).

Storing all these primes would take $1.26691\cdot10^{305}\cdot1024\approx1.29732\cdot10^{308}$ bits—well, or just $1.29479\cdot10^{308}$ bits if you store the first and last bits implicitly.

The Bekenstein bound for the observable universe (mass $2.5\cdot10^{54}$ kg including dark matter/energy, comoving distance $4.4\cdot10^{26}$ m) is approximately $2.8\cdot10^{124}$ bits. It's not possible to store more information: there's no more matter to store it, and matter further away can't reach our Minkowski cone.

So at best we can store $$ \frac{2.8\cdot10^{124}}{1.29479\cdot10^{308}}\approx2.2\cdot10^{-182}\% $$ of those primes.

But never fear! Perhaps you don't need a database of all the primes, you can make do with just some of the primes. So set up the observable universe (minus a small chunk, say the Earth) as your dictionary of primes, then suppose everyone on Earth picks a trillion trillion 2048-bit RSA keys. This is a total of $7.05\cdot10^9\cdot10^{12}\cdot10^{12}\cdot2=1.41\cdot10^{34}$ primes. Your dictionary contains at least one of the primes with probability $\approx1.41\cdot10^{34}\cdot2.2\cdot10^{-184}\approx3.1\cdot10^{-150}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .