As part of my Mathematics degree I'm taking a Discrete Mathematics module which partially covers Public Key Cryptography but does not at all enter it in depth.

I'm currently working on a project that involves writing about the process, security and efficiency (in terms of calculation/processing speed) of a few PKC systems.

I understand the processes and how to discuss the security of these systems, but I'm struggling with what makes a PKC system "good" in terms of efficiency, at least comparatively. I'm only considering the following 3 systems:

  • RSA,
  • El Gamal, &
  • Knapsack.

On a basic level I can compare key sizes and ciphertext expansion, but further than that I'm a bit lost; especially in terms of terminology when attempting further reading. Any direction or advice would be greatly appreciated.

  • $\begingroup$ Welcome to Crypto.SE! As the term “efficiency” can point to several aspects (speed, security, strength, attack resistance, etc.), could you please clarify what exactly you mean when writing “efficiency”? $\endgroup$
    – e-sushi
    Nov 19, 2015 at 11:57
  • $\begingroup$ I hadn't actually realized the term could refer to multiple aspects. I have been taking "efficiency" to refer to the calculation/processing times as well as the size of the data being transmitted. $\endgroup$
    – Jonathan
    Nov 19, 2015 at 12:04
  • $\begingroup$ Oh, OK. So, you want to “benchmark” them… thanks for clarifying that one. (I edited that into your question; hoping you don’t mind.) By the way: “RSA 4096 bit key benchmark” seems to be somewhat related. Maybe it helps for starters while you’re waiting for more on-point answers to your question. By the way, we have a lot of benchmark-related questions around which you might want to take a look at too – that is, if you haven’t already. $\endgroup$
    – e-sushi
    Nov 19, 2015 at 12:10

1 Answer 1


Since you are approaching this from the point of view of mathematics, I think the most fruitful avenue would be to look at asymptotic performance and security of the problems that the cryptosystems are based on.

For example, with RSA you need a modular exponentiation for every message you encrypt or sign. The time that takes depends on the length of the modulus as well as the exponent. The most efficient general purpose algorithm for breaking RSA is GNFS which also takes time dependent on the size of the modulus.

Find out the same for the other algorithms you are interested in and you can compare them and see e.g. whether one will asymptotically become more efficient at equal security.

This will allow you to steer clear of the various practical issues of how the different constants compare and what platform some performance measures might be relevant for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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