Score:0

Example of Elliptic curve Affine compression point

pl flag

I am start learning about Elliptic curve and I read about Compression multipoint in curve which will be more efficient for saving more memory, I am looking for an example I can follow it with correct output.

Score:1
ng flag

"Compression multipoint" is not common terminology. Compressing multiple points is usually done by compressing each point one after another, using point compression. That's how I'll read the question.

For the curve $y^2\equiv x^3+a\,x+b\pmod p$ with $p=23$, $a=1$, $b=1$ of that course, a method of point compression could be to express a point as $\bigl((x\bmod p),((y\bmod p)\bmod 2)\bigr)$, which is a pair of integers with the first one in $[0,p)$ and the second either $0$ or $1$. That's compressed in the sense that a single bit is used for the second integer. E.g. point $(x,y)=(7,11)$ becomes $(7,1)$

To get back at the uncompressed form, we take $x$ (here $x=7$ from the first part of the compressed form) and use the curve's equation to compute $s\gets x^3+a\,x+b\bmod p$ (here $s=7^3+7+1\bmod23=6$), then solve for $y$ the equation $y^2\equiv s\pmod p$. We can use the method there. In our example $p\bmod4=3$ thus one solution (if there is one) must be $y=s^{(p+1)/4}\bmod p$ and (if that's not $0$) the other is $p-y$. We select the appropriate $y$ thanks to the known $y\bmod 2$ (from the second part of the compressed form), then check that indeed $y^2\bmod p=s$. Here this gives $y=6^6\bmod 23=12$ or $y=23-12=11$, we select the second one since $11\bmod2=1$, and indeed $11^2\bmod23=6$. We are back at $(x,y)=(7,11)$.

For the standardized form of point compression, see this.

Cisco Saeed avatar
pl flag
Excellent work and well explaining! So Compression point purpose is to save in memory size and not reduce the multiplication process in scalar algorithm. Right? So it's for if `y` coordinates has big size and need to reduce the size then we can use compression point! I am not sue if I am right or not?
fgrieu avatar
ng flag
@Cisco Saeed: yes this is right. Notice that the form of compression in my answer is not the rather unusual one in the [paper](https://doi.org/10.1109/TC.2007.47) for your [other question](https://crypto.stackexchange.com/q/104132/555), which compresses a pair of points (rather than one point, or two point separately), compresses less (by -33.3% rather than -49.9%), but allows a noticeably faster decompression.
Cisco Saeed avatar
pl flag
Yes I got the idea, but why in Khabbazian paper mentioned double compression can reduce the number of multiplications, what does it mean? what I understand maybe he meant that the compression of long `y coordinates` size will speed up the process which make it faster rather than reduce the number of multiplication process it self.
fgrieu avatar
ng flag
They _"reduce the required number of point doublings"_, but in their application to public key certificate that's at the cost of two or more points rather than one, thus larger size. That increase in size (their _"bandwidth"_) is mitigated by their compression, but only partially. Their compression does _"reduce the decompression cost"_ compared to the compression in the present answer, where the $s^{(p+1)/4}\bmod p$ step requires a lot of field multiplications.
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.