Join Log in
Score:0
mrbrainlet avatar Crypto

Elliptic Curve Key Compression

in flag
mrbrainlet

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?

75
0 + 0
Score:2
poncho avatar Crypto
my flag
poncho

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)

0 + 0
fgrieu avatar
ng flag
fgrieu
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.