Clarification about the recid calculation using generated ecdsa signature

[durgesh-pandey]

Hello,

I am trying to analyse the recid calculated in the ecdsa signature with recid and below is my understanding about it. Correct me if there is any inconsistency in this analysis:

When you calculate the sig (or s ) = k1^-1* decrypted, and before accepting min of two signatures, at that time if we are calculating the recid, it is nothing but to check what is the parity of y co-ordinate, even or odd? Since modulo q (or somewhere it's p too) is odd number, if y has even parity, -y (or p-y) will have odd parity. Now, before accepting the min of the (sig , FE::q() -sig), suppose your ecdsa signature was (r, s), from this you recover two Public keys as follow: From given r, you get two points R and R' with two different y co ordinates, where R = x, y and R' = (x, -y ) = -R . The two pub keys that can be recovered is Q1 = r^-1(sR - zG) and Q2 = r^-1(sR' - zG) . or Q2 = r^-1(s(-R) -zG).
At this point, if you know recid, you can simply say which one of the Q1 and Q2 is your pub key based on whether you used R or R'. But when you force that I want the min of the (sig, fe::q() - sig), and if your sig was greater than FE::q()/2, you will be accepting FE::q() - sig, thus changing the parity/sign of the sig, which means Q1 and Q2 will be swapped based on the sign of s i.e. Q1 = r^-1((-s)R -zG) which is Q2 from above, & Q2 = r^-1((-s) (-R) -zG) which is Q1 from above, you can see Q1 became Q2 and Q2 became Q1. That's where you simply say, If I will now change the recid i.e. R's Y co-ordinate's parity, you will get the original Q. And this is why signature is used for calculating the recid in the code.

Some links I looked into for pubkey extraction are this:

1. https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work
2. https://crypto.stackexchange.com/questions/60218/recovery-public-key-from-secp256k1-signature-and-message?noredirect=1&lq=1

3. https://crypto.stackexchange.com/questions/57718/verification-using-recovered-public-key-from-ecdsa-signature-and-normal-verifica?rq=1

   Thanks.

[omershlo]

Looks good to me on first look. I will take a deeper look later . Cc: @elichai

[elichai]

Yeah so as you said the recid contains 2 pieces of information:

1. If the R point is odd or even.
2. If r(R.x) is between the group order and the field order.

2 is because r is technically a field element(the x part of the point), but in ECDSA verification it is used as a scalar in the group order, so because the group order is smaller than the field order you need to encode if n < r < p, and if it is then when you recover the public key you need to add the group order to r before "lifting" it to a point.

(group order = n, field order = p)

So because of that there can be up to 4 public keys for each (message, signature) tuple (although for example in secp256k1 the chances of randomly hitting that is extremely low, so it will only happen if you construct such a signature on purpose, which is also a problem, because for the sig to be actually valid you'll need to find the discrete logarithm of a point with x > n)

[durgesh-pandey]

Yes, agree that there can be cases where there can be 4 possible R, with (r, y1),( r, -y1), (r+n, y2) and (r+n, -y2) which is derived from r +j*n for j =0 to h, the co-factor which is 1, and probability of r+n being valid x points are very low, like with probability 2^-128. In above,I was referring R and R' for the first two values of R which falls into the point 1 you mentioned. I think in code, we are not checking if the R generated from r+n is point at infinity or valid point because if we do, the recid should be two bits of information (0,1,2,3) instead of just 1 bit, guess that's left because of very less probability of it's occurrence? Thanks a lot for clarification and such a quick response.

[omershlo]

Indeed