pqg.c

来自「支持SSL v2/v3, TLS, PKCS #5, PKCS #7, PKCS」· C语言 代码 · 共 666 行 · 第 1/2 页

/*
 * The contents of this file are subject to the Mozilla Public
 * License Version 1.1 (the "License"); you may not use this file
 * except in compliance with the License. You may obtain a copy of
 * the License at http://www.mozilla.org/MPL/
 * 
 * Software distributed under the License is distributed on an "AS
 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * rights and limitations under the License.
 * 
 * The Original Code is the Netscape security libraries.
 * 
 * The Initial Developer of the Original Code is Netscape
 * Communications Corporation.	Portions created by Netscape are 
 * Copyright (C) 1994-2000 Netscape Communications Corporation.  All
 * Rights Reserved.
 * 
 * Contributor(s):
 * 
 * Alternatively, the contents of this file may be used under the
 * terms of the GNU General Public License Version 2 or later (the
 * "GPL"), in which case the provisions of the GPL are applicable 
 * instead of those above.	If you wish to allow use of your 
 * version of this file only under the terms of the GPL and not to
 * allow others to use your version of this file under the MPL,
 * indicate your decision by deleting the provisions above and
 * replace them with the notice and other provisions required by
 * the GPL.  If you do not delete the provisions above, a recipient
 * may use your version of this file under either the MPL or the
 * GPL.
 */

/*
 * PQG parameter generation/verification.  Based on FIPS 186-1.
 *
 * $Id: pqg.c,v 1.5 2000/09/29 04:03:34 nelsonb%netscape.com Exp $
 */

#include "prerr.h"
#include "secerr.h"

#include "prtypes.h"
#include "blapi.h"
#include "secitem.h"
#include "mpi.h"
#include "mpprime.h"
#include "mplogic.h"
#include "secmpi.h"

#define MAX_ITERATIONS 5  /* Maximum number of iterations of primegen */
#define NUMITER        40 /* Number iterations for primality tests    */

 /* XXX to be replaced by define in blapit.h */
#define BITS_IN_Q 160

/* For FIPS-compliance testing.
** The following array holds the seed defined in FIPS 186-1 appendix 5.
** This seed is used to generate P and Q according to appendix 2; use of
** this seed will exactly generate the PQG specified in appendix 2.
*/
#ifdef FIPS_186_1_A5_TEST
static const unsigned char fips_186_1_a5_pqseed[] = {
    0xd5, 0x01, 0x4e, 0x4b, 0x60, 0xef, 0x2b, 0xa8,
    0xb6, 0x21, 0x1b, 0x40, 0x62, 0xba, 0x32, 0x24,
    0xe0, 0x42, 0x7d, 0xd3
};
#endif

/* Get a seed for generating P and Q.  If in testing mode, copy in the
** seed from FIPS 186-1 appendix 5.  Otherwise, obtain bytes from the
** global random number generator.
*/
static SECStatus
getPQseed(SECItem *seed)
{
    if (seed->data) {
        PORT_Free(seed->data);
        seed->data = NULL;
    }
    seed->data = (unsigned char*)PORT_ZAlloc(seed->len);
    if (!seed->data) {
	PORT_SetError(SEC_ERROR_NO_MEMORY);
	return SECFailure;
    }
#ifdef FIPS_186_1_A5_TEST
    memcpy(seed->data, fips_186_1_a5_pqseed, seed->len);
    return SECSuccess;
#else
    return RNG_GenerateGlobalRandomBytes(seed->data, seed->len);
#endif
}

/* Generate a candidate h value.  If in testing mode, use the h value
** specified in FIPS 186-1 appendix 5, h = 2.  Otherwise, obtain bytes
** from the global random number generator.
*/
static SECStatus
generate_h_candidate(SECItem *hit, mp_int *H)
{
    SECStatus rv = SECSuccess;
    mp_err   err = MP_OKAY;
#ifdef FIPS_186_1_A5_TEST
    memset(hit->data, 0, hit->len);
    hit->data[hit->len-1] = 0x02;
#else
    rv = RNG_GenerateGlobalRandomBytes(hit->data, hit->len);
#endif
    if (rv)
	return SECFailure;
    err = mp_read_unsigned_octets(H, hit->data, hit->len);
    if (err) {
	MP_TO_SEC_ERROR(err);
	return SECFailure;
    }
    return SECSuccess;
}

/* Compute SHA[(SEED + addend) mod 2**g]
** Result is placed in shaOutBuf.
** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 .
*/
static SECStatus
addToSeedThenSHA(const SECItem * seed,
                 unsigned long   addend,
                 int             g,
                 unsigned char * shaOutBuf)
{
    SECItem str = { 0, 0, 0 };
    mp_int s, sum, modulus, tmp;
    mp_err    err = MP_OKAY;
    SECStatus rv  = SECSuccess;
    MP_DIGITS(&s)       = 0;
    MP_DIGITS(&sum)     = 0;
    MP_DIGITS(&modulus) = 0;
    MP_DIGITS(&tmp)     = 0;
    CHECK_MPI_OK( mp_init(&s) );
    CHECK_MPI_OK( mp_init(&sum) );
    CHECK_MPI_OK( mp_init(&modulus) );
    SECITEM_TO_MPINT(*seed, &s); /* s = seed */
    /* seed += addend */
    if (addend < MP_DIGIT_MAX) {
	CHECK_MPI_OK( mp_add_d(&s, (mp_digit)addend, &s) );
    } else {
	CHECK_MPI_OK( mp_init(&tmp) );
	CHECK_MPI_OK( mp_set_ulong(&tmp, addend) );
	CHECK_MPI_OK( mp_add(&s, &tmp, &s) );
    }
    CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)g, NULL, &sum) );/*sum = s mod 2**g */
    MPINT_TO_SECITEM(&sum, &str, NULL);
    rv = SHA1_HashBuf(shaOutBuf, str.data, str.len); /* SHA1 hash result */
cleanup:
    mp_clear(&s);
    mp_clear(&sum);
    mp_clear(&modulus);
    mp_clear(&tmp);
    if (str.data)
	SECITEM_ZfreeItem(&str, PR_FALSE);
    if (err) {
	MP_TO_SEC_ERROR(err);
	return SECFailure;
    }
    return rv;
}

/*
**  Perform steps 2 and 3 of FIPS 186, appendix 2.2.
**  Generate Q from seed.
*/
static SECStatus
makeQfromSeed(
      unsigned int  g,          /* input.  Length of seed in bits. */
const SECItem   *   seed,       /* input.  */
      mp_int    *   Q)          /* output. */
{
    unsigned char sha1[SHA1_LENGTH];
    unsigned char sha2[SHA1_LENGTH];
    unsigned char U[SHA1_LENGTH];
    SECStatus rv  = SECSuccess;
    mp_err    err = MP_OKAY;
    int i;
    /* ******************************************************************
    ** Step 2.
    ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
    **/
    CHECK_SEC_OK( SHA1_HashBuf(sha1, seed->data, seed->len) );
    CHECK_SEC_OK( addToSeedThenSHA(seed, 1, g, sha2) );
    for (i=0; i<SHA1_LENGTH; ++i) 
	U[i] = sha1[i] ^ sha2[i];
    /* ******************************************************************
    ** Step 3.
    ** "Form Q from U by setting the most signficant bit (the 2**159 bit)
    **  and the least signficant bit to 1.  In terms of boolean operations,
    **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160."
    */
    U[0]             |= 0x80;  /* U is MSB first */
    U[SHA1_LENGTH-1] |= 0x01;
    err = mp_read_unsigned_octets(Q, U, SHA1_LENGTH);
cleanup:
     memset(U, 0, SHA1_LENGTH);
     memset(sha1, 0, SHA1_LENGTH);
     memset(sha2, 0, SHA1_LENGTH);
     if (err) {
	MP_TO_SEC_ERROR(err);
	return SECFailure;
     }
     return rv;
}

/*  Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.
**  Generate P from Q, seed, L, and offset.
*/
static SECStatus
makePfromQandSeed(
      unsigned int  L,          /* Length of P in bits.  Per FIPS 186. */
      unsigned int  offset,     /* Per FIPS 186, appendix 2.2. */
      unsigned int  g,          /* input.  Length of seed in bits. */
const SECItem   *   seed,       /* input.  */
const mp_int    *   Q,          /* input.  */
      mp_int    *   P)          /* output. */
{
    unsigned int  k;            /* Per FIPS 186, appendix 2.2. */
    unsigned int  n;            /* Per FIPS 186, appendix 2.2. */
    mp_digit      b;            /* Per FIPS 186, appendix 2.2. */
    unsigned char V_k[SHA1_LENGTH];
    mp_int        W, X, c, twoQ, V_n, tmp;
    mp_err    err = MP_OKAY;
    SECStatus rv  = SECSuccess;
    /* Initialize bignums */
    MP_DIGITS(&W)     = 0;
    MP_DIGITS(&X)     = 0;
    MP_DIGITS(&c)     = 0;
    MP_DIGITS(&twoQ)  = 0;
    MP_DIGITS(&V_n)   = 0;
    MP_DIGITS(&tmp)   = 0;
    CHECK_MPI_OK( mp_init(&W)    );
    CHECK_MPI_OK( mp_init(&X)    );
    CHECK_MPI_OK( mp_init(&c)    );
    CHECK_MPI_OK( mp_init(&twoQ) );
    CHECK_MPI_OK( mp_init(&tmp)  );
    CHECK_MPI_OK( mp_init(&V_n)  );
    /* L - 1 = n*160 + b */
    n = (L - 1) / BITS_IN_Q;
    b = (L - 1) % BITS_IN_Q;
    /* ******************************************************************
    ** Step 7.
    **  "for k = 0 ... n let
    **           V_k = SHA[(SEED + offset + k) mod 2**g]."
    **
    ** Step 8.
    **  "Let W be the integer 
    **    W = V_0 + (V_1 * 2**160) + ... + (V_n-1 * 2**((n-1)*160)) 
    **         + ((V_n mod 2**b) * 2**(n*160))
    */
    for (k=0; k<n; ++k) { /* Do the first n terms of V_k */
	/* Do step 7 for iteration k.
	** V_k = SHA[(seed + offset + k) mod 2**g]
	*/
	CHECK_SEC_OK( addToSeedThenSHA(seed, offset + k, g, V_k) );
	/* Do step 8 for iteration k.
	** W += V_k * 2**(k*160)
	*/
	OCTETS_TO_MPINT(V_k, &tmp, SHA1_LENGTH);      /* get bignum V_k     */
	CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, k*160) );   /* tmp = V_k << k*160 */
	CHECK_MPI_OK( mp_add(&W, &tmp, &W) );         /* W += tmp           */
    }
    /* Step 8, continued.
    **   [W += ((V_n mod 2**b) * 2**(n*160))] 
    */
    CHECK_SEC_OK( addToSeedThenSHA(seed, offset + n, g, V_k) );
    OCTETS_TO_MPINT(V_k, &V_n, SHA1_LENGTH);          /* get bignum V_n     */
    CHECK_MPI_OK( mp_div_2d(&V_n, b, NULL, &tmp) );   /* tmp = V_n mod 2**b */
    CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, n*160) );       /* tmp = tmp << n*160 */
    CHECK_MPI_OK( mp_add(&W, &tmp, &W) );             /* W += tmp           */
    /* Step 8, continued.
    ** "and let X = W + 2**(L-1).
    **  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
    */
    CHECK_MPI_OK( mpl_set_bit(&X, (mp_size)(L-1), 1) );    /* X = 2**(L-1) */
    CHECK_MPI_OK( mp_add(&X, &W, &X) );                    /* X += W       */
    /*************************************************************
    ** Step 9.
    ** "Let c = X mod 2q  and set p = X - (c - 1).
    **  Note that p is congruent to 1 mod 2q."
    */
    CHECK_MPI_OK( mp_mul_2(Q, &twoQ) );                    /* 2q           */
    CHECK_MPI_OK( mp_mod(&X, &twoQ, &c) );                 /* c = X mod 2q */
    CHECK_MPI_OK( mp_sub_d(&c, 1, &c) );                   /* c -= 1       */
    CHECK_MPI_OK( mp_sub(&X, &c, P) );                     /* P = X - c    */
cleanup:
    mp_clear(&W);
    mp_clear(&X);
    mp_clear(&c);
    mp_clear(&twoQ);
    mp_clear(&V_n);
    mp_clear(&tmp);
    if (err) {
	MP_TO_SEC_ERROR(err);
	return SECFailure;
    }
    return rv;
}

/*
** Generate G from h, P, and Q.
*/
static SECStatus
makeGfromH(const mp_int *P,     /* input.  */
           const mp_int *Q,     /* input.  */
                 mp_int *H,     /* input and output. */
                 mp_int *G,     /* output. */
                 PRBool *passed)
{
    mp_int exp, pm1;
    mp_err err = MP_OKAY;
    SECStatus rv = SECSuccess;
    *passed = PR_FALSE;
    MP_DIGITS(&exp) = 0;
    MP_DIGITS(&pm1) = 0;
    CHECK_MPI_OK( mp_init(&exp) );
    CHECK_MPI_OK( mp_init(&pm1) );
    CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) );        /* P - 1            */
    if ( mp_cmp(H, &pm1) > 0)                   /* H = H mod (P-1)  */
	CHECK_MPI_OK( mp_sub(H, &pm1, H) );
    /* Let b = 2**n (smallest power of 2 greater than P).
    ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1
    ** so the above operation safely computes H mod (P-1)
    */
    /* Check for H = to 0 or 1.  Regen H if so.  (Regen means return error). */
    if (mp_cmp_d(H, 1) <= 0) {
	rv = SECFailure;
	goto cleanup;
    }