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

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.