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

[Samuel Neves <[e-mail]>]

On 30-03-2014 21:43, Watson Ladd wrote:
> 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.

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