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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\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$
4
  • 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
    Commented Apr 19, 2015 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
    Commented Apr 20, 2015 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
    Commented Apr 20, 2015 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
    Commented Feb 18, 2020 at 22:29
2
$\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 and acknowledge you have read our privacy policy.

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