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