kg_dlp.c

cryptlib是功能强大的安全工具集。允许开发人员快速在自己的软件中集成加密和认证服务。

/****************************************************************************
*																			*
*				cryptlib DLP Key Generation/Checking Routines				*
*						Copyright Peter Gutmann 1997-2004					*
*																			*
****************************************************************************/

#include <stdlib.h>
#define PKC_CONTEXT		/* Indicate that we're working with PKC context */
#if defined( INC_ALL )
  #include "crypt.h"
  #include "context.h"
  #include "keygen.h"
#elif defined( INC_CHILD )
  #include "../crypt.h"
  #include "context.h"
  #include "keygen.h"
#else
  #include "crypt.h"
  #include "context/context.h"
  #include "context/keygen.h"
#endif /* Compiler-specific includes */

/****************************************************************************
*																			*
*						Determine Discrete Log Exponent Bits				*
*																			*
****************************************************************************/

/* The following function (provided by Colin Plumb) is used to calculate the
   appropriate size exponent for a given prime size which is required to
   provide equivalent security from small-exponent attacks

   This is based on a paper by Michael Wiener on	| The function defined
   the difficulty of the two attacks, which has		| below (not part of the
   the following table:								| original paper)
													| produces the following
	 Table 1: Subgroup Sizes to Match Field Sizes	| results:
													|
	Size of p	Cost of each attack		Size of q	|	Output	Error
	 (bits)		(instructions or		(bits)		|			(+ is safe)
				 modular multiplies)				|
													|
	   512			9 x 10^17			119			|	137		+18
	   768			6 x 10^21			145			|	153		+8
	  1024			7 x 10^24			165			|	169		+4
	  1280			3 x 10^27			183			|	184		+1
	  1536			7 x 10^29			198			|	198		+0
	  1792			9 x 10^31			212			|	212		+0
	  2048			8 x 10^33			225			|	225		+0
	  2304			5 x 10^35			237			|	237		+0
	  2560			3 x 10^37			249			|	249		+0
	  2816			1 x 10^39			259			|	260		+1
	  3072			3 x 10^40			269			|	270		+1
	  3328			8 x 10^41			279			|	280		+1
	  3584			2 x 10^43			288			|	289		+1
	  3840			4 x 10^44			296			|	297		+1
	  4096			7 x 10^45			305			|	305		+0
	  4352			1 x 10^47			313			|	313		+0
	  4608			2 x 10^48			320			|	321		+1
	  4864			2 x 10^49			328			|	329		+1
	  5120			3 x 10^50			335			|	337		+2

   This function fits a curve to this, which overestimates the size of the
   exponent required, but by a very small amount in the important 1000-4000
   bit range.  It is a quadratic curve up to 3840 bits, and a linear curve
   past that.  They are designed to be C(1) (have the same value and the same
   slope) at the point where they meet */

#define AN		1L		/* a = -AN/AD/65536, the quadratic coefficient */
#define AD		3L
#define M		8L		/* Slope = M/256, i.e. 1/32 where linear starts */
#define TX		3840L	/* X value at the slope point, where linear starts */
#define TY		297L	/* Y value at the slope point, where linear starts */

/* For a slope of M at the point (TX,TY), we only have one degree of freedom
   left in a quadratic curve, so use the coefficient of x^2, namely a, as
   that free parameter.

   y = -AN/AD*((x-TX)/256)^2 + M*(x-TX)/256 + TY
	 = -AN*(x-TX)*(x-TX)/AD/256/256 + M*x/256 - M*TX/256 + TY
	 = -AN*x*x/AD/256/256 + 2*AN*x*TX/AD/256/256 - AN*TX*TX/AD/256/256 \
		+ M*x/256 - M*TX/256 + TY
	 = -AN*(x/256)^2/AD + 2*AN*(TX/256)*(x/256)/AD + M*(x/256) \
		- AN*(TX/256)^2/AD - M*(TX/256) + TY
	 = (AN*(2*TX/256 - x/256) + M*AD)*x/256/AD - (AN*(TX/256)/AD + M)*TX/256 \
		+ TY
	 = (AN*(2*TX/256 - x/256) + M*AD)*x/256/AD \
		- (AN*(TX/256) + M*AD)*TX/256/AD + TY
	 =  ((M*AD + AN*(2*TX/256 - x/256))*x - (AN*(TX/256)+M*AD)*TX)/256/AD + TY
	 =  ((M*AD + AN*(2*TX - x)/256)*x - (AN*(TX/256)+M*AD)*TX)/256/AD + TY
	 =  ((M*AD + AN*(2*TX - x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD + TY
	 =  (((256*M*AD+2*AN*TX-AN*x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD + TY

   Since this is for the range 0...TX, in order to avoid having any
   intermediate results less than 0, we need one final rearrangement, and a
   compiler can easily take the constant-folding from there...

	 =  TY + (((256*M*AD+2*AN*TX-AN*x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD
	 =  TY - ((M*AD + AN*TX/256)*TX - ((256*M*AD+2*AN*TX-AN*x)/256)*x)/256/AD
*/

static int getDLPexpSize( const int primeBits )
	{
	long value;	/* Necessary to avoid braindamage on 16-bit compilers */

	/* If it's over TX bits, it's linear */
	if( primeBits > TX )
		value = M * primeBits / 256 - M * TX / 256 + TY;
	else
		/* It's quadratic */
		value = TY - ( ( M * AD + AN * TX / 256 ) * TX - \
					   ( ( 256 * M * AD + AN * 2 * TX - AN * primeBits ) / 256 ) * \
					   primeBits ) / ( AD * 256 );

	/* Various standards require a minimum of 160 bits so we always return at
	   least that size even if it's not necessary */
	return( value > 160 ? ( int ) value : 160 );
	}

/****************************************************************************
*																			*
*			  					Generate DL Primes							*
*							Copyright Kevin J Bluck 1998					*
*						 Copyright Peter Gutmann 1998-2002					*
*																			*
****************************************************************************/

/* DLP-based PKCs 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	( ( MAX_PKCSIZE_BITS / 160 ) + 1 )

/* The maximum number of small primes required to generate a prime using the
   Lim-Lee algorithm.  There's no fixed bound on this value, but in the worst
   case we start with ~ 4096 / getDLPexpSize( 4096 ) primes = ~ 13 values,
   and add one more prime on each retry.  Typically we need 10-15 for keys
   in the most commonly-used range 512-2048 bits.  In order to simplify the 
   handling of values, we allow for 128 primes, which has a vanishingly small 
   probability of failing and also provides a safe upper bound for the
   number of retries (there's something wrong with the algorithm if it 
   requires anything near this many retries) */

#define MAX_NO_PRIMES	128

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