Saturday, January 22

Does every private key have two public keys (ie Y and negated Y?) (secp256k1)

0
46 given a private key Z that multiplied by the generator point G gives a public key P fulfills x^3 + 7 being a square, is it safe to say that either (x,y) is a valid point / pubkey, or (x, curve p – y) is a valid pubkey, and so recovering a pubkey with only the X coordinate can (given that x^3 + 7 is a square) be either Y coordinate?

When (x, y) ∈ E, where E = {(x,y) : x2 = y3 + 7 (mod p)} (the secp256k1 curve), then indeed (x,-y (mod p)) = (x,p-y) ∈ E as well. This is easy to see by substituting y’ = p-y in the equation.

This does however not say anything about the corresponding private key. In fact, if P = (x,y) = qG where G is the generator (or put otherwise, q is the private key corresponding to the public key point P), then it holds that -P = (x,-y mod p) = ((-q) mod n)G. In other words, negating the Y coordinate of a point corresponds with negating the private key (modulo n, the order of the curve, which is different from p, the size of coordinate field the curve is defined over).

Since p is odd, (x,y) and (x,p-y) have distinct parities for their Y coordinates; one will be odd, and the other will be even. Also, one will be in range [0..(p-1)/2] and the other will be in range [(p+1)/2..p-1]. There are more possible tie-breakers between these two; including one based on quadratic residuosity (which I won’t go into here as it would take us too far).

As far as ECDSA is concerned, these are distinct public and private keys. Every private key has exactly one public key corresponding to it, as public keys are (typically) encoded as 1 byte (indicating whether Y is even or odd), plus 32 bytes (for the X coordinate in full).

In BIP340, the Elliptic-Curve Schnorr signature scheme that will be activated in the near future on Bitcoin, along with the Taproot softfork (BIP341), things are different. In BIP340, public keys consist of just the 32-byte X coordinate, where for computation purposes the implicitly-even Y coordinate is used. That implies that there are indeed two private keys corresponding to such an “x-only” public key; q and n-q.