[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Proposal for new DH Groups 6, 7, and 8


Dear list, 

Markku-Juhani asked for ECPP primality proofs for the 2048, 3072 and
4096 bit primes. They can be found at 

  http://people.ssh.fi/mkojo/

I apologize for the delay.

Best regards, 
Mika Kojo
SSH Communications Security Ltd.


Markku-Juhani Saarinen writes:
> On Sun, 6 Feb 2000, Tero Kivinen wrote:
> 
> > I sent at least the 2048 bit prime to the list earlier, here is the
> > values of the index t for those 2048, 3072 and 4096 bit primes:
> > 
> >  < n, t >: (n = number of bits in prime, t = offset from the pi)
> > ----------------------------------------------------------------------
> >  < 2048, 124476 >
> >  < 3072, 1690314 >
> >  < 4096, 240904 >
> > ----------------------------------------------------------------------
> (..)
> 
> Tero and others,
> 
>   I propose the following minimum exponent sizes to be used with the
>   bigger DH MODP groups:
> 
> 	  Prime        Strength     Exponent
> 	  ---------    --------     --------
>           2048 bits    90 bits      180 bits
> 	  3076 bits    112 bits     224 bits
> 	  4096 bits    128 bits     256 bits
> 
>   I have independently verified that your (and Mika's) primes satisfy
>   all requirements given in RFCs 2412 and 2409. Perhaps it would
>   good also to publish the primality proofs (i.e. ECPP certificates).
> 
>   A brief discussion of minimum exponent sizes w.r.t. DH group strength 
>   is included below. 
> 
> - mj
> 
> Markku-Juhani O. Saarinen <mjos@jyu.fi> University of Jyväskylä, Finland
> 
> 
> Rationale
> ---------
> 
>   There are two distinct ways to attack Diffie-Hellman key agreement
>   in a prime field of order p, where p is a Sophie-Germain prime
>   (i.e. (p-1)/2 is also a prime) [1]:
> 
>   1) Use Pollard's Lambda method to compute discrete logarithms. The
>      asymptotic complexity of this method is O(sqrt(e)), where e is
>      the exponent [2]. Hence the exponent size must be at least
>      twice the required security level.
> 
>   2) Compute discrete logarithms in the prime field using the number
>      field sieve method (NFS). The conjectured complexity of this method
>      is:
> 
>         L_p[0.3333, 1.9223],
> 
>      where L_p is the commonly used notation [3]:
> 
>         L_p[a, b] = exp(b*(log(p))^a * (log(log(p)))^(1-a))
> 
>   We can estimate the NFS constant factor using results presented
>   in [4], where a logarithm was computed in a 427-bit field in
>   roughly 2^46 steps. This constant factor also matches the strength
>   estimates given in RFC 2412 (sect 2.11.1).
> 
>   The following graph illustrates strength / modulus relationship:
> 
>   Strength
>       |'''''''''''''''''''''''''''''''''''''''''''''''''''''''''__xx""
>   160 |                                                  __xxx""     |
>   152 |                                            __xx""            |
>   144 |                                       _xx""                  |
>   136 |                                 __xx""                       |
>   128 |                             _xx"                             |
>   120 |                        __x""                                 |
>   112 |                     _x"                                      |
>   104 |                 _x""                                         |
>    96 |              _x"                                             |
>    88 |           _x"                                                |
>    80 |         x"                                                   |
>    72 |       x"                                                     |
>    64 |     x"                                                       |
>    56 |   _"                                                         |
>    48 |  x                                                           |
>    40 | x                                                            |
>    32 |x                                                             |
>    16 |                                                              |
>     8 x                                                              |
>     0 |                                                              |
>       ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
>       0    1024     2048    3072    4096    5120    6144    7168    8192
>                               Modulus size (bits)
> 
> References
> ----------
> 
> [1] P. C. van Oorschot and M. J. Wiener, "On Diffie-Hellman key agreement
>     with short exponents,", proceedings of EuroCrypt '96,
>     Springer 1996, pp. 332--343
> 
> [2] J. M. Pollard, "Monte Carlo methods for index computation (mod p),"
>     Math. Comp., vol. 32, no. 143 (July 1978), pp. 918--924
> 
> [3] D. Weber, "An Implementation of the General Number Field Sieve
>     to Compute Discrete Logarithms (mod p),", proceedings of EuroCrypt
>     '95, Springer 1995, pp. 95--105
> 
> [4] D. Weber and T. Denny, "The Solution of McCurley's Discrete Log
>     Challenge," proceedings of EuroCrypt '98, Springer 1998
> 
>