Moving forward with Curve25519

[Andrey Jivsov]

On 08/05/2014 04:01 AM, Werner Koch wrote:
> On Fri, 20 Jun 2014 15:28, gniibe at fsij.org said:
>
>> For Montgomery curve, it doesn't compute y-coordinate, and the
>> representation in my current implementation is:
>>
>> 	04 || X || ZERO
>
> I would suggest to use
>
>          41 || X
>
> and we are done.  Simon's draft-josefsson-tls-curve25519-05 for TLS does
> the same.
>
> 0x41 is not used by SEC1 but it is quite similar to it.  A nice property
> of the prefix bytes is that they avoid misintrepretation as a negative
> value and are thus compatible to OpenPGP MPIs.  Thus my suggestion is to
> define these prefix bytes:
>
>          40 := Native point format of the curve follows
>          41 := Only X coordinate follows.
>          42 := Only Y coordinate follows.

For all protocols that I know, including OpenPGP, the Y coordinate is 
not used in the calculation of the shared secret in ECDH. This is 
especially true for Curve25519 ECDH, which uses Montgomery curve in the 
original paper, given that the Montgomery formulas don't even compute Y. 
To compute the Y one needs to move an X into an isogenous curve, such as 
EC25519, and use Edwards formulas there. You typically need Y if you 
depend on the exact sign of the point, which is needed when you add 
points, but ECDH doesn't do point additions.

Assuming that there is no interest here to represent Curve25519 point 
used for encryption with anything but a point on the Montgomery curve, 
in the original representation, sending anything but X for ECDH is a 
(small) waste of space and the need to commit to yet another tag.

X has aesthetically pleasing 32 byte size. X is an integer, which fits 
perfectly into the OpenPGP container, which is an MPI.

I think that OpenPGP should adopt X as the format for the ECDH. This 
works with Curve25519 encryption or any other ECDH scheme.

Because "just X" is the minimal representation (i.e. the size is never 
more than 256 bits), this is an unambiguous encoding. It means "if you 
need Y, go and calculate it yourself". 
http://tools.ietf.org/html/draft-jivsov-ecc-compact provides one 
unambiguous method to know the other coordinate from this minimal 
format, but, as mentioned above, this is not needed for ECDH.

( Besides, the value 41 or 42 is implied by the curve OID in the 
following way. If we are talking about encryption and the OID is 
Curve25519, you know it's 41. The value 40 v.s. {41,42} is implied by 
the curveID and the size of the MPI. )

Thank you.

>
> In GnuPG master (and libgcrypt 1.7) 0x40 is already supported for
> Ed25519 keys.  I also working on an I-D for EdDSA (ed25519) support in
> OpenPGP to get an algorithm id assigned.
>
>> IIUC, draft-jivsov-ecc-compact-05 can be applied to 6637
>> straightforwardly, and fingerprint (or keygrip) will be different when
>> representation will be changed.  Is this right?
>
> Should not because we are already using the Jivsov method for key
> creation.
>
> However, I doubt that we need that right now and I would propose to just
> go forward and not wait on the IETF to decide on new curve and point
> representation.  The whole thing is delayed way too long and there are
> no signs that there will be any soon decision.  I am more and more
> convinced we should set the standard by using it.  OpenSSH and several
> other projects settled for the Chicago curves instead of waiting until
> the IETF participants (where some of them work for the NSA or govt
> contractors) agree on something.
>
> Using the Montgomery coordinates for ECDH is just fine.  If an
> implementation wants to use its Edwards maths it can be easily done and
> mapped to Montgomery coordinates.  A revision of RFC-6637 can always be
> made and document the new compression scheme.  We can also wait for an
> successor of RFC-4880 to obsolete the current OpenPGP RFCs.
>
>
> Shalom-Salam,
>
>     Werner
>