Subject: [Cfrg] Question about primes of special form and the NFS

From: Watson Ladd <[email-masked]>
Date: Sun, 30 Mar 2014 13:43:01 -0700

Dear all,
draft-gillmor-tls-negotiated-dl-dhe-00 contains primes of the form
2^{b}-2^{b-64}+k*2^64-1 for b a multiple of 64 and k small, and
recommends them as DHE groups. This is to close a security hole in TLS
in which no set of DHE parameters exists, and no one realized they
can't be validated.

This is not as bad as primes of the form 2^b-small, for which the SNFS
applies trivially. However, I am worried that some of the speedups
might still happen. It's probably not possible, but I don't know the
state of the art in this area, and would appreciate any references
dealing with extensions of SNFS to numbers that aren't that special.

Sincerely,
Watson Ladd

---

From: Samuel Neves <[email-masked]>
Date: Sun, 30 Mar 2014 22:48:12 +0100

> dealing with extensions of SNFS to numbers that aren't that special.

These primes do look risky. Oliver Schirokauer has done some work on discrete logarithms modulo primes with small signed binary representation [1], which applies in this case.

Manually finding small-coefficient NFS polynomials for these primes also seems plausible, which is what differentiates the SNFS from the GNFS. For example, for the 4096-bit prime p = 2^4096 - 2^4032 + 341664 * 2^64 - 1, degree 8 and m = 2^504, we obtain
the polynomial

(2^64-1) * x^8 + (341664 * 2^64 - 1) * x,

which has significantly better coefficient sizes than a random choice of polynomial.

[1] http://eprint.iacr.org/2006/107