From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Andrey Jivsov <openpgp@brainhub.org>
Thread-Topic: [Cfrg] [saag] A proposal for compact representation of an
 elliptic curve point (ECC point compression)
Thread-Index: AQHN2HN1n0mZdiOeF06/Mfx4iUhUp5gVYE2ggACJ5oD//6zskA==
Date: Wed, 12 Dec 2012 20:10:53 +0000
Message-ID: <A113ACFD9DF8B04F96395BDEACB340421E69E4@xmb-rcd-x04.cisco.com>
References: <E1TiZ2u-0004cU-P0@login01.fos.auckland.ac.nz>
 <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com>
 <A113ACFD9DF8B04F96395BDEACB340421E67CA@xmb-rcd-x04.cisco.com>
 <50C8D4D1.8050805@brainhub.org>
In-Reply-To: <50C8D4D1.8050805@brainhub.org>
Accept-Language: en-US
Content-Language: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Cc: Peter Gutmann <pgut001@cs.auckland.ac.nz>, "cfrg@irtf.org" <cfrg@irtf.org>,
 "saag@ietf.org" <saag@ietf.org>
Subject: Re: [Cfrg] [saag] A proposal for compact representation of an
 elliptic curve point (ECC point compression)
Precedence: list

> -----Original Message-----
> From: Andrey Jivsov [mailto:openpgp@brainhub.org]
> Sent: Wednesday, December 12, 2012 2:03 PM
> To: Scott Fluhrer (sfluhrer)
> Cc: Rene Struik; cfrg@irtf.org; saag@ietf.org; Peter Gutmann
> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an
> elliptic curve point (ECC point compression)
>=20
> I have the same comment as Scott, but I am not sure exactly what Rene
> means.
>=20
> I will assume that Rene says that because there are two y for each x, one=
 can
> calculate the corresponding y or p-y and choose one at random.
>=20
> The format I proposed indeed fits very well with the feature of the ECDH-
> based  protocol that Scott refers to (which covers ECC encryption and key
> agreement). As the draft shows, one simply drops the y coordinate to obta=
in
> the compact representation, while there are no extra steps for ECDH key
> generation (because ECDH keys are not sensitive to maintaining the "right=
"
> y).
>=20
> The extra key generation step is only needed for ECDSA keys.

Actually, as Rene pointed out to me privately, it isn't much more for ECDSA=
, at least with the standard algorithm.

The ECDSA verification is a check whether r =3D (uG + vQ)_x, where Q is the=
 public key.  If you are given only the x coordinate of Q, what you do is t=
o pick a corresponding y coordinate (so you get a point S where either S=3D=
Q or S=3D-Q, where Q is the original public key), and check if one of these=
 two holds:

r =3D (uG + vS)_x
r =3D (uG - vS)_x

If either does, the signature verifies.  This adds the cost of a single poi=
nt addition (and the cost of generating the y coordinate of S); fairly smal=
l.

>=20
> On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote:
> >
> >
> >> -----Original Message-----
> >> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf
> >> Of Rene Struik
> >> Sent: Wednesday, December 12, 2012 9:17 AM
> >> To: Andrey Jivsov
> >> Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann
> >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of
> >> an elliptic curve point (ECC point compression)
> >>
> >> Hi Andrey:
> >>
> >> One can already implement the x-coordinate only representation of an
> >> elliptic curve point simply by converting the affine representation
> >> into compressed representation and randomizing the compression "bit".
> >> The reverse operation then yields the point or its inverse (which
> >> have the same x-coordinate).
> >>
> >> To my knowledge, this does not require any changes to data formatting
> >> (nor additional bytes).
> >
> > That randomization of the y-component works fine for ECDH (at least, if
> you use only the x-component of the shared secret); however, it doesn't
> work for ECDSA public keys.
> >
> >>
> >> Best regards,
> >>
> >> Rene
> >>
> >> On 12/11/2012 6:37 PM, Andrey Jivsov wrote:
> >>> On 12/11/2012 03:15 PM, Peter Gutmann wrote:
> >>>> Andrey Jivsov <openpgp@brainhub.org> writes:
> >>>>
> >>>>> I thought that it would be useful for the Internet community to
> >>>>> have an IETF document that describes how to encode an ECC point.
> >>>>
> >>>> Maybe I'm missing something here, but wouldn't this just consist of:
> >>>>
> >>>> -- Snip --
> >>>>
> >>>> See [1].
> >>>>
> >>>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services
> >>>> Industry:
> >>>> The Elliptic Curve Digital Signature Standard (ECDSA)", November,
> 2005.
> >>>>
> >>>> -- Snip --
> >>>>
> >>>> That's what every existing RFC that uses ECC seems to be using.
> >>>>
> >>>> Peter.
> >>>>
> >>>
> >>> Hello Peter.
> >>>
> >>> "X9.62-2005" in the search engine lends me on a page that asks for
> >>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1]
> >>> is more popular as a reference (assuming they are identical
> >>> regarding the point compression method).
> >>>
> >>> I claim that what I submitted is better in many respects than SEC1.
> >>>
> >>> Let me expand on one of the benefits not covered in the spec. It's
> >>> very likely that an employee of a commercial company thinking about
> >>> using [SEC1] compression with any ECC method would get an order from
> >>> the legal department to stay away from compression. The fact that
> >>> somebody on the Internet posted something to the contrary has little
> >>> weight for them. My contribution is an attempt towards a compact
> >>> representation that is actually usable in practice. It's the most
> >>> direct extension to the 1985 idea by [Miller] (see my document for
> >>> details).
> >>>
> >>> Thank you.
> >>>
> >>> _______________________________________________
> >>> saag mailing list
> >>> saag@ietf.org
> >>> https://www.ietf.org/mailman/listinfo/saag
> >>
> >>
> >> --
> >> email: rstruik.ext@gmail.com | Skype: rstruik
> >> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
> >>
> >> _______________________________________________
> >> Cfrg mailing list
> >> Cfrg@irtf.org
> >> http://www.irtf.org/mailman/listinfo/cfrg