[curves] The great debate over point formats

[Robert Ransom]

On 1/30/14, Diego Aranha <dfaranha at gmail.com> wrote:

> Your comments are very relevant, but let me justify some of our design
> choices. We picked field sizes similar to NIST curves, trying to provide
> something closer to drop-in replacements.

A true drop-in replacement for one of the NSA curves would be a
small-parameter Edwards curve over the same field, satisfying the
‘SafeCurves’ criteria, with a=1 and non-square d, such that:

* the isogenous Montgomery form (*not* the isomorphic one; see the
‘Isogeny patterns among Edwards curves’ thread) is isomorphic to a
short-Weierstrass curve with a=-3; and

* if the field order is congruent to 3 mod 4, the isogenous Edwards
curve a'=-1, d'=d-1 has non-square d/a (so square d).

Existing implementations of the NSA curves could simply swap out their
short-Weierstrass b to start using the new curves; over time,
implementations could be updated to use faster, safer formulas on the
new curves.


> Additionally, we considered not
> only vector or hardware implementations, but also the fast integer
> multipliers already available to software implementations in many
> platforms. Of course, these could require specialized assembly-language
> multipliers for optimal performance. You can find some brief notes below.

You seem to be assuming that (a) the implementor can use (an
equivalent of) the Intel ADC instruction, and (b) ADC is fast.  (a)
does not hold for C implementations; according to the Ed25519 paper,
(b) does not hold for whichever of Intel's AMD64 chips was newest at
that time.


Robert Ransom