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

Dan Brown <> Wed, 12 December 2012 18:41 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id CF5601F0CDC for <>; Wed, 12 Dec 2012 10:41:05 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -5.053
X-Spam-Status: No, score=-5.053 tagged_above=-999 required=5 tests=[AWL=0.150, BAYES_00=-2.599, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id LNC5umwAzq9C for <>; Wed, 12 Dec 2012 10:41:04 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 199C01F0CDA for <>; Wed, 12 Dec 2012 10:41:03 -0800 (PST)
X-AuditID: 0a41282f-b7fea6d000001d56-c0-50c8cfb13308
Received: from ( []) by (SBG) with SMTP id 6D.59.07510.1BFC8C05; Wed, 12 Dec 2012 12:40:49 -0600 (CST)
Received: from ( by ( with Microsoft SMTP Server (TLS) id 14.2.318.1; Wed, 12 Dec 2012 13:40:49 -0500
Received: from ([fe80::fcd6:cc6c:9e0b:25bc]) by ([::1]) with mapi id 14.02.0318.001; Wed, 12 Dec 2012 13:40:48 -0500
From: Dan Brown <>
To: 'Andrey Jivsov' <>, "" <>, "" <>
Thread-Topic: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression)
Thread-Index: AQHN1+JKYfEillVVT0CYN/ZbTZXZi5gVcVkg
Date: Wed, 12 Dec 2012 18:40:48 +0000
Message-ID: <>
References: <>
In-Reply-To: <>
Accept-Language: en-CA, en-US
Content-Language: en-US
x-originating-ip: []
Content-Type: text/plain; charset="us-ascii"
content-transfer-encoding: quoted-printable
MIME-Version: 1.0
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFrrOKsWRmVeSWpSXmKPExsXC5bjwnO7G8ycCDJZP07To/nGQyeJ11y8m iyn9nUwOzB63px9m81iy5CeTx+SNh9kCmKMaGG2SEkvKgjPT8/TtbBLz8vJLEktSFVJSi5Nt lXxS0xNzFAKKMssSkysVXDKLk3MSM3NTi5QUMlNslUyUFApyEpNTc1PzSmyVEgsKUvNSlOy4 FDCADVBZZp5Cal5yfkpmXrqtkmewv66FhamlrqGSnW5CJ0/GlOO3WAqmKlfMb3jI2MB4QKaL kYNDQsBE4kWTdhcjJ5ApJnHh3nq2LkYuDiGBVYwSs/uWM0E4Kxklbi4/C+XMYZQ42NvICNLC JqAqcf/oOWaQSSICeRL/tteBhIWBzO7La9hAbBGBfInN+9dD2UYSLbt62UFsFqDW1vlHmEBs XgE3ieX/14CNFBLQlnja/gasnlNAR+LSuyfMIDajgKzE7rPXweqZBcQlbj2ZzwRxtYDEkj3n mSFsUYmXj/+xQtiKEqtf3WKDqNeRWLD7E5StLbFs4WtmiL2CEidnPmGB2KsgceX6PpYJjOKz kKyYhaR9FpL2WUjaFzCyrGIUzM0oNjAzSM5L1ivKzNXLSy3ZxAhOKRr6Oxjfvrc4xCjAwajE wztxx4kAIdbEsuLK3EOMEhzMSiK8bgeAQrwpiZVVqUX58UWlOanFhxhdgSE0kVmKOzkfmO7y SuKNDQxwc5TEeZWZDwYICaQDk1V2ampBahHMHCYOTpA9XFIixcCUk1qUWFqSEQ9KjPHFwNQo 1cCY8tIgWk3/1eqLvz8kbDmXdsF1r+2Lk2cvZ7RZHmN3OfegwUf2U2fs1n9L1nbM4b7PL2vc sEFhcsBFhgu9Dsfzu3qCHy32O2fgaVvx66I5h8fL8jSTx15pRl9THDy/3/q2KsSAb6Zs2DfO sDvmxxrffFh+NHe9ypyVHgof/WIm85yYmzxN4dMvJZbijERDLeai4kQA4ER++WoDAAA=
Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression)
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 12 Dec 2012 18:41:05 -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: [] On Behalf Of
> Andrey Jivsov
> Sent: Tuesday, December 11, 2012 3:57 PM
> To:;
> 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

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.