[curves] General Curve25519 and Ed25519 Libraries

Ron Garret ron at flownet.com
Thu Jun 18 10:45:28 PDT 2015

Some curves have parameters that have particular properties that allow for certain kinds of optimizations that don’t work for general parameters.

For example, to do general modular arithmetic you need to compute remainders, which means you need to do divisions, which are expensive.  But if you are doing modular arithmetic modulo a prime P that is of the form 2^N-k where k is small, then there’s a trick that lets you compute remainders mod P without having to divide by P.  This is why curve25519 is called what it is.  N=255 and k=19.

(The trick, in case you’re wondering, is this: to reduce a number M mod P where P=2^N+k, let M1=M/(2^N) and M2=M mod (2^N), i.e. M1 is M right-shifted N bits and M2 is the N least significant bits of M. Then M mod P = (M2 + M1*k) mod P.  Obviously this is only a win when k is small.)

On Jun 18, 2015, at 10:05 AM, Ray Dillinger <bear at sonic.net> wrote:

> I may be ignorant here but I'm wondering why adding support for
> a different curve is such a big deal for all these libraries and
> programs.
> Isn't a curve just a block of static parameters which some
> generic ECC code can work on?  Why isn't adding a curve just a
> matter of defining a data block?
> 				Bear
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150618/2a0a536b/attachment.sig>

More information about the Curves mailing list