Re: [Cfrg] Curve selection revisited

[Robert Ransom <[e-mail]>]

On 7/25/14, Watson Ladd <[e-mail]> wrote:

> So I'd like to explain a bit about how implementations work, and why
> performance will not help us decide between Curve25519 in twisted
> Edwards form and the NUMS curve of similar size in twisted Edwards
> form.
>
> The first question is how to do the field arithmetic. All the primes
> being considered are of the form 2^s-c, so either one of saturated
> arithmetic
> or unsaturated will work. Unsaturated is more portable: C cannot
> access the carry flag. It offers more freedom in radix, and lets carry
> chains be vectorized. Karatsuba can be used or not, which depends on
> the saturated/unsaturated choice. But the exact values of s and c
> don't matter as much.

The exact value of c determines whether a portable or vectorized
implementation can delay carries until after reduction.  For example,
after curve25519-donna performs a multiply or squaring, each of 19
64-bit limbs has absolute value less than 14*2^54.  When
freduce_degree reduces a field element to 10 limbs without carrying,
the result has absolute value less than (c+1)*14*2^54 = 280*2^54, or a
bit more than 2^62.  In the Microsoft field 2^255 - 765, or even 2^256
- 189, this would not be possible.

Carries between limbs can be performed more efficiently than in
curve25519-donna -- curve25519-donna goes to extra effort to keep
limbs signed.  In the Montgomery ladder, this optimization does not
add any extra carry steps, because the Montgomery-ladder formulas
never perform more than two add/subtract operations between a
multiply/square operation.  With Edwards-curve operations, this
optimization may require an additional carry step in the doubling
formula.

The exact value of s determines whether carries can be vectorized
within a coordinate-field element.  For example, 2^251 - 9 can be
represented using one 26-bit limb (in the least significant position)
and 9 25-bit limbs, but this interferes with the vectorization
strategy described in the neoncrypto paper (by Dr. Bernstein et al.).
Since c=9 is so small, this can be worked around by representing
coordinates modulo 2^252 - 18 instead, but this trick is rarely
possible without running into the bound on c.


> The second question and third question what coordinates and what
> addition formulas to use when, and what algorithm to use. All twisted
> Edwards curves expose the same possibilities here: large precomputed
> tables with mixed coordinate addition vs. smaller tables for variable
> base, or a conversion to some other isogenous curve for variable base
> exponentiation.

Affine Montgomery-form points can be unpacked to and packed from
projective (optionally twisted) Edwards-form points at a trivial extra
cost over unpacking from or packing to a compressed affine
Edwards-form point.  Variable-base scalar-multiplication operations
which use Edwards form internally are not slowed significantly by
having a projective rather than affine input (if any operations rely
on their input being affine, they must occur during table setup), and
they are not slowed at all if they double and/or apply isogenies to
clear the cofactor group before operating on an ‘incomplete’ curve
(e.g. a=-1 in a field in which -1 is a non-square).

As you should know, fixed-base scalar-multiplication operations which
use Edwards form internally are not slowed at all by producing
Montgomery-form output.

Affine Edwards-form points cannot be unpacked to affine
Montgomery-form points for use with the Montgomery ladder without an
extra inversion at the beginning of a scalar multiplication, and using
a projective input in the Montgomery ladder is always slower than
inversion by coordinate exponentiation.

Since the Montgomery ladder remains the simplest implementation
strategy, and the performance benefit to more complex implementations
from using an Edwards-form point format is small at most, I still see
no reason to use an Edwards-form point format.


> If we are willing to use Montgomery form (which the TLS WG initially
> had strong support for in Curve25519)

Has the TLS WG changed its support for using the widely implemented,
de-facto standard point format for Curve25519?  If so, when was this
decision made?

> 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.

> But to be clear, a fast implementation for one prime and
> curve of a certain size and shape will likely be adaptable to a
> different curve
> over a similar prime with the same shape.

This is simply not true.  Curve operations can often be reused, and
some other utility routines can easily be modularized in a way that
supports other coordinate fields with similar properties (e.g.
q=3mod4), but primes which make portable or vectorized coordinate
operation implementations efficient are too rare for there to be any
pairs of ‘similar prime’s.


> Performance data will not distinguish between s=255 and s=256.

It will distinguish between Curve25519 and the Microsoft curves in the
implementations (either portable, open-source C, or heavily-optimized
machine code) which are actually used.


Robert Ransom