I'm working on a project with elliptic curve cryptography (ECC), I'm using the secp256k1 library (the one that's used in bitcoin).
My goal is to create the most compact platform-independent representation of an elliptic curve point.
Currently my encoding consists of an x
-coordinate, 256 bits wide, encoded in a big-endian form, plus the sign (oddity) bit for the y-coordinate. In order to reconstruct the point I use the curve equation to receive the value for the y^2
, and then find the square root. Though calculating square root isn't trivial, this enables to pass only a single bit for y
.
Now I'm thinking to get rid of this bit too. I realize that it's just 0.4% of the data, but for casual point (part of some bigger data set) it's usually aligned to the byte boundary, so it's practically around 3%. Anyway, I'd like to see if/how this is possible.
The idea is that for y
there's a solution for (roughly) half values of x
, so I thought about using this fact. So that if, for example, there's a solution for the encoded x
then even y
is selected. Otherwise there should be some transformation for x
, and then odd y
is selected.
Is there a way to quickly calculate the "counter-part" of x
, i.e. some unique transformation from x
which will give the quadratic residue for y
to x
which will not, and vice-versa?
x
. $\endgroup$ – valdo Jun 3 '18 at 9:11