Re: [Cfrg] 25519 naming

[Robert Ransom <[e-mail]>]

On 9/2/14, Andrey Jivsov <[e-mail]> wrote:
> On 09/02/2014 01:28 AM, Robert Ransom wrote:
>> On 9/2/14, Andrey Jivsov <[e-mail]> wrote:
>>
>>> X25519 performs 9 F(p) multiplications and squares per each bit of a
>>> scalar, for the total of 2295 F(p) operations, not counting additions.
>>> Plus there are also 265 operation for an inversion.
>>>
>>> According to the above, conversion from -1-twisted Edwards coordinates
>>> to
>>> X25519 unfortunately involves a F(p) inversion.
>>>
>>>      265/2560 ~= 10%
>>>
>>> The problem with fixing canonical coordinates seems to be the 10% penalty
>>> in
>>> conversion from Edwards coordinates to Montgomery due to F(p) inversion.
>>> I
>>> wonder if it is possible to not perform the inversion by starting with
>>> z!=1
>>> in the Montgomery formula?
>> That would cost an extra 1M per scalar bit.  1I to rescale the input
>> point is *always* faster.
>
> Doesn't an inverse require at least 1M (multiply or square) per scalar
> bit as well? Or, are you saying that because more of these Ms in the
> inverse are squares, this provides a small benefit?

An unoptimized inversion by exponentiation would cost up to 1M+1S per
bit of the coordinate-field order.  However:

* All coordinate fields that are currently under serious consideration
allow a structured addition chain for inversion which reduces the
number of multiplications significantly (for Curve25519, 11M+254S).
Since 1S is typically about 0.67M, that's much less than 1M per scalar
bit, even if you don't count the three least significant bits as part
of the scalar.

* All implementations must perform an inversion in order to scale
their output points anyway, so if someone decides to use a random
coordinate field, they will use the Euclidean algorithm to compute
inverses at an even lower cost than that.


>>> This would give us fixed-base optimization and dual key use that comes
>>> with
>>> Edwards formula and the speed of Montgomery for variable-base ECDH.
>> A Montgomery-form x coordinate (or its reciprocal) provides that.
>> That's why I've been arguing for a point format based on the
>> Montgomery-form x coordinate for so long, even though no one seems to
>> be listening.
>
> I am interested, especially in a detailed write up.

I just posted a link to one in another thread:
<http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html>


Robert Ransom