What is the computational cost of a public key certificate signature verification?

Question

What is the computational cost of a certificate signature verification in terms of exponentiation, multiplication and other computation operations?

Answer 1

It very much depends on the asymmetric cryptosystem used, and its parameters.

With RSA using small public exponent (which is typical), the cost of verifying a certificate (knowing the signer's public key) is dominated by a few (typically $17$ or $2$) modular multiplications (for $e=2^{16}+1$ or $e=3$) with arguments of the size of the public modulus. With the Rabin cryptosystem, that goes down to a single modular multiplication (or even less with Bernstein's lifting). With the most classical algorithm, one modular multiplication for $n$-bit public modulus costs $\approx 2\cdot(n/w)^2$ multiplication-and-addition with $w$-bit multiplicands and $(2\cdot w)$-bit result. That is often low enough for practical use even on a modest 8-bit CPU (e.g. about $70.000$ multiply-and-add for RSA with $n=1024$-bit modulus, $e=3$, $w=8$).

Most other asymmetric cryptosystems require significantly more work from the verifier, for equivalent security. They are typically implemented using a 32-bit CPU or/and a cryptographic co-processor.

For example, with DSA as defined in section 4 of FIPS186-3, an $n$-bit modulus, and a $h$-bit hash, the cost of verifying a certificate is dominated by two modular exponentiations with $h$-bit exponents and $n$-bit modulus, each using $\approx 1.5\cdot h$ modular multiplications with $n$-bit public modulus (assuming a common, basic exponentiation algorithm). With $h=160$ and $n=1024$ (the minimum specified), that's over 200 times more work than for 1024-bit RSA with $e=3$ (which security is lower, but in the same ballpark).