kg_prime.c

cryptlib安全工具包

					INOUT BN_MONT_CTX *montCTX_n )
	{
	int i, bnStatus = BN_STATUS;

	assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
	assert( isWritePtr( a, sizeof( BIGNUM ) ) );
	assert( isReadPtr( n, sizeof( BIGNUM ) ) );
	assert( isReadPtr( n_1, sizeof( BIGNUM ) ) );
	assert( isReadPtr( u, sizeof( BIGNUM ) ) );
	assert( isReadPtr( montCTX_n, sizeof( BN_MONT_CTX ) ) );

	REQUIRES( k >= 1 && k <= bytesToBits( CRYPT_MAX_PKCSIZE ) );

	/* x(0) = a^u mod n.  If x(0) == 1 || x(0) == n - 1 it's probably
	   prime */
	CK( BN_mod_exp_mont( a, a, u, n, pkcInfo->bnCTX, montCTX_n ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );
	if( BN_is_one( a ) || !BN_cmp( a, n_1 ) )
		return( FALSE );		/* Probably prime */

	for( i = 1; i < k; i++ )
		{
		/* x(i) = x(i-1)^2 mod n */
		CK( BN_mod_mul( a, a, a, n, pkcInfo->bnCTX ) );
		if( bnStatusError( bnStatus ) )
			return( getBnStatus( bnStatus ) );
		if( !BN_cmp( a, n_1 ) )
			return( FALSE );	/* Probably prime */
		if( BN_is_one( a ) )
			return( TRUE );		/* Composite */
		}

	return( TRUE );
	}

/* Perform noChecks iterations of the Miller-Rabin probabilistic primality 
   test (n = candidate prime, a = randomly-chosen check value):

	evaluate u s.t. n - 1 = 2^k * u, u odd

	for i = 1 to noChecks
		if witness( a, n, n-1, u, k )
			return "composite"

	return "prime"

  Destroys tmp1-3, mont1 */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
int primeProbable( INOUT PKC_INFO *pkcInfo, 
				   INOUT BIGNUM *n, 
				   IN_RANGE( 1, 100 ) const int noChecks )
	{
	BIGNUM *a = &pkcInfo->tmp1, *n_1 = &pkcInfo->tmp2, *u = &pkcInfo->tmp3;
	int i, k, iterationCount, bnStatus = BN_STATUS, status;

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

	REQUIRES( noChecks >= 1 && noChecks <= 100 );

	/* Set up various values */
	CK( BN_MONT_CTX_set( &pkcInfo->montCTX1, n, pkcInfo->bnCTX ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* Evaluate u as n - 1 = 2^k * u.  Obviously the less one bits in the 
	   LSBs of n the more efficient this test becomes, however with a 
	   randomly-chosen n value we get an exponentially-decreasing chance 
	   of losing any bits after the first one, which will always be zero 
	   since n starts out being odd */
	CKPTR( BN_copy( n_1, n ) );
	CK( BN_sub_word( n_1, 1 ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );
	for( k = 1, iterationCount = 0; 
		 !BN_is_bit_set( n_1, k ) && \
			iterationCount < FAILSAFE_ITERATIONS_MAX;
		 k++, iterationCount++  );
	ENSURES( iterationCount < FAILSAFE_ITERATIONS_MAX );
	CK( BN_rshift( u, n_1, k ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* Perform n iterations of Miller-Rabin */
	for( i = 0; i < noChecks; i++ )
		{
		/* 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 a1*a2 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.   In theory in order to use the first 
		   noChecks small primes as the base instead of using random bignum 
		   bases we would have to assume that the extended Riemann 
		   hypothesis holds (without this, which allows us to use values 
		   1 < check < 2 * log( candidate )^2, we'd have to pick random 
		   check values as required for Monte Carlo algorithms), however the 
		   requirement for random bases assumes that the candidates could be 
		   chosen maliciously to be pseudoprime to any reasonable list of 
		   bases, thus requiring random bases to evade the problem.  
		   Obviously we're not going to do this so one base is as good as 
		   another, and small primes work well (even a single Fermat test 
		   has a failure probability of around 10e-44 for 512-bit primes if 
		   you're not trying to cook the primes, this is why Fermat works as 
		   a verification of the Miller-Rabin test in generatePrime()) */
		CK( BN_set_word( a, primes[ i ] ) );
		if( bnStatusError( bnStatus ) )
			return( getBnStatus( bnStatus ) );
		status = witness( pkcInfo, a, n, n_1, u, k, &pkcInfo->montCTX1 );
		if( cryptStatusError( status ) )
			return( status );
		if( status )
			return( FALSE );	/* It's not a prime */
		}

	/* It's prime */
	return( TRUE );
	}

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

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
int generatePrime( INOUT PKC_INFO *pkcInfo, 
				   INOUT BIGNUM *candidate, 
				   IN_LENGTH_SHORT_MIN( 120 ) const int noBits, 
				   IN_INT_OPT const long exponent )
	{
	MESSAGE_DATA msgData;
	const int noChecks = getNoPrimeChecks( noBits );
	BOOLEAN *sieveArray, primeFound = FALSE;
	int offset, oldOffset = 0, startPoint, iterationCount;
	int bnStatus = BN_STATUS, status;

	assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
	assert( isWritePtr( candidate, sizeof( BIGNUM ) ) );
	
	REQUIRES( noBits >= 120 && noBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
			  /* The value of 120 doesn't correspond to any key size but is 
			     the minimal value for a prime that we'd generate using the 
				 Lim-Lee algorithm */
	REQUIRES( exponent == CRYPT_UNUSED || \
			  ( exponent >= 17 && exponent < INT_MAX - 1000 ) );

	/* Start with a cryptographically strong odd random number ("There is a 
	   divinity in odd numbers", William Shakespeare, "Merry Wives of 
	   Windsor").  We set the two high bits so that (when generating RSA 
	   keys) pq will end up exactly 2n bits long */
	status = generateBignum( candidate, noBits, 0xC0, 0x1 );
	if( cryptStatusError( status ) )
		return( status );

	/* Allocate the array */
	if( ( sieveArray = clAlloc( "generatePrime", \
								SIEVE_SIZE * sizeof( BOOLEAN ) ) ) == NULL )
		return( CRYPT_ERROR_MEMORY );

	for( iterationCount = 0; 
		 !primeFound && iterationCount < FAILSAFE_ITERATIONS_MAX; 
		 iterationCount++ )
		{
		int innerIterationCount;

		/* Set up the sieve array for the number and pick a random starting
		   point */
		initSieve( sieveArray, SIEVE_SIZE, candidate );
		setMessageData( &msgData, &startPoint, sizeof( int ) );
		status = krnlSendMessage( SYSTEM_OBJECT_HANDLE,
								  IMESSAGE_GETATTRIBUTE_S, &msgData,
								  CRYPT_IATTRIBUTE_RANDOM );
		if( cryptStatusError( status ) )
			break;
		startPoint &= SIEVE_SIZE - 1;
		if( startPoint <= 0 )
			startPoint = 1;		/* Avoid getting stuck on zero */

		/* Perform a random-probing search for a prime (poli, poli, di 
		   umbuendo).  "On generation of probably primes by incremental
		   search" by J鴕gen Brandt and Ivan Damg錼d, Proceedings of
		   Crypto'92, (LNCS Vol.740), p.358, shows that for an n-bit
		   number we'll find a prime after O( n ) steps by incrementing
		   the start value by 2 each time */
		for( offset = nextEntry( startPoint ), innerIterationCount = 0; \
			 offset != startPoint && innerIterationCount < SIEVE_SIZE + 1; \
			 offset = nextEntry( offset ), innerIterationCount++ )
			{
#ifdef CHECK_PRIMETEST
			LARGE_INTEGER tStart, tStop;
			BOOLEAN passedFermat, passedOldPrimeTest;
			int oldTicks, newTicks, ratio;
#endif /* CHECK_PRIMETEST */
			long remainder;

			ENSURES( offset > 0 && offset < SIEVE_SIZE );
			ENSURES( offset != oldOffset );

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

			/* Adjust the candidate by the number of nonprimes that we've
			   skipped */
			if( offset > oldOffset )
				CK( BN_add_word( candidate, ( offset - oldOffset ) * 2 ) );
			else
				CK( BN_sub_word( candidate, ( oldOffset - offset ) * 2 ) );
			oldOffset = offset;
			if( bnStatusError( bnStatus ) )
				{
				status = getBnStatus( bnStatus );
				break;
				}

#if defined( CHECK_PRIMETEST )
			/* 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).  At the moment it's only 
			   used to sanity-check the MR test but if a faster version is 
			   ever made available it can be used as a filter to weed out 
			   most pseudoprimes */
			CK( BN_MONT_CTX_set( &pkcInfo->montCTX1, candidate, 
								 pkcInfo->bnCTX ) );
			CK( BN_set_word( &pkcInfo->tmp1, 2 ) );
			CK( BN_mod_exp_mont( &pkcInfo->tmp2, &pkcInfo->tmp1, candidate, 
								 candidate, pkcInfo->bnCTX,
								 &pkcInfo->montCTX1 ) );
			passedFermat = ( bnStatusOK( bnStatus ) && \
						     BN_is_word( &pkcInfo->tmp2, 2 ) ) ? TRUE : FALSE;

			/* Perform the older probabalistic test */
			QueryPerformanceCounter( &tStart );
			status = primeProbableOld( pkcInfo, candidate, noChecks );
			QueryPerformanceCounter( &tStop );
			assert( tStart.HighPart == tStop.HighPart );
			oldTicks = tStop.LowPart - tStart.LowPart;
			if( cryptStatusError( status ) )
				break;
			passedOldPrimeTest = status;

			/* Perform the probabalistic test */
			QueryPerformanceCounter( &tStart );
			status = primeProbable( pkcInfo, candidate, noChecks );
			QueryPerformanceCounter( &tStop );
			assert( tStart.HighPart == tStop.HighPart );
			newTicks = tStop.LowPart - tStart.LowPart;
			ratio = ( oldTicks * 100 ) / newTicks;
			printf( "%4d bits, old MR = %6d ticks, new MR = %6d ticks, "
					"ratio = %d.%d\n", noBits, oldTicks, newTicks, 
					ratio / 100, ratio % 100 );
			if( status != passedFermat || status != passedOldPrimeTest )
				{
				printf( "Fermat reports %d, old Miller-Rabin reports %d, "
						"new Miller-Rabin reports %d.\n", 
						passedFermat, passedOldPrimeTest, status );
				getchar();
				}
#else
			status = primeProbable( pkcInfo, candidate, noChecks );
#endif /* CHECK_PRIMETEST */
			if( cryptStatusError( status ) )
				break;
			if( status == FALSE )
				continue;				/* It's not a prime */

			ENSURES( status == TRUE );	/* It's prime */

			/* If it's not for RSA use, we've found our candidate */
			if( exponent == CRYPT_UNUSED )
				{
				/* status == TRUE from above */
				primeFound = TRUE;
				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 */
			CK( BN_sub_word( candidate, 1 ) );
			remainder = BN_mod_word( candidate, exponent );
			CK( BN_add_word( candidate, 1 ) );
			if( bnStatusError( bnStatus ) )
				{
				status = getBnStatus( bnStatus );
				break;
				}
			if( remainder > 0 )
				{
				/* status == TRUE from above */
				primeFound = TRUE;
				break;
				}
			}
		ENSURES( innerIterationCount < SIEVE_SIZE + 1 );
		}
	ENSURES( iterationCount < FAILSAFE_ITERATIONS_MAX );
	ENSURES( cryptStatusError( status ) || primeFound );

	/* Clean up */
	zeroise( sieveArray, SIEVE_SIZE * sizeof( BOOLEAN ) );
	clFree( "generatePrime", sieveArray );
	return( cryptStatusError( status ) ? status : CRYPT_OK );
	}

/****************************************************************************
*																			*
*							Generate a Random Bignum						*
*																			*
****************************************************************************/

/* Generate a bignum of a specified length with the given high and low 8 
   bits.  'high' is merged into the high 8 bits of the number (set it to 0x80
   to ensure that the number is exactly 'bits' bits long, i.e. 2^(bits-1) <=
   bn < 2^bits), 'low' is merged into the low 8 bits (set it to 1 to ensure
   that the number is odd).  In almost all cases used in cryptlib, 'high' is
   set to 0xC0 and low is set to 0x01.

   We don't need to pagelock the bignum buffer that we're using because it's 
   being accessed continuously while there's data in it so there's little 
   chance that it'll be swapped unless the system is already thrashing */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
int generateBignum( INOUT BIGNUM *bn, 
					IN_LENGTH_SHORT_MIN( 120 ) const int noBits, 
					IN_BYTE const int high, IN_BYTE const int low )
	{
	MESSAGE_DATA msgData;
	BYTE buffer[ CRYPT_MAX_PKCSIZE + 8 ];
	int noBytes = bitsToBytes( noBits ), status;

	assert( isWritePtr( bn, sizeof( BIGNUM ) ) );

	REQUIRES( noBits >= 120 && noBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
			  /* The value of 120 doesn't correspond to any key size but is 
			     the minimal value for a prime that we'd generate using the 
				 Lim-Lee algorithm */
	REQUIRES( high > 0 && high <= 0xFF );
	REQUIRES( low >= 0 && low <= 0xFF );
			  /* The lower bound may be zero if we're generating e.g. a 
			     blinding value or some similar non-key-data value */

	/* Clear the return value */
	BN_zero( bn );

	/* Load the random data into the bignum buffer */
	setMessageData( &msgData, buffer, noBytes );
	status = krnlSendMessage( SYSTEM_OBJECT_HANDLE, IMESSAGE_GETATTRIBUTE_S, 
							  &msgData, CRYPT_IATTRIBUTE_RANDOM );
	if( cryptStatusError( status ) )
		{
		zeroise( buffer, noBytes );
		return( status );
		}

	/* Merge in the specified low bits, mask off any excess high bits, and
	   merge in the specified high bits.  This is a bit more complex than
	   just masking in the byte values because the bignum may not be a
	   multiple of 8 bytes long */
	buffer[ noBytes - 1 ] |= low;
	buffer[ 0 ] &= 0xFF >> ( -noBits & 7 );
	buffer[ 0 ] |= high >> ( -noBits & 7 );
	if( noBits & 7 )
		buffer[ 1 ] |= ( high << ( noBits & 7 ) ) & 0xFF;

	/* Turn the contents of the buffer into a bignum */
	status = extractBignum( bn, buffer, noBytes, max( noBytes - 8, 1 ),
							CRYPT_MAX_PKCSIZE, NULL, FALSE );
	zeroise( buffer, noBytes );
	return( status );
	}