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


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


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.