Discussion:
F2m curve compression
(too old to reply)
Ofek Lev
2016-12-04 02:08:30 UTC
Permalink
I understand for prime curves it is just `bytes(0x02 + flag) + bytes(x)`
where flag is the LSB of y. For the F2m curves I cannot make out how to do
it.

IEEE P1363
<http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf%20section%205.6.6.1.2>
section
5.6.6.1.2 appears to say flag is '1 if y of point > y of inverse point else
0' which I think just means `if y > x`.

these slides
<http://cs.ucsb.edu/~koc/ccs130h/projects/03-ecc-protocols/Julio_Slides.pdf>
(slide
15) by Julio Lopez and Ricardo Dahab appear to suggest my interpretation of
the IEEE method is off (I think).

http://www.secg.org/sec1-v2.pdf
<http://www.secg.org/sec1-v2.pdf%20section%202.3.3%20part%202.2.2> (which I
think is the standard reference) section 2.3.3 part 2.2.2 has yet another
notation that I do not understand.

I was told there are multiple ways. Can someone please explain the most
*standard* (or easiest) way requiring size m + 1, preferably from a
programmer's perspective? This math is beyond me :)

Any insight would be greatly appreciated.
z***@manian.org
2016-12-04 19:06:11 UTC
Permalink
It appears Ofek got the help he needed here.
https://github.com/pyca/cryptography/pull/3287
Post by Ofek Lev
I understand for prime curves it is just `bytes(0x02 + flag) + bytes(x)`
where flag is the LSB of y. For the F2m curves I cannot make out how to do
it.
IEEE P1363
<http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf%20section%205.6.6.1.2> section
5.6.6.1.2 appears to say flag is '1 if y of point > y of inverse point else
0' which I think just means `if y > x`.
these slides
<http://cs.ucsb.edu/~koc/ccs130h/projects/03-ecc-protocols/Julio_Slides.pdf> (slide
15) by Julio Lopez and Ricardo Dahab appear to suggest my interpretation of
the IEEE method is off (I think).
http://www.secg.org/sec1-v2.pdf
<http://www.secg.org/sec1-v2.pdf%20section%202.3.3%20part%202.2.2> (which
I think is the standard reference) section 2.3.3 part 2.2.2 has yet another
notation that I do not understand.
I was told there are multiple ways. Can someone please explain the most
*standard* (or easiest) way requiring size m + 1, preferably from a
programmer's perspective? This math is beyond me :)
Any insight would be greatly appreciated.
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
lvh
2016-12-04 21:04:48 UTC
Permalink
Hi,
Post by z***@manian.org
It appears Ofek got the help he needed here.
https://github.com/pyca/cryptography/pull/3287 <https://github.com/pyca/cryptography/pull/3287>
I’m responsible for that (hopefully not too terrible given the use case) explanation. The SECG document just has the high-level description in terms of Z=Y/X, but doesn’t seem to mention Frobenius, trace or half-trace in that section. (I haven’t read the rest of the document to see if they eventually do; I’m currently traveling but will be skimming that later. A quick search seems to suggest the string Frobenius does not occur in that document.)

If anyone has any good documentation for how you actually _implement_ that (in code, not just the mathematical derivation), I’d be much obliged; even if it’s only a way to check my work. OpenSSL has an implementation but it’s very OpenSSL so perhaps not the best for instruction; looks like Golang only implements P-x curves, and not the SECG F2^m curves. (I found a Golang implementation on GitHub, but I’m less likely to trust it than the Golang stdlib, and it didn’t implement point compression.)

On a related note: how bad would it be to have a “default” compression for these curves? My understanding is that there are a few options, and while I’ve never seen anything but the SECG method for the SECG curves, I don’t know if the other compression methods are often used in the wild for these or other F2^m curves.

lvh
Post by z***@manian.org
I understand for prime curves it is just `bytes(0x02 + flag) + bytes(x)` where flag is the LSB of y. For the F2m curves I cannot make out how to do it.
IEEE P1363 <http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf%20section%205.6.6.1.2> section 5.6.6.1.2 appears to say flag is '1 if y of point > y of inverse point else 0' which I think just means `if y > x`.
these slides <http://cs.ucsb.edu/~koc/ccs130h/projects/03-ecc-protocols/Julio_Slides.pdf> (slide 15) by Julio Lopez and Ricardo Dahab appear to suggest my interpretation of the IEEE method is off (I think).
http://www.secg.org/sec1-v2.pdf <http://www.secg.org/sec1-v2.pdf%20section%202.3.3%20part%202.2.2> (which I think is the standard reference) section 2.3.3 part 2.2.2 has yet another notation that I do not understand.
I was told there are multiple ways. Can someone please explain the most *standard* (or easiest) way requiring size m + 1, preferably from a programmer's perspective? This math is beyond me :)
Any insight would be greatly appreciated.
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Loading...