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

[Ilari Liusvaara <[e-mail]>]

On Mon, Dec 01, 2014 at 06:17:07AM -0800, Adam Langley wrote:
> On Sun, Nov 30, 2014 at 7:33 PM, Robert Ransom <[e-mail]> wrote:
> 
> > Interesting suggestion.
> >
> > Both 89747 and 121665 are 17 bits long (they are between 2^17 and 2^18
> > - 1), and 89747 has a slightly greater Hamming weight than 121665 (10
> > rather than 9); I would expect any performance improvement on due to
> > that change in curve parameter to be quite small and only applicable
> > to a very few implementation strategies.  Have you done any
> > benchmarking to quantify the performance improvement that you are
> > claiming as a technical benefit of PinkBikeShed?
> 
> I've not done any benchmarking, it's just a guess. But the Edward's d
> parameter for the curve isomorphic to Curve25519 isn't 121665, it's
> +/- 121665/121666 [http://eprint.iacr.org/2007/286.pdf, section 2].
> That value doesn't have a small representation so I think that the
> PinkBikeShed curve does get to use a multiplication by a small
> constant in place of a multiplication by a large constant. That might
> be a small help.

The isogeny that lets one in effect have small d and a24 at the same time
also exists for Curve25519.


AFAICT:

Complete Twisted Edwards curve:

-x^2+y^2=1+121665x^2*y^2 (mod 2^255-19)

With base point:

x=8343919484931660353238246604028044872330114539683257561218125599081866236258
y=10591048728587107161910258178281284043396286849160988064050992288107790236293

Mapped by:
u = -y^2/x^2
v = y*(-x^2+y^2-2)/(i*x^3)

Where (square root of -1):
i=38214883241950591754978413199355411911188925816896391856984770930832735035197

Maps to complete Montgomery curve:

v^2 = u^3 + 486662 * u^2 + u  (mod 2^255-19)

With base point:

u=9
v=14781619447589544791020593568409986887264606134616475288964881837755586237401


Mapped by:
w=u+19298681539552699237261830834781317975544997444273427339909597334652188435537

Maps to Weierstrass curve v^2=w^3+a*w+b:
a=19298681539552699237261830834781317975544997444273427339909597334573241639236
b=55751746669818908907645289078257140818241103727901012315294400837956729358436

With base point:
w=19298681539552699237261830834781317975544997444273427339909597334652188435546
v=14781619447589544791020593568409986887264606134616475288964881837755586237401


All the curves have base order of:
7237005577332262213973186563042994240857116359379907606001950938285454250989



The middle curve and base point match Curve25519 data from Safecurves after
changing variable names (x,y)->(u,v).


The v(x,y) formula looks messy, but for single-coordinate Montgomery, one only
needs u(x,y), which is reasonably fast. And looks like one can compute v(x,y)
together with u(x,y) pretty cheaply (few extra multiplications and additions).

The reverse maps x(u,v) and y(u,v) are more annoying, seemingly containing
two square roots and an inversion (among with few other ops).


-Ilari