Re: [Cfrg] Elliptic Curves - curve form and coordinate systems (ends on March 12th)

[Andrey Jivsov <[e-mail]>]

On 03/05/2015 03:31 PM, Alexey Melnikov wrote:
> CFRG chairs are starting discussion of the next topic:
>
> Q4: draft-irtf-cfrg-curves-01 currently contains curves in both 
> Montgomery form and Edwards form. The scalar multiplication routine is 
> specified using Montgomery form (and is specific to Curve25519, which 
> will need to be changed given our decision to include a higher 
> security level curve). Its input is a scalar and the u-coordinate of a 
> point on a Montgomery-form curve; its output is the u-coordinate of a 
> point on a Montgomery-form curve. The DH function builds on this 
> routine. Do we want to stay with specifying the inputs and outputs in 
> Montgomery form for these routines? Or do we want to switch to an 
> alternative curve form and coordinate system for defining the 
> routines? If so, which form and coordinate system?
>
>
> [Chairs are aware that it is possible to switch back and forward 
> between different curve forms and coordinate systems, with associated 
> costs, no matter which form is specified for the inputs and outputs of 
> the routines. But we now have to decide *which* form we want to use 
> for inputs and outputs, so as to ensure interoperability between Alice 
> and Bob. Chairs did not want to implicitly force the choice of 
> Montgomery form/coordinates without polling the group first.]
>
>
>
> Once this issues is settled, we will be discussing (in no particular 
> order. Chairs reserve the right to add additional questions) wire 
> format, byte order and signature schemes. Please don't discuss any of 
> these future topics at this time.

A unified binary representation for a public key Q=k*G on the same curve 
is preferred, regardless of the fact that the Q is used with ECDH, 
ECDSA, EdDSA, PAKE, etc. My proposal incurs no (measurable) performance 
penalty for the proposed unification.

Consider the benefits of a single set of test vectors, code reuse, and 
the benefits of sharing pre-computed values. This proposal simply 
matches the capability of currently deployed ECC.

I propose the Montgomery curve representation (u, v), which can be used 
for signatures on the same curve.

"u" is identical to the sec 9 of 
https://tools.ietf.org/html/draft-agl-cfrgcurve-00.
"v" is calculated (at virtually no additional computational cost) as v = 
u^3 + 486662*u^2 + u

I am aware of the desire to enforce a key use type at the crypto level, 
but a widely used practice today on TLS servers is to require that a RSA 
server has both digitalSignature | keyEncipherment in its X.509 cert, 
otherwise such a TLS Web server cannot support ECDHE-RSA-AES128-SHA 
(digital signature) and AES128-SHA (RSA key transport) ciphersuites 
preferred by different clients with a single RSA key pair.

A sample of the interest in unified format can be found here:
https://github.com/agl/ed25519/blob/master/extra25519/extra25519.go 
(converts from Edwards to Montgomery for Curve25519)
https://github.com/dchest/ed2curve-js (dedicated to this conversion). 
Also please check other references listed in "Other libraries" there.

* An implementation that uses a Montgomery ladder simply ignores v (it 
only calculates v by reusing F(p) operations from its ECDH scalar 
multiplication code)
* This format allows more internal implementation choices
* The format is friendly for crypto algorithms that need to add points 
(as opposed to ECDH only)
* When a software library must implement both signatures and ECDH 
(something we assume to be common in the future) or even is interested 
in truly ephemeral public keys for ECDHE, the Montgomery ladder in sec 9 
is insufficient. Once that "other code" is written, it can do the job of 
Montgomery ladder at about the same speed.
* This proposal incurs 32 additional bytes of storage overhead for the 
public key, for the total of 64 bytes (compare this with 260+ bytes for 
RSA 2048).

Not sending u means that an implementation must incur ~10% performance 
penalty to recover v (unless the implementation is a Montgomery ladder, 
which doesn't need v). This is a headwind for any future internal 
improvement. On the other hand, calculating the v costs about 2M, under 
0.1% of the entire ECDHE cost.