[curves] General Curve25519 and Ed25519 Libraries

[Gregory Maxwell]

On Wed, Jun 17, 2015 at 10:30 PM, Michael Hamburg <mike at shiftleft.org> wrote:
> As far as other curves go, there is also my Decaf library for
> Ed448-Goldilocks:
>
> http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/
>
> It includes a C++ header with overloaded arithmetic operations, so you can
> do all the arithmetic operations you might expect:
> Scalar +-*/= Scalar
> Point +-= Point
> Point */ Scalar, Scalar * Point
> Precompute point, precomputed point */ scalar
> Constant or variable-time double scalarmul
> Convert point to a string and back
> Hash uniformly or non-uniformly to the curve
> Steganographically encode point on curve
>
> The code implements a prime-order group, so you don’t have to worry about
> cofactor.  All the operations are constant-time except variable-time
> double-scalar-mul (i.e. verify), and steg encoding (which succeeds with
> probability 1/2 on each iteration).

Similarly, I can suggest libsecp256k1 for research-y use, which
implements secp256k1 which is a SECG specified prime order curve (I
agree that not worrying about cofactor is quite nice):
https://github.com/bitcoin/secp256k1/   I should stress that we don't
currently consider this software to have yet had enough formal
analysis to use it for most production uses (though, our standards are
atypically high, we do have more analysis and testing than most
available EC code which doesn't come with these warnings; OTOH we're
also implementing a number of interesting optimizations that should
demand more evidence)

Internally it has the same feature set listed above minus constant
time hash uniformly (methods to do so are known, but I haven't
bothered implementing it due to a lack of a need) and a efficient steg
bijection (which I don't know how to do for that curve; though I
haven't looked into it much).  It's also fast, which may be
interesting for research use since it means that performance measures
against it won't just be toy numbers, Someone showing up doing
something interesting that needed these things (especially the former,
since I know its possible) would probably inspire some work there. :)

On the other hand, the optimization for performance (and production
use) do mean more complexity to implement protocols on it (as you'll
have to deal with knowing when you want affine/projective coordinates,
etc).  For safety reasons we also have no plans to expose basic
cryptography operations externally (because we know from experience
that callers will misuse them), only higher level constructed for
"more complete" cryptosystems that are harder to abuse-- so new
protocols can't just use the public API.

I also recently used this system to make a tech demo for a new zero
knowledge range proof system, which I've been asked to post about, so
I'll go do that now.