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

Question

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?

If so, what is given preference to for wallets to generate if x^3 + 7 is squared? even or odd?

I assume Y would be standard regardless of whether it is odd or not but I am looking through a couple implementations which assume Y is even and will (curve P - Y) if Y is initially odd?

Just wondering if I am understanding this correctly. Is there an obvious term for this that I'm missing, or am I completely misunderstanding this?

Answer 1

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) : x² = y³ + 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.

Answer 2

Elliptic curve equations require that remainders of both sides must be equal for a point to be on the curve.

https://en.bitcoin.it/wiki/Secp256k1 on this page, p denotes the divisor.

As a law of modular arithmetic, (a)^2 (mod p) is equivalent to (n*p + 2)^2

As a mathematical law, (a)^2 = (-a)^2

Combining these, you may prove that for (x,y) satisfying the equation, (x, p-y) would also satisfy

(you may replace 2 with any positive integer)

There is also the curve order, which is related to point addition more than it's related to the elliptic curve equation.