[curves] General Curve25519 and Ed25519 Libraries

[Gregory Maxwell]

On Thu, Jun 18, 2015 at 5:05 PM, Ray Dillinger <bear at sonic.net> wrote:
> I may be ignorant here but I'm wondering why adding support for
> a different curve is such a big deal for all these libraries and
> programs.
>
> Isn't a curve just a block of static parameters which some
> generic ECC code can work on?  Why isn't adding a curve just a
> matter of defining a data block?

For secp256k1 the performance difference between mostly (but not even
fully) generic code, even with ASM optimizations, and specialized code
is on the order of 8x.
Likewise for other curves.

Performance doesn't matter very much for all applications, but there
are few where you couldn't take a performance difference that big and
use it to the defender's favor (e.g. by using bigger parameters).

Similarly for constant time operation much better can be done by
specialized code.

Even for researchy work, that much performance can be the difference
between something you can actually use and try out, vs being a
"simulation" that you can only run a few times before your publication
deadlines.

There is also an argument to be made that showing the correctness of
generic code is harder that specialized code- the generalizations may
not hold in all cases. Though in practice this may be offset by
optimization induced risk in the specialized versions.

Templaitized programming doesn't really help to much with algebraic
optimizations. (yet, perhaps)

On Thu, Jun 18, 2015 at 6:53 PM, Michael Hamburg <mike at shiftleft.org> wrote:
> For Edwards curves they use g^hash, which is going to
> outright break most protocols that use this primitive.  I’m filing a bug
> against that.

Eeek.