From: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Message-Id: <D1EFFB24-C4C1-4595-8F5A-A2834BBA8217@shiftleft.org>
Date: Tue, 9 Sep 2014 11:27:23 -0700
To: IRTF Crypto Forum Research Group <cfrg@irtf.org>
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1973.6\))
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/TwF3GJ2uH-FHx3m1DtlG7qzXbKc
Subject: [Cfrg] Rigidity and performance
Precedence: list

Hello CFRGers,

I tried to send this last night, and it was delivered to cfrg but =
didn=E2=80=99t go through somehow?  So I=E2=80=99m trying again with an =
abridged version.

It=E2=80=99s been argued a few times here that choosing primes for =
performance (or performance vs security trade-off) is too flexible.  In =
an effort to quantify how flexible this is, I searched for primes which =
could be advanced on these grounds in the range of about 192 to about =
256 bits of security.  Specifically, I searched for primes which have =
something about their shape to recommend them (fast Montgomery or =
Barrett reduction, or Solinas or nearly-Solinas form).  I restricted my =
attention to primes which have the carry-handling properties that DJB =
and I have been recommending, on either 64-bit platforms or both 64-bit =
and 32-bit.

I also searched for numbers which had a nice shape and were not prime =
themselves, but were divisible by a large prime.

I then wrote a partial order on these primes, where one prime is =
potentially better than another if it=E2=80=99s 3 mod 4, or 5 mod 8, or =
larger, or sparser, or has fewer limbs, or has fewer non-1 coefficients, =
or has a Montgomery-friendly or Barrett-friendly or Karatsuba-friendly =
shape.  I eliminated primes which could not be defended because another =
prime in the same class was clearly better on every axis.  For example, =
2^416 - 2^208 - 1 has the same performance as 2^448 - 2^224 - 1 on =
almost any platform, has the same sparsity and shape, the same residue =
mod 8, and so on, but it=E2=80=99s smaller and therefore has a worse =
security vs performance tradeoff.

Surely I missed some, but the goal of this exercise was to determine =
whether the number of primes which can be advanced on security vs =
performance reasons is in the dozens, or in the thousands or millions.  =
Here is what I found:

Performance should be fine on 32-bit or 64-bit machines:
2^521 - 1
  NIST-P521, E-521, of course.

2^392 - 2^280 + 1
  Good on 32-bit or 64-bit machines; 14 or 7 limbs
  This might not be a terrible idea at 192-bit security, since it falls =
within the 4-rho-bit limit set by Kenny.
  Too bad it=E2=80=99s 1 mod 8.

2^414 - 17
  Curve41417.

2^448 - 2^224 - 1
  Ed448-Goldilocks.

 2^416 - 18*2^364 + 1
  This is probably actually terrible, but it=E2=80=99s suitable for =
signed Montgomery reduction.

 2^408 - 13*2^204 - 11
  The best 5-mod-8 not-quite-Solinas-quadratic prime.  Probably =
terrible.

 (2^424 - 2^212 - 1) / 11
  Faster than the above prime but has a =E2=80=9Ccofactor"; clearly =
worse than Goldilocks unless you need 5 mod 8.

Performance is only good on 64-bit machines:
2^406 - 2^174 + 1
  Solinas, 7 limbs.

2^480 - 2^240 - 1=20
  Ed480-Ridinghood.

2^480 - 47
  Nice except that it=E2=80=99s 1 mod 8.

 2^468 - 17
  3 mod 4.  There might be a larger prime with a bigger coefficient; I =
only searched up to -50.

 2^470 - 35
  5 mod 8.

 2^456 - 8*2^399 - 1
  Montgomery form.

As listed, some of these primes are probably not actually good enough to =
be advanced even on performance grounds, but then again, there are =
probably some other options which could be advanced.

Of this baker=E2=80=99s dozen of primes, four have already been proposed =
for cryptographic purposes.  This might just mean I=E2=80=99m not very =
creative, but it might also mean that the space of high-performance =
primes isn=E2=80=99t all that large.

Cheers,
=E2=80=94 Mike