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

**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.

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 `recid`

is on one side and the other terms on the other side, something like $recid$ $=$ $Q$... $G$... $r$ $s$... $e$

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!)

- +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 referenced by this document: