0

If we repeat k, I think there is little chance for s to repeat since user's private key x is random which is also used to calculate s.

cscisgqr
  • 1
  • 1
    As for repeated $k$ (not merely biased $k$), you learn two linear equations $s_1 = (h_1 + r_1 x) k^{-1}$ and $s_2 = (h_2 + r_2 x) k^{-1}$ in two unknowns $k^{-1}$ and $x$; I'll leave solving for $x$ as an exercise for the reader. – Squeamish Ossifrage Nov 26 '19 at 06:08
  • @SqueamishOssifrage I know how to calculate, but mod q is also a part of s. How can attacker know the left part without mod q? – cscisgqr Nov 29 '19 at 04:55
  • @SqueamishOssifrage Does attacks need to guess what is before mod q? – cscisgqr Nov 29 '19 at 05:07
  • I don't understand your followup questions. Can you be more specific? – Squeamish Ossifrage Nov 29 '19 at 06:10
  • @SqueamishOssifrage Your formula for s isn't correct because there is also mod q! Not sure if you ignored that intentionally. So you are assuming attackers know the left part, which isn't the case. – cscisgqr Nov 29 '19 at 06:13
  • Everything in the formulas is to be interpreted modulo $q$, and you most certainly do know the necessary $s$ and $r$ values—they make up the signature. – Squeamish Ossifrage Nov 29 '19 at 06:15
  • @SqueamishOssifrage Of course anyone knows s value, but it is after mod q. For the s_1 and s_2 equations you provided, will people be able to learn them? – cscisgqr Nov 29 '19 at 06:22
  • The premise is that you have two signatures: $(r_1, s_1)$ on a message $m_1$, and $(r_2, s_2)$ on a message $m_2$. They both satisfy the signature equation $r_i = (g^{H(m_i) s_i^{-1}} y^{r_i s_i^{-1}} \bmod p) \bmod q$, where $g$ is the standard base point and $y = g^x$ is the public key with secret key $x$. If you also know that the signatures were generated by the standard signing algorithm but $k$ is the same for both of them, then you know that $s_i \equiv (H(m_i) + r_i x) k^{-1} \pmod q$, which you can solve for $k^{-1}$ and $x$ using straightforward linear algebra. – Squeamish Ossifrage Nov 29 '19 at 06:34

0 Answers0