950 lines
32 KiB
C
950 lines
32 KiB
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
|