diff options
Diffstat (limited to 'src/tpm2/crypto/openssl/CryptPrime.c')
| -rw-r--r-- | src/tpm2/crypto/openssl/CryptPrime.c | 440 |
1 files changed, 440 insertions, 0 deletions
diff --git a/src/tpm2/crypto/openssl/CryptPrime.c b/src/tpm2/crypto/openssl/CryptPrime.c new file mode 100644 index 0000000..0de9ef2 --- /dev/null +++ b/src/tpm2/crypto/openssl/CryptPrime.c @@ -0,0 +1,440 @@ +/********************************************************************************/ +/* */ +/* Code for prime validation. */ +/* Written by Ken Goldman */ +/* IBM Thomas J. Watson Research Center */ +/* $Id: CryptPrime.c 1529 2019-11-21 23:29:01Z kgoldman $ */ +/* */ +/* Licenses and Notices */ +/* */ +/* 1. Copyright Licenses: */ +/* */ +/* - Trusted Computing Group (TCG) grants to the user of the source code in */ +/* this specification (the "Source Code") a worldwide, irrevocable, */ +/* nonexclusive, royalty free, copyright license to reproduce, create */ +/* derivative works, distribute, display and perform the Source Code and */ +/* derivative works thereof, and to grant others the rights granted herein. */ +/* */ +/* - The TCG grants to the user of the other parts of the specification */ +/* (other than the Source Code) the rights to reproduce, distribute, */ +/* display, and perform the specification solely for the purpose of */ +/* developing products based on such documents. */ +/* */ +/* 2. Source Code Distribution Conditions: */ +/* */ +/* - Redistributions of Source Code must retain the above copyright licenses, */ +/* this list of conditions and the following disclaimers. */ +/* */ +/* - Redistributions in binary form must reproduce the above copyright */ +/* licenses, this list of conditions and the following disclaimers in the */ +/* documentation and/or other materials provided with the distribution. */ +/* */ +/* 3. Disclaimers: */ +/* */ +/* - THE COPYRIGHT LICENSES SET FORTH ABOVE DO NOT REPRESENT ANY FORM OF */ +/* LICENSE OR WAIVER, EXPRESS OR IMPLIED, BY ESTOPPEL OR OTHERWISE, WITH */ +/* RESPECT TO PATENT RIGHTS HELD BY TCG MEMBERS (OR OTHER THIRD PARTIES) */ +/* THAT MAY BE NECESSARY TO IMPLEMENT THIS SPECIFICATION OR OTHERWISE. */ +/* Contact TCG Administration (admin@trustedcomputinggroup.org) for */ +/* information on specification licensing rights available through TCG */ +/* membership agreements. */ +/* */ +/* - THIS SPECIFICATION IS PROVIDED "AS IS" WITH NO EXPRESS OR IMPLIED */ +/* WARRANTIES WHATSOEVER, INCLUDING ANY WARRANTY OF MERCHANTABILITY OR */ +/* FITNESS FOR A PARTICULAR PURPOSE, ACCURACY, COMPLETENESS, OR */ +/* NONINFRINGEMENT OF INTELLECTUAL PROPERTY RIGHTS, OR ANY WARRANTY */ +/* OTHERWISE ARISING OUT OF ANY PROPOSAL, SPECIFICATION OR SAMPLE. */ +/* */ +/* - Without limitation, TCG and its members and licensors disclaim all */ +/* liability, including liability for infringement of any proprietary */ +/* rights, relating to use of information in this specification and to the */ +/* implementation of this specification, and TCG disclaims all liability for */ +/* cost of procurement of substitute goods or services, lost profits, loss */ +/* of use, loss of data or any incidental, consequential, direct, indirect, */ +/* or special damages, whether under contract, tort, warranty or otherwise, */ +/* arising in any way out of use or reliance upon this specification or any */ +/* information herein. */ +/* */ +/* (c) Copyright IBM Corp. and others, 2016 - 2019 */ +/* */ +/********************************************************************************/ + +/* 10.2.14 CryptPrime.c */ +/* 10.2.14.1 Introduction */ +/* This file contains the code for prime validation. */ + +#include "Tpm.h" +#include "CryptPrime_fp.h" +//#define CPRI_PRIME +//#include "PrimeTable.h" +#include "CryptPrimeSieve_fp.h" +extern const uint32_t s_LastPrimeInTable; +extern const uint32_t s_PrimeTableSize; +extern const uint32_t s_PrimesInTable; +extern const unsigned char s_PrimeTable[]; +extern bigConst s_CompositeOfSmallPrimes; + +/* 10.2.14.1.1 Root2() */ +/* This finds ceil(sqrt(n)) to use as a stopping point for searching the prime table. */ +static uint32_t +Root2( + uint32_t n + ) +{ + int32_t last = (int32_t)(n >> 2); + int32_t next = (int32_t)(n >> 1); + int32_t diff; + int32_t stop = 10; + // + // get a starting point + for(; next != 0; last >>= 1, next >>= 2); + last++; + do + { + next = (last + (n / last)) >> 1; + diff = next - last; + last = next; + if(stop-- == 0) + FAIL(FATAL_ERROR_INTERNAL); + } while(diff < -1 || diff > 1); + if((n / next) > (unsigned)next) + next++; + pAssert(next != 0); + pAssert(((n / next) <= (unsigned)next) && (n / (next + 1) < (unsigned)next)); + return next; +} +/* 10.2.14.1.2 IsPrimeInt() */ +/* This will do a test of a word of up to 32-bits in size. */ +BOOL +IsPrimeInt( + uint32_t n + ) +{ + uint32_t i; + uint32_t stop; + if(n < 3 || ((n & 1) == 0)) + return (n == 2); + if(n <= s_LastPrimeInTable) + { + n >>= 1; + return ((s_PrimeTable[n >> 3] >> (n & 7)) & 1); + } + // Need to search + stop = Root2(n) >> 1; + // starting at 1 is equivalent to staring at (1 << 1) + 1 = 3 + for(i = 1; i < stop; i++) + { + if((s_PrimeTable[i >> 3] >> (i & 7)) & 1) + // see if this prime evenly divides the number + if((n % ((i << 1) + 1)) == 0) + return FALSE; + } + return TRUE; +} +#if !RSA_KEY_SIEVE // libtpms added +/* 10.2.14.1.3 BnIsProbablyPrime() */ +/* This function is used when the key sieve is not implemented. This function Will try to eliminate + some of the obvious things before going on to perform MillerRabin() as a final verification of + primeness. */ +BOOL +BnIsProbablyPrime( + bigNum prime, // IN: + RAND_STATE *rand // IN: the random state just + // in case Miller-Rabin is required + ) +{ +#if RADIX_BITS > 32 + if(BnUnsignedCmpWord(prime, UINT32_MAX) <= 0) +#else + if(BnGetSize(prime) == 1) +#endif + return IsPrimeInt((uint32_t)prime->d[0]); + if(BnIsEven(prime)) + return FALSE; + if(BnUnsignedCmpWord(prime, s_LastPrimeInTable) <= 0) + { + crypt_uword_t temp = prime->d[0] >> 1; + return ((s_PrimeTable[temp >> 3] >> (temp & 7)) & 1); + } + { + BN_VAR(n, LARGEST_NUMBER_BITS); + BnGcd(n, prime, s_CompositeOfSmallPrimes); + if(!BnEqualWord(n, 1)) + return FALSE; + } + return MillerRabin(prime, rand); +} +#endif // libtpms added +/* 10.2.14.1.4 MillerRabinRounds() */ +/* Function returns the number of Miller-Rabin rounds necessary to give an error probability equal + to the security strength of the prime. These values are from FIPS 186-3. */ +UINT32 +MillerRabinRounds( + UINT32 bits // IN: Number of bits in the RSA prime + ) +{ + if(bits < 511) return 8; // don't really expect this + if(bits < 1536) return 5; // for 512 and 1K primes + return 4; // for 3K public modulus and greater +} +/* 10.2.14.1.5 MillerRabin() */ +/* This function performs a Miller-Rabin test from FIPS 186-3. It does iterations trials on the + number. In all likelihood, if the number is not prime, the first test fails. */ +/* Return Values Meaning */ +/* TRUE probably prime */ +/* FALSE composite */ +BOOL +MillerRabin( + bigNum bnW, + RAND_STATE *rand + ) +{ + BN_MAX(bnWm1); + BN_PRIME(bnM); + BN_PRIME(bnB); + BN_PRIME(bnZ); + BOOL ret = FALSE; // Assumed composite for easy exit + unsigned int a; + unsigned int j; + int wLen; + int i; + int iterations = MillerRabinRounds(BnSizeInBits(bnW)); + // + INSTRUMENT_INC(MillerRabinTrials[PrimeIndex]); + + pAssert(bnW->size > 1); + // Let a be the largest integer such that 2^a divides w1. + BnSubWord(bnWm1, bnW, 1); + pAssert(bnWm1->size != 0); + + // Since w is odd (w-1) is even so start at bit number 1 rather than 0 + // Get the number of bits in bnWm1 so that it doesn't have to be recomputed + // on each iteration. + i = (int)(bnWm1->size * RADIX_BITS); + // Now find the largest power of 2 that divides w1 + for(a = 1; + (a < (bnWm1->size * RADIX_BITS)) && + (BnTestBit(bnWm1, a) == 0); + a++); + // 2. m = (w1) / 2^a + BnShiftRight(bnM, bnWm1, a); + // 3. wlen = len (w). + wLen = BnSizeInBits(bnW); + // 4. For i = 1 to iterations do + for(i = 0; i < iterations; i++) + { + // 4.1 Obtain a string b of wlen bits from an RBG. + // Ensure that 1 < b < w1. + // 4.2 If ((b <= 1) or (b >= w1)), then go to step 4.1. + while(BnGetRandomBits(bnB, wLen, rand) && ((BnUnsignedCmpWord(bnB, 1) <= 0) + || (BnUnsignedCmp(bnB, bnWm1) >= 0))); + if(g_inFailureMode) + return FALSE; + + // 4.3 z = b^m mod w. + // if ModExp fails, then say this is not + // prime and bail out. + BnModExp(bnZ, bnB, bnM, bnW); + + // 4.4 If ((z == 1) or (z = w == 1)), then go to step 4.7. + if((BnUnsignedCmpWord(bnZ, 1) == 0) + || (BnUnsignedCmp(bnZ, bnWm1) == 0)) + goto step4point7; + // 4.5 For j = 1 to a 1 do. + for(j = 1; j < a; j++) + { + // 4.5.1 z = z^2 mod w. + BnModMult(bnZ, bnZ, bnZ, bnW); + // 4.5.2 If (z = w1), then go to step 4.7. + if(BnUnsignedCmp(bnZ, bnWm1) == 0) + goto step4point7; + // 4.5.3 If (z = 1), then go to step 4.6. + if(BnEqualWord(bnZ, 1)) + goto step4point6; + } + // 4.6 Return COMPOSITE. + step4point6: + INSTRUMENT_INC(failedAtIteration[i]); + goto end; + // 4.7 Continue. Comment: Increment i for the do-loop in step 4. + step4point7: + continue; + } + // 5. Return PROBABLY PRIME + ret = TRUE; + end: + return ret; +} +#if ALG_RSA +/* 10.2.14.1.6 RsaCheckPrime() */ +/* This will check to see if a number is prime and appropriate for an RSA prime. */ +/* This has different functionality based on whether we are using key sieving or not. If not, the + number checked to see if it is divisible by the public exponent, then the number is adjusted + either up or down in order to make it a better candidate. It is then checked for being probably + prime. */ +/* If sieving is used, the number is used to root a sieving process. */ +TPM_RC +RsaCheckPrime( + bigNum prime, + UINT32 exponent, + RAND_STATE *rand + ) +{ +#if !RSA_KEY_SIEVE + TPM_RC retVal = TPM_RC_SUCCESS; + UINT32 modE = BnModWord(prime, exponent); + NOT_REFERENCED(rand); + if(modE == 0) + // evenly divisible so add two keeping the number odd + BnAddWord(prime, prime, 2); + // want 0 != (p - 1) mod e + // which is 1 != p mod e + else if(modE == 1) + // subtract 2 keeping number odd and insuring that + // 0 != (p - 1) mod e + BnSubWord(prime, prime, 2); + if(BnIsProbablyPrime(prime, rand) == 0) + ERROR_RETURN(g_inFailureMode ? TPM_RC_FAILURE : TPM_RC_VALUE); + Exit: + return retVal; +#else + return PrimeSelectWithSieve(prime, exponent, rand); +#endif +} +/* + * RsaAdjustPrimeCandidate_PreRev155 is the pre-rev.155 algorithm used; we + * still have to use it for old seeds to maintain backwards compatibility. + */ +static void +RsaAdjustPrimeCandidate_PreRev155( + bigNum prime + ) +{ + UINT16 highBytes; + crypt_uword_t *msw = &prime->d[prime->size - 1]; +#define MASK (MAX_CRYPT_UWORD >> (RADIX_BITS - 16)) + highBytes = *msw >> (RADIX_BITS - 16); + // This is fixed point arithmetic on 16-bit values + highBytes = ((UINT32)highBytes * (UINT32)0x4AFB) >> 16; + highBytes += 0xB505; + *msw = ((crypt_uword_t)(highBytes) << (RADIX_BITS - 16)) + (*msw & MASK); + prime->d[0] |= 1; +} + +/* 10.2.14.1.7 RsaAdjustPrimeCandidate() */ + +/* For this math, we assume that the RSA numbers are fixed-point numbers with the decimal point to + the left of the most significant bit. This approach helps make it clear what is happening with + the MSb of the values. The two RSA primes have to be large enough so that their product will be a + number with the necessary number of significant bits. For example, we want to be able to multiply + two 1024-bit numbers to produce a number with 2048 significant bits. If we accept any 1024-bit + prime that has its MSb set, then it is possible to produce a product that does not have the MSb + SET. For example, if we use tiny keys of 16 bits and have two 8-bit primes of 0x80, then the + public key would be 0x4000 which is only 15-bits. So, what we need to do is made sure that each + of the primes is large enough so that the product of the primes is twice as large as each + prime. A little arithmetic will show that the only way to do this is to make sure that each of + the primes is no less than root(2)/2. That's what this functions does. This function adjusts the + candidate prime so that it is odd and >= root(2)/2. This allows the product of these two numbers + to be .5, which, in fixed point notation means that the most significant bit is 1. For this + routine, the root(2)/2 (0.7071067811865475) approximated with 0xB505 which is, in fixed point, + 0.7071075439453125 or an error of 0.000108%. Just setting the upper two bits would give a value > + 0.75 which is an error of > 6%. Given the amount of time all the other computations take, + reducing the error is not much of a cost, but it isn't totally required either. */ +/* This function can be replaced with a function that just sets the two most significant bits of + each prime candidate without introducing any computational issues. */ + +static void +RsaAdjustPrimeCandidate_New( + bigNum prime + ) +{ + UINT32 msw; + UINT32 adjusted; + + // If the radix is 32, the compiler should turn this into a simple assignment + msw = prime->d[prime->size - 1] >> ((RADIX_BITS == 64) ? 32 : 0); + // Multiplying 0xff...f by 0x4AFB gives 0xff..f - 0xB5050...0 + adjusted = (msw >> 16) * 0x4AFB; + adjusted += ((msw & 0xFFFF) * 0x4AFB) >> 16; + adjusted += 0xB5050000UL; +#if RADIX_BITS == 64 + // Save the low-order 32 bits + prime->d[prime->size - 1] &= 0xFFFFFFFFUL; + // replace the upper 32-bits + prime->d[prime->size -1] |= ((crypt_uword_t)adjusted << 32); +#else + prime->d[prime->size - 1] = (crypt_uword_t)adjusted; +#endif + // make sure the number is odd + prime->d[0] |= 1; +} + + +LIB_EXPORT void +RsaAdjustPrimeCandidate( + bigNum prime, + SEED_COMPAT_LEVEL seedCompatLevel // IN: compatibility level; libtpms added + ) +{ + switch (seedCompatLevel) { + case SEED_COMPAT_LEVEL_ORIGINAL: + RsaAdjustPrimeCandidate_PreRev155(prime); + break; + case SEED_COMPAT_LEVEL_LAST: + /* case SEED_COMPAT_LEVEL_RSA_PRIME_ADJUST_FIX: */ + RsaAdjustPrimeCandidate_New(prime); + break; + default: + FAIL(FATAL_ERROR_INTERNAL); + } +} +/* 10.2.14.1.8 BnGeneratePrimeForRSA() */ +/* Function to generate a prime of the desired size with the proper attributes for an RSA prime. */ + +TPM_RC +BnGeneratePrimeForRSA( + bigNum prime, // IN/OUT: points to the BN that will get the + // random value + UINT32 bits, // IN: number of bits to get + UINT32 exponent, // IN: the exponent + RAND_STATE *rand // IN: the random state + ) +{ + BOOL found = FALSE; + // + // Make sure that the prime is large enough + pAssert(prime->allocated >= BITS_TO_CRYPT_WORDS(bits)); + // Only try to handle specific sizes of keys in order to save overhead + pAssert((bits % 32) == 0); + + prime->size = BITS_TO_CRYPT_WORDS(bits); + + while(!found) + { + // The change below is to make sure that all keys that are generated from the same + // seed value will be the same regardless of the endianness or word size of the CPU. + // DRBG_Generate(rand, (BYTE *)prime->d, (UINT16)BITS_TO_BYTES(bits));// old + // if(g_inFailureMode) // old + // libtpms changed begin + switch (DRBG_GetSeedCompatLevel(rand)) { + case SEED_COMPAT_LEVEL_ORIGINAL: + DRBG_Generate(rand, (BYTE *)prime->d, (UINT16)BITS_TO_BYTES(bits)); + if (g_inFailureMode) + return TPM_RC_FAILURE; + break; + case SEED_COMPAT_LEVEL_LAST: + /* case SEED_COMPAT_LEVEL_RSA_PRIME_ADJUST_FIX: */ + if(!BnGetRandomBits(prime, bits, rand)) // new + return TPM_RC_FAILURE; + break; + default: + FAIL(FATAL_ERROR_INTERNAL); + } + RsaAdjustPrimeCandidate(prime, DRBG_GetSeedCompatLevel(rand)); + // libtpms changed end + found = RsaCheckPrime(prime, exponent, rand) == TPM_RC_SUCCESS; + } + return TPM_RC_SUCCESS; +} + +#endif // TPM_ALG_RSA |