📄 lib_kg.c
字号:
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 RSA_PUBLIC_EXPONENT
#define RSA_PUBLIC_EXPONENT 65537L
#endif /* RSA_PUBLIC_EXPONENT */
/* Adjust p and q if necessary to ensure that the CRT decrypt works */
static int fixCRTvalues( PKC_INFO *pkcInfo, const BOOLEAN fixPKCSvalues )
{
BIGNUM *p = &pkcInfo->rsaParam_p, *q = &pkcInfo->rsaParam_q;
/* 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 */
static int getRSAMontgomery( PKC_INFO *pkcInfo, const BOOLEAN isPublicKey )
{
/* Evaluate the public value */
if( !BN_MONT_CTX_set( &pkcInfo->rsaParam_mont_n, &pkcInfo->rsaParam_n,
&pkcInfo->bnCTX ) )
return( CRYPT_ERROR_FAILED );
if( isPublicKey )
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 */
int generateRSAkey( CONTEXT_INFO *contextInfoPtr, const int keySizeBits )
{
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;
/* Determine how many bits to give to each of p and q */
pBits = ( keySizeBits + 1 ) / 2;
qBits = keySizeBits - pBits;
pkcInfo->keySizeBits = pBits + qBits;
/* Generate the primes p and q and set them up so that the CRT decrypt
will work */
BN_set_word( &pkcInfo->rsaParam_e, RSA_PUBLIC_EXPONENT );
status = generatePrime( pkcInfo, p, pBits, RSA_PUBLIC_EXPONENT,
contextInfoPtr );
if( cryptStatusOK( status ) )
status = generatePrime( pkcInfo, q, qBits, RSA_PUBLIC_EXPONENT,
contextInfoPtr );
if( cryptStatusOK( status ) )
status = fixCRTvalues( pkcInfo, FALSE );
if( cryptStatusError( status ) )
return( status );
/* Compute d = eInv mod (p - 1)(q - 1), e1 = d mod (p - 1), and
e2 = d mod (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 ) );
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, and 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 */
return( getRSAMontgomery( pkcInfo, FALSE ) );
}
/****************************************************************************
* *
* Initialise/Check an RSA Key *
* *
****************************************************************************/
/* Perform validity checks on the private key. We have to make the PKC_INFO
data non-const because the bignum code wants to modify some of the values
as it's working with them */
static BOOLEAN checkRSAPrivateKeyComponents( PKC_INFO *pkcInfo )
{
BIGNUM *n = &pkcInfo->rsaParam_n, *e = &pkcInfo->rsaParam_e;
BIGNUM *d = &pkcInfo->rsaParam_d, *p = &pkcInfo->rsaParam_p;
BIGNUM *q = &pkcInfo->rsaParam_q;
BIGNUM *p1 = &pkcInfo->tmp1, *q1 = &pkcInfo->tmp2, *tmp = &pkcInfo->tmp3;
const BN_ULONG eWord = BN_get_word( e );
int bnStatus = BN_STATUS;
/* 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( eWord == BN_MASK2 )
return( FALSE );
CKPTR( BN_copy( p1, p ) );
CK( BN_sub_word( p1, 1 ) );
CKPTR( BN_copy( q1, q ) );
CK( BN_sub_word( q1, 1 ) );
if( bnStatusError( bnStatus ) )
return( FALSE );
/* Verify that n = p * q */
CK( BN_mul( tmp, p, q, &pkcInfo->bnCTX ) );
if( bnStatusError( bnStatus ) || BN_cmp( n, tmp ) != 0 )
return( 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 when the CRT
shortcut is used, so we can only perform this check if d is present */
if( !BN_is_zero( d ) )
{
CK( BN_mod_mul( tmp, d, e, p1, &pkcInfo->bnCTX ) );
if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
return( FALSE );
CK( BN_mod_mul( tmp, d, e, q1, &pkcInfo->bnCTX ) );
if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
return( FALSE );
}
/* Verify that ( q * u ) mod p == 1 */
CK( BN_mod_mul( tmp, q, &pkcInfo->rsaParam_u, p, &pkcInfo->bnCTX ) );
if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
return( 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 that uses a nonstandard value and that would
therefore fail the test, so we perform a quick check that 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. The reason for this was that the original SSH used an
e relatively prime to (p-1)(q-1), choosing odd (in both senses of the
word) numbers > 31. 33 or 35 probably ended up being chosen
frequently, so it was hardcoded into OpenSSH. In order to use
OpenSSH keys, you need to comment out this test and the following
one */
if( eWord != 3 && eWord != 17 && eWord != 257 && eWord != 65537L )
{
static const FAR_BSS 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( eWord % smallPrimes[ i ] == 0 )
return( 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, eWord ) == 0 || BN_mod_word( q1, eWord ) == 0 )
return( FALSE );
return( TRUE );
}
/* Initialise and check an RSA key. Unlike the DLP check, this function
combines the initialisation with the checking, since the two are deeply
intertwingled */
int initCheckRSAkey( CONTEXT_INFO *contextInfoPtr )
{
PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
BIGNUM *n = &pkcInfo->rsaParam_n, *e = &pkcInfo->rsaParam_e;
BIGNUM *d = &pkcInfo->rsaParam_d, *p = &pkcInfo->rsaParam_p;
BIGNUM *q = &pkcInfo->rsaParam_q;
int bnStatus = BN_STATUS, status = CRYPT_OK;
/* Make sure that the necessary key parameters have been initialised */
if( BN_is_zero( n ) || BN_is_zero( e ) )
return( CRYPT_ARGERROR_STR1 );
if( !( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) )
{
if( BN_is_zero( p ) || BN_is_zero( q ) )
return( CRYPT_ARGERROR_STR1 );
if( BN_is_zero( d ) && \
( BN_is_zero( &pkcInfo->rsaParam_exponent1 ) || \
BN_is_zero( &pkcInfo->rsaParam_exponent2 ) ) )
/* Either d or e1 et al must be present, d isn't needed if we
have e1 et al and e1 et al can be reconstructed from d */
return( CRYPT_ARGERROR_STR1 );
}
/* Make sure that the key paramters are valid: n > MIN_PKCSIZE_BITS,
e >= 3, |p-q| > 128 bits */
if( BN_num_bits( n ) <= MIN_PKCSIZE_BITS || BN_get_word( e ) < 3 )
return( CRYPT_ARGERROR_STR1 );
if( !( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) )
{
/* Make sure that p and q differ by at least 128 bits */
CKPTR( BN_copy( &pkcInfo->tmp1, p ) );
CK( BN_sub( &pkcInfo->tmp1, &pkcInfo->tmp1, q ) );
if( bnStatusError( bnStatus ) || BN_num_bits( &pkcInfo->tmp1 ) < 128 )
return( CRYPT_ARGERROR_STR1 );
}
/* If we're not using PKCS keys that have exponent1 = d mod ( p - 1 )
and exponent2 = d mod ( q - 1 ) precalculated, evaluate them now.
If there's no u precalculated, evaluate it now */
if( !( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) )
{
if( BN_is_zero( &pkcInfo->rsaParam_exponent1 ) )
{
BIGNUM *exponent1 = &pkcInfo->rsaParam_exponent1;
BIGNUM *exponent2 = &pkcInfo->rsaParam_exponent2;
CKPTR( BN_copy( exponent1, p ) );/* exponent1 = d mod ( p - 1 ) ) */
CK( BN_sub_word( exponent1, 1 ) );
CK( BN_mod( exponent1, d, exponent1, &pkcInfo->bnCTX ) );
CKPTR( BN_copy( exponent2, q ) );/* exponent2 = d mod ( q - 1 ) ) */
CK( BN_sub_word( exponent2, 1 ) );
CK( BN_mod( exponent2, d, exponent2, &pkcInfo->bnCTX ) );
if( bnStatusError( bnStatus ) )
return( getBnStatus( bnStatus ) );
}
if( BN_is_zero( &pkcInfo->rsaParam_u ) )
{
CKPTR( BN_mod_inverse( &pkcInfo->rsaParam_u, q, p,
&pkcInfo->bnCTX ) );
if( bnStatusError( bnStatus ) )
return( getBnStatus( bnStatus ) );
}
}
/* Make sure that p and q are set up correctly for the CRT decryption and
precompute the Montgomery forms */
if( !( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) )
status = fixCRTvalues( pkcInfo, TRUE );
if( cryptStatusOK( status ) )
status = getRSAMontgomery( pkcInfo,
( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) ? \
TRUE : FALSE );
if( cryptStatusError( status ) )
return( status );
/* Now that we've got the various other values set up, perform further
validity checks on the private key */
if( !( contextInfoPtr->flags & CONTEXT_ISPUBLICKEY ) && \
!checkRSAPrivateKeyComponents( pkcInfo ) )
return( CRYPT_ARGERROR_STR1 );
pkcInfo->keySizeBits = BN_num_bits( &pkcInfo->rsaParam_n );
/* Finally, if we're using blinding, calculate the initial blinding
values */
if( contextInfoPtr->flags & CONTEXT_SIDECHANNELPROTECTION )
{
BIGNUM *k = &pkcInfo->rsaParam_blind_k;
BIGNUM *kInv = &pkcInfo->rsaParam_blind_kInv;
RESOURCE_DATA msgData;
BYTE buffer[ CRYPT_MAX_PKCSIZE ];
int noBytes = bitsToBytes( pkcInfo->keySizeBits );
/* Generate a random bignum. 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 */
setMessageData( &msgData, buffer, noBytes );
status = krnlSendMessage( SYSTEM_OBJECT_HANDLE, IMESSAGE_GETATTRIBUTE_S,
&msgData, CRYPT_IATTRIBUTE_RANDOM_NONCE );
if( cryptStatusOK( status ) )
{
buffer[ 0 ] &= 255 >> ( -pkcInfo->keySizeBits & 7 );
status = ( BN_bin2bn( buffer, noBytes, k ) == NULL ) ? \
CRYPT_ERROR_MEMORY : CRYPT_OK;
}
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 ) );
}
return( status );
}
/****************************************************************************
* *
* 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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -