Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?]

On 2014-03-12 04:56, Watson Ladd wrote:
> A few hours? The trick is to sieve: the numbers for various N are in
> an arithmetic progression with a=2^64. As a result, you can determine
> which N are possible because of small prime obstructions, thus
> decreasing the amount of work to be done. In fact, I think your first
> N is entirely determined by considerations modulo the primes less than
> 100.
>
> Secondly look at (p-1)/2=q instead. If this is known prime determining
> if 2*q+1 is prime is quick using Pocklington's Theorem: you don't need
> to do the extensive primality testing.

Exactly, have you tried this?

For the 8192 bit prime, you are to eliminate 4,743,158 candidates. Suppose:

- you are using a double sieve on both primes that eliminates all but 
0.6-0.7% of the candidates,
- you are doing the Fermat test of the Pocklington criterion first, and 
this eliminates all but 1-2% of the remaining candidates,

then this means your search will still be dominated by some 300,000 
modular exponentiations with a 8192 bit modulus and with 8191 bit 
exponents. Let's say a reasonably optimized implementation performs such 
an exponentiation in 400ms on a contemporary PC. This leaves you with an 
expected running time of 20 min.