On 01/17/2013 10:00 AM, Niels Möller wrote:
As I wrote earlier, for a start I'll limit the support to standard NIST curves. So first question is naming; what's the most established names for these curves? It seems gnutls uses, e.g., "SECP256R1", I guess we can just follow that (rather than, e.g, "P-256", as it's called in the DSA spec fips-186-3)?
Any would do. In any case both are used, so aliases from one to another should be good. In the context of TLS the SECP names are used.
- For point multiplication with the fixed generator, I think I'll use the L=1 special case of Pippenger's algorithm, described in Daniel Bernstein's paper http://cr.yp.to/papers/pippenger.pdf. I think this is more or less the same as the "comb" method or "Lim-Lee"-method, but predating any bogus patents on the algorithm.
How does this algorithm compare to others? The reason I insist on performance is that it would be hard for gnutls to switch to the new functions if they are significantly slower than the current ones, and I'd like to switch eventually to nettle for all operations including ECC.
- For general point multiplication, I tend towards using a simple
non-sliding window, with a small point-specific table computed at run time. If the table is small enough, it might make sense to normalize the entries. As far as I understand, one can't beat the plain binary algorithm by a large factor; the algorithms I'm aware of only reduce the number of adds, but not the number of dups.
I really cannot answer with any facts since I need to check the details, but I've not seen other efficient implementations using a non-sliding window for that. Are you sure that the effect is insignificant? Additions aren't that negligible. Also for that part you don't need constant time. In ECDSA you only multiply the fixed generator with the key (in ECDH you also don't care unless it is fixed key ECDH).
- For verifying ECDSA signatures, one needs to operate on two points, computing e_1 G + e_2 Y, where G is the generator (and hence offers possibilities for precomputation), and Y is the public key.
I would put that of lower priority that signing. Servers (where performance matters) rarely verify ECDSA keys.
I have had a quick look at the gnutls code. wmNAF makes me a bit uneasy when I think about side channels; there seems to be a lot of branches depending on exponent bits.
Why is that? Did you see any issues on the timing resistant version of the function?
In the point addition, it seems hard to avoid special cases when adding a point to itself or to its negation, or adding the zero point.
Do you mean the infinity points or the point (0,0,0)? I think it can be catched by checking whether a point lies on a curve prior to the verification operation (0,0,0 isn't a point in the projective space either).
As far as I understand, for point multiplication in both ECDSA and ECDH, it's only the scalar that ever is secret, the points multiplied are always public.
Yes.
Are there other uses of point multiplication where also the point is secret?
None that I'm aware of in ECDH or ECDSA.
regards, Nikos