lib_kg.c

老外写的加密库cryptlib(版本3.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), i.e. 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( PKC_INFO *pkcInfo )
	{
	BIGNUM *p = &pkcInfo->dlpParam_p, *q = &pkcInfo->dlpParam_q;
	BIGNUM *g = &pkcInfo->dlpParam_g;
	BIGNUM *j = &pkcInfo->tmp1, *gCounter = &pkcInfo->tmp2;
	int bnStatus = BN_STATUS;

	/* j = (p - 1) / q */
	CK( BN_sub_word( p, 1 ) );
	CK( BN_div( j, NULL, p, q, &pkcInfo->bnCTX ) );
	CK( BN_add_word( p, 1 ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* 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.  Note that 
	   we can't use a Montgomery modexp at this point since we haven't
	   evaluated the Montgomery form of p yet */
	CK( BN_set_word( gCounter, 2 ) );
	do
		{
		CK( BN_add_word( gCounter, 1 ) );
		CK( BN_mod_exp( g, gCounter, j, p, &pkcInfo->bnCTX ) );
		}
	while( bnStatusOK( bnStatus ) && BN_is_one( g ) );

	return( getBnStatus( bnStatus ) );
	}

/* Generate prime numbers for DLP-based PKC's using the Lim-Lee algorithm:

	p = 2 * q * ( prime[1] * ... prime[n] ) + 1 */

static int generateDLPublicValues( PKC_INFO *pkcInfo, const int pBits, 
								   int qBits, void *callBackArg )
	{
	const int safeExpSizeBits = getDLPexpSize( pBits );
	const int noChecks = getNoPrimeChecks( pBits );
	BIGNUM llPrimes[ MAX_NO_PRIMES ], llProducts[ MAX_NO_FACTORS ];
	BIGNUM *p = &pkcInfo->dlpParam_p, *q = &pkcInfo->dlpParam_q;
	BOOLEAN primeFound = FALSE;
	int indices[ MAX_NO_FACTORS ];
	int nPrimes, nFactors, factorBits, i, bnStatus = BN_STATUS, status;

	assert( p != NULL );
	assert( pBits >= 512 && pBits <= MAX_PKCSIZE_BITS );
	assert( q != NULL );
	assert( ( qBits >= 160 && qBits <= MAX_PKCSIZE_BITS ) || \
			qBits == CRYPT_USE_DEFAULT );
	assert( callBackArg != NULL );
	assert( getDLPexpSize( 512 ) == 160 );
	assert( getDLPexpSize( 1024 ) == 169 );
	assert( getDLPexpSize( 1536 ) == 198 );
	assert( getDLPexpSize( 2048 ) == 225 );
	assert( getDLPexpSize( 3072 ) == 270 );
	assert( getDLPexpSize( 4096 ) == 305 );

	/* If the caller doesn't require a fixed-size q, use the minimum safe
	   exponent size */
	if( qBits == CRYPT_USE_DEFAULT )
		qBits = safeExpSizeBits;

	/* Determine how many factors we need and the size in bits of the 
	   factors */
	factorBits = ( pBits - qBits ) - 1;
	nFactors = nPrimes = ( factorBits / safeExpSizeBits ) + 1;
	factorBits /= nFactors;

	/* Generate a random prime q and multiply by 2 to form the base for the
	   other factors */
	status = generatePrime( pkcInfo, q, qBits, CRYPT_UNUSED, callBackArg );
	if( cryptStatusError( status ) )
		return( status );
	BN_lshift1( q, q );

	/* Set up the permutation control arrays and generate the first nFactors 
	   factors */
	for( i = 0; i < MAX_NO_FACTORS; i++ )
		BN_init( &llProducts[ i ] );
	for( i = 0; i < MAX_NO_PRIMES; i++ )
		BN_init( &llPrimes[ i ] );
	for( i = 0; i < nFactors; i++ )
		{
		status = generatePrime( pkcInfo, &llPrimes[ i ], factorBits, 
								CRYPT_UNUSED, callBackArg );
		if( cryptStatusError( status ) )
			goto cleanup;
		}

	do
		{
		int indexMoved;

		/* Initialize the indices for the permutation.  We try the first 
		   nFactors factors first, since any new primes are added at the end */
		indices[ nFactors - 1 ] = nPrimes - 1;
		for( i = nFactors - 2; i >= 0; i-- )
			indices[ i ] = indices[ i + 1 ] - 1;
		BN_mul( &llProducts[ nFactors - 1 ], q, &llPrimes[ nPrimes - 1 ], 
				&pkcInfo->bnCTX );
		indexMoved = nFactors - 2;

		/* Test all possible new prime permutations until a prime is found or 
		   we run out of permutations */
		do
			{
			/* Assemble a new candidate prime 2 * q * primes + 1 from the 
			   currently indexed random primes */
			for( i = indexMoved; i >= 0; i-- )
				CK( BN_mul( &llProducts[ i ], &llProducts[ i + 1 ],
							&llPrimes[ indices[ i ] ], &pkcInfo->bnCTX ) );
			CKPTR( BN_copy( p, &llProducts[ 0 ] ) );
			CK( BN_add_word( p, 1 ) );
			if( bnStatusError( bnStatus ) )
				{
				status = getBnStatus( bnStatus );
				goto cleanup;
				}

			/* If the candidate has a good chance of being prime, try a
			   probabilistic test and exit if it succeeds */
			if( primeSieve( p ) )
				{
				status = primeProbable( pkcInfo, p, noChecks, callBackArg );
				if( cryptStatusError( status ) )
					goto cleanup;
				if( status )
					{
					primeFound = TRUE;
					break;
					}
				}

			/* Find the lowest index which is not already at the lowest 
			   possible point and move it down one */
			for( i = 0; i < nFactors; i++ )
				if( indices[ i ] > i )
					{
					indices[ i ]--;
					indexMoved = i;
					break;
					}

			/* If we moved down the highest index, we've exhausted all the 
			   permutations so we have to start over with another prime */
			if( ( indexMoved == nFactors - 1 ) || ( i >= nFactors ) )
				break;

			/* We haven't changed the highest index, take all the indices 
			   below the one we moved down and move them up so they're packed 
			   up as high as they'll go */
			for( i = indexMoved - 1; i >= 0; i-- )
				indices[ i ] = indices[ i + 1 ] - 1;
			} 
		while( indices[ nFactors - 1 ] > 0 );

		/* If we haven't found a prime yet, add a new prime to the pool and
		   try again */
		if( !primeFound )
			{
			if( nPrimes >= MAX_NO_PRIMES )
				{
				/* We've run through an extraordinary number of primes, 
				   something is wrong */
				assert( NOTREACHED );
				status = CRYPT_ERROR_FAILED;
				goto cleanup;
				}
			status = generatePrime( pkcInfo, &llPrimes[ nPrimes++ ], factorBits, 
									CRYPT_UNUSED, callBackArg );
			if( cryptStatusError( status ) )
				goto cleanup;
			}
		}
	while( !primeFound );

	/* Recover the original value of q by dividing by 2 and find a generator 
	   suitable for p and q */
	BN_rshift1( q, q );
	status = findGeneratorForPQ( pkcInfo );

cleanup:

	/* Free the local storage */
	for( i = 0; i < nPrimes; i++ )
		BN_clear_free( &llPrimes[ i ] );
	for( i = 0; i < nFactors; i++ )
		BN_clear_free( &llProducts[ i ] );
	zeroise( llPrimes, sizeof( BIGNUM ) * MAX_NO_PRIMES );
	zeroise( llProducts, sizeof( BIGNUM ) * MAX_NO_FACTORS );

	return( status );
	}

/* Generate the DLP private value x */

static int generateDLPrivateValue( PKC_INFO *pkcInfo )
	{
	BIGNUM *x = &pkcInfo->dlpParam_x, *q = &pkcInfo->dlpParam_q; 
	const int qBits = BN_num_bits( q );
	int bnStatus = BN_STATUS, status;

	/* If it's a PKCS #3 DH key, there won't be a q value present, so we have
	   to estimate the appropriate x size in the same way that we estimated
	   the q size when we generated the public key components */
	if( BN_is_zero( q ) )
		return( generateBignum( x, 
					getDLPexpSize( BN_num_bits( &pkcInfo->dlpParam_p ) ),
					0xC0, 0 ) );

	/* Generate the DLP private value x s.t. 2 <= x <= q-2 (this is the
	   lowest common denominator of FIPS 186's 1...q-1 and X9.42's 2...q-2).
	   Because the mod q-2 is expensive we do a quick check to make sure it's
	   really necessary before calling it */
	status = generateBignum( x, qBits, 0xC0, 0 );
	if( cryptStatusError( status ) )
		return( status );
	CK( BN_sub_word( q, 2 ) );
	if( BN_cmp( x, q ) > 0 )
		{
		/* Trim x down to size.  Actually we get the upper bound as q-3,
		   but over a 160-bit (minimum) number range this doesn't matter */
		CK( BN_mod( x, x, q, &pkcInfo->bnCTX ) );

		/* If the value we ended up with is too small, just generate a new
		   value one bit shorter, which guarantees that it'll fit the 
		   criteria (the target is a suitably large random value value, not 
		   the closest possible fit within the range) */
		if( bnStatusOK( bnStatus ) && BN_num_bits( x ) < qBits - 5 )
			status = generateBignum( x, qBits - 1, 0xC0, 0 );
		}
	CK( BN_add_word( q, 2 ) );

	return( cryptStatusError( status ) ? status : getBnStatus( bnStatus ) );
	}

/* Generate a generic DLP key */

int generateDLPkey( CONTEXT_INFO *contextInfoPtr, const int keyBits,
					const int qBits, const BOOLEAN generateDomainParameters )
	{
	PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
	int bnStatus = BN_STATUS, status;

	/* Generate the domain parameters if necessary */
	if( generateDomainParameters )
		{
		pkcInfo->keySizeBits = keyBits;
		status = generateDLPublicValues( pkcInfo, keyBits, qBits, contextInfoPtr );
		if( cryptStatusError( status ) )
			return( status );
		}

	/* Generate the private key */
	assert( contextInfoPtr->capabilityInfo->cryptAlgo == CRYPT_ALGO_DH || \
			!BN_is_zero( &pkcInfo->dlpParam_q ) );
	status = generateDLPrivateValue( pkcInfo );
	if( cryptStatusError( status ) )
		return( status );

	/* Evaluate the Montgomery forms and calculate y */
	BN_MONT_CTX_init( &pkcInfo->dlpParam_mont_p );
	CK( BN_MONT_CTX_set( &pkcInfo->dlpParam_mont_p, &pkcInfo->dlpParam_p, 
						 &pkcInfo->bnCTX ) );
	if( bnStatusOK( bnStatus ) )
		CK( BN_mod_exp_mont( &pkcInfo->dlpParam_y, &pkcInfo->dlpParam_g,
							 &pkcInfo->dlpParam_x, &pkcInfo->dlpParam_p, 
							 &pkcInfo->bnCTX, &pkcInfo->dlpParam_mont_p ) );
	return( getBnStatus( bnStatus ) );
	}

/****************************************************************************
*																			*
*							Initialise/Check a DLP Key						*
*																			*
****************************************************************************/

/* Check DLP parameters when loading a key.  We have to make the PKC_INFO
   data non-const because the bignum code wants to modify some of the values 
   as it's working with them */

int checkDLPkey( const CONTEXT_INFO *contextInfoPtr, const BOOLEAN isPKCS3 )
	{
	PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
	BIGNUM *p = &pkcInfo->dlpParam_p, *g = &pkcInfo->dlpParam_g;
	BIGNUM *tmp = &pkcInfo->tmp1;
	int bnStatus = BN_STATUS;

	/* Make sure that the necessary key parameters have been initialised.  
	   Since PKCS #3 doesn't use the q parameter, we only require it for 
	   algorithms that specifically use FIPS 186 values */
	if( BN_is_zero( p ) || BN_is_zero( g ) || \
		BN_is_zero( &pkcInfo->dlpParam_y ) || \
		( !( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) && \
		  BN_is_zero( &pkcInfo->dlpParam_x ) ) )
		return( CRYPT_ARGERROR_STR1 );
	if( !isPKCS3 && BN_is_zero( &pkcInfo->dlpParam_q ) )
		return( CRYPT_ARGERROR_STR1 );

	/* Make sure that the key paramters are valid: p > MIN_PKCSIZE_BITS 
	   (nominally 512 bits), 2 <= g <= p-2, and g a generator of order q if 
	   the q parameter is present (i.e. it's a non-PKCS #3 key) */
	if( BN_num_bits( p ) < MIN_PKCSIZE_BITS || BN_num_bits( g ) < 2 )
		return( CRYPT_ARGERROR_STR1 );
	CKPTR( BN_copy( tmp, p ) );
	CK( BN_sub_word( tmp, 1 ) );
	if( bnStatusError( bnStatus ) || BN_cmp( g, tmp ) >= 0 )
		return( CRYPT_ARGERROR_STR1 );
	if( !isPKCS3 )
		{
		CK( BN_mod_exp_mont( tmp, g, &pkcInfo->dlpParam_q, p, &pkcInfo->bnCTX,
							 &pkcInfo->dlpParam_mont_p ) );
		if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
			return( CRYPT_ARGERROR_STR1 );
		}

	/* Make sure that the private key value is valid */
	if( !( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) )
		{
		CK( BN_mod_exp_mont( tmp, g, &pkcInfo->dlpParam_x, p, &pkcInfo->bnCTX,
							 &pkcInfo->dlpParam_mont_p ) );
		if( bnStatusError( bnStatus ) || BN_cmp( tmp, &pkcInfo->dlpParam_y ) )
			return( CRYPT_ARGERROR_STR1 );
		}

	return( CRYPT_OK );
	}

/* Initialise a DLP key */

int initDLPkey( CONTEXT_INFO *contextInfoPtr, const BOOLEAN isDH )
	{
	PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
	BIGNUM *p = &pkcInfo->dlpParam_p, *g = &pkcInfo->dlpParam_g;
	BIGNUM *x = &pkcInfo->dlpParam_x;
	int bnStatus = BN_STATUS;

	/* If it's a DH key and there's no x value present, generate one 
	   implicitly.  This is needed because all DH keys are effectively 
	   private keys.  We also update the context flags to reflect the
	   change in status */
	if( isDH && BN_is_zero( x ) )
		{
		int status;

		status = generateDLPkey( contextInfoPtr, CRYPT_UNUSED, CRYPT_UNUSED,
								 FALSE );
		if( cryptStatusError( status ) )
			return( status );
		contextInfoPtr->flags &= ~CONTEXT_ISPUBLICKEY;
		contextInfoPtr->flags |= CONTEXT_ISPRIVATEKEY;
		}

	/* Some sources (specifically PKCS #11) don't make y available for
	   private keys, so if the caller is trying to load a private key with a
	   zero y value, we calculate it for them.  First, we check to make sure
	   that we have the values available to calculate y.  We calculate y 
	   itself once we have the Montogomery form of p set up */
	if( BN_is_zero( &pkcInfo->dlpParam_y ) && \
		( BN_is_zero( p ) || BN_is_zero( g ) || BN_is_zero( x ) ) )
		return( CRYPT_ARGERROR_STR1 );

	/* Evaluate the Montgomery form and calculate y if necessary */
	BN_MONT_CTX_init( &pkcInfo->dlpParam_mont_p );
	CK( BN_MONT_CTX_set( &pkcInfo->dlpParam_mont_p, p, &pkcInfo->bnCTX ) );
	if( bnStatusOK( bnStatus ) && BN_is_zero( &pkcInfo->dlpParam_y ) )
		CK( BN_mod_exp_mont( &pkcInfo->dlpParam_y, g, x, p, &pkcInfo->bnCTX, 
							 &pkcInfo->dlpParam_mont_p ) );

	pkcInfo->keySizeBits = BN_num_bits( p );
	return( getBnStatus( bnStatus ) );
	}