Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in comparing the computational performance of two signature schemes. However, I am unsure how to do that. My candidates are RSA and Shamir's ID Based Signature scheme. To get a fair comparison, I want both schemes to be parametrized in a way ensuring a "comparable level of security". However, the question remains, what that is.

My first idea was to have a look at the verification condition of both schemes assuming an attacker wants to forge a signature for a given message $m$. It seems fair to choose the parameters in a way that the size of the problem to be solved to do so is equal.

RSA verify: $s^e = f(m) \mod n$

=> $f$, $m$, $e$, $n$ is public

Assuming the attacker wants to calculate $s$ for known $m$, the discrete logarithm has to be solved, which is difficult depending on the size of $n$, which is an RSA modulus.

IBS verify: $s^e = i * t^{f(t,m)} \mod n$

=> $m$, $e$, $i$, $f$, $n$ is public

The signature consists of $(s,t)$, so there are two parameters the attacker can choose. If the attacker randomly chooses $t$, the problem reduces to RSA verify with the same conclusion. However, what happens, if the attacker chooses $t$ and tries to solve for $s$? Can this case also be reduced to solving the discrete logarithm?

This question can also be boiled down to this one: does the size of the RSA modulus used in both schemes lead to a comparable size of the underlying discrete logarithm, if the secret is not known?

share|improve this question
gernerate one RSA keypair and then benchmark both schemes with the same keys. – DrLecter Apr 2 '14 at 19:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.