lib_kg.c

提供了很多种加密算法和CA认证及相关服务如CMP、OCSP等的开发

	{
	int i;

	for( i = 1; i < FAST_SIEVE_NUMPRIMES; i++ )
		if( !BN_mod_word( ( BIGNUM * ) candidate, primes[ i ] ) )
			return( FALSE );

	return( TRUE );
	}

/* Do a Miller-Rabin probabilistic primality test */

static int primeProbable( BIGNUM *candidate, const int noChecks,
						  void *callbackArg )
	{
	BN_MONT_CTX *montCTX;
	BN_CTX *bnCTX, *bnCTX2;
	BIGNUM *check;
	int i, status;

	/* Allocate the BN and Montgomery contexts and convert the candidate to
	   its Montgomery form */
	if( ( bnCTX = BN_CTX_new() ) == NULL )
		return( CRYPT_ERROR_MEMORY );
	bnCTX2 = BN_CTX_new();
	montCTX = BN_MONT_CTX_new();
	if( bnCTX2 == NULL || montCTX == NULL || \
		!BN_MONT_CTX_set( montCTX, candidate, bnCTX ) )
		{
		BN_CTX_free( bnCTX );
		if( bnCTX2 != NULL )
			BN_CTX_free( bnCTX2 );
		if( montCTX != NULL )
			BN_MONT_CTX_free( montCTX );
		return( CRYPT_ERROR_MEMORY );
		}
	check = bnCTX->bn[ bnCTX->tos++ ];

	/* Perform n iterations of Miller-Rabin */
	for( i = 0; i < noChecks; i++ )
		{
		/* Perform the callback.  We do this befor the Miller-Rabin check
		   to ensure that it always gets called at least once for every
		   call to primeProbable() - since the majority of candidates fail
		   the witness() function, it'd almost never get called after
		   witness() is called */
		status = keygenCallback( callbackArg );
		if( cryptStatusError( status ) )
			break;

		/* Instead of using a bignum for the Miller-Rabin check, we use a
		   series of small primes.  The reason for this is that if bases a1
		   and a2 are strong liars for n then their product a1a2 is also very
		   likely to be a strong liar, so using a composite base doesn't give
		   us any great advantage.  In addition an initial test with a=2 is
		   beneficial since most composite numbers will fail Miller-Rabin
		   with a=2, and exponentiation with base 2 is faster than general-
		   purpose exponentiation.  Finally, using small values instead of
		   random bignums is both significantly more efficient and much
		   easier on the RNG.   For these reasons we use the first noChecks
		   small primes as the base instead of using random bignum bases */
		BN_set_word( check, primes[ i ] );
		status = witness( check, candidate, bnCTX, bnCTX2, montCTX );
		if( cryptStatusError( status ) )
			break;
		if( status )
			{
			/* It's not a prime */
			status = FALSE;
			break;
            }
		}

	/* If we made it through all the checks, it's a prime */
	if( i == noChecks )
		status = TRUE;

	/* Free everything */
	bnCTX->tos--;
	BN_MONT_CTX_free( montCTX );
	BN_CTX_free( bnCTX2 );
	BN_CTX_free( bnCTX );

	return( status );
	}

/* Witness function, stolen from original BN code */

static int witness(a,n,ctx,ctx2,mont)
BIGNUM *a;
BIGNUM *n;
BN_CTX *ctx,*ctx2;
BN_MONT_CTX *mont;
    {
	int k,i,ret= -1,good;
    BIGNUM *d,*dd,*tmp,*d1,*d2,*n1;
    BIGNUM *mont_one,*mont_n1,*mont_a;

    d1=ctx->bn[ctx->tos];
    d2=ctx->bn[ctx->tos+1];
    n1=ctx->bn[ctx->tos+2];
    ctx->tos+=3;

    mont_one=ctx2->bn[ctx2->tos];
    mont_n1=ctx2->bn[ctx2->tos+1];
    mont_a=ctx2->bn[ctx2->tos+2];
    ctx2->tos+=3;

    d=d1;
    dd=d2;
    if (!BN_one(d)) goto err;
    if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */
    k=BN_num_bits(n1);

    if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err;
    if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err;
    if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err;

    BN_copy(d,mont_one);
    for (i=k-1; i>=0; i--)
        {
        if (    (BN_cmp(d,mont_one) != 0) &&
            (BN_cmp(d,mont_n1) != 0))
            good=1;
        else
            good=0;

        BN_mod_mul_montgomery(dd,d,d,mont,ctx2);

		if (good && (BN_cmp(dd,mont_one) == 0))
            {
			ret=1;
            goto err;
            }
        if (BN_is_bit_set(n1,i))
            {
            BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2);
            }
        else
            {
            tmp=d;
            d=dd;
            dd=tmp;
            }
        }
    if (BN_cmp(d,mont_one) == 0)
        i=0;
    else    i=1;
    ret=i;
err:
    ctx->tos-=3;
    ctx2->tos-=3;
	return(ret);
	}

/* Generate a prime.  If exponent != 0, this will also verify that
   gcd( (p - 1)(q - 1), exponent ) = 1, which is required for RSA */

int generateRSAPrime( BIGNUM *candidate, const int noBits,
					  const long exponent, void *callbackArg )
	{
	RESOURCE_DATA msgData;
	const int noChecks = getNoPrimeChecks( noBits );
	BOOLEAN *sieveArray = NULL;
	int offset, oldOffset = 0, startPoint, status;

	/* Start with a cryptographically strong odd random number.  We set the
	   two high bits so that pq will end up exactly 2n bits long */
	status = generateBignum( candidate, noBits, 0xC0, 0x1 );
	if( cryptStatusError( status ) )
		return( status );

	do
		{
		/* Set up the sieve array for the number and pick a random starting
		   point */
		sieveArray = initSieve( sieveArray, candidate );
		if( sieveArray == NULL )
			return( CRYPT_ERROR_MEMORY );
		setResourceData( &msgData, &startPoint, sizeof( int ) );
		status = krnlSendMessage( SYSTEM_OBJECT_HANDLE,
								  RESOURCE_IMESSAGE_GETATTRIBUTE_S, &msgData,
								  CRYPT_IATTRIBUTE_RANDOM );
		if( cryptStatusError( status ) )
			break;
		startPoint &= SIEVE_SIZE - 1;

		/* Perform a random-probing search for a prime */
		for( offset = nextEntry( startPoint ); offset != startPoint;
			 offset = nextEntry( offset ) )
			{
			long remainder;

			/* If this candidate is divisible by anything, continue */
			if( sieveArray[ offset ] )
				continue;

			/* Adjust the candidate by the number of nonprimes we've
			   skipped */
			if( offset > oldOffset )
				BN_add_word( candidate, ( offset - oldOffset ) * 2 );
			else
				BN_sub_word( candidate, ( oldOffset - offset ) * 2 );
			oldOffset = offset;

			/* Perform a Fermat test to the base 2 (Fermat = a^p-1 mod p == 1
			   -> a^p mod p == a, for all a), which isn't as reliable as
			   Miller-Rabin but may be quicker if a fast base 2 modexp is
			   available (currently it provides no improvement at all over the
			   use of straight Miller-Rabin).  If a faster version is
			   available, it serves as a convenient filter to weed out most
			   pseudoprimes */
#ifdef USE_FERMAT
			{
			BN_CTX *bnCTX = BN_CTX_new();
			BIGNUM *tmp = BN_new(), *two = BN_new();

			BN_set_word( two, 2 );
			BN_mod_exp( tmp, two, candidate, candidate, bnCTX );
			status = BN_is_word( tmp, 2 );

			BN_clear_free( two );
			BN_clear_free( tmp );
			BN_CTX_free( bnCTX );
			if( !status )
				continue;
			}
#endif /* USE_FERMAT */

			/* Perform the probabalistic test */
			status = primeProbable( candidate, noChecks, callbackArg );
			if( cryptStatusError( status ) )
				break;
			if( !status )
				continue;

			/* If it's not for RSA use, we've found our candidate */
			if( !exponent )
				break;

			/* It's for use with RSA, check the RSA condition that
			   gcd( p - 1, exp ) == 1.  Since exp is a small prime, we can do
			   this efficiently by checking that ( p - 1 ) mod exp != 0 */
			BN_sub_word( candidate, 1 );
			remainder = BN_mod_word( candidate, exponent );
			BN_add_word( candidate, 1 );
			if( remainder )
				break;	/* status = TRUE from above */
			}
		}
	while( status == FALSE );	/* -ve = error, TRUE = success */

	endSieve( sieveArray );
	return( ( status == TRUE ) ? CRYPT_OK : status );
	}

/****************************************************************************
*																			*
*			  					Generate DL Primes							*
*							Copyright Kevin J Bluck 1998					*
*					Hacked to death since then: Peter Gutmann				*
*																			*
****************************************************************************/

/* DLP-based PKC's have various requirements for the generated parameters:

	DSA: p, q, and g of preset lengths (currently p isn't fixed at exactly
		n * 64 bits because of the way the Lim-Lee algorithm works, it's
		possible to get this by iterating the multiplication step until the
		result is exactly n * 64 bits but this doesn't seem worth the
		effort), x = 1...q-1.
	PKCS #3 DH: No g (it's fixed at 2) or q.  This is "real" DH (rather than
		the DSA-hack version) but doesn't seem to be used by anything.  Keys
		of this type can be generated if required, but the current code is
		configured to always generate X9.42 DH keys.
	X9.42 DH: p, q, and g as for DSA but without the 160-bit SHA-enforced
		upper limit on q so that p can go above 1024 bits, x = 2...q-2.
	Elgamal: As X9.42 DH */

/* The maximum number of factors required to generate a prime using the Lim-
   Lee algorithm.  The value 160 is the minimum safe exponent size */

#define MAX_NO_FACTORS	( ( ( CRYPT_MAX_PKCSIZE * 8 ) / 160 ) + 1 )

/* Select a generator g for the prime moduli p and q.  g will be chosen so
   that it is of prime order q, where q divides (p - 1), ie g generates the
   subgroup of order q in the multiplicative group of GF(p) (traditionally
   for PKCS #3 DH g is fixed at 2, which is safe even when it's not a
   primitive root since it still covers half of the space of possible
   residues, however we always generate a FIPS 186-style g value) */

static int findGeneratorForPQ( BIGNUM *p, BIGNUM *q, BIGNUM *g )
	{
	BN_CTX *bnCTX;
	BIGNUM *j, *gCounter;

	/* Allocate the bignums and context */
	if( ( bnCTX = BN_CTX_new() ) == NULL )
		return( CRYPT_ERROR_MEMORY );
	j = BN_new();
	gCounter = BN_new();
	if( j == NULL || gCounter == NULL )
		{
		BN_CTX_free( bnCTX );
		if( j != NULL )
			BN_free( j );
		if( gCounter != NULL )
			BN_free( gCounter );
		return( CRYPT_ERROR_MEMORY );
		}

	/* j = (p - 1) / q */
	BN_sub_word( p, 1 );
	BN_div( j, NULL, p, q, bnCTX );
	BN_add_word( p, 1 );

	/* Starting gCount at 3, set g = (gCount ^ j) mod p until g != 1.
	   Although FIPS 196/X9.30/X9.42 merely require that 1 < g < p-1, if we
	   use small integers it makes this operation much faster */
	BN_set_word( gCounter, 2 );
	do
		{
		BN_add_word( gCounter, 1 );
		BN_mod_exp( g, gCounter, j, p, bnCTX );
		}
	while( BN_is_one( g ) );

	/* Clean up */
	BN_clear_free( j );
	BN_clear_free( gCounter );
	BN_CTX_free( bnCTX );
	return( CRYPT_OK );
	}