Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

[Adam Langley <[e-mail]>]

On Wed, Nov 26, 2014 at 10:57 PM, Alyssa Rowan <[e-mail]> wrote:
> In order to evaluate the performance of simple and secure
> implementations of algorithms over these curves, of course we are also
> going to need safe, efficient implementations for those algorithms,
> ideally available under a liberal licence so stakeholders can actually
> use it (specifically I'm afraid Apache 2.0 won't do due to its licence
> incompatibilities), which also satisfy our patent concerns. Do you
> have such an implementation ready to publish that we can plug into
> SUPERCOP?

For the curve over GF(2^255-19), I certainly agree that
implementations are needed but I believe that there's strong evidence
that the performance would be equal to curve25519.

The Edwards curve in question is isogenous to Curve25519 with A=358990
and, while some uses may want to drop the new curves into existing
code, I hope that this RG can recommend that ECDH operations for the
most part transmit the Montgomery X value. Thus curve25519
implementations should just need to change the (A-2)/4 value.

For implementations of the Edwards curve, the smaller d value, if
anything, might allow a slight speedup over Edwards curve25519.
(Although those implementations would need changes to the scalar
reduction function and any precomputed tables.)

> I note that if you run your algorithm on 2^521-1 you get E-521. If you
> ran it on 2^255-19, why didn't you get the twisted Edwards form of
> Curve25519? Kindly elucidate your objections to the same.

As djb noted in the curve25519 paper[1], the A value for curve25519 is
not minimal. draft-black-rpgecc-00 finds a curve isogenous to the
minimal A. The minimal (and second minimal) value was originally
rejected because, when generating private keys, there's a possibility
of generating a multiple of the order. This can be taken care of with
(I think) a single memcmp, although I need to confirm that just one is
sufficient when I'm back home.

[1] http://cr.yp.to/ecdh/curve25519-20060209.pdf, section "Why this curve?".


Cheers

AGL