Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement

[Robert Ransom <[e-mail]>]

On 1/12/14, Watson Ladd <[e-mail]> wrote:
> On Sun, Jan 12, 2014 at 7:01 AM, Robert Ransom <[e-mail]>
> wrote:
>> On 1/12/14, Manuel Pégourié-Gonnard <[e-mail]> wrote:
>>> On 11/01/2014 18:50, Alyssa Rowan wrote:
>>>> 2. Monty & Eddie
>>>>
>>>> You list both Montgomery and Edwards curves in that list. I suggest
>>>> just listing the Montgomery curves (Curve25519, M383 and M511) for
>>>> this use, as these are the forms that are the very natural choices for
>>>> ECDHE, with the handy x-coordinate-only feature.
>>>>
>>> I tend to agree. But as was noted by others (including Robert Ransom on
>>> the
>>> CFRG
>>> list), every Edwards curve can also be used to do Montgomery. So I'm
>>> curious
>>> to
>>> hear more about whether people are also interested by the Edwards curve
>>> for
>>> ECDHE or if the Montgomery curves are enough.
>>
>> * ECDH should use only Montgomery form, *never* Edwards form.  (There
>> are key-agreement protocols which require Edwards form.  ECDH is not
>> one of them.)
>>
>> * Every curve with minimal Edwards-form parameter can be efficiently
>> used in Montgomery form with the simplest possible implementation.
>> The converse is not true.
>
> Why is using twisted Edwards form, or the Montgomery ladder, so bad from
> an implementation perspective? Twisted Edwards form makes the converse
> true. I now mention it in the draft, as well as the AFRICACRYPT paper which
> introduces it.

Dr. Bernstein's Ed25519 paper specifies the a=-1 twist because that
twist has strictly faster formulas than any other value of a, even if
that twist requires a large value of d.

> Not every implementation needs to be the fastest, just fast enough.

That does not justify choosing curves in a way that unnecessarily
harms the performance of simple implementations and raises the
complexity of fully optimized implementations.


>> * Most of the ‘SafeCurves’ curves (including all of the ones specified
>> in Montgomery form, except Curve25519) would be needlessly unpleasant
>> to implement.  The only curves that I could support using for ECDH at
>> this time are Curve25519, Curve3617, and (possibly) E-521.
>
> You will have to expand on this. All of these curves have primes of
> similar shapes,
> and while some might require more annoying limb placements than
> others, without having
> actual implementations to compare, we don't know how big the impact
> actually will be.
>
> M-383 is actually better than Curve3617 from your perspective: it
> reduces the size of
> the actual coefficient in Montgomery form and in twisted Edwards form
> will be the same size.

Curve3617's Montgomery-form parameter is 1/3617 (or something close to
it).  (In the Montgomery formulas, a reciprocal-of-small-integer
parameter is as efficient as a small-integer parameter.)  M-383's
Montgomery-form parameter will be a small integer with about 6 decimal
digits.

> The prime is also the same.

Curve3617's coordinate field is 414-bit; M-383's coordinate field is
383-bit.  I don't think they're the same.


Robert Ransom