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?