0
$\begingroup$

How to determine if an elliptic point $kG$ is negative? Is $k<0?$

By example, for $k=1234$, the coordinate of the point $1234G$ using secp256k1 = $X= 102884003323827292915668239759940053105992008087520207150474896054185180420338$ $Y= 49384988101491619794462775601349526588349137780292274540231125201115197157452$

Note: $1234 = 0x4D2 = 0b10011010010$

The coordinate of a negative point is equal to (x, -y).

So, $-1234G =$

$(102884003323827292915668239759940053105992008087520207150474896054185180420338,$ $\textbf{-49384988101491619794462775601349526588349137780292274540231125201115197157452})$

We're in a field, so we apply modulo prime: $$-y \; \% \;prime = prime - y$$

So, $-1234G = $

$(102884003323827292915668239759940053105992008087520207150474896054185180420338,$ $ \textbf{prime} - 49384988101491619794462775601349526588349137780292274540231125201115197157452)$

$= (102884003323827292915668239759940053105992008087520207150474896054185180420338,$ $\textbf{66407101135824575629108209407338381264920846885348289499226458806793637514211})$

Is there a trick to known which one correspond to -1234G or 1234G or more generally kG or -kG? Notes: We don't know k. I know that to uncompress a public key, we just know x, we use a bit to say take y less than p/2 or greater than p/2 but in this case it's always a positive k.

Related to: Determine if a public key point y is negative or positive, odd or even?

$\endgroup$

1 Answer 1

4
$\begingroup$

There is no usual and well-defined meaning to "negative" for a point $P$ of an elliptic curve on a finite field, as used in cryptography. If $P=k\,G$ for negative $k$, then $P=k'\,G$ for $k'=k\bmod n$, which is non-negative (it would be $k'=k+n$ if $0<|k|<n$ ), and $n$ is the order of the group (or of $G$ )

For a given $P$, we could uniquely define $k$ as the integer with the smallest absolute value and $P=k\,G$, then consider the sign of $k$. But

  • that not usual
  • if the group is cryptographically strong, there is no efficient algorithm to determine the sign of that $k$ from an arbitrary $P$. Argument: if there was such method, it could be used as a subprogram to solve the Discrete Logarithm Problem (that is find $k$ for a given random $P$ in the group generate by $G$ ), by binary search.
$\endgroup$
0

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.