Public keys in the form of 04[x,y] can be compressed since the x axis is symmetrical. Hence we only need the x-coordinate with the 02/03 prefix which states if Y is odd or even. I don't understand the latter, are odd/even on an elliptic curve the same as pos/neg on a Cartesian plain? This makes sense since negative integers can't be expressed in keys. So would the 'negative' Y-coordinate correspond to an 'odd' (03 prefix). If so, how are these coordinates differ in odd/even if the x axis is symmetrical?
1 Answer
Yes and no.
The X and Y coordinates of points on the secp256k1 curve are integers modulo p = 2256 - 232 - 977. Positive/negative don't exist there, as modulo p it holds for every a that -a = p-a.
So, we need another criterion to distinguish the two solutions for y for the equation y2 = x3 + 7.
There are a number of possibilities:
- High/low: we could simply distinguish them based on whether they are below/above p/2. If *a < p/2, then its "negation" p-a will be > p/2. As p is odd, no point is equal to p/2 itself.
- Even/odd: what the standard picked is looking at the parity of a when brough to range [0, p). Because p is odd, negating any number except 0 will change its parity. And it can be shown that no solutions for y=0 exist.
- A third possibility is using quadratic residuosity as a tie-breaker. It turns out that of the two solutions for y, one will always be a square modulo p, and the other won't be. This is perhaps most similar to solutions in the real numbers and their sign: the postive numbers in R, just like the quadratic residues mod p, have a square root - and their negations don't.
So yes, it is somewhat like positive/negative for real solutions, but that "somewhat" is just a property that is true for half the domain, and which is complemented when negating the coordinate.
-
Thanks Pieter! To fully digest that i will need to learn some more EC arithmetic. Also, how does the modulo function work here? So are the number of possible points on secp256k1 the remainder of y^2 = x^3 + 7 divided by p = a large proven prime less than 2^256? Jun 11, 2021 at 6:24
-
1The curve consists of all points (x,y) for which y^2 = x^3 + 7 (mod p), or in other words: y^2 - x^3 - 7 is a multiple of p. And yes, p = 2^256 - 2^32 - 977 is a prime number. Jun 11, 2021 at 6:30
-
1The number of points satisfying such an equation was an unsolved problem for a long time, but since 1985 a reasonably efficient algorithm exists: en.wikipedia.org/wiki/Schoof%27s_algorithm (warning: not easy). Without this, elliptic curve cryptography wouldn't be possible. Jun 11, 2021 at 6:36
-