On Thu, Jan 29, 2015 at 09:55:35PM +0000, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 
> On 28/01/2015 15:53, Watson Ladd wrote:
> > The following have been suggested for primes at sizes between 
> > 2^255-19 and 2^521-1.
> 
> I think what would inform my preference most is performance data, so,
> tabulating Mike Hamburg's data¹:
> 
> ┏━━━━━━━━━━━━━━━┳━━━━━━━┳━━━━━━━┳━━━━━━━┓
> ┃ Prime         ┃   ρ   ┃  mul  ┃  sqr  ┃
> ┡━━━━━━━━━━━━━━━╇━━━━━━━╇━━━━━━━╇━━━━━━━┩
> │ 2^521-1       │ 260.3 │ 145.5 │ 110.7 │
> │ 2^512-569     │ 255.8 │ 199.9 │ 140.6 │
> │ 2^448-2^224-1 │ 222.8 │ 118.0 │  88.9 │
> │ 2^414-17      │ 205.3 │       │       │
> │ 2^389-21      │       │ 112.5 │  75.5 │
> │ 2^384-317     │ 191.8 │ 117.5 │  89.8 │
> │ 2^379-19      │       │       │       │
> └───────────────┴───────┴───────┴───────┘
> 
>   ρ = approx cost (in bits) of pollard-rho (higher is better)
>   mul = cycles per multiply (lower is faster)
>   sqr = cycles per square (lower is faster)
> 
>   (Please feel free to fill in the blanks with more data.)
> 
> I'm guessing ρ for 2^389-21 and 2^379-19 would be around 188-192ish
> (but I haven't actually generated the curves to count ℓ).

One can use the approximation l~p/h for calcuating rho (error
is at most a few times sqrt(p)).

The exact point counts (hexadecimal) are:
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF753D798B1D68B9D18A3275D50226FC291D59B7A56D87475
8000000000000000000000000000000000000000000000000F015C9EE5991796231BCD44844D798E8CD39734D450782F5

(the first is 379-bit curve [a=-1,d=143305,p=2^379-19], the
latter is 389-bit [d=-5423,p=2^389-21]).

>From this one gets rho of 187.8 and 193.3.

Regarding speeds, one needs to take number of scalar bits into
account.

Taking that into account (multiply by bitcount) and wildly picking
60/40 mul/sqr weighting, one gets:

2^521-1:	68553
2^512-569:	90204
2^480-2^240-1:	51052	(fares very badly on 32-bit)
2^448-2^224-1:	47649
2^416-2^208-1:	44245
2^414-17:	N/A
2^389-21:	38005
2^384-317:	40865
2^379-19:	N/A

This ignores additions, but usually those are fairly minor part.

> Not sure I find 379 tempting, unless it turns out significantly faster.

Depends on hardware. On decent hardware (Intel x86, modern ARM),
virtually a tie.

Having implemented both (pretty badly speedwise), I would say that
389 is nicer to implement (due to rational base working nicely).

> Goldilocks looks promising. I'm missing data on 41417, which also
> deserves a fair crack of the whip.

There's also Goldilocks-like curve on 416-bit level
(d=-44875, p=2^416-2^208-1). One can assume Goldilocks mul/sqr times
for it (I included it in above table).

On curve41417, the algorithm doesn't generate that if given p=2^414-17,
but curve with d=-142113 (which is h=4). Speedwise those two curves
over the same field are tied on CPUs (on dedicated hardware there
might be differece due to d being much larger).

Which has faster multiplication is unknown.

> I think E-521 can also go a bit faster than this, but I don't have too
> many details. It's rigid enough several groups have generated it
> independently. But maybe too slow.

IIRC, there were recent speedups on it, but the figures probably
include those already.
 
> Remembering that if we do choose a 'big' curve, CAs will use it, and
> that means frequent verification for even mobile clients.

For CA certificates or end-entity?

There are so few CA certificates (hundreds) that caching those is
likely feasible. End-entity certs are another matter.

Also, with ECC, signing is faster than verification (by factor of
about 3 or so).


-Ilari