Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question already has an answer here:

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

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

1 Answer 1

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.

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

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