// This file was extracted from the TCG Published // Trusted Platform Module Library // Part 4: Supporting Routines // Family "2.0" // Level 00 Revision 01.16 // October 30, 2014 #include "OsslCryptoEngine.h" #ifdef TPM_ALG_RSA // // This file produces no code unless the compile switch is set to cause it to generate code. // #ifdef RSA_KEY_SIEVE //% #include "RsaKeySieve.h" // // This next line will show up in the header file for this code. It will make the local functions public when // debugging. // //%#ifdef RSA_DEBUG // // // Bit Manipulation Functions // // Introduction // // These functions operate on a bit array. A bit array is an array of bytes with the 0th byte being the byte // with the lowest memory address. Within the byte, bit 0 is the least significant bit. // // ClearBit() // // This function will CLEAR a bit in a bit array. // void ClearBit( unsigned char *a, // IN: A pointer to an array of byte int i // IN: the number of the bit to CLEAR ) { a[i >> 3] &= 0xff ^ (1 << (i & 7)); } // // // SetBit() // // Function to SET a bit in a bit array. // void SetBit( unsigned char *a, // IN: A pointer to an array of byte int i // IN: the number of the bit to SET ) { a[i >> 3] |= (1 << (i & 7)); } // // // IsBitSet() // // Function to test if a bit in a bit array is SET. // // // // // Return Value Meaning // // 0 bit is CLEAR // 1 bit is SET // UINT32 IsBitSet( unsigned char *a, // IN: A pointer to an array of byte int i // IN: the number of the bit to test ) { return ((a[i >> 3] & (1 << (i & 7))) != 0); } // // // BitsInArry() // // This function counts the number of bits set in an array of bytes. // int BitsInArray( unsigned char *a, // IN: A pointer to an array of byte int i // IN: the number of bytes to sum ) { int j = 0; for(; i ; i--) j += bitsInByte[*a++]; return j; } // // // FindNthSetBit() // // This function finds the nth SET bit in a bit array. The caller should check that the offset of the returned // value is not out of range. If called when the array does not have n bits set, it will return a fatal error // UINT32 FindNthSetBit( const UINT16 aSize, // IN: the size of the array to check const BYTE *a, // IN: the array to check const UINT32 n // IN, the number of the SET bit ) { UINT32 i; const BYTE *pA = a; UINT32 retValue; BYTE sel; (aSize); //find the bit for(i = 0; i < n; i += bitsInByte[*pA++]); // The chosen bit is in the byte that was just accessed // Compute the offset to the start of that byte pA--; retValue = (UINT32)(pA - a) * 8; // Subtract the bits in the last byte added. i -= bitsInByte[*pA]; // Now process the byte, one bit at a time. for(sel = *pA; sel != 0 ; sel = sel >> 1) { if(sel & 1) { i += 1; if(i == n) return retValue; } retValue += 1; } FAIL(FATAL_ERROR_INTERNAL); } // // // Miscellaneous Functions // // RandomForRsa() // // This function uses a special form of KDFa() to produces a pseudo random sequence. It's input is a // structure that contains pointers to a pre-computed set of hash contexts that are set up for the HMAC // computations using the seed. // This function will test that ktx.outer will not wrap to zero if incremented. If so, the function returns FALSE. // Otherwise, the ktx.outer is incremented before each number is generated. // void RandomForRsa( KDFa_CONTEXT *ktx, // IN: a context for the KDF const char *label, // IN: a use qualifying label TPM2B *p // OUT: the pseudo random result ) { INT16 i; UINT32 inner; BYTE swapped[4]; UINT16 fill; BYTE *pb; UINT16 lLen = 0; UINT16 digestSize = _cpri__GetDigestSize(ktx->hashAlg); CPRI_HASH_STATE h; // the working hash context if(label != NULL) for(lLen = 0; label[lLen++];); fill = digestSize; pb = p->buffer; inner = 0; *(ktx->outer) += 1; for(i = p->size; i > 0; i -= digestSize) { inner++; // Initialize the HMAC with saved state _cpri__CopyHashState(&h, &(ktx->iPadCtx)); // Hash the inner counter (the one that changes on each HMAC iteration) UINT32_TO_BYTE_ARRAY(inner, swapped); _cpri__UpdateHash(&h, 4, swapped); if(lLen != 0) _cpri__UpdateHash(&h, lLen, (BYTE *)label); // Is there any party 1 data if(ktx->extra != NULL) _cpri__UpdateHash(&h, ktx->extra->size, ktx->extra->buffer); // Include the outer counter (the one that changes on each prime // prime candidate generation UINT32_TO_BYTE_ARRAY(*(ktx->outer), swapped); _cpri__UpdateHash(&h, 4, swapped); _cpri__UpdateHash(&h, 2, (BYTE *)&ktx->keySizeInBits); if(i < fill) fill = i; _cpri__CompleteHash(&h, fill, pb); // Restart the oPad hash _cpri__CopyHashState(&h, &(ktx->oPadCtx)); // Add the last hashed data _cpri__UpdateHash(&h, fill, pb); // gives a completed HMAC _cpri__CompleteHash(&h, fill, pb); pb += fill; } return; } // // // 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. I all // likelihood, if the number is not prime, the first test fails. // If a KDFa(), PRNG context is provide (ktx), then it is used to provide the random values. Otherwise, the // random numbers are retrieved from the random number generator. // // Return Value Meaning // // TRUE probably prime // FALSE composite // BOOL MillerRabin( BIGNUM *bnW, int iterations, KDFa_CONTEXT *ktx, BN_CTX *context ) { BIGNUM *bnWm1; BIGNUM *bnM; BIGNUM *bnB; BIGNUM *bnZ; BOOL ret = FALSE; // Assumed composite for easy exit TPM2B_TYPE(MAX_PRIME, MAX_RSA_KEY_BYTES/2); TPM2B_MAX_PRIME b; int a; int j; int wLen; int i; pAssert(BN_is_bit_set(bnW, 0)); INSTRUMENT_INC(MillerRabinTrials); // Instrumentation BN_CTX_start(context); bnWm1 = BN_CTX_get(context); bnB = BN_CTX_get(context); bnZ = BN_CTX_get(context); bnM = BN_CTX_get(context); if(bnM == NULL) FAIL(FATAL_ERROR_ALLOCATION); // Let a be the largest integer such that 2^a divides w1. BN_copy(bnWm1, bnW); BN_sub_word(bnWm1, 1); // Since w is odd (w-1) is even so start at bit number 1 rather than 0 for(a = 1; !BN_is_bit_set(bnWm1, a); a++); // 2. m = (w1) / 2^a BN_rshift(bnM, bnWm1, a); // 3. wlen = len (w). wLen = BN_num_bits(bnW); pAssert((wLen & 7) == 0); // Set the size for the random number b.b.size = (UINT16)(wLen + 7)/8; // 4. For i = 1 to iterations do for(i = 0; i < iterations ; i++) { // Obtain a string b of wlen bits from an RBG. step4point1: // In the reference implementation, wLen is always a multiple of 8 if(ktx != NULL) RandomForRsa(ktx, "Miller-Rabin witness", &b.b); else _cpri__GenerateRandom(b.t.size, b.t.buffer); if(BN_bin2bn(b.t.buffer, b.t.size, bnB) == NULL) FAIL(FATAL_ERROR_ALLOCATION); // If ((b 1) or (b w1)), then go to step 4.1. if(BN_is_zero(bnB)) goto step4point1; if(BN_is_one(bnB)) goto step4point1; if(BN_ucmp(bnB, bnWm1) >= 0) goto step4point1; // z = b^m mod w. if(BN_mod_exp(bnZ, bnB, bnM, bnW, context) != 1) FAIL(FATAL_ERROR_ALLOCATION); // If ((z = 1) or (z = w 1)), then go to step 4.7. if(BN_is_one(bnZ) || BN_ucmp(bnZ, bnWm1) == 0) goto step4point7; // For j = 1 to a 1 do. for(j = 1; j < a; j++) { // z = z^2 mod w. if(BN_mod_mul(bnZ, bnZ, bnZ, bnW, context) != 1) FAIL(FATAL_ERROR_ALLOCATION); // If (z = w1), then go to step 4.7. if(BN_ucmp(bnZ, bnWm1) == 0) goto step4point7; // If (z = 1), then go to step 4.6. if(BN_is_one(bnZ)) goto step4point6; } // Return COMPOSITE. step4point6: if(i > 9) INSTRUMENT_INC(failedAtIteration[9]); else INSTRUMENT_INC(failedAtIteration[i]); goto end; // Continue. Comment: Increment i for the do-loop in step 4. step4point7: continue; } // 5. Return PROBABLY PRIME ret = TRUE; end: BN_CTX_end(context); return ret; } // // // NextPrime() // // This function is used to access the next prime number in the sequence of primes. It requires a pre- // initialized iterator. // UINT32 NextPrime( PRIME_ITERATOR *iter ) { if(iter->index >= iter->final) return (iter->lastPrime = 0); return (iter->lastPrime += primeDiffTable[iter->index++]); } // // // AdjustNumberOfPrimes() // // Modifies the input parameter to be a valid value for the number of primes. The adjusted value is either the // input value rounded up to the next 512 bytes boundary or the maximum value of the implementation. If // the input is 0, the return is set to the maximum. // UINT32 AdjustNumberOfPrimes( UINT32 p ) { p = ((p + 511) / 512) * 512; // if(p == 0 || p > PRIME_DIFF_TABLE_BYTES) p = PRIME_DIFF_TABLE_BYTES; return p; } // // // PrimeInit() // // This function is used to initialize the prime sequence generator iterator. The iterator is initialized and // returns the first prime that is equal to the requested starting value. If the starting value is no a prime, then // the iterator is initialized to the next higher prime number. // UINT32 PrimeInit( UINT32 first, // IN: the initial prime PRIME_ITERATOR *iter, // IN/OUT: the iterator structure UINT32 primes // IN: the table length ) { iter->lastPrime = 1; iter->index = 0; iter->final = AdjustNumberOfPrimes(primes); while(iter->lastPrime < first) NextPrime(iter); return iter->lastPrime; } // // // SetDefaultNumberOfPrimes() // // This macro sets the default number of primes to the indicated value. // //%#define SetDefaultNumberOfPrimes(p) (primeTableBytes = AdjustNumberOfPrimes(p)) // // // IsPrimeWord() // // Checks to see if a UINT32 is prime // // Return Value Meaning // // TRUE number is prime // FAIL number is not prime // BOOL IsPrimeWord( UINT32 p // IN: number to test ) { #if defined RSA_KEY_SIEVE && (PRIME_DIFF_TABLE_BYTES >= 6542) UINT32 test; UINT32 index; UINT32 stop; if((p & 1) == 0) return FALSE; if(p == 1 || p == 3) return TRUE; // Get a high value for the stopping point for(index = p, stop = 0; index; index >>= 2) stop = (stop << 1) + 1; stop++; // If the full prime difference value table is present, can check here test = 3; for(index = 1; index < PRIME_DIFF_TABLE_BYTES; index += 1) { if((p % test) == 0) return (p == test); if(test > stop) return TRUE; test += primeDiffTable[index]; } return TRUE; #else BYTE b[4]; if(p == RSA_DEFAULT_PUBLIC_EXPONENT || p == 1 || p == 3 ) return TRUE; if((p & 1) == 0) return FALSE; UINT32_TO_BYTE_ARRAY(p,b); return _math__IsPrime(p); #endif } typedef struct { UINT16 prime; UINT16 count; } SIEVE_MARKS; const SIEVE_MARKS sieveMarks[5] = { {31, 7}, {73, 5}, {241, 4}, {1621, 3}, {UINT16_MAX, 2}}; // // // PrimeSieve() // // This function does a prime sieve over the input field which has as its starting address the value in bnN. // Since this initializes the Sieve using a pre-computed field with the bits associated with 3, 5 and 7 already // turned off, the value of pnN may need to be adjusted by a few counts to allow the pre-computed field to // be used without modification. The fieldSize parameter must be 2^N + 1 and is probably not useful if it is // less than 129 bytes (1024 bits). // UINT32 PrimeSieve( BIGNUM *bnN, // IN/OUT: number to sieve UINT32 fieldSize, // IN: size of the field area in bytes BYTE *field, // IN: field UINT32 primes // IN: the number of primes to use ) { UINT32 i; UINT32 j; UINT32 fieldBits = fieldSize * 8; UINT32 r; const BYTE *p1; BYTE *p2; PRIME_ITERATOR iter; UINT32 adjust; UINT32 mark = 0; UINT32 count = sieveMarks[0].count; UINT32 stop = sieveMarks[0].prime; UINT32 composite; // UINT64 test; //DEBUG pAssert(field != NULL && bnN != NULL); // Need to have a field that has a size of 2^n + 1 bytes pAssert(BitsInArray((BYTE *)&fieldSize, 2) == 2); primes = AdjustNumberOfPrimes(primes); // If the remainder is odd, then subtracting the value // will give an even number, but we want an odd number, // so subtract the 105+rem. Otherwise, just subtract // the even remainder. adjust = BN_mod_word(bnN,105); if(adjust & 1) adjust += 105; // seed the field // This starts the pointer at the nearest byte to the input value p1 = &seedValues[adjust/16]; // Reduce the number of bytes to transfer by the amount skipped j = sizeof(seedValues) - adjust/16; adjust = adjust % 16; BN_sub_word(bnN, adjust); adjust >>= 1; // This offsets the field p2 = field; for(i = fieldSize; i > 0; i--) { *p2++ = *p1++; if(--j == 0) { j = sizeof(seedValues); p1 = seedValues; } } // Mask the first bits in the field and the last byte in order to eliminate // bytes not in the field from consideration. field[0] &= 0xff << adjust; field[fieldSize-1] &= 0xff >> (8 - adjust); // Cycle through the primes, clearing bits // Have already done 3, 5, and 7 PrimeInit(7, &iter, primes); // Get the next N primes where N is determined by the mark in the sieveMarks while((composite = NextPrime(&iter)) != 0) { UINT32 pList[8]; UINT32 next = 0; i = count; pList[i--] = composite; for(; i > 0; i--) { next = NextPrime(&iter); pList[i] = next; if(next != 0) composite *= next; } composite = BN_mod_word(bnN, composite); for(i = count; i > 0; i--) { next = pList[i]; if(next == 0) goto done; r = composite % next; if(r & 1) j = (next - r)/2; else if(r == 0) j = 0; else j = next - r/2; for(; j < fieldBits; j += next) ClearBit(field, j); } if(next >= stop) { mark++; count = sieveMarks[mark].count; stop = sieveMarks[mark].prime; } } done: INSTRUMENT_INC(totalFieldsSieved); i = BitsInArray(field, fieldSize); if(i == 0) INSTRUMENT_INC(emptyFieldsSieved); return i; } // // // PrimeSelectWithSieve() // // This function will sieve the field around the input prime candidate. If the sieve field is not empty, one of // the one bits in the field is chosen for testing with Miller-Rabin. If the value is prime, pnP is updated with // this value and the function returns success. If this value is not prime, another pseudo-random candidate // is chosen and tested. This process repeats until all values in the field have been checked. If all bits in the // field have been checked and none is prime, the function returns FALSE and a new random value needs // to be chosen. // BOOL PrimeSelectWithSieve( BIGNUM *bnP, // IN/OUT: The candidate to filter KDFa_CONTEXT *ktx, // IN: KDFa iterator structure UINT32 e, // IN: the exponent BN_CTX *context // IN: the big number context to play in #ifdef RSA_DEBUG //% ,UINT16 fieldSize, // IN: number of bytes in the field, as // determined by the caller UINT16 primes // IN: number of primes to use. #endif //% ) { BYTE field[MAX_FIELD_SIZE]; UINT32 first; UINT32 ones; INT32 chosen; UINT32 rounds = MillerRabinRounds(BN_num_bits(bnP)); #ifndef RSA_DEBUG UINT32 primes; UINT32 fieldSize; // Adjust the field size and prime table list to fit the size of the prime // being tested. primes = BN_num_bits(bnP); if(primes <= 512) { primes = AdjustNumberOfPrimes(2048); fieldSize = 65; } else if(primes <= 1024) { primes = AdjustNumberOfPrimes(4096); fieldSize = 129; } // else { primes = AdjustNumberOfPrimes(0); // Set to the maximum fieldSize = MAX_FIELD_SIZE; } if(fieldSize > MAX_FIELD_SIZE) fieldSize = MAX_FIELD_SIZE; #endif // Save the low-order word to use as a search generator and make sure that // it has some interesting range to it first = bnP->d[0] | 0x80000000; // Align to field boundary bnP->d[0] &= ~((UINT32)(fieldSize-3)); pAssert(BN_is_bit_set(bnP, 0)); bnP->d[0] &= (UINT32_MAX << (FIELD_POWER + 1)) + 1; ones = PrimeSieve(bnP, fieldSize, field, primes); #ifdef RSA_FILTER_DEBUG pAssert(ones == BitsInArray(field, defaultFieldSize)); #endif for(; ones > 0; ones--) { #ifdef RSA_FILTER_DEBUG if(ones != BitsInArray(field, defaultFieldSize)) FAIL(FATAL_ERROR_INTERNAL); #endif // Decide which bit to look at and find its offset if(ones == 1) ones = ones; chosen = FindNthSetBit(defaultFieldSize, field,((first % ones) + 1)); if(chosen >= ((defaultFieldSize) * 8)) FAIL(FATAL_ERROR_INTERNAL); // Set this as the trial prime BN_add_word(bnP, chosen * 2); // Use MR to see if this is prime if(MillerRabin(bnP, rounds, ktx, context)) { // Final check is to make sure that 0 != (p-1) mod e // This is the same as -1 != p mod e ; or // (e - 1) != p mod e if((e <= 3) || (BN_mod_word(bnP, e) != (e-1))) return TRUE; } // Back out the bit number BN_sub_word(bnP, chosen * 2); // Clear the bit just tested ClearBit(field, chosen); } // Ran out of bits and couldn't find a prime in this field INSTRUMENT_INC(noPrimeFields); return FALSE; } // // // AdjustPrimeCandiate() // // 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 is approximated with 0xB505 which is, in fixed point is 0.7071075439453125 or an // error of 0.0001%. 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. // The function also puts the number on a field boundary. // void AdjustPrimeCandidate( BYTE *a, UINT16 len ) { UINT16 highBytes; highBytes = BYTE_ARRAY_TO_UINT16(a); // This is fixed point arithmetic on 16-bit values highBytes = ((UINT32)highBytes * (UINT32)0x4AFB) >> 16; highBytes += 0xB505; UINT16_TO_BYTE_ARRAY(highBytes, a); a[len-1] |= 1; } // // // GeneratateRamdomPrime() // void GenerateRandomPrime( TPM2B *p, BN_CTX *ctx #ifdef RSA_DEBUG //% ,UINT16 field, UINT16 primes #endif //% ) { BIGNUM *bnP; BN_CTX *context; if(ctx == NULL) context = BN_CTX_new(); else context = ctx; if(context == NULL) FAIL(FATAL_ERROR_ALLOCATION); BN_CTX_start(context); bnP = BN_CTX_get(context); while(TRUE) { _cpri__GenerateRandom(p->size, p->buffer); p->buffer[p->size-1] |= 1; p->buffer[0] |= 0x80; BN_bin2bn(p->buffer, p->size, bnP); #ifdef RSA_DEBUG if(PrimeSelectWithSieve(bnP, NULL, 0, context, field, primes)) #else if(PrimeSelectWithSieve(bnP, NULL, 0, context)) #endif break; } BnTo2B(p, bnP, (UINT16)BN_num_bytes(bnP)); BN_CTX_end(context); if(ctx == NULL) BN_CTX_free(context); return; } KDFa_CONTEXT * KDFaContextStart( KDFa_CONTEXT *ktx, // IN/OUT: the context structure to initialize TPM2B *seed, // IN: the seed for the digest proce TPM_ALG_ID hashAlg, // IN: the hash algorithm TPM2B *extra, // IN: the extra data UINT32 *outer, // IN: the outer iteration counter UINT16 keySizeInBit ) { UINT16 digestSize = _cpri__GetDigestSize(hashAlg); TPM2B_HASH_BLOCK oPadKey; if(seed == NULL) return NULL; pAssert(ktx != NULL && outer != NULL && digestSize != 0); // Start the hash using the seed and get the intermediate hash value _cpri__StartHMAC(hashAlg, FALSE, &(ktx->iPadCtx), seed->size, seed->buffer, &oPadKey.b); _cpri__StartHash(hashAlg, FALSE, &(ktx->oPadCtx)); _cpri__UpdateHash(&(ktx->oPadCtx), oPadKey.b.size, oPadKey.b.buffer); ktx->extra = extra; ktx->hashAlg = hashAlg; ktx->outer = outer; ktx->keySizeInBits = keySizeInBits; return ktx; } void KDFaContextEnd( KDFa_CONTEXT *ktx // IN/OUT: the context structure to close ) { if(ktx != NULL) { // Close out the hash sessions _cpri__CompleteHash(&(ktx->iPadCtx), 0, NULL); _cpri__CompleteHash(&(ktx->oPadCtx), 0, NULL); } } //%#endif // // // Public Function // // Introduction // // This is the external entry for this replacement function. All this file provides is the substitute function to // generate an RSA key. If the compiler settings are set appropriately, this this function will be used instead // of the similarly named function in CpriRSA.c. // // _cpri__GenerateKeyRSA() // // Generate an RSA key from a provided seed // // Return Value Meaning // // CRYPT_FAIL exponent is not prime or is less than 3; or could not find a prime using // the provided parameters // CRYPT_CANCEL operation was canceled // LIB_EXPORT CRYPT_RESULT _cpri__GenerateKeyRSA( TPM2B *n, // OUT: The public modulus TPM2B *p, // OUT: One of the prime factors of n UINT16 keySizeInBits, // IN: Size of the public modulus in bits UINT32 e, // IN: The public exponent TPM_ALG_ID hashAlg, // IN: hash algorithm to use in the key // generation process TPM2B *seed, // IN: the seed to use const char *label, // IN: A label for the generation process. TPM2B *extra, // IN: Party 1 data for the KDF UINT32 *counter // IN/OUT: Counter value to allow KDF // iteration to be propagated across // multiple routines #ifdef RSA_DEBUG //% ,UINT16 primes, // IN: number of primes to test UINT16 fieldSize // IN: the field size to use #endif //% ) { CRYPT_RESULT retVal; UINT32 myCounter = 0; UINT32 *pCtr = (counter == NULL) ? &myCounter : counter; KDFa_CONTEXT ktx; KDFa_CONTEXT *ktxPtr; UINT32 i; BIGNUM *bnP; BIGNUM *bnQ; BIGNUM *bnT; BIGNUM *bnE; BIGNUM *bnN; BN_CTX *context; // Make sure that the required pointers are provided pAssert(n != NULL && p != NULL); // If the seed is provided, then use KDFa for generation of the 'random' // values ktxPtr = KDFaContextStart(&ktx, seed, hashAlg, extra, pCtr, keySizeInBits); n->size = keySizeInBits/8; p->size = n->size / 2; // Validate exponent if(e == 0 || e == RSA_DEFAULT_PUBLIC_EXPONENT) e = RSA_DEFAULT_PUBLIC_EXPONENT; else if(!IsPrimeWord(e)) return CRYPT_FAIL; // Get structures for the big number representations context = BN_CTX_new(); BN_CTX_start(context); bnP = BN_CTX_get(context); bnQ = BN_CTX_get(context); bnT = BN_CTX_get(context); bnE = BN_CTX_get(context); bnN = BN_CTX_get(context); if(bnN == NULL) FAIL(FATAL_ERROR_INTERNAL); // Set Q to zero. This is used as a flag. The prime is computed in P. When a // new prime is found, Q is checked to see if it is zero. If so, P is copied // to Q and a new P is found. When both P and Q are non-zero, the modulus and // private exponent are computed and a trial encryption/decryption is // performed. If the encrypt/decrypt fails, assume that at least one of the // primes is composite. Since we don't know which one, set Q to zero and start // over and find a new pair of primes. BN_zero(bnQ); BN_set_word(bnE, e); // Each call to generate a random value will increment ktx.outer // it doesn't matter if ktx.outer wraps. This lets the caller // use the initial value of the counter for additional entropy. for(i = 0; i < UINT32_MAX; i++) { if(_plat__IsCanceled()) { retVal = CRYPT_CANCEL; goto end; } // Get a random prime candidate. if(seed == NULL) _cpri__GenerateRandom(p->size, p->buffer); else RandomForRsa(&ktx, label, p); AdjustPrimeCandidate(p->buffer, p->size); // Convert the candidate to a BN if(BN_bin2bn(p->buffer, p->size, bnP) == NULL) FAIL(FATAL_ERROR_INTERNAL); // If this is the second prime, make sure that it differs from the // first prime by at least 2^100. Since BIGNUMS use words, the check // below will make sure they are different by at least 128 bits if(!BN_is_zero(bnQ)) { // bnQ is non-zero, we have a first value UINT32 *pP = (UINT32 *)(&bnP->d[4]); UINT32 *pQ = (UINT32 *)(&bnQ->d[4]); INT32 k = ((INT32)bnP->top) - 4; for(;k > 0; k--) if(*pP++ != *pQ++) break; // Didn't find any difference so go get a new value if(k == 0) continue; } // If PrimeSelectWithSieve returns success, bnP is a prime, #ifdef RSA_DEBUG if(!PrimeSelectWithSieve(bnP, ktxPtr, e, context, fieldSize, primes)) #else if(!PrimeSelectWithSieve(bnP, ktxPtr, e, context)) #endif continue; // If not, get another // Found a prime, is this the first or second. if(BN_is_zero(bnQ)) { // copy p to q and compute another prime in p BN_copy(bnQ, bnP); continue; } //Form the public modulus if( BN_mul(bnN, bnP, bnQ, context) != 1 || BN_num_bits(bnN) != keySizeInBits) FAIL(FATAL_ERROR_INTERNAL); // Save the public modulus BnTo2B(n, bnN, n->size); // And one prime BnTo2B(p, bnP, p->size); #ifdef EXTENDED_CHECKS // Finish by making sure that we can form the modular inverse of PHI // with respect to the public exponent // Compute PHI = (p - 1)(q - 1) = n - p - q + 1 // Make sure that we can form the modular inverse if( BN_sub(bnT, bnN, bnP) != 1 || BN_sub(bnT, bnT, bnQ) != 1 || BN_add_word(bnT, 1) != 1) FAIL(FATAL_ERROR_INTERNAL); // find d such that (Phi * d) mod e ==1 // If there isn't then we are broken because we took the step // of making sure that the prime != 1 mod e so the modular inverse // must exist if( BN_mod_inverse(bnT, bnE, bnT, context) == NULL || BN_is_zero(bnT)) FAIL(FATAL_ERROR_INTERNAL); // And, finally, do a trial encryption decryption { TPM2B_TYPE(RSA_KEY, MAX_RSA_KEY_BYTES); TPM2B_RSA_KEY r; r.t.size = sizeof(r.t.buffer); // If we are using a seed, then results must be reproducible on each // call. Otherwise, just get a random number if(seed == NULL) _cpri__GenerateRandom(keySizeInBits/8, r.t.buffer); else RandomForRsa(&ktx, label, &r.b); // Make sure that the number is smaller than the public modulus r.t.buffer[0] &= 0x7F; // Convert if( BN_bin2bn(r.t.buffer, r.t.size, bnP) == NULL // Encrypt with the public exponent || BN_mod_exp(bnQ, bnP, bnE, bnN, context) != 1 // Decrypt with the private exponent || BN_mod_exp(bnQ, bnQ, bnT, bnN, context) != 1) FAIL(FATAL_ERROR_INTERNAL); // If the starting and ending values are not the same, start over )-; if(BN_ucmp(bnP, bnQ) != 0) { BN_zero(bnQ); continue; } } #endif // EXTENDED_CHECKS retVal = CRYPT_SUCCESS; goto end; } retVal = CRYPT_FAIL; end: KDFaContextEnd(&ktx); // Free up allocated BN values BN_CTX_end(context); BN_CTX_free(context); return retVal; } #endif //% #endif // TPM_ALG_RSA