# How long to bruteforce a RSA key [duplicate]

Suppose I have a 2048 bit RSA public key, and want to brute force the corresponding private key. I guess there are 2048^16 possible combinations?

How long would this take me to brute force with an i7, with a GPU, and with Amazon Cloud?

Is there any benchmarking data, that can be used to calculate similar for a 16 bit key, or a 1024 bit key?

Thanks

-

## marked as duplicate by Maeher, Thomas, fgrieu, Gilles, mikeazo♦Jun 25 '13 at 18:35

if "bruteforce" is extended to include better algorithms than the incredibly naive approach in the question, see this answer and the landmark article – fgrieu Jun 11 '13 at 5:03

We do not know the number of possible combinations, since the exact numbers of 1024 bit primes is unknown, but it is MUCH larger than $2048^{16}$. I do not know how you guessed this number, but here are some estimates:
For N with 2048 you need primes p,q with 1024 bit each. There are $2^{1023}$ numbers with this length (a leading 1 and then 1023 binary digits).
According to the prime number theorem, we get this: $$\pi(2^{1024}) \approx \frac{2^{1024}}{ln(2^{1024})} \approx\frac {2^{1024}}{710}\approx 2^{1014.53}$$
Similar you can approximate the number $\pi(2^{1023})$ to almost exactly 1 bit less, and subtract those primes (all the primes with lower length). This leaves still over $2^{1013}$ prime numbers of the according size.