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

CoderApprentice

5/25/23, 2:24 PM

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$

0 + 0

signature

dsa

key-recovery

secp256k1

kelalaka

5/25/23, 6:58 PM

Don't you have the public key in which the $y$ is already mentioned?

CoderApprentice

5/26/23, 12:43 AM

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

Score:1

Crypto

meshcollider

5/25/23, 11:20 PM

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 + 0

CoderApprentice

5/26/23, 1:04 AM

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.

meshcollider

5/26/23, 1:52 AM

Correct. I am not even sure if recid is standardised anywhere or just implementation-dependent. I know that [libsecp256k1](https://github.com/bitcoin-core/secp256k1) 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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: สามารถคำนวณ Recovery ID โดยตรงจากข้อความ ลายเซ็น และรหัสสาธารณะใน ECDSA/secp256k1 ได้หรือไม่

RO: Este posibil să se calculeze direct ID-ul de recuperare dintr-un mesaj, semnătură și cheie publică în ECDSA/secp256k1?

RU: Можно ли напрямую вычислить идентификатор восстановления из сообщения, подписи и открытого ключа в ECDSA/secp256k1?

VI: Có thể tính toán trực tiếp ID khôi phục từ một thông báo, chữ ký và khóa chung trong ECDSA/secp256k1 không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.