0
$\begingroup$

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
$\endgroup$
  • 2
    $\begingroup$ In theory you'd need about 3 multiplications for the exponent three and about 17 for 65537, making the modular multiplication step 5 times faster in theory (using a naive implementation). By the looks of it, this wasn't the run-time dominating step in your case then... $\endgroup$ – SEJPM Sep 14 '16 at 12:31
  • $\begingroup$ Can the time-consuming step be padding? $\endgroup$ – Thanh Bui Sep 14 '16 at 14:07
  • 3
    $\begingroup$ Did you include the time it took to generate the RSA key pairs? If you did, well, that be what dominates the time. $\endgroup$ – poncho Sep 14 '16 at 14:09
  • 1
    $\begingroup$ No, I am sure that I excluded the time to generate the key pairs. The results were similar when I used only one key pair and repeated the encryption for 10000 times. $\endgroup$ – Thanh Bui Sep 14 '16 at 14:19
  • $\begingroup$ M2Crypto is an SSL wrapper. Is the config such that OpenSSL delegates crypto operation to e.g. a crypto accelerator? Is what's measured clock time, or CPU time? Ideas: could be OpenSSL (or whatever it delegates to) using Montgomery arithmetic, or implementing side channel countermeasures, both of which can have large overhead compared to RSA public-key operation. Also, that could be a slow RNG used for the random padding. Less likely: data hash, of Mask Generation and its (possibly other) hash. Version of OpenSSL and its compilation/config options could have an influence, but that's off-topic. $\endgroup$ – fgrieu Sep 14 '16 at 18:21
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ With 10000 encryption operations, it took my computer around 27 seconds to execute. I believe it's long enough. $\endgroup$ – Thanh Bui Sep 16 '16 at 11:21
  • $\begingroup$ Could you update your question with your results? 27 seconds for keygen+encryption or for encryption alone? What was your measurement method? You didn't mention your RSA keysize either... $\endgroup$ – axapaxa Sep 16 '16 at 17:19
  • $\begingroup$ I have updated the question $\endgroup$ – Thanh Bui Sep 17 '16 at 11:53
  • $\begingroup$ I have updated my answer. I was able to reproduce the difference in timing in pow which PyCrypto seems to be using. $\endgroup$ – axapaxa Sep 17 '16 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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