dhprimes.c

Netscape公司提供的安全套接字层

/****

These groups were generated by Colin Plumb and are taken from
the following posting to sci.crypt:

    Date: 15 Jun 1996 21:25:18 -0600
    From: [e-mail] (Colin Plumb)
    Subject: Re: Diffie-Hellman public values
    Organization: University of Denver, Dept. of Math & Comp. Sci.
    Newsgroups: sci.crypt
    
    In article <4ptjjn$[e-mail]>,
    Peter Gutmann <[e-mail]> wrote:
    > Does anyone know of any recognised, non-draft standard with published values
    > for 512, 1024, 2048, and 4096-bit primes suitable for DH?
    
    Since I came up with the primes for SKIP (which are the same ones as
    in PGPfone), perhaps I can help.  I didn't know of any either, so I
    devised a simple variant of Kravitz' "kosherizer" for generating SHA
    keys.  The process is as follows:
    
    - Pick a seed value, a string of bytes.
    - Take the SHA.1 hash of the seed value, and make that the low 160 bits
      of the number.
    - Increment the last byte of the seed value (carrying to the second-last
      byte as needed) and hash again.  This produces bits 160..319.
    - Repeat until you have enough bits.
    - Set the two most significant bits to force the number into the desired
      range.
    - Search for the next largest p with q = (p-1)/2 also prime.  This lets you
      use short exponents safely and 2 as a generator, which offer speed
      advantages in practice.
    
    Unless you assume that I can break SHA.1 and pick an innocuous-looking
    seed value which generates a sneakily easy-to-take-discrete-logs number,
    this generates a prime which is random except for the parameters I searched
    for, namely two MSBs set to 1 (to make it large) and a strong prime.
    
    The seed value was chosen by Philip Zimmermann.  It is the 79 ASCII bytes
    of a quote from Gandhi:
    
    Whatever you do will be insignificant, but it is very important that you do it.
    
    This technique is documented in the PGPfone manual and the SKIP draft.
    I designed it to be simple and defensible, and follow Kravitz where
    there was no reason to differ.  Using linear search speeds up the
    generation of the primes greatly, so people *can* verify these results,
    without hurting the numbers as far as I am aware, although they are just
    slightly less uniform.
    
    The primes I have generated from this seed are listed below as C arrays of
    big-endian bytes.
    
    > While I'm on the lookout for magic numbers, does anyone have test vectors for
    > DESX?
    
    If you have DES, I'm sure you can generate them manually.
    --
            -Colin

****/

/*
 * These time figures, except for the 4096-bit prime, are for
 * a 50 MHz SPARC processor.
 */
/* 256-bit time = 2 sec. */
unsigned char prime256[256/8] = {
        0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
        0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
        0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
        0xA2, 0x5E, 0xC3, 0x55, 0xE9, 0x28, 0x54, 0x03
};

/* 512-bit time = 22 sec. */
unsigned char prime512[512/8] = {
        0xF5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
        0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
        0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
        0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
        0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
        0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
        0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
        0xA2, 0x5E, 0xC3, 0x55, 0xE9, 0x2A, 0x05, 0x5F
};

/* 768-bit time = 105 sec. (1:45) */
unsigned char prime768[768/8] = {
        0xF3, 0xC9, 0x23, 0xC0, 0x43, 0xF0, 0xA5, 0x5B,
        0x18, 0x8D, 0x8E, 0xBB, 0x55, 0x8C, 0xB8, 0x5D,
        0x38, 0xD3, 0x34, 0xFD, 0x7C, 0x17, 0x57, 0x43,
        0xA3, 0x1D, 0x18, 0x6C, 0xDE, 0x33, 0x21, 0x2C,
        0xB5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
        0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
        0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
        0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
        0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
        0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
        0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
        0xA2, 0x5E, 0xC3, 0x55, 0xE9, 0x2B, 0x1A, 0xB3
};

/* 1024-bit time = 499 sec.  (8:19) */
unsigned char prime1024[1024/8] = {
        0xF4, 0x88, 0xFD, 0x58, 0x4E, 0x49, 0xDB, 0xCD,
        0x20, 0xB4, 0x9D, 0xE4, 0x91, 0x07, 0x36, 0x6B,
        0x33, 0x6C, 0x38, 0x0D, 0x45, 0x1D, 0x0F, 0x7C,
        0x88, 0xB3, 0x1C, 0x7C, 0x5B, 0x2D, 0x8E, 0xF6,
        0xF3, 0xC9, 0x23, 0xC0, 0x43, 0xF0, 0xA5, 0x5B,
        0x18, 0x8D, 0x8E, 0xBB, 0x55, 0x8C, 0xB8, 0x5D,
        0x38, 0xD3, 0x34, 0xFD, 0x7C, 0x17, 0x57, 0x43,
        0xA3, 0x1D, 0x18, 0x6C, 0xDE, 0x33, 0x21, 0x2C,
        0xB5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
        0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
        0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
        0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
        0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
        0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
        0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
        0xA2, 0x5E, 0xC3, 0x55, 0xE9, 0x2F, 0x78, 0xC7
};

/* 1280-bit time = 632 sec. (10:32) */
unsigned char prime1280[1280/8] = {
        0xE1, 0xCE, 0x7C, 0xC9, 0x66, 0xFF, 0x15, 0xF9,
        0xBB, 0xFD, 0x91, 0x5E, 0xC7, 0x01, 0xAA, 0xD3,
        0x5B, 0x9E, 0x8D, 0xA0, 0xA5, 0x72, 0x3A, 0xD4,
        0x1A, 0xF0, 0xBF, 0x46, 0x00, 0x58, 0x2B, 0xE5,
        0xF4, 0x88, 0xFD, 0x58, 0x4E, 0x49, 0xDB, 0xCD,
        0x20, 0xB4, 0x9D, 0xE4, 0x91, 0x07, 0x36, 0x6B,
        0x33, 0x6C, 0x38, 0x0D, 0x45, 0x1D, 0x0F, 0x7C,
        0x88, 0xB3, 0x1C, 0x7C, 0x5B, 0x2D, 0x8E, 0xF6,
        0xF3, 0xC9, 0x23, 0xC0, 0x43, 0xF0, 0xA5, 0x5B,
        0x18, 0x8D, 0x8E, 0xBB, 0x55, 0x8C, 0xB8, 0x5D,
        0x38, 0xD3, 0x34, 0xFD, 0x7C, 0x17, 0x57, 0x43,
        0xA3, 0x1D, 0x18, 0x6C, 0xDE, 0x33, 0x21, 0x2C,
        0xB5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
        0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
        0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
        0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
        0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
        0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
        0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
        0xA2, 0x5E, 0xC3, 0x55, 0xE9, 0x2C, 0xA6, 0x6F
};

/* 1536-bit time = 10787 sec. (2:59:47) */
unsigned char prime1536[1536/8] = {
        0xF8, 0xF5, 0x59, 0x5F, 0xDC, 0x76, 0x52, 0x4F,
        0x3D, 0x3D, 0x8D, 0xDB, 0xCE, 0x99, 0xE1, 0x57,
        0x92, 0x59, 0xCD, 0xFD, 0xB8, 0xAE, 0x74, 0x4F,
        0xC5, 0xFC, 0x76, 0xBC, 0x83, 0xC5, 0x47, 0x30,
        0x61, 0xCE, 0x7C, 0xC9, 0x66, 0xFF, 0x15, 0xF9,
        0xBB, 0xFD, 0x91, 0x5E, 0xC7, 0x01, 0xAA, 0xD3,
        0x5B, 0x9E, 0x8D, 0xA0, 0xA5, 0x72, 0x3A, 0xD4,
        0x1A, 0xF0, 0xBF, 0x46, 0x00, 0x58, 0x2B, 0xE5,
        0xF4, 0x88, 0xFD, 0x58, 0x4E, 0x49, 0xDB, 0xCD,
        0x20, 0xB4, 0x9D, 0xE4, 0x91, 0x07, 0x36, 0x6B,
        0x33, 0x6C, 0x38, 0x0D, 0x45, 0x1D, 0x0F, 0x7C,
        0x88, 0xB3, 0x1C, 0x7C, 0x5B, 0x2D, 0x8E, 0xF6,
        0xF3, 0xC9, 0x23, 0xC0, 0x43, 0xF0, 0xA5, 0x5B,
        0x18, 0x8D, 0x8E, 0xBB, 0x55, 0x8C, 0xB8, 0x5D,
        0x38, 0xD3, 0x34, 0xFD, 0x7C, 0x17, 0x57, 0x43,
        0xA3, 0x1D, 0x18, 0x6C, 0xDE, 0x33, 0x21, 0x2C,
        0xB5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
        0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
        0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
        0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
        0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
        0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,