# 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}$ –  Ricky Demer Jun 25 '12 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. –  Thomas Jun 25 '12 at 8:26

It's not possible.

The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of 512bit 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:

$1.88×10^{302}ms / 10^{80} = 1.88×10^{222}ms = 1.88×10^{219}s = 5.22×10^{215}h = 1.43×10^{213} \text{years}$. 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). $\;\;$ –  Ricky Demer Jun 25 '12 at 8:50
You made a typo at the first $10^{80}$ - a zero went MIA. –  Thomas Jun 25 '12 at 8:52
Thanks, I fixed both errors. –  Maeher Jun 25 '12 at 8:57
CAUTION: That does not accurately answer the real question, which is in the title! –  fgrieu Jun 25 '12 at 11:40

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? –  eggyal Jun 25 '12 at 12:30
@eggyal: I updated my answer. –  fgrieu Jun 25 '12 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. –  eggyal Jun 25 '12 at 13:46