9
$\begingroup$

It is proven that ECDSA algorithms are faster in key and signature generation compared to RSA. In addition, the signatures are much shorter.

However, I would like to know the performance difference of the variants ECKCDSA and ECGDSA compared to either ECDSA or RSA. ECGDSA avoids the calculation of the inverse in the signing phase, but is there really a significant performance increase?

In the ECKCDSA algorithm, the public keys are validated by means of certificates. Does this step decrease the performance?

$\endgroup$
  • 1
    $\begingroup$ ECGDSA outsources the calculation of the inverse to the public key generation. It should be faster as it basically drops the most expensive operation from the signing phase, depending on how long hashing takes, I'd expect double digit per cent performance improvements (10%+). EC-KCDSA shouldn't be significantly slower than ECGDSA (it's a variant thereof) depending on how long your hash needs to process the additional few kilobytes. However I don't have actual measurements -> no answer. $\endgroup$ – SEJPM Jan 11 '16 at 20:53
  • $\begingroup$ Yes, that's what I thought. But the question is, is there any proof that both algorithms are faster than ECDSA? ECDSA has been repeatedly evaluated but I cannot find any performance analysis about the other two algorithms. $\endgroup$ – budderick Jan 12 '16 at 15:35
  • $\begingroup$ I've just requested implementation for the algorithms in Crypto++. Crypto++ handles the signature algorithms at a high level and so the implementations should be of comparable optimization. Hopefully this will give us informations on the speed advantage soon(tm). $\endgroup$ – SEJPM Jan 12 '16 at 19:50
  • $\begingroup$ It would be awesome to get some results from the Crypto++ framework. Do you think it would be possible to implement the algorithms soon? I found a paper that compares ECDSA and ECGDSA among others (airccj.org/CSCP/vol4/csit42111.pdf). It says that signing is about 16% faster, verification is the same and key generation is about 6% slower. Unfortunately, it doesn't evaluate the performance of ECGDSA. Hence, it would be perfect to validate and extend these results with the Crypto++ framework. $\endgroup$ – budderick Jan 18 '16 at 17:39
  • $\begingroup$ Botan already does implement all of these and more. $\endgroup$ – Vega4 Sep 20 '17 at 20:49
5
$\begingroup$

If you want to know practical measurements, which depend not just on the signature scheme family but also on the choice of curve and so on, your best approach will be to submit the software you are considering using to eBATS, unless you are also concerned with specific hardware not represented there in which case you're in a better position to do your own measurements than anyone else.

That said, we can estimate costs of the arithmetic required for straightforward implementations of these signature schemes. Let $B$ be the standard base point in the curve group in question, $n$ its order, and $A$ another curve point serving as public key, with $A = [a]B$ for secret $a$ known only to the signer.

Verification. The verification equations for a signature $r, s \in \mathbb Z/n\mathbb Z$ on a message $m$ (and certificate hash $h$ in ECKCDSA) are:

  • ECDSA: $r \equiv x\bigl([H(m)\,s^{-1}] B + [r s^{-1}] A\bigr) \pmod n$
  • ECGDSA: $r \equiv x\bigl([r^{-1} H(m)] B + [r^{-1} s] A\bigr) \pmod n$
  • ECKCDSA: $r = H\bigl(x\bigl([r \oplus H(m, h)]B + [s]A\bigr)\bigr)$

(I'm omitting details of checking the ranges of $r$ and $s$, rejecting zero, etc. If you run with the scissors included in this post and you stab yourself to security death, it's your fault, not mine! Consult the standards for what you need to pacify auditors.)

It is hard to imagine that verification performance would be different between comparable implementations of ECDSA and ECGDSA, because you can trivially express one as the other with different parameters. The ECKCDSA verification equation involves an extra hash, but that is likely to be negligible compared to the cost of the inversion it avoids altogether.

Signing.

Here $k$ is a scalar modulo $n$ chosen uniformly at random. I'm omitting all the details of fenceposts required by the procedure in the standards, and the additional step of verifying the signature after generation to confirm no faults.

  • ECDSA: Compute $r = x([k]B)$; $s$ must be a root of $H(m)\,s^{-1} + r s^{-1} a - k$ modulo $n$, so compute $$s \equiv k^{-1} (H(m) + r a) \pmod n.$$ Thus, the cost is

    • 1 elliptic-curve scalar multiplication,
    • 1 inversion modulo $n$ to compute $k^{-1}$,
    • 2 multiplications modulo $n$ to compute $r a$ and $k^{-1} (H(m) + r a)$, and
    • 1 addition modulo $n$ to compute $H(m) + r a$.
  • ECGDSA: Compute $r = x([k]B)$; $s$ must be a root of $r^{-1} H(m) + r^{-1} s a - k$ modulo $n$, so compute $$s \equiv a^{-1} (k r - H(m)) \pmod n.$$ The substantive difference from ECDSA is that the element we must invert is the long-term secret $a$, so we can just store $a^{-1}$ rather than recompute it, rather than the per-signature secret $k$. Thus, the cost is

    • 1 elliptic-curve scalar multiplication to compute $[k]B$,
    • 2 multiplications modulo $n$ to compute $k r$ and $a^{-1} (k r - H(m))$, and
    • 1 addition modulo $n$ to compute $k r - H(m)$.
  • ECKCDSA: Compute $r = H(x([k]B))$; $s$ must be a root of $r \oplus H(m, h) + s a - k$ modulo $n$, so compute $$s \equiv a^{-1} (k - r \oplus H(m, h)) \pmod n.$$ Once again, we invert the long-term secret rather than the per-signature secret, so the cost is

    • 1 elliptic-curve scalar multiplication to compute $[k]B$,
    • 1 multiplication modulo $n$ to compute $a^{-1} (k - r \oplus H(m, h))$, and
    • 1 addition modulo $n$ to compute $k - r \oplus H(m, h)$


    (and 1 $\lceil\log_2 n\rceil$-bit xor to compute $r \oplus H(m, h)$, which should be negligible).

Cost of inversions. How much does an inversion cost versus a multiplication or an addition? Usually inversion will be computed using Euler's theorem with square-and-multiply exponentiation in Montgomery form. This costs $\ell + w$ multiplications into $2\ell$-bit integers, $\ell$ squarings into $2\ell$-bit integers, and $2\ell + w$ additions into $\ell$-bit integers for the Montgomery reductions, where $\ell = \lceil\log_2 (n - 2)\rceil$ is the length of $n$ in bits and $w$ is the Hamming weight of $n - 2$, plus a little more to get the Montgomery multiplication started.

So outside the elliptic-curve scalar multiplications, inversions dominate the time spent, and there is probably a measurable difference to be had by avoiding them. Could you do better than generic square-and-multiply exponentiation using a custom multiplication chain? Yes, but unless $n$ has a very special form (which is hard to imagine!), inversion would still dominate. Replacing one multiplication by an xor in ECGDSA vs. ECKCDSA? Probably not going to matter to you.

Could you do ECDSA without per-signature inversions? Yes: you could swap the rôles of $r$ and $s$ and effectively get ECGDSA and nobody would be any the wiser, except for the auditors hired to study your software who crash your party wondering why you aren't following the letter of the bureaucratic government standard mandating a wacky bizarro variant of Schnorr signatures with unreasonably slow signing procedures.

Inversion-free alternative. May I interest you in the Schnorr-based EdDSA, which avoids inversions altogether for signing and verification, and is widely available in high-quality software running in constant time with defense against broken random number generators at signing time?

(Schnorr's patent expired a while ago, so you don't have that excuse to hide behind any more!)

$\endgroup$

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.