kg_dlp.c

cryptlib安全工具包

			   currently indexed random primes */
			for( i = indexMoved; bnStatusOK( bnStatus ) && 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 );
				if( cryptStatusError( status ) )
					goto cleanup;
				if( status == TRUE )
					{
					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 of 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 of the indices 
			   below the one that we moved down and move them up so that 
			   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 && \
			   innerIterationCount++ < ( FAILSAFE_ITERATIONS_LARGE * 10 ) );
		ENSURES( innerIterationCount < ( FAILSAFE_ITERATIONS_LARGE * 10 ) );

		/* 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( DEBUG_WARN );
				status = CRYPT_ERROR_FAILED;
				goto cleanup;
				}
			status = generatePrime( pkcInfo, &llPrimes[ nPrimes++ ], factorBits, 
									CRYPT_UNUSED );
			if( cryptStatusError( status ) )
				goto cleanup;
			}
		}
	while( !primeFound && iterationCount++ < FAILSAFE_ITERATIONS_LARGE );
	ENSURES( iterationCount < FAILSAFE_ITERATIONS_LARGE );

	/* Recover the original value of q by dividing by 2 and find a generator 
	   suitable for p and q */
	CK( BN_rshift1( q, q ) );
	if( bnStatusError( bnStatus ) )
		{
		status = getBnStatus( bnStatus );
		goto cleanup;
		}
	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, MAX_NO_PRIMES * sizeof( BIGNUM ) );
	zeroise( llProducts, MAX_NO_FACTORS * sizeof( BIGNUM ) );

	return( status );
	}

/* Generate the DLP private value x */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int generateDLPPrivateValue( INOUT PKC_INFO *pkcInfo )
	{
	BIGNUM *x = &pkcInfo->dlpParam_x, *q = &pkcInfo->dlpParam_q; 
	const int qBits = BN_num_bits( q );
	int bnStatus = BN_STATUS, status;

	assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );

	/* 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 
	   that 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 that 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 ) );
	}

/* Finish setting up a DLP key */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int completeInitDLPkey( INOUT CONTEXT_INFO *contextInfoPtr,
							   const BOOLEAN calculateY )
	{
	PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
	int bnStatus = BN_STATUS;

	/* Evaluate the Montgomery form of p and calculate y if required */
	CK( BN_MONT_CTX_set( &pkcInfo->dlpParam_mont_p, &pkcInfo->dlpParam_p, 
						 pkcInfo->bnCTX ) );
	if( bnStatusOK( bnStatus ) && calculateY )
		{
		CK( BN_mod_exp_mont( &pkcInfo->dlpParam_y, &pkcInfo->dlpParam_g,
							 &pkcInfo->dlpParam_x, &pkcInfo->dlpParam_p, 
							 pkcInfo->bnCTX, &pkcInfo->dlpParam_mont_p ) );
		}
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* Enable side-channel protection if required */
	if( !( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION ) )
		return( CRYPT_OK );
	return( enableSidechannelProtection( pkcInfo ) );
	}

/* Generate a generic DLP key */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
int generateDLPkey( INOUT CONTEXT_INFO *contextInfoPtr, 
					IN_LENGTH_SHORT_MIN( MIN_PKCSIZE * 8 ) const int keyBits )
	{
	PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
	int status;

	assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );

	REQUIRES( keyBits >= bytesToBits( MIN_PKCSIZE ) && \
			  keyBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );

	/* Generate the domain parameters */
	pkcInfo->keySizeBits = keyBits;
	status = generateDLPPublicValues( pkcInfo, keyBits );
	if( cryptStatusError( status ) )
		return( status );

	/* Generate the private key */
	status = generateDLPPrivateValue( pkcInfo );
	if( cryptStatusError( status ) )
		return( status );

	/* Finish setting up the key */
	return( completeInitDLPkey( contextInfoPtr, TRUE ) );
	}

/****************************************************************************
*																			*
*							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 */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
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 length, bnStatus = BN_STATUS;

	assert( isReadPtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );

	/* 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_FLAG_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:

		pLen >= MIN_PKCSIZE, pLen <= CRYPT_MAX_PKCSIZE.

		2 <= g <= p - 2.
		PKCS #3 keys: g < 256.  This isn't strictly necessary but use of g 
			in DH typically sets g = 2, the only reason for setting it to a 
			larger value is either stupidity or a deliberate DoS, neither of 
			which we want to encourage.
		Non-PKCS #3 keys: g a generator of order q when the q parameter is 
			present.  FIPS 186/X9.42 use a g the same size as p so we can't
			limit the size.

		y < p */
	length = BN_num_bytes( p );
	if( isShortPKCKey( length ) )
		{
		/* Special-case handling for insecure-sized public keys */
		return( CRYPT_ERROR_NOSECURE );
		}
	if( length < MIN_PKCSIZE || length > CRYPT_MAX_PKCSIZE )
		return( CRYPT_ARGERROR_STR1 );
	if( 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 )
		{
		if( BN_num_bits( g ) > 8 )
			return( CRYPT_ARGERROR_STR1 );
		}
	else
		{
		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 );
		}
	if( BN_cmp( &pkcInfo->dlpParam_y, p ) >= 0 )
		return( CRYPT_ARGERROR_STR1 );

	/* Make sure that the private key value is valid */
	if( !( contextInfoPtr->flags & CONTEXT_FLAG_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 */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
int initDLPkey( INOUT 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;
	BOOLEAN calculateY = FALSE;

	assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );

	/* 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 = generateDLPPrivateValue( pkcInfo );
		if( cryptStatusError( status ) )
			return( status );
		contextInfoPtr->flags &= ~CONTEXT_FLAG_ISPUBLICKEY;
		calculateY = TRUE;
		}

	/* 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 */
	if( BN_is_zero( &pkcInfo->dlpParam_y ) && \
		( BN_is_zero( p ) || BN_is_zero( g ) || BN_is_zero( x ) ) )
		return( CRYPT_ARGERROR_STR1 );

	pkcInfo->keySizeBits = BN_num_bits( p );

	/* Finish setting up the key.  The use of the calculateY value here is
	   a bit odd because it'll cause any existing y value to be overwritten
	   by a new one based on the newly-generated x value.  This means that 
	   if we load a DH key from a certificate constaining an existing y 
	   value then this process will overwrite the value with a new one, so
	   that the context associated with the certificate will contain a y 
	   value that differs from the one in the certificate.  This is 
	   unfortunate, but again because of the DH key duality we need to have
	   both an x and a y value present otherwise the key is useless, and in
	   order to get an x value we have to recreate the y value */
	return( completeInitDLPkey( contextInfoPtr, calculateY ) );
	}