<p>Put some comments embedded with code, still, some questions remain, hopefully, to be improved time by time.</p>
<p>The below code used in public key recovery method, is aiming for recover the R (rx, ry) from provided r and recid (0 or 1), for recid (2or3) case, simply reduce (provided r)-n.</p>
<pre><code>{    if (recid &amp; 2) {    /* if recid=2 or 3 */
    if (secp256k1_fe_cmp_var(&amp;fx, &amp;secp256k1_ecdsa_const_p_minus_order) &gt;= 0) {
        /* if fx &gt;= p-n, not a valid signature */
        return 0;
    }
    /* else if fx &lt; p-n, do fx=fx+n  */

    secp256k1_fe_add(&amp;fx, &amp;secp256k1_ecdsa_const_order_as_fe);
}
</code></pre>
<p>next call up secp256k1_ge_set_xo_var(), for the recid=0/1 (recid 2/3 result will also be passed in?)</p>
<pre><code>static int secp256k1_ge_set_xo_var(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd) {
/* for all below operation on Field (p), implicitly mod p */ 
secp256k1_fe_t x2, x3, c;
/* directly get rx */
r-&gt;x = *x;
/* calculate x2 = x^2 */
secp256k1_fe_sqr(&amp;x2, x);
/* calculate x3 = x^2 *x = x^3 */
secp256k1_fe_mul(&amp;x3, x, &amp;x2);
/* set up infinity flag =0 as won't be 1 for below operation */
r-&gt;infinity = 0;
/* calculate c=x^3 +7 */
secp256k1_fe_set_int(&amp;c, 7);
secp256k1_fe_add(&amp;c, &amp;x3);
/* calculate sqrt(c), put to ry*/
if (!secp256k1_fe_sqrt_var(&amp;r-&gt;y, &amp;c)) {
    return 0;
}
/* what does normalize mean ? */
secp256k1_fe_normalize_var(&amp;r-&gt;y);
/* odd (recid passed in) could be 0(ry=even) or 1(ry=odd) */
/* exp: if odd=0, but odd(ry)=1 !=0, then do reverse*/
/* exp: if odd=1, also odd(ry)=1 == 1, then simply return */
if (secp256k1_fe_is_odd(&amp;r-&gt;y) != odd) {
    /* for getting -R, i.e. -(r.y) one can simply do p-(r.y) */
    /* below likely does p*2*(1+1)-(r.y), why??*/
    secp256k1_fe_negate(&amp;r-&gt;y, &amp;r-&gt;y, 1);
}
return 1;
</code></pre>
<p>}</p>

CC BY-SA 4.0
2021-03-17T04:42:53.150Z
Everything is implicitly mod p. We set infinity=0 because we need to set infinity=0 or infinity1 in the output, and we know the result won't be infinity. Normalize means bring to canonical representation (secp256k1_fe can be temporarily "denormalized" which allows some faster operations, but isn't compatible with fe_is_odd, for example). fe_negate(a,b,n) just computes the negation of b and puts it in a; the n argument gives the maximum magnitude of the input (which is 1, because the input is normalized).
Pieter Wuille
CC BY-SA 4.0
2021-03-17T04:45:30.140Z
For dealing with recid=2 or recid=3, that means we have r = R.x - n (remember: r = R.x mod n, so either r = R.x or r = R.x - n). We're given r in the signature, but we need to recover the full R.x coordinate. If recid=2 or recid=3, we need to add n: R.x = r + n.
Pieter Wuille
CC BY-SA 4.0
2021-03-17T04:54:53.547Z
The deal with normalization: field elements are represented as 5 52-bit "limbs" (on 64-bit symbols). Those limbs are allowed to overflow (be larger than 2^52), which permits addition/negation without carry (much faster for some operation); for addition you just add the corresponding limbs; for negation you subtract it from a multiple of limbs representing n... but you need to know how big the input is allowed to be (as you need to make sure no limb can result in a negative number). That's why fe_negate takes in a magnitude argument.
Pieter Wuille
CC BY-SA 4.0
2021-03-20T02:55:14.227Z
@PieterWuille "Everything is implicitly mod p“ -> this is for the F(p) operation I suppose? if operate in Group (for exp, calculate Point Add/Mult, which are operated on both X/Y coordination, that will be mod n?
LeonMSH
CC BY-SA 4.0
2021-03-20T03:11:19.380Z
The scalar factor in point multiplication is indeed modulo n. But all variables in this snippet ("fe" types) are modulo p.
Pieter Wuille
CC BY-SA 4.0
2021-03-21T15:03:55.887Z
@PieterWuille for recid0/1 case, I have two questions: Q1: we need to calculate the sqrt(x3+7) to get the Ry -- if solving a mathmetic function we shall get +/- solution-- from code it likely we will get only one solution--that could be old or even, we then compare old/even with recid to decide if we need do negate.--is this correct?  Q2: if I don't use the secp256k1 speedup lib (which has 5*64bit and mentioned normalized tricky), but using some general 256 bit operation, if I know R.y, to getting negation -R.y, can I do the (p-R.y)?
LeonMSH
CC BY-SA 4.0
2021-03-21T17:13:24.723Z
1) Yes, computing the sqrt(x^3+7) always gives you the square root that is a square itself, but that could be even or odd. By comparing its parity with recid and conditionally negating, you get the intended result. 2) Yes.
Pieter Wuille
CC BY-SA 4.0
2021-05-24T12:02:42.640Z
@PieterWuille I had made one successful public key recovery routine by following the secp256k1 lib implementation method. Thanks so much for your question answer. I find most of the timing consumed on the recovery y from the y^2 (I simply calculate the power ((p + 1)/4) %p by using the fast exponential modular algorithm, which usually takes 256 iterations) -- if refer to lib secp256k1_fe_mul that looks taking some fast computing (multiple squares and multiply, though underline are assembly code) --is there any reference documentation that can you recommend for reading?
LeonMSH
CC BY-SA 4.0
2021-04-08T04:14:38.233Z
@PieterWuille I noticed that the signature (r,s,z,x,y) generated by OpenSSL API will be verified fail by using secp256k1 lib, further investigate I found that I need to reverse the byte sequence for each of (r,s,z,x,y)--then it will pass. It seems the secp256k1 lib arrange the storage differently (byte-level reorder) than the OpenSSL, is that correct? and if that is true, why?
LeonMSH
CC BY-SA 4.0
2021-04-10T02:59:56.130Z
That's not correct, and I suspect you're not using things right. The serialization of public keys, signatures, and private keys all uses big endian, both in libsecp256k1 and OpenSSL.
Pieter Wuille
CC BY-SA 4.0
2021-03-16T04:37:36.687Z
2021-03-21T14:40:46.553Z
2021-03-21T14:40:46.553Z
LeonMSH
<blockquote>
<p>1). from the secp256k1 code I did not find 27~34 value, all I found are 0~3; so where the difference come from?</p>
</blockquote>
<p>The serialization as a 65-byte signature + recovery byte happens on the Bitcoin Core side, not in libsecp256k1. See <a href="https://github.com/bitcoin/bitcoin/blob/v0.21.0/src/key.cpp#L257" rel="nofollow noreferrer">key.cpp</a>:</p>
<pre><code>vchSig[0] = 27 + rec + (fCompressed ? 4 : 0);
</code></pre>
<blockquote>
<p>2). I guess [27~30 and [31~34] such value set does not come from nonsense, but why using these two value set to map to [0~3]? Guess some tricky hidden inside--is that because of some trick on bit-level operation?</p>
</blockquote>
<p>There is nothing special about it. I just picked an arbitrary offset so the signature byte arrays wouldn't be confused with public keys or other signatures. But there is no special meaning to the number 27 (and in retrospect, it's a rather strange choice).</p>
<p>I'll try to expand this answer later to explain the code.</p>

CC BY-SA 4.0
2021-02-10T02:56:54.447Z
Great thanks for the reply, didn't expect to get the original author helping on this;-) ... it took me some time to think why this number is selected. Waiting for more comments of the code.. for my Q3, from some other post I thought it would be due to when recid=2/3 means (x,y) sit on the location that satisfies (n<x<p)? But I did not understand the function of secp256k1_fe_cmp_var yet.
LeonMSH
CC BY-SA 4.0
2021-03-14T06:54:47.970Z
if possible, could you please help to explain the logic behind the if secp256k1_ge_set_xo_var(&x, &fx, recid & 1)? this piece of code looks not link to SEC standard document-- is that specific tricky to the secp256k1 curve?
LeonMSH
CC BY-SA 4.0
2021-03-14T08:59:04.917Z
Recoverable pubkeys are something we invented for bitcoin message signing. It's not in any standard.
Pieter Wuille
CC BY-SA 4.0
2021-03-14T13:44:13.470Z
I can find the pub key recovery method here: https://www.secg.org/sec1-v2.pdf (CH4.1.6) but the detail implementation is not the same (it has no recover id) a recover id indeed help speed up the algorithm, but short of the reference of the algorithm--is there any more documentation can help to understand the logic behind these piece of code?
LeonMSH
CC BY-SA 4.0
2021-03-16T04:40:08.680Z
I paste one more post below, put all my understanding here if you can help to comment whether they are correct or not... if anything is wrong--would you please suggest the correct understanding?
LeonMSH
CC BY-SA 4.0
2021-02-09T05:25:52.423Z
2021-02-09T05:25:52.423Z
Pieter Wuille
<p>Here I have some questions regarding the recovery id (recid) defined in secp256k1 implementation.
I had found few posts about how the recid is defined and what does it mean, also the source code (<a href="https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h" rel="nofollow noreferrer">https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h</a>).</p>
<p>As explain by bitcoin developers like Peter Wuille the recid is [27~30] for compressed pubkey and [31~34] for non-compressed pubkey.
my question are:</p>
<p>1). from the secp256k1 code I did not find 27~34 value, all I found are 0~3; so where the difference come from?</p>
<p>2). I guess [27~30 and [31~34] such value set does not come from nonsense, but why using these two value set to map to [0~3]? Guess some tricky hidden inside--is that because of some trick on bit-level operation?</p>
<p>3). can someone help to explain this piece of code (come from <a href="https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h#L104-L112" rel="nofollow noreferrer">https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h#L104-L112</a>)</p>
<p>looks for me recid &amp;2 (0x10) actually select recid=2/3 case.</p>
<p>and if recid !=2/3 all left code will be executed--is that understanding correct?</p>
<pre><code>if (recid &amp; 2) {
    if (secp256k1_fe_cmp_var(&amp;fx, &amp;secp256k1_ecdsa_const_p_minus_order) &gt;= 0) {
        return 0;
    }
    secp256k1_fe_add(&amp;fx, &amp;secp256k1_ecdsa_const_order_as_fe);
}
if (!secp256k1_ge_set_xo_var(&amp;x, &amp;fx, recid &amp; 1)) {
    return 0;
}
</code></pre>

CC BY-SA 4.0
2021-02-12T18:11:30.607Z
If you have one specific question, there should be one question mark, not four.
David Grayson
CC BY-SA 4.0
2021-02-21T15:16:09.113Z
Sorry for that--I think initially I had one "specific" question but when I was trying to draft the question, some more questions may be raised and it turned out better to make them seperately..
LeonMSH
<public-key><ecdsa><secp256k1>
secp256k1 recovery id and how does the code work
LeonMSH
# secp256k1 recovery id and how does the code work

(Asked by: username_0 on 2021-02-09)

Here I have some questions regarding the recovery id (recid) defined in secp256k1 implementation.
I had found few posts about how the recid is defined and what does it mean, also the source code (<https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h>).

As explain by bitcoin developers like Peter username_2 the recid is [27~30] for compressed pubkey and [31~34] for non-compressed pubkey.
my question are:

1). from the secp256k1 code I did not find 27~34 value, all I found are 0~3; so where the difference come from?

2). I guess [27~30 and [31~34] such value set does not come from nonsense, but why using these two value set to map to [0~3]? Guess some tricky hidden inside--is that because of some trick on bit-level operation?

3). can someone help to explain this piece of code (come from <https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h#L104-L112>)

looks for me recid &2 (0x10) actually select recid=2/3 case.

and if recid !=2/3 all left code will be executed--is that understanding correct?

```
if (recid & 2) {
    if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
        return 0;
    }
    secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
}
if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
    return 0;
}

```

**Tags:** public-key, ecdsa, secp256k1

> **Comments:**
> **username_1**: If you have one specific question, there should be one question mark, not four.  
> **username_0**: Sorry for that--I think initially I had one "specific" question but when I was trying to draft the question, some more questions may be raised and it turned out better to make them seperately..  

---

## 2 answers

### Answer by username_2 on 2021-02-09. Score: 3 | Accepted answer

> 1). from the secp256k1 code I did not find 27~34 value, all I found are 0~3; so where the difference come from?

The serialization as a 65-byte signature + recovery byte happens on the Bitcoin Core side, not in libsecp256k1. See [key.cpp](https://github.com/bitcoin/bitcoin/blob/v0.21.0/src/key.cpp#L257):

```
vchSig[0] = 27 + rec + (fCompressed ? 4 : 0);

```

> 2). I guess [27~30 and [31~34] such value set does not come from nonsense, but why using these two value set to map to [0~3]? Guess some tricky hidden inside--is that because of some trick on bit-level operation?

There is nothing special about it. I just picked an arbitrary offset so the signature byte arrays wouldn't be confused with public keys or other signatures. But there is no special meaning to the number 27 (and in retrospect, it's a rather strange choice).

I'll try to expand this answer later to explain the code.

> **Comments:**
> **username_0**: Great thanks for the reply, didn't expect to get the original author helping on this;-) ... it took me some time to think why this number is selected. Waiting for more comments of the code.. for my Q3, from some other post I thought it would be due to when recid=2/3 means (x,y) sit on the location that satisfies (n<x<p)? But I did not understand the function of secp256k1_fe_cmp_var yet.  
> **username_0**: if possible, could you please help to explain the logic behind the if secp256k1_ge_set_xo_var(&x, &fx, recid & 1)? this piece of code looks not link to SEC standard document-- is that specific tricky to the secp256k1 curve?  
> **username_2**: Recoverable pubkeys are something we invented for bitcoin message signing. It's not in any standard.  
> **username_0**: I can find the pub key recovery method here: https://www.secg.org/sec1-v2.pdf (CH4.1.6) but the detail implementation is not the same (it has no recover id) a recover id indeed help speed up the algorithm, but short of the reference of the algorithm--is there any more documentation can help to understand the logic behind these piece of code?  
> **username_0**: I paste one more post below, put all my understanding here if you can help to comment whether they are correct or not... if anything is wrong--would you please suggest the correct understanding?  

---

### Answer by username_0 on 2021-03-16. Score: 0

Put some comments embedded with code, still, some questions remain, hopefully, to be improved time by time.

The below code used in public key recovery method, is aiming for recover the R (rx, ry) from provided r and recid (0 or 1), for recid (2or3) case, simply reduce (provided r)-n.

```
{    if (recid & 2) {    /* if recid=2 or 3 */
    if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
        /* if fx >= p-n, not a valid signature */
        return 0;
    }
    /* else if fx < p-n, do fx=fx+n  */

    secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
}

```

next call up secp256k1\_ge\_set\_xo\_var(), for the recid=0/1 (recid 2/3 result will also be passed in?)

```
static int secp256k1_ge_set_xo_var(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd) {
/* for all below operation on Field (p), implicitly mod p */ 
secp256k1_fe_t x2, x3, c;
/* directly get rx */
r->x = *x;
/* calculate x2 = x^2 */
secp256k1_fe_sqr(&x2, x);
/* calculate x3 = x^2 *x = x^3 */
secp256k1_fe_mul(&x3, x, &x2);
/* set up infinity flag =0 as won't be 1 for below operation */
r->infinity = 0;
/* calculate c=x^3 +7 */
secp256k1_fe_set_int(&c, 7);
secp256k1_fe_add(&c, &x3);
/* calculate sqrt(c), put to ry*/
if (!secp256k1_fe_sqrt_var(&r->y, &c)) {
    return 0;
}
/* what does normalize mean ? */
secp256k1_fe_normalize_var(&r->y);
/* odd (recid passed in) could be 0(ry=even) or 1(ry=odd) */
/* exp: if odd=0, but odd(ry)=1 !=0, then do reverse*/
/* exp: if odd=1, also odd(ry)=1 == 1, then simply return */
if (secp256k1_fe_is_odd(&r->y) != odd) {
    /* for getting -R, i.e. -(r.y) one can simply do p-(r.y) */
    /* below likely does p*2*(1+1)-(r.y), why??*/
    secp256k1_fe_negate(&r->y, &r->y, 1);
}
return 1;

```

}

> **Comments:**
> **username_2**: Everything is implicitly mod p. We set infinity=0 because we need to set infinity=0 or infinity1 in the output, and we know the result won't be infinity. Normalize means bring to canonical representation (secp256k1_fe can be temporarily "denormalized" which allows some faster operations, but isn't compatible with fe_is_odd, for example). fe_negate(a,b,n) just computes the negation of b and puts it in a; the n argument gives the maximum magnitude of the input (which is 1, because the input is normalized).  
> **username_2**: For dealing with recid=2 or recid=3, that means we have r = R.x - n (remember: r = R.x mod n, so either r = R.x or r = R.x - n). We're given r in the signature, but we need to recover the full R.x coordinate. If recid=2 or recid=3, we need to add n: R.x = r + n.  
> **username_2**: The deal with normalization: field elements are represented as 5 52-bit "limbs" (on 64-bit symbols). Those limbs are allowed to overflow (be larger than 2^52), which permits addition/negation without carry (much faster for some operation); for addition you just add the corresponding limbs; for negation you subtract it from a multiple of limbs representing n... but you need to know how big the input is allowed to be (as you need to make sure no limb can result in a negative number). That's why fe_negate takes in a magnitude argument.  
> **username_0**: @username_2 "Everything is implicitly mod p“ -> this is for the F(p) operation I suppose? if operate in Group (for exp, calculate Point Add/Mult, which are operated on both X/Y coordination, that will be mod n?  
> **username_2**: The scalar factor in point multiplication is indeed modulo n. But all variables in this snippet ("fe" types) are modulo p.  
> **username_0**: @username_2 for recid0/1 case, I have two questions: Q1: we need to calculate the sqrt(x3+7) to get the Ry -- if solving a mathmetic function we shall get +/- solution-- from code it likely we will get only one solution--that could be old or even, we then compare old/even with recid to decide if we need do negate.--is this correct?  Q2: if I don't use the secp256k1 speedup lib (which has 5*64bit and mentioned normalized tricky), but using some general 256 bit operation, if I know R.y, to getting negation -R.y, can I do the (p-R.y)?  
> **username_2**: 1) Yes, computing the sqrt(x^3+7) always gives you the square root that is a square itself, but that could be even or odd. By comparing its parity with recid and conditionally negating, you get the intended result. 2) Yes.  
> **username_0**: @username_2 I noticed that the signature (r,s,z,x,y) generated by OpenSSL API will be verified fail by using secp256k1 lib, further investigate I found that I need to reverse the byte sequence for each of (r,s,z,x,y)--then it will pass. It seems the secp256k1 lib arrange the storage differently (byte-level reorder) than the OpenSSL, is that correct? and if that is true, why?  
> **username_2**: That's not correct, and I suspect you're not using things right. The serialization of public keys, signatures, and private keys all uses big endian, both in libsecp256k1 and OpenSSL.  
> **username_0**: @username_2 I had made one successful public key recovery routine by following the secp256k1 lib implementation method. Thanks so much for your question answer. I find most of the timing consumed on the recovery y from the y^2 (I simply calculate the power ((p + 1)/4) %p by using the fast exponential modular algorithm, which usually takes 256 iterations) -- if refer to lib secp256k1_fe_mul that looks taking some fast computing (multiple squares and multiply, though underline are assembly code) --is there any reference documentation that can you recommend for reading?  

---

