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

[Watson Ladd <watsonbladd%gmail.com@localhost>]

On Tue, Mar 11, 2014 at 6:18 PM, Henrick Hellström <henrick%streamsec.se@localhost> wrote:
>
> On 2014-03-11 23:14, Daniel Kahn Gillmor wrote:
>>
>> More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of
>> pi, followed by 64 more bits of 0xFF.  I don't know why this sequence
>> was selected.  Does anyone have any pointers to reasons you might want
>> the modulus structured this way?
>
>
> - If the least significant word of the modulus equals 2^w-1, Montgomery reduction becomes more efficient.
> - If the most significant word of the modulus equals 2^w-1, school-book reduction and Barrett reduction becomes more efficient.
> - Pi usually plays the role of a "nothing-up-my-sleeve" value. If a random value had been chosen, there would have been no easy way to verify that a specially crafted value hadn't been chosen. For instance, it is possible to generate a prime, such that the discrete logarithm of selected smooth numbers becomes to known to the entity generating the prime, and that would make the discrete logarithm problem easier for that entity.
>
>
>>
>> i haven't yet generated these (mainly due to time):
>>
>>  * 4096-bit (MODP 16)
>>  * 6144-bit (MODP 17)
>>  * 8192-bit (MODP 18)
>
>
> Python is likely too slow for this. Generating the 8192 bit prime takes a couple of hours on a contemporary PC using reasonably optimized native code.

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.

Sincerely,
Watson Ladd
>
>
> _______________________________________________
> TLS mailing list
> TLS%ietf.org@localhost
> https://www.ietf.org/mailman/listinfo/tls




-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin