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