# If H(m) = 0 for some m, how can a DSA signature be forged?

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.

• @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. – DrLecter Dec 5 '13 at 17:48
• 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. – D.W. Dec 6 '13 at 1:46
• @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$. – DrLecter Dec 6 '13 at 3:30
• @DrLecter, would you mind officially answering this question so it gets off of our "unanswered questions" statistic? – SEJPM Jun 28 '15 at 18:56

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.