I want to be able to tell how many keys per second, using RSA 1024-bit keys, can be checked on a standard Pentium 4 system. How can I use this to determine decryption performance, and possibly remaining time?
closed as too localized by Jeff Ferland♦, Gilles, AviD♦ Aug 22 '12 at 8:21
This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, see the FAQ.
Performance really depends on the implementation, the type of processor, the processor clock, and many other factors. The OpenSSL command-line utility includes a benchmark tool. For instance:
The machine I ran this on is known to be quite slow (it is a low-power VIA C7 x86 clone). A Pentium 4 (which is also a 32-bit system) should run at least as fast as that, but probably not supremely faster (I would be surprised if OpenSSL reached 1000 signatures per second with RSA 1024 on a Pentium 4).
Translating such a figure into application performance is a difficult exercise.
This question is tagged as "brute-force". Trying to naively brute-force 1024-bit RSA by trying every possible 1024-bit RSA key is obviously not feasible. Even if you were able to validate a key in Planck time (Wikipedia) and could run this algorithm on every atom in the universe and would have done so since the big bang, you still wouldn't have found the key.
The good news is that there are short cuts. One option is integer factorization. If you know the public key and are trying to brute force the private key, you can try an integer factorization algorithm. If you are successful you can then go to RSA Laboratories and claim your $100,000 award. Good luck with that :-).
A more likely approach is based on the fact that RSA key pairs are generally chosen using deterministic algorithms which start from a relatively short pseudo-random seed. If you know (or can guess) the algorithm used to choose the key under attack and the number of possible seeds is also limited (either because the seed size is small or because the pseudo random number generator is week) this could limit the number of possible keys to a palatable number. Such attacks have been done in the past on keys generated by specific systems, but these are quite rare and far in between.
Even if you're lucky and the RSA key pair algorithm used is based on a 16-byte random seed (I've never seen anything shorter than that), and even if you had a computer that could do a million RSA private key operations a second (and you don't) it would still take you some on average about 6 trillion trillion years to brute force the key.
So the only situation in which it may be feasible today to brute force a 1024-bit RSA private key is if the pseudo-random seed used to generate the key is somewhat predictable and limits the number of possible seed to a number under 2 by the power of 50 or so. If you happen to know of such a faulty algorithm which is in use it would definitely be worth a research paper. Otherwise the fastet brute firce algorithm would be to wait until you can get your hands on a quantum computer.