Recovery public key from secp256k1 signature and message [closed]

Question

Regarding this article about a signature recovery

However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two public keys

So we can derive 2 public keys for each signature and message

I try work with python library https://github.com/ludbb/secp256k1-py. This library is a wrapper for C++ implementation of secp256k1. As I understand from this library we have special function sign_recoverable that returned signature with included information for recovery unique public keys. And regarding this https://github.com/ludbb/secp256k1-py/blob/f5e455227bf1e833128adf80de8ee0ebcebf218c/secp256k1/init.py#L135

   def ecdsa_recoverable_deserialize(self, ser_sig, rec_id):
      if not HAS_RECOVERABLE:
        raise Exception("secp256k1_recovery not enabled")
      if rec_id < 0 or rec_id > 3:
        raise Exception("invalid rec_id")
      if len(ser_sig) != 64:
        raise Exception("invalid signature length")
      recover_sig = ffi.new('secp256k1_ecdsa_recoverable_signature *')
      parsed = lib.secp256k1_ecdsa_recoverable_signature_parse_compact(

We have 4 variant of a possible public key from 1 signature.

In my code and attempts receive Public keys for signature in DER format (i want to iterate all available)

def public_key_recovery(signature, messsage, rec_id, compressed=True, hex=True):
if isinstance(signature, str):
    signature = unhexlify(signature)
if isinstance(messsage, str):
    messsage = unhexlify(messsage)
raw_sig = ffi.new('secp256k1_ecdsa_signature *')
r = secp256k1.secp256k1_ecdsa_signature_parse_der(ECDSA_CONTEXT_VERIFY,
                                                  raw_sig,
                                                  signature,
                                                  len(signature))
if not r:
    raise RuntimeError("secp256k1 error")
compact_sig = ffi.new('unsigned char[%d]' % 64)
r = secp256k1.secp256k1_ecdsa_signature_serialize_compact(ECDSA_CONTEXT_VERIFY,
                                                          compact_sig,
                                                          raw_sig)
if not r:
    raise RuntimeError("secp256k1 error")

recover_sig = ffi.new('secp256k1_ecdsa_recoverable_signature *')
t = secp256k1.secp256k1_ecdsa_recoverable_signature_parse_compact(
                                        ECDSA_CONTEXT_ALL, recover_sig, compact_sig, rec_id)
if not r:
    raise RuntimeError("secp256k1 error")

pubkey_ptr = ffi.new('secp256k1_pubkey *')
t = secp256k1.secp256k1_ecdsa_recover(
             ECDSA_CONTEXT_ALL, pubkey_ptr, recover_sig, messsage)
len_key = 33 if compressed else 65
pubkey = ffi.new('char [%d]' % len_key)
outlen = ffi.new('size_t *', len_key)
compflag = EC_COMPRESSED if compressed else EC_UNCOMPRESSED
if bytes(ffi.buffer(pubkey_ptr.data, 64)) == b"\x00" * 64:
    return None
r = secp256k1.secp256k1_ec_pubkey_serialize(ECDSA_CONTEXT_VERIFY, pubkey, outlen, pubkey_ptr, compflag)
if not r:
    raise RuntimeError("secp256k1 error")
pub = bytes(ffi.buffer(pubkey, len_key))
return hexlify(pub).decode() if hex else pub

I got correct result for first 2 variants (0,1), and for last 2 always 64 zeros byte string

What is real count 2 or 4 public keys posible derive from signature?

Answer 1

You can usually derive two public keys. However, sometimes (very rarely), you can get four public keys.

With some details:

• There is an elliptic curve. In Bitcoin, this is secp256k1. Each curve point has two coordinates $(X,Y)$; the coordinates are integers modulo a given prime integer $p$ (precisely, $p = 2^{256} - 4294968273$).

• The curve order (number of points on the curve) is an integer $n$, which happens to be prime, and to be very slightly lower than $p$.

• Private key is $x$, a non-zero integer modulo $n$. Public key is $Q = xG$, i.e. multiplication of a conventional generator point $G$ by the private key $x$.

• To sign a message $m$, things go the following way:

  • A random (non-zero) integer $k$ modulo $n$ is generated.
  • The point $kG$ is computed, and its $X$ coordinate (an integer modulo $p$, hence in the $0$ to $p-1$ range) is reduced modulo $n$, thus yielding a value between $0$ and $n-1$. The result is called $r$.
  • The value $s = (h(m)+xr)/k \bmod n$ is computed. $h(m)$ is the hash of the message to sign, with some hash function that yields a sequence of bytes which is interpreted as an integer.
  • The signature is $(r,s)$.

Now suppose that you have a message $m$ and a signature $(r,s)$, and you want to recompute the corresponding public key $Q$. If you somehow obtain the point $P = kG$, then you can compute: $$ Q = r^{-1} (sP - h(m)G) $$

Thus, if you can get the point $P$, then you can have the public key $Q$. However, you do not have the point $P$. Instead, you have $r$, the $X$ coordinate of the point $P$, reduced modulo $n$.

Since $n$ is very slightly lower than $p$, there can be two values $X$ that match $r$. In general there will be only one, but if $r < p-n$, then there will be two.

For each possible coordinate $X$, there can be two corresponding points. Indeed, points on the curve follow the curve equation: $$ Y^2 = X^3+7 $$ Thus, if $(X,Y)$ is a point on the curve, then $(X,-Y)$ is also a point on the curve, and has the same coordinate $X$.

Putting all together: from the value $r$ (in the signature), you can have up to two candidates for the $X$ coordinate of $P$, and from each such candidate, you can have up to two matching points. In total, there can be up to four curve points $P$ that match the $r$ value from the signature. For each of them, you can compute the corresponding public key $Q$. But note that the case of two possible $X$ coordinates for a single $r$ is very rare; indeed, this will happen randomly with probably about $2^{-128}$, i.e. never in practice (although you might be able to force it with specially crafted data). Thus, you can normally expect to recover two public keys, but (at least theoretically) you might get four.