ctx_rsa.c

cryptlib安全工具包

	   can't use the length returned from getBignumData() because this is 
	   the length of the zero-truncated result, not the full length */
	CK( BN_mod_exp_mont( data, data, e, n, pkcInfo->bnCTX,
						 &pkcInfo->rsaParam_mont_n ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );
	offset = length - BN_num_bytes( data );
	if( offset > 0 )
		memset( buffer, 0, offset );
	return( getBignumData( data, buffer + offset, noBytes - offset, &dummy ) );
	}

/* Use the Chinese Remainder Theorem shortcut for RSA decryption/signature
   generation.  n isn't needed because of this.

   There are two types of side-channel attack protection that we employ for
   prvate-key operations, the first being standard blinding included in the
   code below.  The second type applies to CRT-based RSA implementations and
   is based on the fact that if a fault occurs during the computation of p2
   or q2 (to give, say, p2') then applying the CRT will yield a faulty
   signature M'.  An attacker can then compute q from
   gcd( M' ** e - ( C mod n ), n ), and the same for q2' and p.  The chances
   of this actually occurring are... unlikely, given that it requires a
   singleton failure inside the CPU (with data running over ECC-protected
   buses) at the exact moment of CRT computation (the original threat model
   assumed a fault-injection attack on a smart card), however we can still
   provide protection against the problem for people who consider it a
   genuine threat.

   The problem was originally pointed out by Marc Joye, Arjen Lenstra, and
   Jean-Jacques Quisquater in "Chinese Remaindering Based Cryptosystems in
   the Presence of Faults", Journal of Cryptology, Vol.12, No.4 (Autumn
   1999), p.241, based on an earlier result "On the importance of checking
   cryptographic protocols for faults", Dan Boneh, Richard DeMillo, and
   Richard Lipton, EuroCrypt'97, LNCS Vol.1233, p.37.  Adi Shamir presented
   one possible solution to the problem in the conference's rump session in
   "How to check modular exponentiation", which performs a parallel
   computation of the potentially fault-affected portions of the CRT
   operation in blinded form and then checks that the two outputs are
   consistent.  This has three drawbacks: It's slow, Shamir patented it
   (US Patent 5,991,415), and if one CRT is faulty there's no guarantee
   that the parallel CRT won't be faulty as well.  Better solutions were
   suggested by Sung-Ming Yen, Seungjoo Kim, Seongan Lim, and Sangjae
   Moon in "RSA Speedup with Residue Number System Immune against Hardware
   Fault Cryptanalysis", ICISC'01, LNCS Vol.2288, p.397.  These have less
   overhead than Shamir's approach and are also less patented, but like
   Shamir's approach they involve messing around with the CRT computation.
   A further update to this given by Sung-Ming Yen, Sangjae Kim, and Jae-
   Cheol Ha in "Hardware Fault Attack on RSA with CRT Revisited", ICISC'02,
   LNCS Vol.2587, p.374, which updated the earlier work and also found flaws
   in Shamir's solution.

   A much simpler solution is just to verify the CRT-based private-key
   operation with the matching public-key operation after we perform it.
   Since this is only required for signatures (the output of a decrypt is
   (a) never visible to an attacker and (b) verified via the PKCS #1
   padding), we perform this operation at a higher level, performing a
   signature verify after each signature generation at the crypto mechanism
   level */

static int decryptFn( CONTEXT_INFO *contextInfoPtr, BYTE *buffer, int noBytes )
	{
	PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
	BIGNUM *p = &pkcInfo->rsaParam_p, *q = &pkcInfo->rsaParam_q;
	BIGNUM *u = &pkcInfo->rsaParam_u, *e1 = &pkcInfo->rsaParam_exponent1;
	BIGNUM *e2 = &pkcInfo->rsaParam_exponent2;
	BIGNUM *data = &pkcInfo->tmp1, *p2 = &pkcInfo->tmp2, *q2 = &pkcInfo->tmp3;
	const int length = bitsToBytes( pkcInfo->keySizeBits );
	int iterationCount, offset, dummy, bnStatus = BN_STATUS, status;

	assert( noBytes == length );

	/* Move the data from the buffer into a bignum.  We need to make an 
	   unfortunate exception to the valid-length check for SSL's weird 
	   signatures, which sign a raw concatenated MD5 and SHA-1 hash with a 
	   total length of 36 bytes */
	status = extractBignum( data, buffer, length, 36, CRYPT_MAX_PKCSIZE, 
							&pkcInfo->rsaParam_n, FALSE );
	if( cryptStatusError( status ) )
		return( status );
	if( BN_num_bytes( data ) != 36 && \
		BN_num_bytes( data ) < MIN_PKCSIZE - 8 )
		{
		/* If it's not the weird SSL signature and it's outside the valid 
		   length range, reject it */
		return( CRYPT_ERROR_BADDATA );
		}

	/* If we're blinding the RSA operation, set
	   data = ( ( rand^e ) * data ) mod n */
	if( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION )
		{
		CK( BN_mod_mul( data, data, &pkcInfo->rsaParam_blind_k,
						&pkcInfo->rsaParam_n, pkcInfo->bnCTX ) );
		if( bnStatusError( bnStatus ) )
			return( getBnStatus( bnStatus ) );
		}

	/* Rather than decrypting by computing a modexp with full mod n
	   precision, compute a shorter modexp with mod p and mod q precision:
		p2 = ( ( C mod p ) ** exponent1 ) mod p
		q2 = ( ( C mod q ) ** exponent2 ) mod q */
	CK( BN_mod( p2, data, p,			/* p2 = C mod p  */
				pkcInfo->bnCTX ) );
	CK( BN_mod_exp_mont( p2, p2, e1, p, pkcInfo->bnCTX,
						 &pkcInfo->rsaParam_mont_p ) );
	CK( BN_mod( q2, data, q,			/* q2 = C mod q  */
				pkcInfo->bnCTX ) );
	CK( BN_mod_exp_mont( q2, q2, e2, q, pkcInfo->bnCTX,
						 &pkcInfo->rsaParam_mont_q ) );
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* p2 = p2 - q2; if p2 < 0 then p2 = p2 + p.  In some extremely rare
	   cases (q2 large, p2 small) we have to add p twice to get p2
	   positive */
	CK( BN_sub( p2, p2, q2 ) );
	for( iterationCount = 0;
		 p2->neg && iterationCount < FAILSAFE_ITERATIONS_SMALL;
		 iterationCount++ )
		{
		CK( BN_add( p2, p2, p ) );
		if( bnStatusError( bnStatus ) )
			return( getBnStatus( bnStatus ) );
		}
	if( iterationCount >= FAILSAFE_ITERATIONS_SMALL )
		retIntError();

	/* M = ( ( ( p2 * u ) mod p ) * q ) + q2 */
	CK( BN_mod_mul( data, p2, u, p,		/* data = ( p2 * u ) mod p */
					pkcInfo->bnCTX ) );
	CK( BN_mul( p2, data, q,			/* p2 = data * q (bn can't reuse data) */
				pkcInfo->bnCTX ) );
	CK( BN_add( data, p2, q2 ) );		/* data = p2 + q2 */
	if( bnStatusError( bnStatus ) )
		return( getBnStatus( bnStatus ) );

	/* If we're blinding the RSA operation, set
	   data = ( ( data^e ) / rand ) mod n
			= ( rand^-1 * data ) mod n */
	if( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION )
		{
		BIGNUM *n = &pkcInfo->rsaParam_n;
		BIGNUM *k = &pkcInfo->rsaParam_blind_k;
		BIGNUM *kInv = &pkcInfo->rsaParam_blind_kInv;

		CK( BN_mod_mul( data, data, kInv, n, pkcInfo->bnCTX ) );
		if( bnStatusError( bnStatus ) )
			return( getBnStatus( bnStatus ) );

		/* Update the blinding values in such a way that we get new random
		   (that is, unpredictable to an outsider) numbers of the correct
		   form without having to do a full modexp as we would if starting
		   with new random data:

			k = ( k^2 ) mod n 
		
		   In theory we could replace the random blinding value periodically
		   in order to avoid an attacker being able to build up stats on it 
		   and the values derived from it, but it seems unlikely that they 
		   can do much with this and leads to problems of its own since the
		   process of calculating the new blinding value is itself 
		   susceptible to side-channel attacks */
		CK( BN_mod_mul( k, k, k, n, pkcInfo->bnCTX ) );
		CK( BN_mod_mul( kInv, kInv, kInv, n, pkcInfo->bnCTX ) );
		if( bnStatusError( bnStatus ) )
			return( getBnStatus( bnStatus ) );
		}

	/* Copy the result to the output.  Since the bignum code performs
	   leading-zero truncation, we have to adjust where we copy the
	   result to in the buffer to take into account extra zero bytes
	   that aren't extracted from the bignum.  In addition we can't use
	   the length returned from getBignumData() because this is the 
	   length of the zero-truncated result, not the full length */
	offset = length - BN_num_bytes( data );
	if( offset > 0 )
		memset( buffer, 0, offset );
	return( getBignumData( data, buffer + offset, noBytes - offset, &dummy ) );
	}

/****************************************************************************
*																			*
*								Load Key Components							*
*																			*
****************************************************************************/

/* Load key components into an encryption context */

static int initKey( CONTEXT_INFO *contextInfoPtr, const void *key,
					const int keyLength )
	{
	int status;

#ifndef USE_FIPS140
	/* Load the key component from the external representation into the
	   internal bignums unless we're doing an internal load */
	if( key != NULL )
		{
		PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
		const CRYPT_PKCINFO_RSA *rsaKey = ( CRYPT_PKCINFO_RSA * ) key;

		contextInfoPtr->flags |= ( rsaKey->isPublicKey ) ? \
							CONTEXT_FLAG_ISPUBLICKEY : CONTEXT_FLAG_ISPRIVATEKEY;
		status = extractBignum( &pkcInfo->rsaParam_n, rsaKey->n, 
								bitsToBytes( rsaKey->nLen ), 
								RSAPARAM_MIN_N, RSAPARAM_MAX_N, NULL, TRUE );
		if( cryptStatusOK( status ) )
			status = extractBignum( &pkcInfo->rsaParam_e, rsaKey->e, 
									bitsToBytes( rsaKey->eLen ),
									RSAPARAM_MIN_E, RSAPARAM_MAX_E,
									&pkcInfo->rsaParam_n, FALSE );
		if( cryptStatusOK( status ) )
		if( !rsaKey->isPublicKey )
			{
			if( cryptStatusOK( status ) && rsaKey->dLen > 0 )
				status = extractBignum( &pkcInfo->rsaParam_d, rsaKey->d, 
										bitsToBytes( rsaKey->dLen ),
										RSAPARAM_MIN_D, RSAPARAM_MAX_D,
										&pkcInfo->rsaParam_n, FALSE );
			if( cryptStatusOK( status ) )
				status = extractBignum( &pkcInfo->rsaParam_p, rsaKey->p, 
										bitsToBytes( rsaKey->pLen ),
										RSAPARAM_MIN_P, RSAPARAM_MAX_P,
										&pkcInfo->rsaParam_n, FALSE );
			if( cryptStatusOK( status ) )
				status = extractBignum( &pkcInfo->rsaParam_q, rsaKey->q, 
										bitsToBytes( rsaKey->qLen ),
										RSAPARAM_MIN_Q, RSAPARAM_MAX_Q,
										&pkcInfo->rsaParam_n, FALSE );
			if( cryptStatusOK( status ) && rsaKey->uLen > 0 )
				status = extractBignum( &pkcInfo->rsaParam_u, rsaKey->u, 
										bitsToBytes( rsaKey->uLen ),
										RSAPARAM_MIN_U, RSAPARAM_MAX_U,
										&pkcInfo->rsaParam_n, FALSE );
			if( cryptStatusOK( status ) && rsaKey->e1Len > 0 )
				status = extractBignum( &pkcInfo->rsaParam_exponent1, rsaKey->e1, 
										bitsToBytes( rsaKey->e1Len ),
										RSAPARAM_MIN_EXP1, RSAPARAM_MAX_EXP1,
										&pkcInfo->rsaParam_n, FALSE );
			if( cryptStatusOK( status ) && rsaKey->e2Len > 0 )
				status = extractBignum( &pkcInfo->rsaParam_exponent2, rsaKey->e2, 
										bitsToBytes( rsaKey->e2Len ),
										RSAPARAM_MIN_EXP2, RSAPARAM_MAX_EXP2,
										&pkcInfo->rsaParam_n, FALSE );
			}
		contextInfoPtr->flags |= CONTEXT_FLAG_PBO;
		if( cryptStatusError( status ) )
			return( status );
		}
#endif /* USE_FIPS140 */

	/* Complete the key checking and setup */
	status = initCheckRSAkey( contextInfoPtr );
	if( cryptStatusOK( status ) )
		status = contextInfoPtr->ctxPKC->calculateKeyIDFunction( contextInfoPtr );
	return( status );
	}

/* Generate a key into an encryption context */

static int generateKey( CONTEXT_INFO *contextInfoPtr, const int keySizeBits )
	{
	int status;

	status = generateRSAkey( contextInfoPtr, keySizeBits );
	if( cryptStatusOK( status ) &&
#ifndef USE_FIPS140
		( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION ) &&
#endif /* USE_FIPS140 */
		!pairwiseConsistencyTest( contextInfoPtr ) )
		{
		assert( DEBUG_WARN );
		status = CRYPT_ERROR_FAILED;
		}
	if( cryptStatusOK( status ) )
		status = contextInfoPtr->ctxPKC->calculateKeyIDFunction( contextInfoPtr );
	return( status );
	}

/****************************************************************************
*																			*
*						Capability Access Routines							*
*																			*
****************************************************************************/

static const CAPABILITY_INFO FAR_BSS capabilityInfo = {
	CRYPT_ALGO_RSA, bitsToBytes( 0 ), "RSA", 3,
	MIN_PKCSIZE, bitsToBytes( 1024 ), CRYPT_MAX_PKCSIZE,
	selfTest, getDefaultInfo, NULL, NULL, initKey, generateKey, encryptFn, decryptFn,
	NULL, NULL, NULL, NULL, NULL, NULL, decryptFn, encryptFn
	};

const CAPABILITY_INFO *getRSACapability( void )
	{
	return( &capabilityInfo );
	}