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.

  • $\begingroup$ Better use \stackrel r\gets as here $\endgroup$
    – kelalaka
    Commented Nov 14, 2020 at 10:04
  • $\begingroup$ Is this a homework question? $\endgroup$
    – kelalaka
    Commented Nov 14, 2020 at 10:28
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Nov 14, 2020 at 15:36
  • $\begingroup$ Hint: the critical difference with normal DSA is that in the question, $k$ is known. $\endgroup$
    – fgrieu
    Commented Nov 14, 2020 at 19:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.