2
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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$.
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    May 27, 2013 at 16:55
  • $\begingroup$ @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. $\endgroup$ May 28, 2013 at 7:20
  • $\begingroup$ A quick follow up, is there a big difference in authentication and verification complexity between RSA with a 1024 modulus and a 2048 modulus? $\endgroup$
    – Anonymous
    Jun 6, 2013 at 9:00
  • $\begingroup$ @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. $\endgroup$ Jun 6, 2013 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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