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%, 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
