Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different?

Question

We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as: $s=\frac{H(m)+xr}{k}$

Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, that verify under two pubkeys $x_1G, x_2G$.

If the two public keys are equal then the secret keys should be equal $x_1 = x_2$ and we can easily recover the $k$ using the standard attack on nonce reuse. Once we know $k$ we can recover the secret key.

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r}$

$x_1 = x_2 \rightarrow x_1r - x_2r = 0$

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)} = k$

My question is can this attack be made to work if the secret keys are not equal i.e. $x_1 \ne x_2$:

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r} = \frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+ (x_1 - x_2)r}$

If you know either $x_1 - x2$ or $\frac{x_1}{x_2}$ you should be able to compute $k$ as long as $s_1 \ne s_2$.

You can calculate $x_1 - x_2 = \frac{H(m_2) - H(m_1)}{r}$ in case where $s_1 - s_2 = 0$. However this case seems to reduce to the hardness of ECDSA since anyone can compute the pubkey for a new message $m_2$ that verifies under first signature $(s, r)$ using public key recovery.

If $s_1 \ne s_2$ you can compute $\frac{x_1 - x_2}{k}$ which allows you to convert $s_1$ into $s_2$ and vice versa.

Answer 1

Suppose you have two message signature pairs and following values are then public i.e. known to you -

• The public keys: $Q_1 (= x_1G)$, $Q_2 (= x_2G)$
• The messages and their hashes: $m_1$, $m_2$, $H(m_1)$, $H(m_2)$
• The signatures: $(r_1, s_1)$, ($r_2, s_2$)

The following are unknown -

• The private keys: $x_1$, $x_2$
• The nonce: $k$

The following relations are known as well -

• $s_1 = k^{-1}(H(m_1) + r_1x_1)$
• $s_2 = k^{-1}(H(m_2) + r_2x_2)$

Note that we have two equations in three unknowns. In order to solve these we'll need to eliminate at least one unknown so that we can write one equation in terms of only one unknown and substitute that into the other equation (resulting in an equation with one unknown which can be solved via basic algebra).

The trick employed when $k$ is used with the same $x$ (i.e. $x_1 = x_2$) is that it eliminate two unknowns ($x_1$ and $x_2$) which yields an equation that is easily solved.

So how do we approach this when $x_1 \ne x_2$? The only way I see is to try to divide $s_1$ by $s_2$ to eliminate $k^{-1}$. Eliminating $x_1$ or $x_2$ seems like it would require index calculus, and that would mean solving ECDLP, which would violate the security assumptions ECDSA is predicated on.

So let's see what $\frac{s_1}{s_2}$ yields -

$$\frac{s_1}{s_2} = \frac{k^{-1}(H(m_1) + r_1x_1)}{k^{-1}(H(m_2) + r_2x_2)}$$ $$\frac{s_1}{s_2} = \frac{H(m_1) + r_1x_1}{H(m_2) + r_2x_2}$$ $$\frac{s_1(H(m_2) + r_2x_2)}{s_2} = H(m_1) + r_1x_1$$ $$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{s_2} = r_1x_1$$ $$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{r_1s_2} = x_1$$

Note that we can now remove $x_1$ from the equation defining $s_1$ and we are left with a system of two equations in two variables, which can be solved via linear algebra as long as they are not linearly dependent.

(From here on I'll be using $h_n = H(m_n)$ for the sake of brevity)

$$s_1 = k^{-1}(h_1 + r_1\frac{s_1(h_2 + r_2x_2) - s_2h_1}{r_1s_2})$$ $$k = s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2})$$

Then doing some more substitution -

$$s_2 = k^{-1}(h_2 + r_2x_2)$$ $$k = s_2^{-1}(h_2 + r_2x_2)$$ $$s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_2^{-1}(h_2 + r_2x_2)$$ $$s_2(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$ $$s_2(\frac{h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$ $$(h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1) = s_1(h_2 + r_2x_2)$$ $$s_1(h_2 + r_2x_2) = s_1(h_2 + r_2x_2)$$

So we're left with a tautology... why? Because substituting for $x_1$ into the first equation essentially left us with two instances of the same equation, just with some extra terms and terms on different sides of the equation. This means we can't solve the system. Or more precisely, that the system we have has infinitely many solutions. A simple way to see this is to consider a simpler system -

$$x = 2y$$ $$2x = 4y$$

You could substitute for $x$ in the second equation but it won't do you any good.

---

In conclusion, it would appear that nonce reuse with different key pairs does not allow recovery of any secret material. While far from a full or rigorous proof the above should convince you that it at least does not fall victim to an attack that uses the same approach as the nonce reused with the same key setting. In any case, if you have the choice I would advise to avoid this scenario, there are plenty of good ways to generate nonces out there. RFC 6979 is a good place to start.

Answer 2

NO! because if you use the same K(random number), then R will be the same for any signature on the same curve: R depends only on KG (G generation point on curve)

Example: we have two signatures (r1,s1), (r2,s2) If K is the same, then the key can be calculated as follows:

1. r1=r2 (because r=xP modn and P=kG (G generation point on curve) is the same for both signatures).

2. From the equaition for s: (s1-s2)mod n = K**(-1)(z1-z2) mod n

3. Multiply by K: K*(s1-s2)mod n = (z1-z2)mod n
4. Divide by (s1-s2) to get K: k=(z1−z2)*(s1−s2)**(-1)mod n
5. Get private key X: s=K**(-1)*(z+rX)mod n -> X=R**(-1)*(sK−z)mod n

Example for static K and two various private key:

Please note that for different private keys, resp. different public keys and, most importantly, the first value in the signature (the same R) is the same for different private keys, different public keys and different messages. I cited the algorithm for calculating the key above.

    Curve: secp256k1
    static K: 0x6f347e49ec1b25e50dd9bf56b2d0a7e340ad95bde99ac57fb65815742a0f869f

Private key: 0xc2ca56f311dc91cd15fb6b2a9b66b0579fed1f38a8e6fcbfd721a8c720d8d0d9
Public key(x,y): (0x91d1d4188286f780f879800794ea46b68dcfae941f5a76f7161255cd907443ab, 0x59508303be1539be3a2a73ed7867f6db94374cca8b40ccf1c740829d838fb110)
Message: b'Hello!'
Signature(r,s): (0x760eb603ad708e7306d79f9c4c9f7b82c4720eed8051111c46106c5441899abf, 0x9746c29bcc65fad45ddb533978d5a16cbc22a31ddeb98ba4dde5a5cd2b8922d2)
Verification: signature matches 

Private key1: 0xe61144621e67a5d78be714497bcf3777b18e43580b7b84ce49fcd559532b1062
Public key1(x,y): (0xcef0ce622b51c479f09f726172c8e7c28a6147a9cfa170f4242ee4ed70072f24, 0x3f1c6b2096c1d83fdd567a736ed9f760fcd9c89ed1588f5a4b7bf92a586c0122)
Message: b'I do not understand what is not clear'
Signature1(r,s): (0x760eb603ad708e7306d79f9c4c9f7b82c4720eed8051111c46106c5441899abf, 0x98d6440373ecc23e3a538edd5f12e090fd707852d24660b8f8f68a1cc6e2f691)
Verification: signature matches 

Scrypt python

this script was written by Andrea Corbellini, I just edited it a bit for static K.

P.S. By the way, I recommend reading his article, perhaps there will be additional clarity. (last link)