[email protected] (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
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
