| // 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; |
| } |
| #else |
| static void noFuntion( |
| void |
| ) |
| { |
| pAssert(1); |
| } |
| #endif //% |
| #endif // TPM_ALG_RSA |