3
$\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$
3
  • $\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.
    Commented Sep 27, 2015 at 18:36
  • $\begingroup$ remon78eg.tk/curve this site shows you that any point on the curve can still hold the private key information and you can extract odd/even , mod 2 or mod 3 from the public key, try it yourself also see the video youtube.com/watch?v=iux7to1iNlw $\endgroup$
    – remon78eg
    Commented Oct 22, 2020 at 18:04
  • $\begingroup$ @remon78eg (Moderator note). The above comment originally was an answer, but it did not address the question, hence the removal. Independently, the linked material apparently requires a variation of a standard curve, e.g. secp256k1. The goal could be extraction of private key information from an implementation (e.g. BC wallet) modified without detailed code analysis, merely by changing secp256k1 parameters. That's nice, but the need to change curve parameters warrants at least a note along the links. $\endgroup$
    – fgrieu
    Commented Oct 23, 2020 at 13:39

2 Answers 2

9
$\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.

$\endgroup$
2
  • 1
    $\begingroup$ Bitcoin does use $s<n/2$ signatures, but r,s in an ECDSA signature are not a point or even elements of $F_p$ like point coordinates, they are nonzero elements of $Z_n^+$ one of which, r, is derived from an x-coordinate. $\endgroup$ Commented Oct 23, 2020 at 4:15
  • $\begingroup$ It's worth noting that the choice may depend on representation of the field elements. Most of the time, prime field elements are represented as non-negative integers from 0 to $p-1$, but one may use an alternate representation like: integers from $-(p-1)/2$ to $(p-1)/2$. With such representations, there is a natural choice for what we could call the "sign" of the element, and perhaps even a limited definition of "ordering" between elements $\endgroup$ Commented Feb 15, 2023 at 19:13
1
$\begingroup$

In finite fields there 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.

$\endgroup$
2
  • $\begingroup$ why does the LSB distinguish the two points? how come they can't have the same LSB? $\endgroup$ Commented Jul 11, 2022 at 10:30
  • $\begingroup$ @MatthewTranmer Assume a prime order field where we choose the representation $0 \le x < p$. Then $-x$ is represented as $p-x$. Since $p$ is odd, this changes parity and thus the least significant bit. (Except when $x=0$ of course) $\endgroup$ Commented Feb 15, 2023 at 22:11

Your Answer

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

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