Score:0

Reason for two random numbers in DSA?

at flag

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

fgrieu avatar
ng flag
$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.
cryptoQueen avatar
at flag
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)$?
poncho avatar
my flag
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$
Score:1
my flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.