4
$\begingroup$

Take an elliptic curve cryptography public key (x, y) and its additive inverse (x, -y). How do you identify which is the positive point and which is the negative point?

Examples:

Private key 1 -> (x, y)

x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798L

y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

-y = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777L

Private key 2 -> (x, y)

x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5L

y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52aL

-y = 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705L

Private key 3 -> (x, y)

x = 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9L

y = 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672L

-y = 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bdL

Also, how can you identify which public key is odd and which is even?

For example: private key 1 x,y is odd, private key 2 x,y is even (based with pub key).


$\endgroup$
  • $\begingroup$ Unlike the ordinary integers, there's no notion of "positive" or "negative" points on an elliptic curve. So asking which of (x,y) and (x,-y) is the negative point is not relevant. The same for even and odd. $\endgroup$ – K.G. Sep 27 '15 at 18:36
5
$\begingroup$

Elements of finite fields don't really have a sign. But depending on context you can define a property that's different for $x$ and $-x$ (when $x$ is not $0$) and call that property sign.

Some possible choices:

  • A number is called a square (or Quadratic residue) if there is another number which produces it when squared. Since positive real numbers are squares, identifying square field elements with a positive sign is a natural choice.

    The Legendre symbol is 0 for 0, +1 for squares and -1 for non-squares. The Legendre symbol of the product of two numbers is the product of the two Legendre symbols, which mirrors how signs behave under multiplication.

    You can even define $i = \sqrt{-1}$ to get some kind of complex numbers. Imaginary values of the $y$ coordinate of an elliptic curve correspond to its twist.

  • You can use the least significant bit. Computing this is very cheap, you only need to look at that one bit. This approach is often used to store the "sign" of a compressed elliptic curve coordinate.

  • Values smaller than $p/2$ have one sign, values greater than $p/2$ the other. I believe Bitcoin uses this convention to define canonical signatures.

You can extend any of these definitions from the underlying field to the elliptic curve defined over that field by defining the sign of the point as the sign of its $y$ coordinate.

| improve this answer | |
$\endgroup$
0
$\begingroup$

In finite fields there are is no distinction between positive and negative numbers. This implies that you also do not have positive or negative points in an elliptic curve over a finite field. But you can nevertheless distinguish the two points by looking at the least significant bit. For instance, this will be used by the point compression method.

| improve this answer | |
$\endgroup$

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.