lib_kg.c

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

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

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

   Generation of the q and g values is optional, they are ignored if NULL */

static int generateDLPublicValues( BIGNUM *p, const int pBits, BIGNUM *q,
								   int qBits, BIGNUM *g,
								   CRYPT_INFO *cryptInfo )
	{
	const int safeExpSizeBits = getDLPexpSize( pBits );
	const int noChecks = getNoPrimeChecks( pBits );
	BIGNUM *products[ MAX_NO_FACTORS ], **primes;
	BOOLEAN primeFound = FALSE;
	int indices[ MAX_NO_FACTORS ];
	int nPrimes, nAllocatedPrimes, nFactors = 1, factorBits, i, status;

	int indexMoved;

	assert( p != NULL );
	assert( pBits >= 512 && pBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
	assert( q != NULL );
	assert( ( qBits >= 160 && qBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) ) || \
			qBits == CRYPT_USE_DEFAULT );
	assert( g != NULL );
	assert( cryptInfo != NULL );

	/* 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 (it appears that we need an even
	   number of factors, so we reduce it to the next even number) and the
	   size in bits of the factors */
	while( ( pBits - qBits - 1 ) / nFactors  >= safeExpSizeBits )
		nFactors++;
	nFactors = nPrimes = ( nFactors - 1 ) & ~1;
	factorBits = ( ( pBits - qBits ) - 1 ) / nFactors;

	/* When we allocate storage for the primes, we overallocate by a useful
	   amount to save having to reallocate the prime array every time we
	   generate a new one.  The following allocates at least 16 more values
	   than the minimum necessary, rounded up to the nearest multiple of 16.
	   Every time we need more primes after this, we allocate another chunk
	   of 16 values */
	nAllocatedPrimes = ( nPrimes + 32 ) & ~15;

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

	/* Set up the permutation control arrays */
	status = CRYPT_ERROR_MEMORY;
	if( ( primes = malloc( nAllocatedPrimes * sizeof( BIGNUM  * ) ) ) == NULL )
		return( CRYPT_ERROR_MEMORY );
	for( i = 0; i < nFactors; i++ )
		if( ( products[ i ] = BN_new() ) == NULL )
			{
			nFactors = i;	/* Remember how far we got */
			goto cleanup;
			}

	/* Generate the first nFactors factors */
	for( i = 0; i < nFactors; i++ )
		{
		if( ( primes[ i ] = BN_new() ) != NULL )
			status = generateRSAPrime( primes[ i ], factorBits, 0,
									   cryptInfo );
		if( cryptStatusError( status ) )
			{
			nPrimes = i;	/* Remember how far we got */
			goto cleanup;
			}
		}

	do
	{
		/* Initialize indices for permutation. We try first the nFactors
		   number of potential factors which are highest in the list, since
		   new primes are always added to the end of the list. */
		indices[nFactors - 1] = nPrimes - 1;
		for (i = nFactors - 2; i >= 0; i--)
			indices[i] = indices[i + 1] - 1;
		BN_mul(products[nFactors - 1], q, primes[nPrimes - 1]);
		indexMoved = nFactors - 2;

		/* Test all the currently new possible prime permutations until a
		   prime is found or we run out of permutations. */
		do
		{
			/* Assemble a new candidate prime from the currently indexed
			   random primes */
			for( i = indexMoved; i >= 0; i-- )
				BN_mul( products[ i ], products[ i + 1 ],
						primes[ indices[ i ] ] );
			BN_copy( p, products[ 0 ] );
			BN_add_word( p, 1 );

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

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

			/* If we did not change the highest index, take all the indices
			   below the one we moved down, and move them all up so they're
			   packed up as high as they will go. If we moved down the highest
			   index, then we're done with all the permutations, so break the
			   loop to generate another prime and start over.  */
			if ((indexMoved != nFactors - 1) && (i < nFactors))
			{
				for (i = indexMoved - 1; i >= 0; i--)
					indices[i] = indices[i + 1] - 1;
			}
			else
				break;

		} while (indices[nFactors - 1]);

		/* If we haven't found a prime yet, add a new prime to the pool and
		   try again */
		if( !primeFound )
			{
			/* If there's not enough room for the new prime, expand the
			   existing storage */
			status = CRYPT_ERROR_MEMORY;
			if( nPrimes + 1 > nAllocatedPrimes )
				{
				BIGNUM **newPrimes;

				nAllocatedPrimes += 16;
				newPrimes = malloc( nAllocatedPrimes * sizeof( BIGNUM * ) );
				if( newPrimes == NULL )
					goto cleanup;
				memcpy( newPrimes, primes, nPrimes * sizeof( BIGNUM * ) );
				free( primes );
				primes = newPrimes;
				}

			/* Allocate and generate the new prime */
			if( ( primes[ nPrimes ] = BN_new() ) == NULL )
				goto cleanup;
			nPrimes++;
			status = generateRSAPrime( primes[ nPrimes - 1 ], factorBits, 0,
									   cryptInfo );
			if( cryptStatusError( status ) )
				goto cleanup;
			}
		}
	while( !primeFound );

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

cleanup:

	/* Free the local storage */
	for( i = 0; i < nPrimes; i++ )
		if( primes[ i ] != NULL )
			BN_clear_free( primes[ i ] );
	free( primes );
	for( i = 0; i < nFactors; i++ )
		if( products[ i ] != NULL )
			BN_clear_free( products[ i ] );

	return( cryptStatusError( status ) ? status : CRYPT_OK );
	}

/* Generate the DLP private value x */

static int generateDLPrivateValue( BIGNUM *x, BIGNUM *q )
	{
	const int qBits = BN_num_bits( q );
	int status;

	/* 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 bnMod() 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 );
	BN_sub_word( q, 2 );
	if( BN_cmp( x, q ) > 0 )
		{
		BN_CTX *bnCTX = BN_CTX_new();

		/* 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 */
		if( bnCTX != NULL )
			{
			BN_mod( x, x, q, bnCTX );
			BN_CTX_free( bnCTX );
			}

		/* If the value we ended up with is too small, just generate a new
		   value one bit shorter which guarantees it'll fit the criteria
		   (the target is a suitably large random value value, not the
		   closest possible fit within the range).  This also allows us to
		   recover from memory allocation errors in a nicer way than just
		   returning an error */
		if( bnCTX == NULL || BN_num_bits( x ) < qBits - 5 )
			status = generateBignum( x, qBits - 1, 0xC0, 0 );
		}
	BN_add_word( q, 2 );

	return( CRYPT_OK );
	}

/* Generate a generic DLP key */

int generateDLPKey( CRYPT_INFO *cryptInfo, const int keyBits,
					const int qBits, const BOOLEAN generateDomainParameters )
	{
	int status;

	/* Generate the domain parameters if necessary */
	if( generateDomainParameters )
		{
		cryptInfo->ctxPKC.keySizeBits = keyBits;
		status = generateDLPublicValues( cryptInfo->ctxPKC.dlpParam_p, keyBits,
										 cryptInfo->ctxPKC.dlpParam_q, qBits,
										 cryptInfo->ctxPKC.dlpParam_g, cryptInfo );
		if( cryptStatusError( status ) )
			return( status );
		}

	/* Generate the private key */
	status = generateDLPrivateValue( cryptInfo->ctxPKC.dlpParam_x,
									 cryptInfo->ctxPKC.dlpParam_q );
	if( cryptStatusOK( status ) )
		{
		BN_CTX *bnCTX = BN_CTX_new();

		if( bnCTX == NULL )
			return( CRYPT_ERROR_MEMORY );
		BN_mod_exp( cryptInfo->ctxPKC.dlpParam_y, cryptInfo->ctxPKC.dlpParam_g,
					cryptInfo->ctxPKC.dlpParam_x, cryptInfo->ctxPKC.dlpParam_p,
					bnCTX );
		BN_CTX_free( bnCTX );
		}
	if( cryptStatusError( status ) )
		return( status );
	cryptInfo->ctxPKC.isPublicKey = FALSE;
	return( CRYPT_OK );
	}

/* Check DLP parameters when loading a key.  This should really be in a
   hypothetical lib_dlp.c but in its abscence this seems to be the best place
   for it */

int checkDLParams( const CRYPT_INFO *cryptInfo, const BOOLEAN isPKCS3 )
	{
	BN_CTX *bnCTX;
	BIGNUM *tmp;
	int status = CRYPT_OK;

	/* Make sure the necessary key parameters have been initialised.  Since
	   PKCS #3 doesn't use the q parameter, we only require it for algorithms
	   which specifically use FIPS 186 values */
	if( BN_is_zero( cryptInfo->ctxPKC.dlpParam_p ) || \
		BN_is_zero( cryptInfo->ctxPKC.dlpParam_g ) || \
		BN_is_zero( cryptInfo->ctxPKC.dlpParam_y ) || \
		( !cryptInfo->ctxPKC.isPublicKey && BN_is_zero( cryptInfo->ctxPKC.dlpParam_x ) ) )
		return( CRYPT_ARGERROR_STR1 );
	if( !isPKCS3 && BN_is_zero( cryptInfo->ctxPKC.dlpParam_q ) )
		return( CRYPT_ARGERROR_STR1 );

	/* This isn't used until further on, but we initialise it now to catch
	   memory errors before we're in the middle of the code block */
	if( ( bnCTX = BN_CTX_new() ) == NULL )
		return( CRYPT_ERROR_MEMORY );
	tmp = BN_new();

	/* Make sure the key paramters are valid: p > 510 (nominally 512 bits),
	   2 <= g <= p-2, and g a generator of order q if the q parameter is
	   present */
	if( BN_num_bits( cryptInfo->ctxPKC.dlpParam_p ) < 510 || \
		BN_num_bits( cryptInfo->ctxPKC.dlpParam_g ) < 2 )
		status = CRYPT_ARGERROR_STR1;
	BN_sub_word( cryptInfo->ctxPKC.dlpParam_p, 1 );
	if( BN_cmp( cryptInfo->ctxPKC.dlpParam_g,
				cryptInfo->ctxPKC.dlpParam_p ) >= 0 )
		status = CRYPT_ARGERROR_STR1;
	BN_add_word( cryptInfo->ctxPKC.dlpParam_p, 1 );
	if( cryptStatusOK( status ) && !isPKCS3 )
		{
		BN_mod_exp( tmp, cryptInfo->ctxPKC.dlpParam_g,
					cryptInfo->ctxPKC.dlpParam_q,
					cryptInfo->ctxPKC.dlpParam_p, bnCTX );
		if( !BN_is_one( tmp ) )
			status = CRYPT_ARGERROR_STR1;
		}

	/* Make sure the private key value is valid */
	if( !cryptInfo->ctxPKC.isPublicKey )
		{
		BN_mod_exp( tmp, cryptInfo->ctxPKC.dlpParam_g,
					cryptInfo->ctxPKC.dlpParam_x,
					cryptInfo->ctxPKC.dlpParam_p, bnCTX );
		if( BN_cmp( tmp, cryptInfo->ctxPKC.dlpParam_y ) )
			status = CRYPT_ARGERROR_STR1;
		}

	BN_clear_free( tmp );
	BN_CTX_free( bnCTX );
	return( status );
	}