1
$\begingroup$

In DSA, we compute the signature $(r,s)$ on $m$ by sampling $k\in\{1,...,q-1\}$ and then computing

$r := g^k \bmod p$

$s := k^{-1}*(m+x*r) \bmod q$

During verification, we compute $v:=g^{m*s^{-1}}*y^{r*s^{-1}}\bmod p$ and then check $r=v \bmod q$.

Question: Would it be fine to leave $k^{-1}$ out from the computation of $s$ (i.e., $s := m+x*r$) and then instead check for $g = v$?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Question: Would it be fine to leave $k^{-1}$ out from the computation of $s$ (i.e., $s := m+x*r$) and then instead check for $g = v$?

In other words, the check would then be $g = g^{ms^{-1}}y^{rs^{-1}}$

Now, that would not be secure; suppose we have a valid signature for $m$, that is, we have the values $(m, r, s)$ such that $g = g^{ms^{-1}}y^{rs^{-1}}$

Then, for an arbitrary message $m'$, we can compute $s' = m'm^{-1}s$ and $r' = rs's^{-1}$; We have $g^{m's'^{-1}}y^{r's'^{-1}} = g^{ms^{-1}} y^{rs^{-1}}$, which is $g$ (because the original signature is valid); that is, $(m', r', s')$ is a forgery.

$\endgroup$
1
  • 3
    $\begingroup$ Worse yet, we can recover the private key $x$ because $x=(s-m)/r\pmod q$ and $s$, $m$ and $r$ are all public values. $\endgroup$
    – Daniel S
    May 28, 2022 at 16:00

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.