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?

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?

3
  • No one uses negative y? y^2 = x^3 + 7 makes this obvious. The smaller y is the positive which is to be used. Does this help? crypto.stackexchange.com/questions/54845/…
    – MCCCS
    Aug 6 '21 at 16:26
  • Sorry, right, I mean that Y itself is subtracted by P, not that Y in itself is negative. I have to admit I have very little knowledge about this particular subject and it's actually a bit of an XY problem that I stumbled upon but I think the key lies herein that when Y is initially odd, it is correct to say that you can subtract it from curve P to get an even Y? Aug 6 '21 at 16:32
  • @MCCCS If I skimmed over that correctly it seems to confirm my suspicions. thanks! Aug 6 '21 at 16:40
2

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.

1
  • 1
    Thanks. I think your last paragraph described the crux of the issue: a BIP340 implementation I found was forcing even Y coordinates while my other library didn't + there was just a hex X-coordinate and no "is Y even" markers (eg 0x02 : 0x03) when encoded as you mentioned, causing some confusion about what exactly is considered the standard, though I should perhaps just have read the BIP.. Thank you anyway for your eleborate answer as well as @MCCCS (I can only mark one answer...) Aug 6 '21 at 18:32
0

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.