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

[Paul Lambert <[e-mail]>]

]-----Original Message-----
]From: Cfrg [mailto:[e-mail]] On Behalf Of Andrey Jivsov
]Sent: Thursday, March 12, 2015 12:19 PM
]To: [e-mail]
]Subject: Re: [Cfrg] Elliptic Curves - curve form and coordinate systems
](ends on March 12th)
]
]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. 

+1  

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

Please - no such limitations.  The public key should be able to be used
for either or both ECDH and signatures.

Paul


]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.
]
]_______________________________________________
]Cfrg mailing list
][e-mail]
]http://www.irtf.org/mailman/listinfo/cfrg