Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression)

Hi Andrey,

Some quibbles.

The SEC1 EC point format profiles the ANSI X9.62 and IEEE 1363 formats.

My belief is that octet strings, rather than integers, were chosen (long before I was involved) for these formats because (at least partly, and perhaps mainly) these standards also allowed other finite fields (binary and odd characteristic extension fields), which are not naturally represented by integers.  

The SEC1 format also has the property of being a prefix-free encoding (for a given elliptic curve), which I think was intentional.  My limited understanding of networking theory is that prefix-free encoding helps to avoid misinterpretations of streams.  Well, at least DER encoding of ASN.1 seems (to me) to be prefix-free.  Certainly, the SEC1 format prefix-free property is redundant when inside an ASN.1 wrapper, but otherwise, if used outside of ASN.1, the prefix-free property of SEC1 may be a little helpful.

Your ID mentions power-of-two byte alignment.  I understand alignment to be quite important for storage, but how important is it for networking?  (Octet string formats help networking interoperability; for local storage, an implementation can really use any format.)  

Because your format specifies integers, it can fit into an ASN.1 type.  The current ASN.1 types for ECC public keys (and generators in domain parameters) expect ASN.1 octet string types.   These ASN.1 ECC public key formats would need to be changed.

Some formats use two's complement, which assumes signed integers.  I think that BER and DER use it for integers.  This forces a sign bit, which could add a byte.  Section 6 of your ID says a P-256 point will never exceed 32 bytes, but it might need an extra byte if DER encoded.  (Please correct me if I am wrong, which is likely, since I am not an ASN.1 expert.)  The extra sign byte would have value zero, which slightly conflicts with the SEC1 format for the point-at-infinity.  Also, since DER encodings are variable length, the power-of-two alignment might suffer.

Best regards,

Daniel Brown
Research In Motion Limited

> -----Original Message-----
> From: saag-bounces@ietf.org [mailto:saag-bounces@ietf.org] On Behalf Of
> Andrey Jivsov
> Sent: Tuesday, December 11, 2012 3:57 PM
> To: saag@ietf.org; cfrg@irtf.org
> Subject: [saag] A proposal for compact representation of an elliptic
> curve point (ECC point compression)
> 
> Greetings.
> 
> 
> I thought that it would be useful for the Internet community to have an
> IETF document that describes how to encode an ECC point. I will focus
> on the elliptic curves over the prime fields here.
> 
> http://datatracker.ietf.org/doc/draft-jivsov-ecc-compact
> 
> 
> Cryptographic protocols defined in IETF most often work with large
> integers, such as the modulus of an RSA key, which they encode with
> some applicable protocol-specific method.
> 
> Unfortunately, the default representation of an ECC point is not just a
> "large integer". It is either a pair of integers of x,y, or x with
> optional information about y. Additional metadata tagged to x,y is
> common. The encoding of an ECC point needs further definition, plus the
> additional complexity is present due to the decisions to make ECC point
> compression optional (I suspect on the ground of IPR concerns).
> 
> In the ideal world the situation would be the following: there is an
> RFC for ECC point definition; it uses compact representation; the
> representation is just a large integer; it's free of patents; secure;
> and that's the default mandatory method in every IETF standard.
> 
> I am proposing here a format that in my opinion comes the closest to
> the ideal features outlined above. Getting to the ideal world is
> another story, but the first step on this journey is a working method
> that I am pleased to present here. At the very least, the new protocols
> can take advantage of the proposal; otherwise the new submissions will
> likely to gravitate towards the SEC1 format, at least on the practical
> grounds because the SEC1 is the only popular format that is searchable
> and publicly available. I would like to offer an alternative / useful
> point of reference to future standards.
> 
> Thank you.
> 
> _______________________________________________
> saag mailing list
> saag@ietf.org
> https://www.ietf.org/mailman/listinfo/saag

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.