[curves] Microsoft ECCLib for "NUMS" curves

[Trevor Perrin]

On Mon, Jun 30, 2014 at 9:41 AM, Trevor Perrin <trevp at trevp.net> wrote:
> On Mon, Jun 30, 2014 at 3:08 AM, Samuel Neves <sneves at dei.uc.pt> wrote:
>> I've fixed up the 256-bit arithmetic to run on Linux;
[...]
>> Here are the results on Sandy Bridge, compiled with gcc-4.8 -O3 -march=corei7-avx:
>
> Thanks!
>
> Looks pretty close to what's already in the spreadsheet, i.e. you
> reported 283.5 Kcycles and (the Weierstrass curve) and 229.5 Kcycles
> (Edwards), whereas the spreadsheet has 281 and 234.
>
> So I think it's still still slower than 25519.  I wonder about the
> "nature vs nurture" question: is it inherently a slower curve (harder
> for field reduction?) or just less optimized?

To answer my own question: the observed difference is probably mostly
"nurture".  Microsoft's 256-bit Edwards curve is similar to Curve25519
so could probably be optimized to about the same speed:

 - Microsoft's field prime is 2^256 - 189 instead of 2^255 - 19.
Seems pretty similar.  Is there any inherent efficiency difference for
scalar multiplication?

 - Microsoft's field prime is 3 mod 4 instead of 5 mod 8.  AIUI,
calculating square roots (e.g. point decompression) for 5 mod 8 has a
50% chance of needing a small extra step (a field multiplication by
the constant sqrt(-1)).  Could anyone summarize the significance of
this?  If the curves are mostly the same otherwise, is this a reason
to switch?

 - Microsoft's cofactor is 4 instead of 8.  Also similar - once you
have to account for a cofactor in protocols, it doesn't really matter
what it is.  Cofactor 4 instead of 8 does mean a larger "main
subgroup", so an extra ~0.5 bits of security against Pollard Rho.


Trevor