[curves] Microsoft ECCLib for "NUMS" curves

[Michael Hamburg]

On Jul 3, 2014, at 2:38 AM, Trevor Perrin <trevp at trevp.net> wrote:

> 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 numbers with Mers 256 vs 255 suggest that the “nature” difference
on this is about 5%, though it’s possible that a DJB or a Shay could optimize
one or the other much better than has been done, or that one is better on certain
architectures (eg ARM).  The main efficiency differences are that with packed
arithmetic (profitable at 256 but probably not at 512), you have to reduce more
aggressively; and with non-packed arithmetic, you care about the constant
being small (19 vs 189).

> - 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?

It’s not a big deal, and in my opinion it isn’t a reason to switch.  It’s slightly more
annoying, and it makes some other things not work as well (can’t use choose
principal square root).

> - 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.

I don’t think this is big a deal either.  It only matters if you want to validate that
the points are in the subgroup for some reason.

These points might be reasons to choose Mers 255 or Mers 256 over Ed25519
if we didn’t already have a good curve at that level, but I don’t think they’re enough
reason to switch, except maybe if it’s a matter of “we want to standardize 3 curves
which are all chosen using the same process, at different security levels”.

— Mike