# Why is verification using DSA slower than verification with RSA?

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?

-

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$.
-
For DSA, the order of magnitude seems right to me. But for RSA and $e=65537=2^{16}+1$, that's 16 squares and 1 multiplication $\bmod n$; not 4 squares and 2 multiplications. –  fgrieu May 27 '13 at 16:55
@fgrieu: Yes, you are right. The reason the number of multiplications was one off, is because most algorithms also include a multiplication by one, which obviously might be optimized away. –  Henrick Hellström May 28 '13 at 7:20
Thanks you for the response and the clear answer! –  11d060a946665fb769d865f4bbb48c May 28 '13 at 9:25
A quick follow up, is there a big difference in authentication and verification complexity between RSA with a 1024 modulus and a 2048 modulus? –  11d060a946665fb769d865f4bbb48c Jun 6 '13 at 9:00
@SanderDemeester: That depends on both software and hardware. If you use a schoolbook implementation on hardware with a normal word size (such as 32 or 64), you should expect the private key operation to be up to 8 times slower, and the public key operation to be 4 times slower, if you increase the modulus by a factor of 2. The actual difference might be both greater and smaller, depending on things such as which algorithm is used, the CPU cache etc. –  Henrick Hellström Jun 6 '13 at 9:20