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.

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?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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$.
share|improve this answer
1  
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

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.