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

> -----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)
> 
> I have the same comment as Scott, but I am not sure exactly what Rene
> means.
> 
> 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.
> 
> 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 obtain
> the compact representation, while there are no extra steps for ECDH key
> generation (because ECDH keys are not sensitive to maintaining the "right"
> y).
> 
> 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 = (uG + vQ)_x, where Q is the public key.  If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds:

r = (uG + vS)_x
r = (uG - vS)_x

If either does, the signature verifies.  This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small.

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