1
$\begingroup$

Suppose I want to compare between RSA and Paillier encryption algorithms. I have coded two different programs in the same programming language. Now how to compare between these two and in what aspects they can be compared?

Are there tools available for same?

$\endgroup$
  • 2
    $\begingroup$ Generally you just perform the operation, say, a thousand times for keys with similar security properties and record the time for each. Note that the speed is rather implementation dependent, so you're measuring the implementations of the algorithm rather than just the algorithm. $\endgroup$ – Maarten - reinstate Monica Aug 25 '16 at 15:02
  • 3
    $\begingroup$ In addition to Maarten's correct caevat about speed being implementation dependant, you also need to consider about the quality of the implementations. If you coded them yourself, do you know about the implementation tricks for both algorithms that a quality implementation would use? Comparing naive implementations might not tell you very much. $\endgroup$ – poncho Aug 25 '16 at 15:13
  • $\begingroup$ In addition to the above, it is not just the optimization level of the implementation that matters, but e.g. resistance to side channel attacks, so in some cases an implementation could even be faster than a good implementation. $\endgroup$ – otus Aug 25 '16 at 16:26
  • $\begingroup$ If you want to compare RSA and Paillier encryption algorithms, then you shouldn't compare two implementations of those algorithms, you should compare the computational complexity of the algorithms. $\endgroup$ – user2768 Aug 26 '16 at 8:38
  • $\begingroup$ In this case, one thing to consider is the different length of the modulus and numbers involved (In Paillier, calculations are done with numbers twice as long, if the same $n$ is used, due to mod $n^2$). $\endgroup$ – tylo Aug 26 '16 at 10:49
2
$\begingroup$

I'll collect the comments and build an answer from that.
First,

[..] you just perform the operation, say, a thousand times for keys with similar security properties and record the time for each. Note that the speed is rather implementation dependent, so you're measuring the implementations of the algorithm rather than just the algorithm.

of course life and code development would be too simple with this, so

[Y]ou also need to consider [..] the quality of the implementations. If you coded them yourself, do you know about the implementation tricks for both algorithms that a quality implementation would use? Comparing naive implementations might not tell you very much.

and still of course security developement has its own special issues which need to be respected before comparing speed:

In addition to the above, it is not just the optimization level of the implementation that matters, but e.g. resistance to side channel attacks, so in some cases an implementation could even be faster than a good implementation.

So the logical conclusion is ...

If you want to compare RSA and Paillier encryption algorithms, then you shouldn't compare two implementations of those algorithms, you should compare the computational complexity of the algorithms.

with this helpful comment on how to do so:

In this case, one thing to consider is the different length of the modulus and numbers involved (In Paillier, calculations are done with numbers twice as long, if the same $n$ is used, due to $\bmod n^2$).

Credits to Maarten, poncho, otus, user2768 and tylo for this joint effort of an answer.

$\endgroup$
0
$\begingroup$

If it were me, I would use time.time() in python, and compare the results starting at the beginning and the end, and then the difference between the end time and the start time. Here's an example with md5:

root@kali:~/projects/crypto# cat hashtest.py 
import time, hashlib

#Tests MD5 hash algorithm 'iterations' times.
def testHashes(iterations):
    for i in range(iterations):
        x = hashlib.md5("The quick brown fox jumps over the lazy dog")

if __name__ == '__main__':
    begTime = time.time()
    testHashes(1000)
    endTime = time.time()
    print "1000 iterations of MD5 computed in %s seconds" % (endTime - begTime)

root@kali:~/projects/crypto# python hashtest.py 
1000 iterations of MD5 computed in 0.000519037246704 seconds

Very simple example, but the concept could be applied to both algorithms you suggested. However, it would be a much more accurate representation of the actual speed of the algorithm if you were to use something like OpenSSL's implementations and use this same methodology in C. Because of python's heavily typed/interpreted/everything-is-an-object implementation, it will be much slower than a lower level language like C, and probably equally easy to implement.

$\endgroup$
  • $\begingroup$ In python, arguably it is better to use the timeit module, although it doesn't make a huge difference in such a simple eample. In more complex software, the setup should be separated from the iterations and not included in the timing. $\endgroup$ – tylo Aug 26 '16 at 10:45

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.