[curves] Microsoft ECCLib for "NUMS" curves
Trevor Perrin
trevp at trevp.net
Fri Jul 4 00:52:34 PDT 2014
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
More information about the Curves
mailing list