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

From: Watson Ladd <[email-masked]>
Date: Wed, 28 Jan 2015 07:53:05 -0800

Dear all,

The following have been suggested for primes at sizes between 2^255-19
and 2^521-1.

2^521-1
2^512-big
2^448-2^224-1
2^414-17
2^389-21
2^384-big
2^379-19

I'm omitting smaller primes from the list, because I don't think that
2^324-24 is that interesting to anyone, for instance, as the time
taken to compute  a discrete log isn't that much bigger than 2^255-19
and the performance not much better then 2^379-19.

Personally I think 2^521-1 needs to be in there, and 2^379-19 is
reasonable, absent hard numbers showing its terrible. I'm hoping
sometime to get those hard numbers.

I'm assuming we use Edwards with the minimal d and the isogenous
Montgomery curve with small value of a24 for all of these: there
doesn't seem to be a reason not to. We can twist if that produces a
complete curve: it's almost completely irrelevant.

Sincerely,
Watson Ladd

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 29 Jan 2015 21:55:35 +0000

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.

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

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.

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

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

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 30 Jan 2015 21:11:38 +0200

On Thu, Jan 29, 2015 at 09:55:35PM +0000, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 

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

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

> independently. But maybe too slow.

IIRC, there were recent speedups on it, but the figures probably
include those already.
 
> 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