0
$\begingroup$

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$

Improve this question
$\endgroup$
2
  • $\begingroup$ Don't you have the public key in which the $y$ is already mentioned? $\endgroup$
    – kelalaka
    Commented Jan 25, 2022 at 18:58
  • $\begingroup$ @kelalaka The way I understand it, the recid relates to the y-parity of the point kG = (x,y) = X (where k is randomly chosen during signing and G is the generator of secp256k1) and not the y-parity of the public key. $\endgroup$
    – CoderApprentice
    Commented Jan 26, 2022 at 0:43

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – CoderApprentice
    Commented Jan 26, 2022 at 1:04
  • $\begingroup$ 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. $\endgroup$
    – meshcollider
    Commented Jan 26, 2022 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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