/* Microsoft Reference Implementation for TPM 2.0 * * The copyright in this software is being made available under the BSD License, * included below. This software may be subject to other third party and * contributor rights, including patent rights, and no such rights are granted * under this license. * * Copyright (c) Microsoft Corporation * * All rights reserved. * * BSD License * * Redistribution and use in source and binary forms, with or without modification, * are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this list * of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, this * list of conditions and the following disclaimer in the documentation and/or * other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ""AS IS"" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ //** 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; //** Functions //*** 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; } //*** 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; } //*** 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); } //*** 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 } //*** 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 Type: BOOL // TRUE(1) probably prime // FALSE(0) 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 //*** 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 } //*** RsaAdjustPrimeCandiate() // 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 2028 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. // LIB_EXPORT void RsaAdjustPrimeCandidate( 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; } //***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 endianess or word size of the CPU. // DRBG_Generate(rand, (BYTE *)prime->d, (UINT16)BITS_TO_BYTES(bits));// old // if(g_inFailureMode) // old if(!BnGetRandomBits(prime, bits, rand)) // new return TPM_RC_FAILURE; RsaAdjustPrimeCandidate(prime); found = RsaCheckPrime(prime, exponent, rand) == TPM_RC_SUCCESS; } return TPM_RC_SUCCESS; } #endif // ALG_RSA