Why is verification using DSA slower than verification with RSA?

Question

We read in literature that verification of a digital signature is slower using DSA than if we used RSA. Why is this?

DSA parameter generation:

• choose prime number $p$
• choose prime number $q$ such that $q \mid (p-1)$
• $g = h^{\frac{p-1}{q}}\mod p$ with $1 < h < (p-1)$ (multiplicative order)
• private key: choose $x$ such that $0 < x < q$
• public key: $y = (g^x\mod p)$

Public key: $(p,q,g,y)$ and private key: $(x)$.

To calculate the signature $(r,s)$:

• choose $k$ $(0 < k < q)$
• $r = (g^k\mod p)\mod q$
• $s = [k^-1 (H(M) + xr)]\mod q$. ($H()$ is our hash function)

To verify our signature we calculate

• $w = s^{-1}\mod q$
• $u_{1} = [H(M)w]\mod q$
• $u_{2} = (rw)\mod q$
• $v = [(g^{u_{1}}y^{u_{2}})\mod p]\mod q$

So, I understand how this works. But why is verification slower than RSA verification?

Answer 1

If you compare DSA with SHA-256 and a 2048 bit group modulus $p$, to RSA with SHA-256, a 2048 bit modulus $n$ and public exponent $e = 65537$, on you will at least perform the following operations:

DSA

• $g^{u_1}y^{u_2}$ - 2*256 squares $\mod p$, up to on average 2*128 multiplications $\mod p$, depending on implementation optimizations.

RSA

• $s^e$ - 16 squares $\mod n$, 1 multiplication $\mod n$.