1
$\begingroup$

Are all doubled points on an elliptic curve even, meaning if you compress the point, it will have '02' plus the $x$ coordinate? If not, what distinguishes a doubled point from a point resulting from point addition?

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to Cryptography.se Not a clear question! 02 prefix is for compression in Secp256k1 for even $y$. Are you asking P+P is different from 2P? $\endgroup$
    – kelalaka
    Dec 9, 2023 at 21:13

1 Answer 1

1
$\begingroup$

Are all doubled points on an elliptic curve even, meaning if you compress the point, it will have '02' plus the $x$ coordinate?

No.

Assume an elliptic curve group of prime order $n$ on a prime field $\mathbb F_p$, such as secp256k1 or secp256r1, and consider points other than the point at infinity $\mathcal O$. Being "even" in the question's sense is a characteristic of the $y$ coordinate of the point after reduction modulo the prime $p$ to range $[0,p)$. If that $y$ is even (resp. odd), the first byte in compressed form is conventionally '02' (resp. '03').

And being a "doubled point" is not a characteristic of the point, but only of how the point was obtained. Every point $P$ of the curve can be obtained by doubling another point $Q$. We can compute this point as $Q=\displaystyle\frac{n+1}2\times P$. This is equivalent to $P=2\times Q$.

We can't tell from a point if it was obtained by doubling or not, much like we can't tell if $6$ was obtained as $2\times3$ or $5+1$. And that analogy is not limited to even numbers, it also works for e.g. $5\pmod{11}$: we can't tell if $5$ is obtained as $(2\times8)\bmod11=5$ or as $(4+1)\bmod 11=5$.


There is another characteristic of a point $P$ that could be even or odd: it's corresponding private key $k$ in range $[0,n)$, that is the smallest non-negative $k$ with $P=k\times G$. However, for secure elliptic curves, there is no known practical way to tell if $k$ is even or odd from the coordinates of a random $P$. We could turn an hypothetical method doing that into a way to find any private key from the matching public key.

$\endgroup$
2
  • $\begingroup$ What about if it was possible to obtain the slope from the public key points by the way is it possible given the public key point (x,y). Can derive the slope and then test the slope by inserting it into either the formula for deriving the x through point addition or deriving the x through point doubling like s² - 2x or s²-Gx--Qx which ever gives you the corresponding x tells you how x was formed and i already know how to half and subtract a point to get me the x's of before that we will be testing the slope with i just need to know if it's possible to find the slope $\endgroup$
    – Dev Tenji
    Dec 10, 2023 at 8:16
  • $\begingroup$ @DevTenji: It's easy to get the slope of the curve at a point of the curve from the coordinates of the point, as $\lambda\equiv\frac{3x^2+a}{2y}\pmod p$ (remembering that the operations are in the base field $\mathbb F_p$, thus division is multiplication by the modular inverse). That formula is here (§2.2.1, case 5). But no that can't help to tell if $x$ or the point was formed by point doubling or point addition (again, since that's not something that depends on the point, but on how the point was obtained). $\endgroup$
    – fgrieu
    Dec 10, 2023 at 9:55

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.