Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question
    
cryptopp.com/benchmarks.html - 2.68 mega cycles per second on opteron 2.2 - I have to say it's seriously slow or maybe I am wrong –  Andrew Smith Aug 21 '12 at 19:09
    
so 2.6 million decryption per second for 1024 bit RSA right ? because someone else said each RSA decryption will take about 0.002 second which seems much slower ... ? –  mario Aug 21 '12 at 20:19
    
    
Hi @mario, welcome to Information Security. Closing this as too localized, since this is likely to change over time, and depends greatly on what system you have, and anyway 6 months from now a "standard" system would have much more power. –  AviD Aug 22 '12 at 8:21
    
If you need high performance private key operations, consider elliptic curve crypto. –  CodesInChaos Aug 22 '12 at 18:14
add comment

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, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

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.

share|improve this answer
add comment

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:

$ openssl speed rsa1024
Doing 1024 bit private rsa's for 10s: 2430 1024 bit private RSA's in 9.28s
Doing 1024 bit public rsa's for 10s: 48984 1024 bit public RSA's in 9.92s
OpenSSL 1.0.1 14 Mar 2012
built on: Tue Jul  3 20:15:19 UTC 2012
options:bn(64,32) rc4(8x,mmx) des(ptr,risc1,16,long) aes(partial) blowfish(idx) 
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN
-DHAVE_DLFCN_H -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4
-Wformat -Wformat-security -Werror=format-security -D_FORTIFY_SOURCE=2
-Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT
-DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DOPENSSL_BN_ASM_PART_WORDS -DOPENSSL_IA32_SSE2
-DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM
-DRMD160_ASM -DAES_ASM -DVPAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
                  sign    verify    sign/s verify/s
rsa 1024 bits 0.003819s 0.000203s    261.9   4937.9

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.

share|improve this answer
add comment

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