1
$\begingroup$

If we know for some message $m$ that $H(m) = 0$, how can we forge a DSA signature with only the public key?

I got that $g^s*r = (g^x)^r$ where $x$ is the private key, but that's one equation with 2 unknowns, and since discrete log is hard, I can't substitute a value for either $s$ or $r$ and find the other and satisfying the condition $0 < s$ and $r < q$ at the same time.

$\endgroup$
  • 1
    $\begingroup$ @24601 Your current approach does not really help you. Look what happens to $u_1$ if $H(m)$ happens to be zero and how the verification equation simplifies. Now, take a closer look at the right hand side of the verification equation. Could the choice of $s$ help you? ;) I used the notation from here. $\endgroup$ – DrLecter Dec 5 '13 at 17:48
  • $\begingroup$ As DrLecter says, when asking this sort of question, please make sure to describe what you've tried and where you got stuck. We expect you to make a serious effort before asking here and to show us what you've tried and where you got stuck. $\endgroup$ – D.W. Dec 6 '13 at 1:46
  • $\begingroup$ @24601 correct. But that's only one choice for $r$ ;) You can exponentiate your choice of $r$ with an arbitrary value $a$ (other than $1$) from $Z_q$ as long as you also put it's inverse in $s$. $\endgroup$ – DrLecter Dec 6 '13 at 3:30
  • $\begingroup$ @DrLecter, would you mind officially answering this question so it gets off of our "unanswered questions" statistic? $\endgroup$ – SEJPM Jun 28 '15 at 18:56
1
$\begingroup$

The signature equation is $$r = (g^{H(m) s^{-1}} y^{r s^{-1}} \bmod p) \bmod q,$$ where $g$ is the standard generator of an order-$q$ subgroup of $\mathbb Z/p\mathbb Z$, $y \in \mathbb Z/p\mathbb Z$ is a public key, $m$ is a message, and the signature is $(r, s)$ for scalars $r, s \in \mathbb Z/n\mathbb Z$.

If $H(m) = 0$, this reduces to $r = (y^{r s^{-1}} \bmod p) \bmod q$. If you pick $r = s = y \bmod q$, then $r s^{-1} \equiv 1 \pmod q$, so $y^{r s^{-1}} \bmod p = y$ and so $(y^{r s^{-1}} \bmod p) \bmod q = y \bmod q = r$ as desired.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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