Nikos Mavrogiannopoulos nmav@gnutls.org writes:
Congratulations!
Thanks!
About the ECC part, if you plan to base it on what I submitted last year, some clarifications.
Not sure which code to reuse. I also wrote a proof-of-concept ecc implementation for Yubico last year (targeted at 8-bit and 16-bit microcontrollers), which is LGPL licensed.
What I submitted was about curves mod p (I think the patch was about arbitrary curves, but had been tested only with curves that had a=-3 - the nist curves).
For now, I think I'll do only standard mod p curves ("secp192r1", "secp224r1", "secp256r1", there are also other names for these curves, I don't know which names are the most established ones).
This code has been further improved by Ilya in the last google summer of code by adding wmNAF multiplication and other optimizations in the code base.
What's wmNAF? Optimizations I'm aware of:
* Multiplication for an arbitrary point: Use a standard window-based exponentiation algorithm. Not sure if it makes sense to aim for data-independent timing (like GMP mpz_pomw_sec).
* Multiplication for the generator point: Use the "comb" method for fixed-base exponentation (see Handbook of Applied Cryptography). Gives a large speedup for generating ECDSA signatures, at the cost of some constant tables.
* Representation for multiplication. In the code I've written I've used homogeneous cooordinates, not sure if maybe Jacobi coordinates would be more efficient? Do you know? When using compile-time constant tables, take advantage of normalization in the tabulated values (the homogeneous coordinate Z always 1).
* At least for the primes used for the 192-bit and 224-bit curve, Montgomery representation is not needed, since the structure of the primes (top 128 bits all ones) makes standard euclidean modulo very efficient. For the 256-bit curve, only the top 32-bits are all ones, so on 64-bit machines one may want to use montgomery, or some other special trick.
What is missing is support for curves over F(2^p).
For a start, I think I'll stick to what's described in RFC 6090, since then it seems very unlikely that I'll get into patent-related troubles.
I wouldn't say that ARMv6 is obsolete. It exists in many embedded devices.
I see.
Regards, /Niels