Performance of RSA encryption when the public exponent is 3 and 65537

Question

I wanted to test the performance of RSA encryption when the public exponent was 3 and when it was 65537. Python and M2Crypto library were used to generate keys and do encryption:

key = RSA.gen_key(KEY_SIZE, 65537)

key.public_encrypt(s, RSA.pkcs1_oaep_padding)

where s is a 256-bit string and KEY_SIZE is 2048 bit. For each exponent value, I generated 10000 RSA key pairs and measured the total time they took to encrypt the data string (not included the key-generating time).

I expected that when the public exponent was 3, the running time would be much shorter. However, they took almost the same time (around 27 seconds). I used the time.time() function in Python to measure the running time.

Can anyone explain me the reason?

Updated: I have tested the same operations with PyCrypto, Java (using Bouncy castle library) and C (using OpenSSL library) as well. Here are the results:

• PyCrypto: around 5s for both public exponents (PE).
• Java: 0.7s for PE = 3 and 1.5s for PE = 65537
• C: 0.11s for PE = 3 and 0.27s for PE = 65537

Answer 1

This can be due to various reasons, most likely more than one:

• First use of that key initializes some data that takes longer to compute than your actual public key operation (for example, sliding window initialization can take as long as public key operation). Since you only perform one operation per key, this makes this probable.
• Your key is so short that it is relative to time other stuff takes (padding, calling the library,various checks on input data, splitting and synchronizing threads [in case of private key operations with Chinese Reminder Theorem]).
• Your measurement of time is not precise enough.
• Your library uses protection against time side-channel. This is very likely if you are using OpenSSL or other well-studied library, since those are usually secure against most side-channels, but this is usually only done for private key operations.
• Other things, like processor not having data in it's cache or branch mis-predictions and background work can also be a factor, especially since you didn't mention that you ran public key computation in loop. For example, if your computer decides to do a thread-switch across your measurement, it can make your result seem lot longer.

Generally, you should execute your computation so long that it actually takes more than few seconds to compute, to avoid small factors that invalidate your results. Also, you should be sure that your library doesn't protect against side-channels in your specific scenario. Only then those measurements can be deemed accurate enough to look deeper.

But this usually isn't padding that is case for time being same. Padding is usually at least 10x faster than public key computation (even when public key operation is hand-optimized SSE2 assembly).

My best guess is that your computation is simply not precise, with both not using accurate timing, and executing computation doesn't take long enough (especially executing public-key operation just once per key isn't enough).

UPDATE

You said that you use python's time.time(). On my machine it has 1ms resolution. Now, since you have to start measurement, then stop it after you ended your encryption (since then you generate new key), this adds to inaccuracy of your measurement. Also, you compared your results to Java and C which both are compiled, and therefore I assume quite a lot faster. It could be that simply everything involved in calling proper functions takes far longer than encryption itself. Adding inaccuracy of time.time() this makes your result of 5sec for both quite probable. To maximize chance of finding difference, I'd recommend generating one key, then encrypting result multiple times, and timing it all. Since PyCrypto uses built-in pow, I've checked if results differ, and indeed they do in my very simple test. I've got 832ms for 3 and 5200ms for 65537 (for a fairly small prime and 100000 iterations of pow).