**Background:**

If `q`

denotes the order of `secp256k1`

with associated prime field `Fq`

, a signature is an ordered pair `(r,s)`

of non-zero elements of `Fq`

. Given some message `m`

with projection `e = proj(m)`

on `Fq`

, a signature `(r,s)`

is valid for `m`

and some public key `X`

(a point on the elliptic curve), if and only if the point `Y = (s^(-1)e)G + (s^(-1)r)X`

satisfies `proj(Y) = r`

, where `G`

denotes the generator of `secp256k1`

(a point on the elliptic curve) and the projection operator `proj: EC -> Fq`

sends `(a,b)`

with `a <= 0 < p`

to `a mod q`

(`p`

being the underlying prime of `secp256k1`

).

Given a signature `(r,s)`

and `e`

, we can recover a unique value of `X`

given a value of `Y`

. However, there are potentially as many as four elliptic curve points `Y`

which satisfies `proj(Y) = r`

. This means that **given a signature and message, we are not able to recover the public key corresponding to the signing private key**. Some additional information is required to single out the particular value of `Y`

which satisfies `proj(Y) = r`

. Writing `Y = (a,b)`

with `0 <= a,b < p`

, since `q < p`

the possible values of `a`

are `a = r`

and `a = r + q`

(provided `r + q < p`

) and each value of `a`

leads to two possible values for `b`

(even or odd). **Hence when encoding a signature in a way which allows public key recovery, we need to encode an additional 2 bits information** (whether `Y = (a,b)`

has even or odd `b`

and whether `a = r`

or `a = r + q`

). In fact, if we also wish to recover the compression status of the signing key, a third bit is required…

**Question**: Given a signature `sig = (r,s)`

, associated message `m`

and public key `X`

(a point on the elliptic curve), in order to achieve an encoding of the signature which allows public key recovery the question naturally arises of computing `twoBitsInfo(sig,m,X)`

, i.e. the relevant two bits information. My question is regarding the algorithm to compute these two bits: The `java`

library `bitcoinj`

has something along the lines of:

`int recId = -1; for(int i = 0; i < 4; ++i){ ECKey k = ECKey.recoverFromSignature(i, sig, m) if(k != null && X.equals(k.getPubKeyPoint()){ recId = i; break; } } assert(recId != -1); return recId; `

where the `recoverFromSignature`

essentially computes `Y`

from `i`

and returns `X`

from `Y`

. **I wanted to confirm that this algorithm is somewhat wasteful and that** `twoBitsInfo(sig,m,X)`

**can simply be computed by computing** `Y = (a,b)`

**from** `X`

, **then check the parity of** `b`

, **and whether** `a = r`

**or** `a = r + q`

. This simpler algorithm seems to have a computing cost equivalent to a single call to `recoverFromSignature`

(both do a computation of type `X <-> Y`

) instead of 4 in the worst case. Of course, it is very rare that `r + q < p`

(i.e `i = 2,3`

) and in practice `bitcoinj`

‘s implementation will only cost twice the normal cost in 50% of cases (even or odd parity), leading to an expected cost of 50% higher (rather 4 times).

Recent Questions – Bitcoin Stack Exchange