[curves] Microsoft ECCLib for "NUMS" curves

[Trevor Perrin]

On Thu, Jul 3, 2014 at 8:13 AM, Michael Hamburg <mike at shiftleft.org> wrote:
>
> 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%,

I know that's a rough number, but I'm curious how you arrived at it.

In [1] and [2] Microsoft quotes:

ed-256-mers (2^256 - 189) => 234 Kcycles
ed-255-mers (2^255 - 765) => 226 Kcyles

Adjusting for the extra half-bit of security at 256, ed-255-mers only
looks ~2.5% more efficient.  Assuming that Microsoft implemented these
similarly (which is a guess because they haven't released
ed-255-mers), could we roughly attribute that 2.5% to using a 255 bit
field instead of 256?

Curve25519 has prime closer to 2^255 (-19 versus -765), so I guess
you're estimating additional benefit from that?

To be fair we should account for 2^255-19 being 5 mod 8, whereas
Microsoft's curves have 3 mod 4 primes.  So point decompression during
signature validation might include a couple extra field operations.
But I think this should be well less than 1% of signature verification
cost (?), so I guess you're assuming the benefits of small constant
(19) outweigh the added cost of 5 mod 8?


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

Could you expand on that?  What other things don't work as well?
What's a "principal square root"?

Trevor

[1] http://eprint.iacr.org/2014/130.pdf
[2] http://patricklonga.webs.com/Presentation_CFRG_Selecting_Elliptic_Curves_for_Cryptography.pdf