I'm considering this for bitcoin transaction as it uses ECDSA so if the signer generates two signatures suppose s1 and s2. where: enter image description here

I get it that any attacker who have s1 and s2 can recover its private key x. But the question is can the signer use a different private key x1 for instance to generate s2..in such a way even if he uses same k but still its private key will be safe.??(cryptocurrency like bitcoin allows multiple public private key pair of a user) Am i getting something wrong otherwise this would have been not a well known ECDSA vulnerability in bitcoin. Please explain the contradiction. Thanks in advance

  • 1
    $\begingroup$ One may want to note that this question is equivalent to asking "assume that by chance two ECDSA signatures by two distinct private keys use the same k, given just the signatures produced, can we recover either private key?". $\endgroup$ – SEJPM Jun 5 '18 at 17:49

You are positing that the signer signs two messages $m_1$ and $m_2$ under different private keys $x_1$ and $x_2$, but the same per-signature secret $k$.

\begin{align*} s_1 &= (h(m_1) + x_1 r)/k, \\ s_2 &= (h(m_2) + x_2 r)/k. \end{align*}

Note that $r = x([k]B)$ where $B$ is the standard base point. Even if you are given $s_1$, $s_2$, $m_1$, $m_2$, and $r$, this is a system of two equations in three unknowns. This doesn't even constrain you to a unique solution: for any nonzero value of $x_1$, there is a corresponding value of $(x_2, k)$; likewise $x_2$ and $(x_1, k)$, and $k$ and $(x_1, x_2)$. Indeed, for, e.g., secp256k1, there are approximately $2^{256}$ possible solutions for $(x_1, x_2, k)$.

| improve this answer | |
  • $\begingroup$ I think the attacker entity is misjudged in my question actually its related to bitcoin double spend attack..so in your terminology, i meant: if the signer signs s1 using private key x.. and again for another transaction he signs s2 using private key x1...and lets suppose the attacker eavesdrops and get to know s1 and s2..but still he cant get the private key right? as two different keys are used to generate signatures..right? $\endgroup$ – Prashant Varma Jun 5 '18 at 16:31
  • $\begingroup$ @PrashantVarma: that's not a bitcoin double-spend, which requires the key owner issue conflicting but otherwise valid (signed) txns using/spending the same UTXO(s). A bitcoin user usually has many keypairs, but only one keypair can be used for a given UTXO (except for special cases like multisig, and even then you can't just substitute one keypair for another). Plus bitcoin software, like all decent ECDSA implementations, chooses random k always, regardless of the key used. $\endgroup$ – dave_thompson_085 Jun 6 '18 at 3:07

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