# How much computing resource is required to brute-force RSA?

It's been over 30 years since Rivest, Shamir and Adleman first publicly described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for around 40 years—possibly longer.

It's fair to assume that, during those 40 years, certain three-letter organisations have employed their vast resources toward "breaking" RSA. One brute-force approach may have been to enumerate every possible key-pair such that, upon encountering a message known to be encrypted with a particular public-key, they need merely lookup the associated private-key in order to decrypt that message. Signatures could be forged similarly.

How reasonable is this hypothesis? How much computing resource would have been required over those 40 years to enumerate every possible {1024,2048,4096}-bit key-pair? I think it best to avoid discussion and leave the question of whether the spooks could have harnessed such resource as an exercise to the reader.

• Would something have to have actually been tried to qualify as "having been an approach"? $\hspace{1 in}$
– user991
Commented Jun 25, 2012 at 8:15
• Even if you had infinite computing power you would not have the space to store all these public/private key pairs (I'll spare you the semimathematical posts comparing the space required to the number of protons in the universe). Many people have trouble perceiving just how big a number $2^{2048}$ is, it's a common error. A much more practical approach instead is to harvest as many real-life public keys as possible, and trying to find common factors between them. It actually works because of poor key generation practices. Commented Jun 25, 2012 at 8:26
• Related question: How many RSA keys before a collision? Commented Jul 1, 2015 at 6:54

It's not possible.

The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of $512$ bit primes (approximately the length you need for $1024$ bit modulus) is approximately:

$$\frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151}$$

The number of RSA moduli (i.e. pair of two distinct primes) is therefore:

$$\frac{(2.76×10^{151})^2}{2}-2.76×10^{151}=1.88×10^{302}$$

Now consider that the observable universe contains about $10^{80}$ atoms. Assume that you could use each of those atoms as a CPU, and each of those CPUs could enumerate one modulus per millisecond. To enumerate all $1024$ bit RSA moduli you would need:

\begin{eqnarray*} 1.88×10^{302}ms / 10^{80}&=&1.88×10^{222}ms\\ &=&1.88×10^{219}s\\ &=&5.22×10^{215}h\\ &=&5.95×10^{211} \text{years} \end{eqnarray*}

Just as a comparison: the universe is about $13.75×10^9$ years old.

It's not a question of resources, it's simply not possible.

Also, it would not make any sense to do that. There are much faster ways to find out a secret key. In fact there are algorithms with sub-exponential running time for factoring integers.

• You forgot to divide by 2 in your calculation. $\:$ Anyway, one can show rigorously (i.e., without using any approximations) that the number of possible 1024-bit RSA moduli is greater than $10^{302}$ (even when the primes must be distinct). $\;\;$
– user991
Commented Jun 25, 2012 at 8:50
• You made a typo at the first $10^{80}$ - a zero went MIA. Commented Jun 25, 2012 at 8:52
• CAUTION: That does not accurately answer the real question, which is in the title!
– fgrieu
Commented Jun 25, 2012 at 11:40
• Still slightly off: 5.22e215 hours = 2.18e214 days = 5.96e211 years. (But +1 for having this available to reference.) Commented Feb 13, 2015 at 20:43
• @dave_thompson_085 "Slightly" by two orders of magnitude. :D Fixed it. (though it's 5.95495, so 5.95) Commented Feb 14, 2015 at 10:46

The brute force technique described in the question is hopeless, as pointed in this other answer.

However there are much better techniques to attack RSA keys, including GNFS. Therefore 1024-bit RSA keys, even though they offer sizable security, can no longer be considered entirely safe from predictable academic efforts, or even safe at all from Three-Letter-Agencies. See my detailed answer to How big an RSA key is considered secure today?. And for new systems, use whatever recommendation is applicable, or refer to one of the many on this site dedicated to keylength recommendations.

Also, sometime one can exploit a goof in the key generator, or attack RSA in ways that do not involve integer factorization: stealing the private key; extracting it by Differential Power Analysis, Timing or Fault attack; or taking advantage of a weakness in padding. See also Twenty Years of Attacks on the RSA Cryptosystem.

Update: Computational efforts performed in the last 40 years help new attacks because the methods have been worked out, but (for any known practical method) the computational effort spent for attacking a particular key is not useful in attacking another key, much like knowing that $1234567890221=23801\cdot 51870421$ does not really help finding the factorization of $1234567890197$.

• Thank you for all of the additional links - lots of very useful reading! I suppose my perspective was whether due consideration had been given not only to the challenge of breaking RSA today from a zero-starting point, but had also factored in 40 years of effort? Commented Jun 25, 2012 at 12:30
• @eggyal: I updated my answer.
– fgrieu
Commented Jun 25, 2012 at 13:27
• Thanks, but I'd really meant that once the factorisation you give has been discovered it can then be applied wherever the given product needs to be factorised. Over forty years with vast computing resources, many such factorisations could be discovered. I find @Maeher's answer more convincing in countering this argument, as it helps me to realise that the number of such factorisations required to be generated and stored even for 1024-bit RSA moduli is so vast that it is simply not reasonable even to hope for a collision with a known key. Commented Jun 25, 2012 at 13:46