3

This is a paragraph from Andreas' book on compressed/uncompressed public keys.

Chapter 4 - Section - Key Formats

Whereas uncompressed public keys have a prefix of 04 ,compressed public keys start with either a 02 or a 03 prefix. Let’s look at why there are two possible prefixes: because the left side of the equation is y^2 , that means the solution for y is a square root, which can have a positive or negative value. Visually, this means that the resulting y coordinate can be above the x-axis or below the x-axis. As you can see from the graph of the elliptic curve in Figure 4-2, the curve is symmetric, meaning it is reflected like a mirror by the x-axis. So, while we can omit the y coordinate we have to store the sign of y (positive or negative), or in other words, we have to remember if it was above or below the x-axis because each of those options represents a different point and a different public key. When calculating the elliptic curve in binary arithmetic on the finite field of prime order p, the y coordinate is either even or odd, which corresponds to the positive/negative sign as explained earlier. Therefore, to distinguish between the two possible values of y, we store a compressed public key with the prefix 02 if the y is even, and 03 if it is odd, allowing the software to correctly deduce the y coordinate from the x coordinate and uncompress the public key to the full coordinates of the point. Public key compression is illustrated in Figure 4-7

What I don't get is that bold text.

Why an even or odd y coordinate corresponds to the positive / negative sign?

For example, are all even public keys below the x-axis?

Improve this question

2 Answers 2

Reset to default
13

There is no such thing as a negative or a positive value when you're talking in a finite field.

For example, in Z7, the field of integers modulo 7. There holds:

  • 0 = 7 = 14 = -7
  • 1 = 8 = 15 = -6
  • 2 = 9 = 16 = -5
  • ...

So you can't say that the number 2 is positive, because it's equal to -5.

Despite that, the square root still has two solutions. For example, 3^2 = 9 = 2, 4^2 = 16 = 2. Thus both 3 and 4 are square roots of 2.

So we need a way to say which solution we want. Turns out, that when reduced to a range of 0-6, the two solutions of the square, one is odd and the other is even.

Improve this answer
5
  • 2
    +1 for clarifying that pos & neg are not meaningful in modulo fields
    – Richard
    Dec 7, 2015 at 1:38
  • @Pieter Wuille, i am getting confused with the powers of 2s. I tried the exercise with y² mod p = (x³ + 7) mod p , for p = 5, x = 3, i get 2 solutions as you explained, and it happens that you can find the odd/even solution (2² mod 5 = 3² mod 5) for y². I had to force this to come up with 2 and 3 as square roots of 4 although it makes sense as the real roots are2 and -2, and -2 mod 5 = 3. What if x=4? We get 1² mod 5 and ... 2.44948974² mod 5. A fractional number can't be odd or even.
    – Souza
    Feb 15, 2018 at 13:39
  • 1
    Square root here does not refer to the classical real square root. It refers to the inverse function of x^2 mod p. So we say y is the square root of x mod p iff y^2 mod p = x.
    – Pieter Wuille
    Feb 15, 2018 at 16:05
  • @PieterWuille i got it now!!! Thank you. Sorry for my misconception. Lastly, why does one need to know if s*2>N at: is_high_s = s*2 > N and v = 27 + ((y % 2) ^ (1 if is_high_s else 0)) ?
    – Souza
    Feb 20, 2018 at 18:56
  • Because every number that has a square root has in fact two (negating a number does not change its square). Thus we need a way to convey which of the two square roots is the one meant.
    – Pieter Wuille
    Feb 20, 2018 at 19:35
3

Elliptic curves are of the form y^2 = f(x).

This means there are two roots to the equation. i.e. if we know an x there are two possible y values that satisfy the equation (y & -y). Because we are using a modulo type number field, it happens that the even and odd translate to y and -y

https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus

This confused me too, until I figured out modulo type fields are not as normal as we expect.

Improve this answer
2
  • Why not just transmit the y value instead as 2s complement.
    – Setheron
    May 15, 2016 at 14:54
  • See Pieter's answer above (very good detail). Basically a 2s complement is the modulus of the word size (in bits); so we need to use a Ns complement - where N is the modulus of the field. So a modulus of 2^n - we can use 2s complement
    – Richard
    May 17, 2016 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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