Re: [Cfrg] Progress on curve recommendations for TLS WG

[Ilari Liusvaara <[e-mail]>]

On Sun, Jul 27, 2014 at 08:04:45PM +0000, Paterson, Kenny wrote:

> - Do the current proposals (Curve25519 and friends, and the NUMS curves)
> provide an adequate degree of rigidity that is likely to satisfy the
> widest set of commentators? Or should we be thinking about generating
> fresh curves using a public process having verifiably random inputs? What
> would the likely impact be on performance?

I split the question to two parts: Prime and parameters

a) Prime

Picking prime randomly has _devastating_ impact on performance. Nobody will
seriously use the curve. This is THE reason why Brainpool is not used much
in the wild.

If one picks prime for performance (the prime is the dominant factor in
performance), there are very few primes that perform well[1].

This would force high degree of rigridity if performance is a major goal.

b) Parameters

While bad parameters aren't devastating for performance, badly picked ones
are still significantly slower (e.g. loses that ~0.75M advantage from small
parameter on addition or Montgomery step).

With parameters, random choice is not wise, given that there are very few
(I think 4 or 2 depending on bitlength[2][3]) rational choices for
deterministic curve per prime. It would be very hard to reach similar
rigidity via random process.


[1] The "contestants" all seem to be (pseudo) Mersennes with small c and
Solinas trinomials. I think some have tried to develop metrics to measure
the effectiveness of various primes.


[2] Complete Edwards (minimal |d|) vs. Complete Montgomery (minimal |a24|),
q < 2^n vs. q > 2^n.


[3] I think that shrinks to 2 on higher bitlengths, since using windowing
on Edwards curve becomes faster than using Montgomery ladder on Montgomery
curve.


-Ilari