Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

[Andrey Jivsov <[e-mail]>]

On 01/05/2015 11:15 AM, Alexey Melnikov wrote:
> This message starts 2 weeks adoption call (ending on January 19th 2015) on:
>
> https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml
>
> as the starting point for the CFRG document which describes an algorithm
> for safe curve parameter generation for a particular security level and
> also recommends a specific curve (2^255-19) for the 128-bit security level.
>
> Please reply to this message or directly to CFRG chairs, stating whether
> you support (or not) adoption of this document. If you do not support
> adoption of this document, please state whether you support adoption of
> any alternative document or whether you want a particular change be made
> to the document before adoption.


For http://tools.ietf.org/html/draft-agl-cfrgcurve-00:
>
> 9. Elliptic Curve Diffie-Hellman
>
>
...
>        z_2 = E * (AA + a24 * E)
>        // Conditional swap; see text below.
>        (x_2, x_3) = cswap (s_t, x_2, x_3)
>        (z_2, z_3) = cswap (s_t, z_2, z_3)
>    Return x_2 * (z_2^(p - 1))

should be

      Return x_2 * (z_2^(p - 2))

> 8. Wire-format of field elements

>    When transmitting field elements in the Diffie-Hellman protocol
>    below, they MUST be encoded as an array of bytes, x,

I would like to see an uncompressed format allowed as (x,y) as an 
optional format. This avoids ~10% performance penalty for some 
applications, v.s. the case when only (x) is sent.

the y above can be calculated for "free" at the end of Montgomery ladder 
calculation due to the above z_2^-1 inverse calculation, using a method 
described in section 5 (p.13-14) in 
http://ed25519.cr.yp.to/ed25519-20110705.pdf. The code would be needed 
anyway for decompression with signatures that use compressed point.

Likewise, receiving (x,y) allows a conversion to a projective form of 
twisted Edwards coordinates for "free" for a peer. At the same time a 
peer is free to ignore y and proceed with the Montgomery ladder 
multiplication exactly as described in sec 9.

Therefore, (x,y) on the wire allows the most suitable choice of 
implementation for ECDH, whereas (x) limits it to Montgomery ladder 
given that one needs to overcome the 10% penalty of recovering y with a 
square root.

Many applications and protocols will require generation of a new ECDH 
key pair (i.e. they cannot reuse it). For these applications fixed-base 
scalar multiplication on Edwards curve is much faster. These 
applications may prefer to use the same code for variable-base scalar 
multiplication as well. Likewise, the code reuse argument applies to 
applications that support signatures on Curve25519.

I support the draft with the above tweak.