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

From: Andrey Jivsov <[email-masked]>
Date: Tue, 11 Dec 2012 12:57:14 -0800

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.

---

From: Dan Brown <[email-masked]>
Date: Wed, 12 Dec 2012 18:40:48 +0000

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: [email-masked] [mailto:[email-masked]] On Behalf Of
> Andrey Jivsov
> Sent: Tuesday, December 11, 2012 3:57 PM
> To: [email-masked]; [email-masked]
> 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.
> 
> 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
> [email-masked]
> 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.

---

From: Russ Housley <[email-masked]>
Date: Wed, 12 Dec 2012 13:43:39 -0500

Dan:

OCTET STRING was chosen to avoid the need to carry an extra byte to make the sign bit a zero.

Russ

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 12 Dec 2012 12:02:21 -0800

Hello Dan:

> 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 fi…

I believe that the same ideas I used in my proposal will carry over to 
EC(F(2^m)) curves, i.e. "binary curves", but I put emphasis on the 
proposal being a very simple spec for the ease of reference and analysis.

As a very forward-looking thought, if there is interest in similar 
proposal for binary curves, this could be another document.

> 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…

Interesting. It sheds more light on the rationale behind the SEC1 format.

I feel that the complexity of SEC1 doesn't compare favorably with my 
value proposition:

An ECC key in F(p) can be represented the same way as we represent an 
RSA key modulus. It's just an integer.

One might advance the simplicity even further and say that there is no 
compressed or uncompressed point: there is the compact definition that I 
proposed.

This is simple and elegant.

> 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 interoperabil…

My thought was about applications that need to pack lots of ECC points 
together. For example, a blob with millions of public keys. It helps 
that the indexing is an efficient bit shift of the offset to get an 
index and there there is no space wasted on a byte that carries only one 
bit.

> 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 AS…

( One can put an integer that is less than 2^256 into a 256 bit octet 
string by zero-padding it. )

My format will be able to be encoded as an OCTET STRING, BIT STRING, or 
INTEGER. So, the higher level encodings are free to select the optimal 
encoding.

> 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…

Let's analyze this by comparison with the encoding of an RSA key modulus 
(or P,Q,G of DSA parameters). Does the encoding that packages together 
the integers (such as ASN.1+DER) requires a leading zero? Well, then I 
will respectfully note that this is an unfortunate design decision 
because overwhelmingly all crypto protocol rely on positive integers. If 
an RSA modulus encoding will need a leading zero, so will the ECC 
compact point. In any case, I would argue for a modular design in which 
an ECC point format shall not attempt  to remedy any issue with 
higher-level encodings (because it will inevitably bring some overhead). 
I am simply bringing the ECC encoding within the pack of currently used 
algorithms.

Just as for an RSA modulus, one can try to generate keys so that they 
don't have the high bit set, but I am not proposing that in general.

Note, however, that there is an interesting option that my proposal 
introduced. There are applications that involve keys being read/typed by 
humans, where the key size is important. In this case one can generate 
an ECC key with some number of highest bits being zero. The method is 
also of value for P-521 keys that can be represented under 2^512. My 
format will mean that the final key will get shorter ("it is just an 
integer"). I believe that SEC1 will encode it as 03 00 00 00 ... FF, 
where FF is the most significant byte of the x. (Am I correct that SEC1 
doesn't allow 03 FF encoding in my example?).

Thank you.