how to efficiently compute private key in DSA with known parameters

For textbook DSA, as defined below. If $$r, s, k, g, p, q, m$$ are all known, is it possible to efficiently compute $$x$$ from all these given values? How does the math work out?

• Secret key: $$x\stackrel R\gets \mathbb{Z}_{q}$$
• Private key: $$X=g^{x}\in \mathbb{Z}^{*}_{p}$$
• Signature:
$$\text{Algorithm }S_x(M)\\\quad{ m\gets H(M)\\ k\stackrel\\\\gets\mathbb Z_q^*\\ r\gets(g^k\bmod p)\bmod q\\ s\gets(m+x\,r)\,k^{-1}\bmod q\\ \text{return }(r,s)}$$
• Verification:
$$\text{Algorithm }V_X(M,(r,s))\\\quad{ m\gets H(M)\\ w\gets s^{-1}\bmod q\\ u_1\gets m\,w\bmod q\\ u_2\gets r\,w\bmod q\\ v\gets(g^{u_1}\,X^{u_2}\bmod p)\bmod q\\ \text{if }(v=r)\text{ return }1\\ \text{else return }0}$$

where $$H$$ is just SHA-1.

• Better use \stackrel r\gets as here Commented Nov 14, 2020 at 10:04
• Is this a homework question? Commented Nov 14, 2020 at 10:28
• I corrected the algorithms previously specified as images. $r$ is computed $\bmod p$, not $\bmod q$. And Algorithms $V$ is parametrized by $X$, not $x$. Also improved typo.
– fgrieu
Commented Nov 14, 2020 at 15:36
• Hint: the critical difference with normal DSA is that in the question, $k$ is known.
– fgrieu
Commented Nov 14, 2020 at 19:34