Cryptography
signature dsa key-recovery secp256k1
Updated Fri, 20 May 2022 02:32:04 GMT

Possible to directly calculate the Recovery ID from a msg, signature and public key in ECDSA/secp256k1?


Problem

Let's say I receive a signature $(r,s)$, the corresponding public key and the message that was signed. I don't have access to the private key. I need to know what the recid (Recovery ID) is that corresponds to the public key. One thing I can do is recover the public key from the signature using a multitude of libraries and trying all the possible recid values (0 or 1, very rarely 2 or 3). But I was wondering, why would I try multiple options instead of just calculating it directly?

Now according to this article... http://coders-errand.com/ecrecover-signature-verification-ethereum/

... I can simply reverse the formula and fill in all the constants of the secpk256k1 curve: https://en.bitcoin.it/wiki/Secp256k1

So I tried to think about how this would be implemented. The difference between the article and my situation is that I already have the public key $Q$. I'm interested in the $y$-parity of the Point $[k]G$ ($X$ in the article). I can calculate $X$ because I have $Q$, $R$, $S$ and all the constant values given in the wiki. But then I would have to calculate two points again:

\begin{align} X &= \frac{(eG + rQ)}{s} \bmod n\\ -X &= \frac{(eG + rQ)}{-s} \bmod n\\ \end{align}

but it's the parity precisely which I am interested in, the -. However, now I would have two points, where 1 is invalid because it would belong to a different Q, and I wouldn't know how to verify which one is correct. Furthermore, I am now again checking two points, which is what I wanted to prevent in the first place.

Question

My question is, is the only way to simply recover the public key for multiple recid values and narrow it down to the recid for your own public key? Or is it possible to come up with a formula, where recidis on one side and the other terms on the other side, something like $recid$ $=$ $Q$... $G$... $r$ $s$... $e$

Solution

Unfortunately I don't think that is possible without just testing which one works. That is because $[s]R$ and $[-s](-R)$ are the same curve point, and both $R$ and $-R$ have the same x-coordinate $r$, so $(r, s)$ and $(r, -s)$ are both valid signatures under the same public key $Q$. There is no way to determine from such a signature, whether $R$ or $-R$ needs to be used in recovery, because you don't know the secret nonce $k$. So you just need to test both possibilities out and find the one that works.

(If anyone else knows a smart way to do this that I am missing, I am happy to be corrected!)

Comments (2)

  • +0 – Well that makes sense. I guess what I'm doing here is calculating 2 coordinates that are both valid for the same public key, but actually I need to find which public key corresponds to the private key that signed the message. I tried to find a formula such that recid = <insert Q G e r s here>, but the recid isn't actually part of the formulas. So the (x,y) we actually want depends on which k was chosen during signing? And that's a number we can never find out if we don't have the private key. — Jan 26, 2022 at 01:04  
  • +0 – Correct. I am not even sure if recid is standardised anywhere or just implementation-dependent. I know that libsecp256k1 uses the first bit to indicate an odd y coordinate (when set to 1), and the second bit (when recid = 2 or 3) indicates that the x-coordinate exceeded the group order. — Jan 26, 2022 at 01:52  

External Links

External links referenced by this document:

References