[Crypto] secp256k1: is it theoretically possible to generate same signature with different key, message hash and k?

Solution 1:

We want $(r,s)$ same for two different set of $d,k,h$

In ECDSA

• $r = x_0([k]G) \bmod n$ where $k \in [1,n-1]$ and $x_o$ is the x-coordinate of the scalar multiplication $[k]G$
• $s = k^{-1}\cdot (h+r\cdot d)$ where $h$ is the left most bits of $h$ to fit in the group order ( for simplicity we called it $h$ again).

Now we want same $(r,s)$ for $d,k,h$ and $d',k',h'$

• $r = x_0([k]G) = x_0([k']G)$ although this may indicate that $k=k'$ it is not. The reason is that the coordinate field $p$ is smaller than the order $n$ of the base point. Therefore we can have solutions other than the trivial.

• $s = k^{-1}\cdot (h+r\cdot d) = k'^{-1}\cdot (h'+r\cdot d')$,

  then with $k'=k$ we have;

  \begin{align} (d'-d)\cdot r &= (h-h') \\ \end{align}

  then with $k'\neq k$ with $c = k^{-1}$ and $c' = k'^{-1}$ ( for our eyes) we have;

  \begin{align} c'\cdot h + c' \cdot r \cdot d &= c\cdot h' + c \cdot r \cdot d' \\ c'\cdot h -c\cdot h' &= c \cdot c \cdot d' -c' \cdot r \cdot d \\ c'\cdot h -c\cdot h' &= r \cdot ( c \cdot d' -c' \cdot d) \\ \end{align}

As we can see by knowing $r$;

Either

• we need to find a proper $d'$ for a given $d$ for given different hash values. This is free since we found the private key by just arithmetics.
• OR, we need to find a message that produces desired hash value $h'$ so that we have equality. This is hard since we need to break pre-image resistance of SHA256.

As we can see it is possible but hard.

For the case $k'\neq k$ the calculations are similar.

---

Solution 2:

For a given private key $d$, random $k$ and message hash $h$: is it possible that there exists a different set of $d$, $k$ and $h$ which produces the same ECDSA signature using the $\text{secp256k1}$ curve?

Yes, and further it's easy to explicitly compute an alternate $(d',k',h')$ that matches all reasonable meanings of "different set of $d$, $k$ and $h$":

• different tuples: $(d',k',h')\ne(d,k,h)$
• pairwise different values: $d'\ne d$, $k'\ne k$, and $h'\ne h$ (which implies the above)
• different sets: $\{d',k',h'\}\ne\{d,k,h\}$, which is literally what's asked, but rather exotic: order of elements does not matter in sets, thus $\{1,2,3\}=\{2,3,1\}$, and $\{1,1,2\}=\{2,2,1\}$. Also, that set equality has two different possible meanings depending on if we assimilate hashes (like $h$) to integers (like $k$ and $d$) for the purpose of comparison, which is a matter of convention.

---

"Same signature" means $(r,s)$ is unchanged, that is $r$ and $s$ both are unchanged.

In ECDSA, $r$ is unchanged if and only if $k'=k$ or $k'=n-k$. I settle for $k'=n-k$, which implies $k'\ne k$ because $n$ is odd.

Given the above, $s$ is unchanged if and only $k'^{-1}\,(h'+r\,d')\equiv k^{-1}\,(h+r\,d)\pmod n$. That is $h+h'+r\,(d+d')\equiv0\pmod n$, thus $d'=-d-r^{-1}\,(h+h')\bmod n$.

Thus we only need to

• compute $r$ the normal way (if it's not a given),
• select a different $h'$ (overwhelmingly likely, it's enough to hash a different message; otherwise, we retry with another message),
• compute $k'\gets n-k$ and $d'\gets-d-r^{-1}\,(h+h')\bmod n$.

That insures $(d',k',h')$ yields the same signature $(r,s)$ as $(d,k,h)$ does, with $k'\ne k$ and $h'\ne h$, and overwhelmingly likely $d'\ne d$ (otherwise, we retry with another message/$h'$).

If we do not assimilate bitsrings and integers, $h'\ne h\implies\{d',k',h'\}\ne\{d,k,h\}$. If we do, it's overwhelmingly likely that $h'$ is neither $d'$ nor $k'$ (otherwise, we retry with another message/$h'$).

---

Solution 3:

It is totally possible and fairly easy to see without any advanced maths. The curve has order n (n Points in the curve) the private key d is [0... n-1] and the random number k [1... n-1] and there are 2^256 possible values for h. So there are n*(n-1)*2^256 possible inputs (d, k, h combinations). The output is r, s. Where r is there x part of a point so there are definitely not more (actually less) values than there are points on the curve and s is taken mod n, so there are not more than n possible values for that either.

So in total there are around nn2^256 inputs for maximal than n*n signatures. So the pigeonhole principle tells us that there must be multiple inputs that produce the same output.