kg_rsa.c

cryptlib安全工具包

/****************************************************************************
*																			*
*				cryptlib RSA Key Generation/Checking Routines				*
*						Copyright Peter Gutmann 1997-2007					*
*																			*
****************************************************************************/

#define PKC_CONTEXT		/* Indicate that we're working with PKC contexts */
#if defined( INC_ALL )
  #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 */

/* We use F4 as the default public exponent e unless the user chooses to
   override this with some other value:

	Fn = 2^(2^n) + 1, n = 0...4.

	F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.
   
   The older (X.509v1) recommended value of 3 is insecure for general use 
   and more recent work indicates that values like 17 (used by PGP) are also 
   insecure against the Hastad attack.  We could work around this by using 
   41 or 257 as the exponent, however current best practice favours F4 
   unless you're doing banking standards, in which case you set e=2 (EMV) 
   and use raw, unpadded RSA (HBCI) to make it easier for students to break 
   your banking security as a homework exercise.

   Since some systems may be using 16-bit bignum component values we use an
   exponent of 257 for these cases to ensure that it fits in a single
   component value */

#ifndef RSA_PUBLIC_EXPONENT
  #ifdef SIXTEEN_BIT
	#define RSA_PUBLIC_EXPONENT		257
  #else
	#define RSA_PUBLIC_EXPONENT		65537L
  #endif /* 16-bit bignum components */
#endif /* RSA_PUBLIC_EXPONENT */

/* The minimum allowed public exponent.  In theory this could go as low as 3,
   however there are all manner of obscure corner cases that have to be 
   checked if this exponent is used and in general the necessary checking 
   presents a more or less intractable problem.  To avoid this minefield we
   require a minimum exponent of at 17, the next generally-used value above 
   3.  However even this is only used by PGP 2.x, the next minimum is 33 (a
   weird value used by OpenSSH, see the comment further down) and then 257
   or (in practice) 65537 by everything else */

#if defined( USE_PGP )
  #define MIN_PUBLIC_EXPONENT		17
#elif defined( USE_SSH )
  #define MIN_PUBLIC_EXPONENT		33
#else
  #define MIN_PUBLIC_EXPONENT		257
#endif /* Smallest exponents used by various crypto protocols */

/****************************************************************************
*																			*
*							Utility Functions								*
*																			*
****************************************************************************/

/* Enable various side-channel protection mechanisms */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int enableSidechannelProtection( INOUT PKC_INFO *pkcInfo, 
										const BOOLEAN isPrivateKey )
	{
	BIGNUM *n = &pkcInfo->rsaParam_n, *e = &pkcInfo->rsaParam_e;
	BIGNUM *k = &pkcInfo->rsaParam_blind_k;
	BIGNUM *kInv = &pkcInfo->rsaParam_blind_kInv;
	MESSAGE_DATA msgData;
	BYTE buffer[ CRYPT_MAX_PKCSIZE + 8 ];
	int noBytes = bitsToBytes( pkcInfo->keySizeBits );
	int bnStatus = BN_STATUS, status;

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

	/* Generate a random bignum for blinding.  Since this merely has to be 
	   unpredictable to an outsider but not cryptographically strong, and to 
	   avoid having more crypto RNG output than necessary sitting around in 
	   memory, we get it from the nonce PRNG rather than the crypto one.  In
	   addition we don't have to perform a range check on import to see if 
	   it's larger than 'n' since we're about to reduce it mod n in the next 
	   step, and doing so would give false positives */
	setMessageData( &msgData, buffer, noBytes );
	status = krnlSendMessage( SYSTEM_OBJECT_HANDLE, IMESSAGE_GETATTRIBUTE_S,
							  &msgData, CRYPT_IATTRIBUTE_RANDOM_NONCE );
	if( cryptStatusOK( status ) )
		{
		buffer[ 0 ] &= 0xFF >> ( -pkcInfo->keySizeBits & 7 );
		status = extractBignum( k, buffer, noBytes, MIN_PKCSIZE - 8, 
								CRYPT_MAX_PKCSIZE, NULL, FALSE );
		}
	zeroise( buffer, noBytes );
	if( cryptStatusError( status ) )
		return( status );

	/* Set up the blinding and unblinding values */
	CK( BN_mod( k, k, n, pkcInfo->bnCTX ) );	/* k = rand() mod n */
	CKPTR( BN_mod_inverse( kInv, k, n, pkcInfo->bnCTX ) );
												/* kInv = k^-1 mod n */
	CK( BN_mod_exp_mont( k, k, e, n, pkcInfo->bnCTX,
						 &pkcInfo->rsaParam_mont_n ) );
												/* k = k^e mod n */
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* Use constant-time modexp() to protect the private key from timing 
	   channels if required */
	if( isPrivateKey )
		{
		BN_set_flags( &pkcInfo->rsaParam_exponent1, BN_FLG_EXP_CONSTTIME );
		BN_set_flags( &pkcInfo->rsaParam_exponent2, BN_FLG_EXP_CONSTTIME );
		}

	return( CRYPT_OK );
	}

/****************************************************************************
*																			*
*							Generate an RSA Key								*
*																			*
****************************************************************************/

/* Adjust p and q if necessary to ensure that the CRT decrypt works */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int fixCRTvalues( INOUT PKC_INFO *pkcInfo, 
						 const BOOLEAN fixPKCSvalues )
	{
	BIGNUM *p = &pkcInfo->rsaParam_p, *q = &pkcInfo->rsaParam_q;

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

	/* Make sure that p > q, which is required for the CRT decrypt */
	if( BN_cmp( p, q ) >= 0 )
		return( CRYPT_OK );

	/* Swap the values p and q and, if necessary, the PKCS parameters e1
	   and e2 that depend on them (e1 = d mod (p - 1) and
	   e2 = d mod (q - 1)), and recompute u = qInv mod p */
	BN_swap( p, q );
	if( !fixPKCSvalues )
		return( CRYPT_OK );
	BN_swap( &pkcInfo->rsaParam_exponent1, &pkcInfo->rsaParam_exponent2 );
	return( BN_mod_inverse( &pkcInfo->rsaParam_u, q, p,
							pkcInfo->bnCTX ) != NULL ? \
			CRYPT_OK : CRYPT_ERROR_FAILED );
	}

/* Evaluate the Montgomery forms for public and private components */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int getRSAMontgomery( INOUT PKC_INFO *pkcInfo, 
							 const BOOLEAN isPrivateKey )
	{
	assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );

	/* Evaluate the public value */
	if( !BN_MONT_CTX_set( &pkcInfo->rsaParam_mont_n, &pkcInfo->rsaParam_n,
						  pkcInfo->bnCTX ) )
		return( CRYPT_ERROR_FAILED );
	if( !isPrivateKey )
		return( CRYPT_OK );

	/* Evaluate the private values */
	return( BN_MONT_CTX_set( &pkcInfo->rsaParam_mont_p, &pkcInfo->rsaParam_p,
							 pkcInfo->bnCTX ) && \
			BN_MONT_CTX_set( &pkcInfo->rsaParam_mont_q, &pkcInfo->rsaParam_q,
							 pkcInfo->bnCTX ) ? \
			CRYPT_OK : CRYPT_ERROR_FAILED );
	}

/* Generate an RSA key pair into an encryption context.  For FIPS 140 
   purposes the keygen method used here complies with FIPS 186-3 Appendix 
   B.3, "IFC Key Pair Generation", specifically method B.3.3, "Generation of 
   Random Primes that are Probably Prime".  Note that FIPS 186-3 provides a
   range of key-generation methods and allows implementations to select one
   that's appropriate, this implementation provides the one in B.3.3, with
   the exception that it allows keys in the range MIN_PKC_SIZE ... 
   CRYPT_MAX_PKCSIZE to be generated.  FIPS 186-3 is rather confusing in
   that it discusses conditions and requirements for generating pairs from
   512 ... 3072 bits and then gives different lengths and restrictions on
   lengths depending on which portion of text you consult.  Because of this
   confusion, and the fact that telling users that they can't generate the
   key that they want because of some obscure document that they've never
   even heard of will cause friction, we leave it as a policy decision to
   define the appropriate key size to use */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
int generateRSAkey( INOUT CONTEXT_INFO *contextInfoPtr, 
					IN_LENGTH_SHORT_MIN( MIN_PKCSIZE * 8 ) const int keyBits )
	{
	PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
	BIGNUM *d = &pkcInfo->rsaParam_d, *p = &pkcInfo->rsaParam_p;
	BIGNUM *q = &pkcInfo->rsaParam_q;
	BIGNUM *tmp = &pkcInfo->tmp1;
	int pBits, qBits, bnStatus = BN_STATUS, status;

	assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
	
	REQUIRES( keyBits >= bytesToBits( MIN_PKCSIZE ) && \
			  keyBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );

	/* Determine how many bits to give to each of p and q */
	pBits = ( keyBits + 1 ) / 2;
	qBits = keyBits - pBits;
	pkcInfo->keySizeBits = pBits + qBits;

	/* Generate the primes p and q and set them up so that the CRT decrypt
	   will work.  FIPS 186-3 requires that they be in the range 
	   sqr(2) * 2^(keyBits-1) ... 2^keyBits (so that pq will be exactly 
	   keyBits long), but this is guaranteed by the way that generatePrime()
	   selects its prime values so we don't have to check explicitly for it
	   here */
	BN_set_word( &pkcInfo->rsaParam_e, RSA_PUBLIC_EXPONENT );
	status = generatePrime( pkcInfo, p, pBits, RSA_PUBLIC_EXPONENT );
	if( cryptStatusOK( status ) )
		status = generatePrime( pkcInfo, q, qBits, RSA_PUBLIC_EXPONENT );
	if( cryptStatusOK( status ) )
		status = fixCRTvalues( pkcInfo, FALSE );
	if( cryptStatusError( status ) )
		return( status );

	/* Compute d = eInv mod (p - 1)(q - 1) */
	CK( BN_sub_word( p, 1 ) );
	CK( BN_sub_word( q, 1 ) );
	CK( BN_mul( tmp, p, q, pkcInfo->bnCTX ) );
	CKPTR( BN_mod_inverse( d, &pkcInfo->rsaParam_e, tmp, pkcInfo->bnCTX ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

#ifdef USE_FIPS140
	/* Check that sizeof( d ) > sizeof( p ) / 2, a weird requirement set by 
	   FIPS 186-3.  This is one of those things where the probability of the
	   check going wrong in some way outweighs the probability of the 
	   situation actually occurring by about two dozen orders of magnitude 
	   so we only do this when we have to.  The fact that this parameter is
	   never even used makes the check even less meaningful.
	   
	   (This check possibly has something to do with defending against 
	   Wiener's continued-fraction attack, which requires d < n^(1/4) in
	   order to succeed, later extended into the range d < n^(0.29) by
	   Boneh and Durfee/Bloemer and May and d < 1/2 n^(1/2) by Maitra and 
	   Sarkar) */
	if( BN_num_bits( d ) <= pkcInfo->keySizeBits / 2 )
		return( CRYPT_ERROR_FAILED );
#endif /* USE_FIPS140 */

	/* Compute e1 = d mod (p - 1), e2 = d mod (q - 1) */
	CK( BN_mod( &pkcInfo->rsaParam_exponent1, d,
				p, pkcInfo->bnCTX ) );
	CK( BN_mod( &pkcInfo->rsaParam_exponent2, d, q, pkcInfo->bnCTX ) );
	CK( BN_add_word( p, 1 ) );
	CK( BN_add_word( q, 1 ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* Compute n = pq, u = qInv mod p */
	CK( BN_mul( &pkcInfo->rsaParam_n, p, q, pkcInfo->bnCTX ) );
	CKPTR( BN_mod_inverse( &pkcInfo->rsaParam_u, q, p, pkcInfo->bnCTX ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* Evaluate the Montgomery forms */
	status = getRSAMontgomery( pkcInfo, TRUE );
	if( cryptStatusError( status ) )
		return( status );

	/* Enable side-channel protection if required */
	if( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION )
		status = enableSidechannelProtection( pkcInfo, TRUE );
	return( status );
	}

/****************************************************************************
*																			*
*							Initialise/Check an RSA Key						*
*																			*