path: root/RSAKeySieve.c

// 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