1

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

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.

4
  • 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? – Matt Tainsh Jun 11 at 6:24
  • 1
    The 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. – Pieter Wuille Jun 11 at 6:30
  • 1
    The 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. – Pieter Wuille Jun 11 at 6:36
  • Fascinating, thanks again! – Matt Tainsh Jun 11 at 7:20

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.