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?



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.

However, the list of all prime numbers is way too huge and does not exist. This is beyond the capability of all computation power on earth for a couple of millenia.

| improve this answer | |
  • 1
    $\begingroup$ I think "for a couple of millenia" is putting it very lightly. Fortunately better algorithms than enumerating primes exist. $\endgroup$ – Thomas Jun 11 '13 at 2:15

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