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, 2023 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, 2023 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, 2023 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 you have read our privacy policy.

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