0

I have a library that stores all its ECC Field Elements in uncompressed form, in a bloated Base64 XML format, and storage has become a concern. (We want to support QR code as a form factor,etc)

Rather than ask the crypto library authors to support compressed points in ECC (I don't know how difficult this would be) I think it may be possible to have a piece software proxy capture these elements inline, compress them (with a sign bit), and decompress them when deserializing

My goal is to make the library not even know that I used compressed ECC for temporary, in-transit storage.

Is this a viable approach? What other things should I consider prior to doing this?

For reference I plan on using this code in Bouncy Castle

    public override byte[] GetEncoded(bool compressed)
    {
        if (this.IsInfinity)
        {
            return new byte[1];
        }

        ECPoint normed = Normalize();

        byte[] X = normed.XCoord.GetEncoded();

        if (compressed)
        {
            byte[] PO = new byte[X.Length + 1];
            PO[0] = (byte)(normed.CompressionYTilde ? 0x03 : 0x02);
            Array.Copy(X, 0, PO, 1, X.Length);
            return PO;
        }

        byte[] Y = normed.YCoord.GetEncoded();

        {
            byte[] PO = new byte[X.Length + Y.Length + 1];
            PO[0] = 0x04;
            Array.Copy(X, 0, PO, 1, X.Length);
            Array.Copy(Y, 0, PO, X.Length + 1, Y.Length);
            return PO;
        }
    }
2

Point compression does not lose information; that's the point.

Technical details: suppose we are working in field Zp for a big prime p. The curve equation is:

Y2 = X3 + aX + b

for two constants a and b which define the curve. For a point (X,Y) on the curve, you can use the equation to recover Y2 from X alone. Since we are working in a field, Y2 can have at most two square roots, and they are opposite to each other (that's Y and -Y). Since p is a big prime, it is odd, so Y and -Y always differ in their least significant bit, except if Y = 0, in which case -Y = 0 too. Therefore, knowledge of X and the least significant bit of Y is always sufficient to unambiguously recover Y, at which point you have the full point.

(Moreover, you normally choose your curve so that it has a prime order, which indirectly implies that there can be no point on the curve such that Y = 0. But even if there is such a point, then compression still works.)

A similar mechanism works for binary curves (when the field is GF(2m) for some integer m) but it is slightly more complex to explain (it involves computing half-traces).


Be wary, when uncompressing, to make sure that you get a valid point. If the computation yields a value "Y2" which is not actually a square in Zp, then decompression will fail, but some square root functions won't notice it. Unwanted behaviour on abnormal data is a classic source of security weaknesses; such is the subtlety of practical crypto.


There are some rumours that point compression would still be covered by some patents, which explains why opensource library developers don't rush to implement it. Whether the rumour is true, though, is another story. This Wikipedia page lists two patents, one from Certicom (but it is about binary curves in GF(2m) only, and it is due to expire on July 29th, just five days from now), and another from HP (that one purports to cover point compression in general, but half of it concentrates on binary curves).

I think the HP patent would not go far in court, in particular since it was filed in 1998, at which time the concept of point compression had already been published far and wide. I am not a patent lawyer, though (I am a bear with a fake name).

3
  • (love the answer, esp the INAL part) Crazy question, in crypto, does negative zero exist? Jul 24 '14 at 23:17
  • Usually, in crypto, we use finite groups and rings and fields, where there is no notion of negative at all, since there is no natural ordering of elements (you cannot have a "less than" relationship compatible with the group law on a finite group).
    – Tom Leek
    Jul 24 '14 at 23:21
  • "You cannot have a 'less than' relationship compatible with the group law on a" non-trivial finite group.
    – user49075
    Jul 25 '14 at 4:03

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.