0
$\begingroup$

Why is the signature in DSA the way it is?

I am referring to $r$ and $k$ in the Signing-Algorithm depicted below. Is it really necessary to have both, $r$ and $s$, or would it still be secure if only one of them is used?

In the Schnorr-Signature only one random number is involved, for example.

enter image description here

$\endgroup$
3
  • 3
    $\begingroup$ $k$ is drawn at random. $r$ and $s$ are not, they are obtained by applying a function. So I see no more random numbers in DSA than in Schnorr Signature. $\endgroup$
    – fgrieu
    Aug 1 at 9:38
  • $\begingroup$ Sorry, I confused $s$ with $k$. So my question essentially is: why could the signature not be $s:=H(m)+xr$ or $s:=k^{-1}(H(m)+x)$? $\endgroup$ Aug 1 at 15:41
  • $\begingroup$ Well, both those alternatives you listed would allow easy forgery. For the first one, given a valid signature, the attacker knows $s, H(m), r$, so they can easily recover the private key $x$. For the second one, the validation formula is $r^s = g^{H(m)}g^x$; from a valid signature, the attacker can recover $g^x$. Then, to forge a signature to message $m'$, he just sets $r = g^{H(m')}g^x$ and $s= 1$ $\endgroup$
    – poncho
    Aug 1 at 16:19

1 Answer 1

1
$\begingroup$

So my question essentially is: why could the signature not be $s=H(m)+xr$ or $s=k^{−1}(H(m)+x)$?

Well, both those alternatives would allow an easy forgery after a single valid signature (or the public key in the second case)

For $s=H(m)+xr$, the adversary with a valid message/signature pair knows $s, H(m), r$. With that, simple algebra allows him to recover $x$, the private key (and with that, he can sign anything).

For $s=k^{−1}(H(m)+x)$, the validation formula (because $r=g^k$) is $g^{ks} = r^s = g^{H(m)+x} = g^{H(m)}g^x$. With a single valid message/signature pair, the adversary knows $r, s, H(m)$ (and $g$); that allows him to recover the value $g^x$ (alternatively, if the adversary has the public key, that's $g^x$, so the attacker might not even need a valid signature).

Then, to sign a message $m'$, the adversary can compute $r = g^{H(m')}g^x$ and $s=1$ - it is easy to see that satisfies the validation formula.

$\endgroup$

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.