On Thu, Jul 3, 2014 at 8:13 AM, Michael Hamburg <[email protected]> wrote: > > On Jul 3, 2014, at 2:38 AM, Trevor Perrin <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
