nisse@lysator.liu.se (Niels Möller) writes:

I'v started to look closer at curve25519, and I've added support for it in the eccdata program.

I'm working slowly on this, on a new branch "curve25519". I now have an ecc_dup_eh function, which duplicates a point on an Edwards curve, using homogeneous coordinates, and a function ecc_eh_to_a to convert the coordinates back to affine coordinates on the equivalent Montgomery curve (typically, curve25519). And a basic test case for that.

To get a uniform interface for different types of curves, I'm considering moving some functions from the public header ecc.h to ecc-internal.h. In particular, the ecc_j_to_a, ecc_dup_jj, ecc_add_jja, ecc_add_jjj. And instead have functions for converting to some unspecied internal coordinates, based on some additional function pointer in the internal struct ecc_curve. The documented ecc functions would be left unchanged. Would that cause any problems?

I haven't yet looked very closely at the API other curve25519 are using, or at the definition of ed25519 signatures.

It would make sense to me to have the curve25519 function operating on byte strings (as specified by djb), looking something like

void curve25519 (uint8_t *r, const uint8_t *point, const uint8_t *scalar);

where POINT is the x coordinate of the base point, or NULL for the generator (x == 9), SCALAR is the secret number to multpily the point with, and R gets the x coordinate of the resulting point. Or two separate functions. The thing is that the case x == 9 is an important special case, and it can be sped up a lot with a few KB of precomputed tables, just like for the other curves, or fix-base exponentiation in general.

So suggestions on what the API should look like are apppreciated. And what's a good source for test cases for the curve25519 function?

For ECC in general, I think it would be good to have another look at modular inversion. The current side-channel silent code works but is fairly slow. It sometimes beats GMPs mpn_sec_powm (for a prime p, a^{-1} = a^{p-2}), but often it doesn't, in particular for the smaller primes. I'd like to try doing a fix-exponent powm, using the optimized mod or redc functions for the prime in question, and some well-chosen addition chain for each needed exponent.

And if anyone wants a bit of summer reading, I can recommend the square root overview http://www.math.vt.edu/people/brown/doc/sqrts.pdf, which I stumbled upon when searching for a description of the Shanks-Tonnelli algorithm for square root modulo p.

Regards, /Niels