lib_rsa.c

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

/****************************************************************************
*																			*
*						cryptlib RSA Encryption Routines					*
*						Copyright Peter Gutmann 1993-2002					*
*																			*
****************************************************************************/

/* I suppose if we all used pure RSA, the Illuminati would blackmail God into
   putting a trapdoor into the laws of mathematics.
														-- Lyle Seaman */
#include <stdlib.h>
#include <string.h>
#include "crypt.h"
#include "cryptctx.h"

/* Prototypes for functions in lib_kg.c */

int generateRSAPrime( BIGNUM *candidate, const int noBits,
					  const long exponent, void *callbackArg );

/* We use F4 as the default public exponent e unless the user chooses to 
   override this with some other value.  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 */

#ifndef PUBLIC_EXPONENT
  #define PUBLIC_EXPONENT		65537L
#endif /* PUBLIC_EXPONENT */

/****************************************************************************
*																			*
*							RSA Self-test Routines							*
*																			*
****************************************************************************/

/* Test the RSA implementation using a sample key.  Because a lot of the
   high-level encryption routines don't exist yet, we cheat a bit and set
   up a dummy encryption context with just enough information for the
   following code to work */

typedef struct {
	int nLen; BYTE n[ 64 ];
	int eLen; BYTE e[ 1 ];
	int dLen; BYTE d[ 64 ];
	int pLen; BYTE p[ 32 ];
	int qLen; BYTE q[ 32 ];
	int uLen; BYTE u[ 32 ];
	int e1Len; BYTE e1[ 32 ];
	int e2Len; BYTE e2[ 32 ];
	} RSA_PRIVKEY;

static const RSA_PRIVKEY rsaTestKey = {
	/* n */
	512,
	{ 0xE1, 0x95, 0x41, 0x17, 0xB4, 0xCB, 0xDC, 0xD0,
	  0xCB, 0x9B, 0x11, 0x19, 0x9C, 0xED, 0x04, 0x6F,
	  0xBD, 0x70, 0x2D, 0x5C, 0x8A, 0x32, 0xFF, 0x16,
	  0x22, 0x57, 0x30, 0x3B, 0xD4, 0x59, 0x9C, 0x01,
	  0xF0, 0xA3, 0x70, 0xA1, 0x6C, 0x16, 0xAC, 0xCC,
	  0x8C, 0xAD, 0xB0, 0xA0, 0xAF, 0xC7, 0xCC, 0x49,
	  0x4F, 0xD9, 0x5D, 0x32, 0x1C, 0x2A, 0xE8, 0x4E,
	  0x15, 0xE1, 0x26, 0x6C, 0xC4, 0xB8, 0x94, 0xE1 },
	/* e */
	5,
	{ 0x11 },
	/* d */
	509,
	{ 0x13, 0xE7, 0x85, 0xBE, 0x53, 0xB7, 0xA2, 0x8A,
	  0xE4, 0xC9, 0xEA, 0xEB, 0xAB, 0xF6, 0xCB, 0xAF,
	  0x81, 0xA8, 0x04, 0x00, 0xA2, 0xC8, 0x43, 0xAF,
	  0x21, 0x25, 0xCF, 0x8C, 0xCE, 0xF8, 0xD9, 0x0F,
	  0x10, 0x78, 0x4C, 0x1A, 0x26, 0x5D, 0x90, 0x18,
	  0x79, 0x90, 0x42, 0x83, 0x6E, 0xAE, 0x3E, 0x20,
	  0x0B, 0x0C, 0x5B, 0x6B, 0x8E, 0x31, 0xE5, 0xCF,
	  0xD6, 0xE0, 0xBB, 0x41, 0xC1, 0xB8, 0x2E, 0x17 },
	/* p */
	256,
	{ 0xED, 0xE4, 0x02, 0x90, 0xA4, 0xA4, 0x98, 0x0D,
	  0x45, 0xA2, 0xF3, 0x96, 0x09, 0xED, 0x7B, 0x40,
	  0xCD, 0xF6, 0x21, 0xCC, 0xC0, 0x1F, 0x83, 0x09,
	  0x56, 0x37, 0x97, 0xFB, 0x05, 0x5B, 0x87, 0xB7 },
	/* q */
	256,
	{ 0xF2, 0xC1, 0x64, 0xE8, 0x69, 0xF8, 0x5E, 0x54,
	  0x8F, 0xFD, 0x20, 0x8E, 0x6A, 0x23, 0x90, 0xF2,
	  0xAF, 0x57, 0x2F, 0x4D, 0x10, 0x80, 0x8E, 0x11,
	  0x3C, 0x61, 0x44, 0x33, 0x2B, 0xE0, 0x58, 0x27 },
	/* u */
	255,
	{ 0x68, 0x45, 0x00, 0x64, 0x32, 0x9D, 0x09, 0x6E,
	  0x0A, 0xD3, 0xF3, 0x8A, 0xFE, 0x15, 0x8C, 0x79,
	  0xAD, 0x84, 0x35, 0x05, 0x19, 0x2C, 0x19, 0x51,
	  0xAB, 0x83, 0xC7, 0xE8, 0x5C, 0xAC, 0xAD, 0x7A },
	/* exponent1 */
	256,
	{ 0x99, 0xED, 0xE3, 0x8A, 0xC4, 0xE2, 0xF8, 0xF9,
	  0x87, 0x69, 0x70, 0x70, 0x24, 0x8A, 0x9B, 0x0B,
	  0xD0, 0x90, 0x33, 0xFC, 0xF4, 0xC9, 0x18, 0x8D,
	  0x92, 0x23, 0xF8, 0xED, 0xB8, 0x2C, 0x2A, 0xA3 },
	/* exponent2 */
	256,
	{ 0xB9, 0xA2, 0xF2, 0xCF, 0xD8, 0x90, 0xC0, 0x9B,
	  0x04, 0xB2, 0x82, 0x4E, 0xC9, 0xA2, 0xBA, 0x22,
	  0xFE, 0x8D, 0xF6, 0xFE, 0xB2, 0x44, 0x30, 0x67,
	  0x88, 0x86, 0x9D, 0x90, 0x8A, 0xF6, 0xD9, 0xFF }
	};

int rsaInitKey( CRYPT_INFO *cryptInfo, const void *key, const int keyLength );
int rsaEncrypt( CRYPT_INFO *cryptInfo, BYTE *buffer, int noBytes );
int rsaDecrypt( CRYPT_INFO *cryptInfo, BYTE *buffer, int noBytes );

int rsaSelfTest( void )
	{
	CRYPT_INFO cryptInfo;
	CRYPT_PKCINFO_RSA *rsaKey;
	static const CAPABILITY_INFO capabilityInfo = { CRYPT_ALGO_RSA, 0, NULL,
													64, 128, 512, 0 };
	BYTE buffer[ 64 ];
	int status;

	/* Set up the key components */
	if( ( rsaKey = ( CRYPT_PKCINFO_RSA * ) malloc( sizeof( CRYPT_PKCINFO_RSA ) ) ) == NULL )
		return( CRYPT_ERROR_MEMORY );
	cryptInitComponents( rsaKey, CRYPT_KEYTYPE_PRIVATE );
	cryptSetComponent( rsaKey->n, rsaTestKey.n, rsaTestKey.nLen );
	cryptSetComponent( rsaKey->e, rsaTestKey.e, rsaTestKey.eLen );
	cryptSetComponent( rsaKey->d, rsaTestKey.d, rsaTestKey.dLen );
	cryptSetComponent( rsaKey->p, rsaTestKey.p, rsaTestKey.pLen );
	cryptSetComponent( rsaKey->q, rsaTestKey.q, rsaTestKey.qLen );
	cryptSetComponent( rsaKey->u, rsaTestKey.u, rsaTestKey.uLen );
	cryptSetComponent( rsaKey->e1, rsaTestKey.e1, rsaTestKey.e1Len );
	cryptSetComponent( rsaKey->e2, rsaTestKey.e2, rsaTestKey.e2Len );

	/* Initialise the BigNum information and components */
	memset( &cryptInfo, 0, sizeof( CRYPT_INFO ) );
	cryptInfo.ctxPKC.param1 = BN_new();
	cryptInfo.ctxPKC.param2 = BN_new();
	cryptInfo.ctxPKC.param3 = BN_new();
	cryptInfo.ctxPKC.param4 = BN_new();
	cryptInfo.ctxPKC.param5 = BN_new();
	cryptInfo.ctxPKC.param6 = BN_new();
	cryptInfo.ctxPKC.param7 = BN_new();
	cryptInfo.ctxPKC.param8 = BN_new();
	cryptInfo.capabilityInfo = &capabilityInfo;

	/* Perform the test en/decryption of a block of data */
	memset( buffer, 0, 64 );
	memcpy( buffer, "abcde", 5 );
	rsaInitKey( &cryptInfo, rsaKey, CRYPT_UNUSED );
	if( ( status = rsaEncrypt( &cryptInfo, buffer, 64 ) ) == CRYPT_OK )
		status = rsaDecrypt( &cryptInfo, buffer, 64 );
	if( status != CRYPT_OK || memcmp( buffer, "abcde", 5 ) )
		status = CRYPT_ERROR;

	/* Clean up */
	cryptDestroyComponents( rsaKey );
	BN_clear_free( cryptInfo.ctxPKC.param1 );
	BN_clear_free( cryptInfo.ctxPKC.param2 );
	BN_clear_free( cryptInfo.ctxPKC.param3 );
	BN_clear_free( cryptInfo.ctxPKC.param4 );
	BN_clear_free( cryptInfo.ctxPKC.param5 );
	BN_clear_free( cryptInfo.ctxPKC.param6 );
	BN_clear_free( cryptInfo.ctxPKC.param7 );
	BN_clear_free( cryptInfo.ctxPKC.param8 );
	if( cryptInfo.ctxPKC.rsaParam_mont_n != NULL )
		BN_MONT_CTX_free( cryptInfo.ctxPKC.rsaParam_mont_n );
	if( cryptInfo.ctxPKC.rsaParam_mont_p != NULL )
		BN_MONT_CTX_free( cryptInfo.ctxPKC.rsaParam_mont_p );
	if( cryptInfo.ctxPKC.rsaParam_mont_q != NULL )
		BN_MONT_CTX_free( cryptInfo.ctxPKC.rsaParam_mont_q );
	zeroise( &cryptInfo, sizeof( CRYPT_INFO ) );
	free( rsaKey );

	return( status );
	}

/****************************************************************************
*																			*
*								Utility Routines							*
*																			*
****************************************************************************/

/* Adjust p and q if necessary so the CRT decrypt works */

static void fixCRTvalues( PKC_INFO *pkcInfo, const BOOLEAN fixPKCSvalues,
						  BN_CTX *bnCTX )
	{
	BIGNUM *tmp;

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

	/* Swap the values p and q and, if necessary, the dependant parameters
	   e1 = d mod (p - 1) and e2 = d mod (q - 1), and recompute
	   u = qInv mod p */
	tmp = pkcInfo->rsaParam_p;
	pkcInfo->rsaParam_p = pkcInfo->rsaParam_q;
	pkcInfo->rsaParam_q = tmp;
	if( !fixPKCSvalues )
		return;
	tmp = pkcInfo->rsaParam_exponent1;
	pkcInfo->rsaParam_exponent1 = pkcInfo->rsaParam_exponent2;
	pkcInfo->rsaParam_exponent2 = tmp;
	BN_clear_free( pkcInfo->rsaParam_u );
	pkcInfo->rsaParam_u = BN_mod_inverse( pkcInfo->rsaParam_q,
										  pkcInfo->rsaParam_p, bnCTX );
	}

/* Precompute Montgomery values for public and private components */

static int precomputeMontgomery( PKC_INFO *pkcInfo, BN_CTX *bnCTX )
	{
	/* Precompute the public value */
	if( ( pkcInfo->rsaParam_mont_n = BN_MONT_CTX_new() ) == NULL )
		return( CRYPT_ERROR_MEMORY );
	BN_MONT_CTX_set( pkcInfo->rsaParam_mont_n, pkcInfo->rsaParam_n, bnCTX );
	if( pkcInfo->isPublicKey )
		return( CRYPT_OK );

	/* Precompute the private values */
	if( ( pkcInfo->rsaParam_mont_p = BN_MONT_CTX_new() ) == NULL || \
		( pkcInfo->rsaParam_mont_q = BN_MONT_CTX_new() ) == NULL )
		return( CRYPT_ERROR_MEMORY );
	BN_MONT_CTX_set( pkcInfo->rsaParam_mont_p, pkcInfo->rsaParam_p, bnCTX );
	BN_MONT_CTX_set( pkcInfo->rsaParam_mont_q, pkcInfo->rsaParam_q, bnCTX );

	return( CRYPT_OK );
	}

/* Perform validity checks on the private key */

static BOOLEAN checkPrivateKeyComponents( const PKC_INFO *pkcInfo,
										  BN_CTX *bnCTX )
	{
	BIGNUM *p1, *q1, *tmp;
	BOOLEAN retVal = TRUE;
	const unsigned long e = BN_get_word( pkcInfo->rsaParam_e );

	/* We don't allow bignum e values, both because it doesn't make sense to
	   use them and because the tests below assume that e will fit into a
	   machine word */
	if( e == BN_MASK2 )
		return( FALSE );

	p1 = BN_new();
	q1 = BN_new();
	tmp = BN_new();

	BN_copy( p1, pkcInfo->rsaParam_p );
	BN_sub_word( p1, 1 );
	BN_copy( q1, pkcInfo->rsaParam_q );
	BN_sub_word( q1, 1 );

	/* Verify that n = p * q */
	BN_mul( tmp, pkcInfo->rsaParam_p, pkcInfo->rsaParam_q );
	if( BN_cmp( pkcInfo->rsaParam_n, tmp ) != 0 )
		retVal = FALSE;

	/* Verify that ( d * e ) mod p-1 == 1 and ( d * e ) mod q-1 == 1.  Some
	   implementations don't store d since it's not needed so we can only
	   perform this check if d is present */
	if( !BN_is_zero( pkcInfo->rsaParam_d ) )
		{
		BN_mod_mul( tmp, pkcInfo->rsaParam_d, pkcInfo->rsaParam_e, p1, bnCTX );
		if( !BN_is_one( tmp ) )
			retVal = FALSE;
		BN_mod_mul( tmp, pkcInfo->rsaParam_d, pkcInfo->rsaParam_e, q1, bnCTX );
		if( !BN_is_one( tmp ) )
			retVal = FALSE;
		}

	/* Verify that ( q * u ) mod p == 1 */
	BN_mod_mul( tmp, pkcInfo->rsaParam_q, pkcInfo->rsaParam_u,
				pkcInfo->rsaParam_p, bnCTX );
	if( !BN_is_one( tmp ) )
		retVal = FALSE;

	/* Verify that e is a small prime.  The easiest way to do this would be
	   to compare it to a set of standard values, but there'll always be some
	   wierdo implementation which uses a nonstandard value and which would
	   therefore fail the test, so we perform a quick check which just tries
	   dividing by all primes below 1000.  In addition since in almost all
	   cases e will be one of a standard set of values, we don't bother with
	   the trial division unless it's an unusual value.  This test isn't
	   perfect, but it'll catch obvious non-primes.

	   Note that OpenSSH hardcodes e = 35, which is both a suboptimal
	   exponent (it's less efficient that a safer value like 257 or F4)
	   and non-prime, it's likely that this value is used in error since
	   there's no good reason for using this value.  In order to use OpenSSH
	   keys, you need to comment out this test and the following one */
	if( e != 3 && e != 17 && e != 257 && e != 65537L )
		{
		static const unsigned int smallPrimes[] = {
			   2,   3,   5,   7,  11,  13,  17,  19,
			  23,  29,  31,  37,  41,  43,  47,  53,
			  59,  61,  67,  71,  73,  79,  83,  89,
			  97, 101, 103, 107, 109, 113, 127, 131,
			 137, 139, 149, 151, 157, 163, 167, 173,
			 179, 181, 191, 193, 197, 199, 211, 223,
			 227, 229, 233, 239, 241, 251, 257, 263,
			 269, 271, 277, 281, 283, 293, 307, 311,
			 313, 317, 331, 337, 347, 349, 353, 359,
			 367, 373, 379, 383, 389, 397, 401, 409,
			 419, 421, 431, 433, 439, 443, 449, 457,
			 461, 463, 467, 479, 487, 491, 499, 503,
			 509, 521, 523, 541, 547, 557, 563, 569,
			 571, 577, 587, 593, 599, 601, 607, 613,
			 617, 619, 631, 641, 643, 647, 653, 659,
			 661, 673, 677, 683, 691, 701, 709, 719,
			 727, 733, 739, 743, 751, 757, 761, 769,
			 773, 787, 797, 809, 811, 821, 823, 827,
			 829, 839, 853, 857, 859, 863, 877, 881,
			 883, 887, 907, 911, 919, 929, 937, 941,
			 947, 953, 967, 971, 977, 983, 991, 997,
			 0
			 };
		int i;

		for( i = 0; smallPrimes[ i ] != 0; i++ )
			if( e % smallPrimes[ i ] == 0 )
				retVal = FALSE;
		}

	/* Verify that gcd( ( p - 1 )( q - 1), e ) == 1.  Since e is a small
	   prime, we can do this much more efficiently by checking that
	   ( p - 1 ) mod e != 0 and ( q - 1 ) mod e != 0 */
	if( BN_mod_word( p1, BN_get_word( pkcInfo->rsaParam_e ) ) == 0 || \
		BN_mod_word( q1, BN_get_word( pkcInfo->rsaParam_e ) ) == 0 )
		retVal = FALSE;

	BN_clear_free( tmp );
	BN_clear_free( q1 );
	BN_clear_free( p1 );

	return( retVal );
	}

/****************************************************************************
*																			*
*							Init/Shutdown Routines							*
*																			*
****************************************************************************/

/* Not needed for the RSA routines */

/****************************************************************************
*																			*
*							RSA En/Decryption Routines						*
*																			*
****************************************************************************/

/* Encrypt/signature check a single block of data  */

int rsaEncrypt( CRYPT_INFO *cryptInfo, BYTE *buffer, int noBytes )
	{
	BN_CTX *bnCTX;
	BIGNUM *n;
	const int length = bitsToBytes( cryptInfo->ctxPKC.keySizeBits );
	int i, status = CRYPT_OK;

	assert( noBytes == length );

	/* Make sure we're not being fed suspiciously short data quantities */