On Jul 4, 2014, at 3:52 AM, Trevor Perrin <[email protected]> wrote: > 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?
I was measuring merely speed, and not efficiency scaled for bit length. > 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? 2^255-19 is faster than Microsoft’s 255-mers due to a combination of a small constant, the 255 instead of 256, and many years of implementations. >>> - 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 In a 3 mod 4 field, one of the roots is always square and the other is not. The square one is “principal”, and it’s a power of the input point. It’s a nice way to specify square roots. The squaring map is also 1:1 on values which are already square, which is sometimes useful in Elligator-style constructions. A related feature is that one can use Legendre symbol instead of high bit or low bit to define the sign of a number. Since the Legendre symbol is algebraic, it propagates through formulas in nicer ways. The downside of 3 mod 4 is that you need to use isogenies to switch between straight and twisted Edwards curves, instead of isomorphisms, and also that you’re excluding attractive primes like 2^255 - 19. — Mike _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
