Re: [Cfrg] Primes (last time hopefully!)

On Thu, Jan 29, 2015 at 1:55 PM, Alyssa Rowan <akr@akr.io> 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 ℓ).
>
> Not sure I find 379 tempting, unless it turns out significantly faster.

The reason 379 was put forward was saturated would be faster. But
until we have SUPERCOP runs we don't know how true that is: it's a
consideration on small ARMs sans NEON. Until we have extensively
optimized code we don't know for sure.

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

I could have sworn it was in SUPERCOP.

>
> 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.

The Granville and some other people methods are already in the
figures. Bear in mind that is a Brazilian standard: we will be
adopting it anyway. (Sidenote: why the heck is Curve25519
controversial, and GHOST/ANISSI/Brainpool/China's equivalent not?)

>
> Remembering that if we do choose a 'big' curve, CAs will use it, and
> that means frequent verification for even mobile clients.

Not sure I follow: If we provide both 521 and 448/379, why would CAs
use the ridiculously oversized one? They didn't for RSA after all.

>
> Enough already I think to rule 512 and 384 out now: they're slower
> than stronger curves (even if the MSR ECCLib comb gave them an advantage).

The comb is prime independent. The right way to measure would be all
optimized as much as possible, so the effects of arithmetic and curve
size shine through. (And on the same framework)

Sincerely,
Watson Ladd
>
> Those who really think performance doesn't matter are free to use
> 2^1024-105 if they like. ;-)
>
> ___
> 1. <https://www.ietf.org/mail-archive/web/cfrg/current/msg05733.html>
>
> - --
> /akr
> -----BEGIN PGP SIGNATURE-----
>
> iQIcBAEBCgAGBQJUyqxXAAoJEOyEjtkWi2t6kn8QALQ+ArkbKfTyJ8DFhwYaFj91
> jiU2yJJbQCZeZ7pro+8fXrhD21lTDtWw+D8gbRlggR4HBsOnfNYrrekpBtV13MEC
> yoKIdBFaOdl9ZVRHrPyipS8NU6fMt2VDIUMXDzyZKExL0imwqiSbT6SiUKxy4b3c
> os+KrGlkuW5lr1nc1p2opQF2Xfcv39kE5AKb//rYz0vlqIMNrVYAsti/tPtfas7Z
> mxDihbaEf5Pw7ravkSsJkHLDotUOvAaf3QLOzIMnbJaNdRTdPlwxd+CMA832lxvO
> r1zas7YUJg0HqO19UDY5Kv34G6Nt5TfuNPjsLI0Zz5D7l4jCedTQQYHSfdozIMtO
> OQ734xxTyUa4aERTdrMwyE7izUPz0Eh0t79YlaFnMM0lh7DhcI+Fw0Tw/IOrZCrN
> id8HgtLS/rXr9hj30MqX35WR+29EbOqLuyvCsQhkW18Z9bbR0/Xl2aviRrZTm7CZ
> ZixzRZLb9cMtk1rXae8OKe9bf6GeZAWV7btD2+ju/3KD96YG7ZB6qJMCUIn5hT2c
> ToOoLibvxGQTAhG/yDudd685ZMGnJy1kOvm4zoPZyGZ1Zo1U/prWCG/PuIqUjqiH
> 7aEgkFxsFUYs0eo89eX5dJHrxIsL6L6Pl6jEYVyvhjeATaenz6eP8CHBRnlej+yi
> yFmsKUUiWIZempHK+R25
> =1f7h
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin