0
$\begingroup$

I have an elliptic curve y2 = x3 -x + 3 over a finite field of 127. I am trying to compress a point using the X9.62 standard. I know for the key compression you are supposed to check if the y value is even or odd to determine which side of the curve it is on. For most points on the curve the upper point is even and the lower point is odd. However, for the pair (16, 20) and (16, 107) and a few others, the lower point is even and the upper point is odd.

Does this mean that you can't use key compression on this specific curve or is there another way to do it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I know for the key compression you are supposed to check if the y value is even or odd to determine which side of the curve it is on.

To be more precise, you determine whether $y$ is even or odd so that you can give enough of a hint for the decompression to know which $y$ value to reconstruct.

For any value of $x$, there are (at most) two values for $y$ that satisfies the the curve equation (which is, in your case, $y^2 = x^3 - x + 3$). And, it turns out that (for odd characteristic fields, which this is) one of the two solutions for $y$ will be even, and one will be odd - hence, just stating whether $y$ is even or odd is enough information for the decompressor to know which one was meant.

For most points on the curve the upper point is even and the lower point is odd

Whether the curve is on the "upper half" (which, I suppose means $y > p/2$) or the "lower half" is irrelevant; we use the lsbit, no matter what the magnitude of $y$ happens to be.

Now, one could define an alternative compression algorithm that relied on whether $y > p/2$, rather than the lsbit of $y$. After all, in a prime field, one of the solutions will have $y > p/2$ and the other will have $y < p/2$. However, that's not what people actually do (one possible reason is because it's easier to test a single bit than to do a comparison on the full value)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Addition: to determine if $x\pmod p$ is even or odd, we find integer $a$ in range $[0,p)$ with $a\equiv x\pmod p$, that is $a$ computed as $a\gets x\bmod p$, and test if $a$ is even or odd. For example, $129\pmod{127}$ is even, because $2\equiv129\pmod{127}$, and $0\le2<127$, and $2$ is even. Also $-2\pmod{127}$ is odd, because $125\equiv-2\pmod{127}$, and $0\le125<127$, and $125$ is odd. $\endgroup$
    – fgrieu ♦
    Commented Sep 11, 2021 at 10:57

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.