1

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?

7

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.

  • 1
    +1 for clarifying that pos & neg are not meaningful in modulo fields – Richard Dec 7 '15 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 . 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 '18 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 '18 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 '18 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 '18 at 19:35
2

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.

  • Why not just transmit the y value instead as 2s complement. – Setheron May 15 '16 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 '16 at 0:47

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.