4
$\begingroup$

I am working with a library that outputs EC points in uncompressed form. To save space, I'm considering modifying said library to use compressed EC points. Assuming that I keep track of the sign bit prior to compression, is there any risk in compressing said point?

I read this Q and related answer, but want to ensure that I may not be opening the door for other issues.

$\endgroup$
2
$\begingroup$

You will need a quadratic non-residue in order to decompress the points, and
there is no known deterministic algorithm that will provably find one efficiently.
Also, if you allow both sign bits for $\: y=0 \:$ or the point-at-infinity,
then you will lose non-malleability and strong unforgeability.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Huh? To decompress a point, you need to compute a modular square-root. If $p \equiv 3 \pmod 4$, that's easy to do. If one were to work in a prime field with $p \equiv 1 \pmod 4$, then, yes, it's a bit more difficult, and you will need to find a quadratic nonresidue (which isn't that complicated -- pick random points until you find one works); however we generally work in fields with characteristic 3 mod 4. $\endgroup$ – poncho Apr 19 '15 at 2:12
  • $\begingroup$ @poncho Curve25519 has $p \equiv 5 \pmod 8$. P-224 has $p \equiv 1 \pmod 4$. But there are efficient algorithms for computer square-roots in both of those fields. $\endgroup$ – CodesInChaos Apr 20 '15 at 18:42
  • 1
    $\begingroup$ @CodesInChaos: actually, there's a deterministic solution in that case as well; it's a tad more complex than the 3 mod 4 solution, but still works. What's tougher is the 1 mod 8 case... $\endgroup$ – poncho Apr 20 '15 at 18:47
  • $\begingroup$ Cipolla-Lehmer modular square root works for all prime moduli and is easier to implement compared to Shanks-Tonelli. en.wikipedia.org/wiki/Cipolla%27s_algorithm $\endgroup$ – Pierre Feb 18 at 22:29
1
$\begingroup$

I would argue the opposite: it's safer to compress a point.

The reason is fairly simple. During decompression- whose most expensive operation is a modular square root - your are guaranteeing that the resulting point either is on the curve, zero or infinity.

One of the most frequent errors in elliptic curve operations is failing to properly validate a point before operating on it. The most public example of this is the Bluetooth pairing vulnerability - which, had it used compressed points, would not have been vulnerable to MITM attacks.

While validation is less expensive than decompression - it's one of those "seemingly optional" steps that people can forget to do. With compressed points there's no option.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.