9
$\begingroup$

A DSA signature consists of two scalars $(r,s)$.

When signing $s$ is generated as:

  • $s=k^{-1}(H(m)+xr) \mod q$
  • The signature is $(r,s)$

When verifying $s$ is only used to compute $w = s^{-1}$. So why does DSA store $s$ in the signature instead of $w$?

Using $w$ has no performance effect on signing since computing either $s$ or $w$ requires one modular inversion. $w = s^{-1} \mod q = k (H(m)+xr)^{-1} \mod q$.
It would speed up verification since the modular inversion to compute $w$ isn't necessary anymore.

The only advantage of $s$ I see is that the modular inversion can be computed before the hash is known. Did the DSA designers consider that pre-computation more important than the verification slowdown, or is there some other advantage of using $s$ that I don't see?

|improve this question
$\endgroup$
  • $\begingroup$ The signature verification involves two elliptic curve multiplications, which take way more time than the modular division, so there is not really a point to precalculate this. $\endgroup$ – Willem Hengeveld Jul 15 '14 at 14:28
10
$\begingroup$

Well, it's been an entire day, and no one has given an authoritative answer; I'll throw in my guess as to why the people designing DSA made the choices they did.

With DSA, there are three operations that are relevent to this discussion:

  • A: do precomputation of a signature (without seeing the message being signed)

  • B: given a precomputed signature and a message, generate the actual signature

  • C: verify a signature.

Standard DSA and your variant DSA perform exactly the same operations, except that standard DSA computes a modular inverse during steps A and C, while your variant computes it at step B.

It is true that standard DSA does two modular inverse, while your variant does only one; however, that may not be the only factor.

If we look at step B, we see that the operations involved at quite cheap (a single modular multiplication and addition); if we were to include a modular multiplication operation there, we would increase the cost of that operation by a large percentage. In contrast, steps A and C are already expensive (involving a modular exponentiation or point multiplication); including a modular inverse only slows down those operations by a small percentage.

That is, DSA has the property that, with precomputation, generating a signature is extremely fast. Your variant significantly reduces this advantage; the DSA designers designed to keep this advantage, even at the cost of increasing the total computation required.

Now, you may disagree with the above logic; in fact, people have proposed a DSA-variant exactly like what you suggest.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ It would be useful if you could state whether this nice theory came as pure product your mind, or is from some source you consider authoritative (even if it can't be named). Also it would be nice to better characterize the people that proposed the DSA variant reinvented by CodesInChaos. $\endgroup$ – fgrieu Jun 6 '13 at 16:23
  • 1
    $\begingroup$ @fgrieu: I believe that I mentioned in the first paragraph that this was a "guess"; that is, I have no direct knowledge, but instead reconstructed the likely reasoning based on the differences in the DSA variants. As for the people that proposed the DSA variants, I don't have a direct reference, I do have a reference "Horster, P. et al; Meta-ElGamal signature schemes; University of Technology Chemnitz-Zwickau, 1994" which talks about the relationships of both standard DSA and this variant (and others). $\endgroup$ – poncho Jun 6 '13 at 16:33
  • 1
    $\begingroup$ Thanks, your comment does just what I asked. (side note: let's see if this format for link to comments works) $\endgroup$ – fgrieu Jun 6 '13 at 17:29
  • $\begingroup$ "a single modular multiplication and addition" and a hash. $\;$ $\endgroup$ – user991 Jun 7 '13 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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