Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.