38
$\begingroup$

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?

Improve this question
$\endgroup$
2

7 Answers 7

Reset to default
43
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Are these long scale or short scale billions? (Short scale, if I counted right.) $\endgroup$
    – Paŭlo Ebermann
    Oct 23, 2011 at 21:56
  • $\begingroup$ 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. $\endgroup$
    – Thomas Pornin
    Oct 24, 2011 at 0:48
  • 3
    $\begingroup$ Reading this answer again, the storage problem is even worse! According to the holographic principle, the maximum information density in a volume is proportional to the square of its radius (e.g., its surface area) rather than the cube (e.g., its volume). Redoing the math, we can only pack roughly $10^{84}$ values in the observable universe, and would need $10^{224}$ universes to store them. And of course, once you've stored them, you'd need to be able to efficiently look them up when needed, which is a whole other can of worms. $\endgroup$
    – Stephen Touset
    Jan 5, 2016 at 18:38
  • $\begingroup$ @ThomasPornin I am reading this again and appreciate your thinking and your level of sophistication. But let's try to push this a bit further. What if the storage problem was tackled in a different manner? What if, rather than storing each prime, the deity decided to store just enough sparse numbers, allowing it to jump to a number, and then walk from there up or down. How sparse would that data be? And lets say, given 5 years head start to create these sparse indexes, the actual search from any point to find the right private key, must not take more than 7 days. Would that make it feasible? $\endgroup$
    – mjs
    Jul 22, 2019 at 17:58
  • $\begingroup$ The generating computer(s) would be able to generate randomly and keep only the found prime long enough from next, removing older ones. Or walk from zero + 2 to infinity, albeit that might put things into perspective. How long would it take to walk to 2^2048 ? $\endgroup$
    – mjs
    Jul 22, 2019 at 18:03
25
$\begingroup$

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 in 1995, 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 systems in existence by 2020 have a capacity of about $2^{64}$ bits, so if each prime used only one bit, the odds that the right prime is present is about $2^{-121}$. We are talking odds thinner than winning the lottery (e.g. the jackpot there) 4 times in a row.

Improve this answer
$\endgroup$
11
$\begingroup$

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...

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why are we counting atoms? An electron or proton is not an atom and much smaller... right? $\endgroup$
    – mjs
    Oct 24, 2011 at 9:56
  • 6
    $\begingroup$ @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. $\endgroup$
    – Dennis
    Oct 24, 2011 at 10:58
9
$\begingroup$

The Prime Number Theorem proves that there are approximately $\frac{x}{\ln x}$ primes less than any positive integer $x$. There are thus about $\frac{2^{2048}-1}{\ln (2^{2048}-1)}-\frac{2^{2047}}{\ln (2^{2047})}=22.8\times 10^{612} - 11.4\times 10^{612}=11\times 10^{612}$ 2048-bit primes. That's a rather large number, since there are only about $10^{80}$ atoms in the entire universe. So unless the attacker has $10^{533}$ spare universes, all entirely transformed into computer storage, this won't work. The time it would take to compute all of these primes is also rather large.

Improve this answer
$\endgroup$
3
7
$\begingroup$

You are underestimating something, either the number of primes that an attacker would have to generate and store, or the size of the primes that must be multiplied in standard factorisation-based cryptosystems. Current recommandations suggest taking $1024$-bit primes. The number of $1024$-bit primes is about $1.26\times 10^{305}$, according to this answer on math.stackexchange. Even if the attacker was able to generate a billion prime per second, it would not take a week to generate all such primes, it would take $4\times 10^{288}$ years, and I do not have good ways of describing how huge this number is. The number of particles in the universe is nothing compared to that. Even the cube of the number of particles in the universe is nothing compared to that. I'm not even talking about storing this gigantic list, or searching through it.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So, basically, the answer to the question "what stops an attacker" is: "reality". $\endgroup$
    – Jörg W Mittag
    Feb 14, 2017 at 1:54
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

The answer is no. It would not help at all to know all primes!

The proof is relatively simple from the fundamental theorem on the growth rate of primes. According to this theorem there are approximately $n/\log(n)$ primes less than $n$ for sufficiently large $n$. So if you are trying all divisors of $n$ less than $\sqrt{n}$, then you must try about $\sqrt{n}/\log(\sqrt{n})$ primes. This is about $\sqrt{n}/\log{n}$ primes as opposed to about $\sqrt{n}$ possible integers. As you see the speedup factor is $O(\log n)$ compared to brute force.

There are other methods of factorization that have much better asymptotic performance. The easiest one to understand is the modified Fermat's factorization which has an asymptotic performance $O(n^{1/3})$ [Lehman], in practice this can be reduced to $O(n^{1/4})$, although there is no well known proof for that. More advanced methods such as quadratic sieve or the general number field have much better asymptotic performance. These more advanced methods do not rely on knowing if a number is prime. So having a list of primes does not speed up these methods.

Improve this answer
$\endgroup$

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