Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
