Re: [Cfrg] Curve selection revisited

[Watson Ladd <[e-mail]>]

<choping irrelevent stuff>

>
> “Easy” does not mean “low-cost”.  Adding support for Edwards-form
> input points to a Montgomery-ladder implementation is easy, but has a
> high performance cost (1I per scalarmult).  Adding support for
> Montgomery-form input points to an implementation which operates on
> Edwards form is easy, and has much smaller performance cost.

By "easy" I meant that as the field arithmetic is already done, which
is the vast
bulk of the difficulty, the additional code is smaller. Adding the
Montgomery ladder
as a routine on top of the arithmetic is not hard: it's 10 function
calls and a loop more or less.
>
>
>> (there is an additional question of small parameters: a Montgomery
>> curve with small
>> parameter is birationally equivalent to a twisted Edwards curve of
>> small parameter, but
>> the converse is not (obviously) true. Most generated curves seem to be
>> in Edwards form
>> however.)
>
> Curve25519 chose (A+2)/4 to be a small integer because Edwards curves
> had not been published yet.  All new curves should be chosen to have
> Edwards d be a small integer, because that makes the Edwards-form
> unified addition formulas faster at no cost to the Montgomery ladder
> on the isomorphic Montgomery curve.  (I've mentioned this to CFRG
> before; I wish more people had listened to me.)

Doesn't A become a ratio of small integers rather than a small integer? Although
this is still pretty fast.

>
>>>> one caches ephemeral DH
>>>> parameters so the cost of fixed-base exponentiation is amortized
>>>> across connections. OpenSSL does this anyway, and this affects
>>>> technique
>>>> slightly.
>>>
>>> This is good for performance even if you use a table to optimize
>>> fixed-base scalar multiplications.
>>
>> Very true: the NUMS performance results are thus dead wrong in ECDHE costs,
>> which are two variable-base multiplications plus a very amortized
>> fixed-base multiplication, not
>> the fixed+variable base they used.
>
> I don't see anything wrong with what MSR states as the cost of ECDHE
> -- they're consistent across the implementations, and not reusing
> ephemeral keys is the simplest implementation strategy.  (If they did
> change their figures to take key reuse into account, though, the cost
> would be only one variable-base scalar multiplication, not two.)

The numbers are right, but the conclusions are thus wrong since a
common optimization
is neglected. In particular, the absence of Montgomery form from the
proposal is based on
performance measures including a fixed based exponentiation.

Sincerely,
Watson Ladd

>
>
> Robert Ransom



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin