Re: [Cfrg] Safecurves draft redux

[Robert Ransom <[e-mail]>]

On 1/9/14, Watson Ladd <[e-mail]> wrote:

> But as for efficiency, pontification about what is fast and what isn't
> will always be behind the drive of implementors to accelerate
> everything. What seems like an awkward limb placement can be fixed by
> some clever use of fractional radix arithmetic.

There is a limit to how much ‘fractional-radix arithmetic’ can help.
2^255 - k has a nice regular (vectorizable) pattern of 10 limbs ([26,
25]*5); no other pattern works as well.  2^414 - k can be split into
18 or 9 equal-size limbs, or a vectorizable pattern of 16 or 8 limbs.
None of the other curves' coordinate fields (with the possible
exception of M-221) have both a good arrangement of limbs and a
sufficiently small k to postpone carrying after multiplication until
after modular reduction.

> Lastly, just because a protocol suggests a form to go on the wire does
> not mean that the calculations an implementation does need to resemble
> it. Robert Ransom has made this point, and I agree with it.

And I also made the exact opposite point: twist security is only
useful because implementations will be free to use Montgomery's ladder
formulas.

> Good
> standards specify observed behavior, not how it is attained.

Good standards specify *both* the intended observable behaviour *and*
how to attain it.  The whole point of SafeCurves is to assist in
*implementing* ECC both safely and efficiently.

> As a metacomment: we shouldn't let our desire for "The Idiots Guide to
> ECC" in RFC form get in the way of standardizing these curves. I don't
> think our job is done with putting these curve formulas in an RFC, but
> it does substantially help anyone who wants to use these curves in
> another IETF protocol.

Shoveling this pile of curve equations into an I-D or RFC accomplishes
nothing.  What matters is specifying how to use curves of this class
in protocols, and that requires not only specifying point formats and
curve-operation formulas, but choosing the right set of point formats
to support in each case, and documenting how to assemble the primitive
curve operations into the exact procedures that the protocol requires.
 It's a matter of systems engineering, not mathematics or cryptography
alone.


Robert Ransom