// 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 <string.h>
#include "CryptoEngine.h"
#ifndef EMBEDDED_MODE
#include "OsslCryptoEngine.h"
//
//
// Externally Accessible Functions
//
// _math__Normalize2B()
//
// This function will normalize the value in a TPM2B. If there are leading bytes of zero, the first non-zero
// byte is shifted up.
//
// Return Value Meaning
//
// 0 no significant bytes, value is zero
// >0 number of significant bytes
//
LIB_EXPORT UINT16
_math__Normalize2B(
TPM2B *b // IN/OUT: number to normalize
)
{
UINT16 from;
UINT16 to;
UINT16 size = b->size;
for(from = 0; b->buffer[from] == 0 && from < size; from++);
b->size -= from;
for(to = 0; from < size; to++, from++ )
b->buffer[to] = b->buffer[from];
return b->size;
}
//
//
//
// _math__Denormalize2B()
//
// This function is used to adjust a TPM2B so that the number has the desired number of bytes. This is
// accomplished by adding bytes of zero at the start of the number.
//
// Return Value Meaning
//
// TRUE number de-normalized
// FALSE number already larger than the desired size
//
LIB_EXPORT BOOL
_math__Denormalize2B(
TPM2B *in, // IN:OUT TPM2B number to de-normalize
UINT32 size // IN: the desired size
)
{
UINT32 to;
UINT32 from;
// If the current size is greater than the requested size, see if this can be
// normalized to a value smaller than the requested size and then de-normalize
if(in->size > size)
{
_math__Normalize2B(in);
if(in->size > size)
return FALSE;
}
// If the size is already what is requested, leave
if(in->size == size)
return TRUE;
// move the bytes to the 'right'
for(from = in->size, to = size; from > 0;)
in->buffer[--to] = in->buffer[--from];
// 'to' will always be greater than 0 because we checked for equal above.
for(; to > 0;)
in->buffer[--to] = 0;
in->size = (UINT16)size;
return TRUE;
}
//
//
// _math__sub()
//
// This function to subtract one unsigned value from another c = a - b. c may be the same as a or b.
//
// Return Value Meaning
//
// 1 if (a > b) so no borrow
// 0 if (a = b) so no borrow and b == a
// -1 if (a < b) so there was a borrow
//
LIB_EXPORT int
_math__sub(
const UINT32 aSize, // IN: size of a
const BYTE *a, // IN: a
const UINT32 bSize, // IN: size of b
const BYTE *b, // IN: b
UINT16 *cSize, // OUT: set to MAX(aSize, bSize)
BYTE *c // OUT: the difference
)
{
int borrow = 0;
int notZero = 0;
int i;
int i2;
// set c to the longer of a or b
*cSize = (UINT16)((aSize > bSize) ? aSize : bSize);
// pick the shorter of a and b
i = (aSize > bSize) ? bSize : aSize;
i2 = *cSize - i;
a = &a[aSize - 1];
b = &b[bSize - 1];
c = &c[*cSize - 1];
for(; i > 0; i--)
{
borrow = *a-- - *b-- + borrow;
*c-- = (BYTE)borrow;
notZero = notZero || borrow;
borrow >>= 8;
}
if(aSize > bSize)
{
for(;i2 > 0; i2--)
{
borrow = *a-- + borrow;
*c-- = (BYTE)borrow;
notZero = notZero || borrow;
borrow >>= 8;
}
}
else if(aSize < bSize)
{
for(;i2 > 0; i2--)
{
borrow = 0 - *b-- + borrow;
*c-- = (BYTE)borrow;
notZero = notZero || borrow;
borrow >>= 8;
}
}
// if there is a borrow, then b > a
if(borrow)
return -1;
// either a > b or they are the same
return notZero;
}
//
//
// _math__Inc()
//
// This function increments a large, big-endian number value by one.
//
// Return Value Meaning
//
// 0 result is zero
// !0 result is not zero
//
LIB_EXPORT int
_math__Inc(
UINT32 aSize, // IN: size of a
BYTE *a // IN: a
)
{
//
for(a = &a[aSize-1];aSize > 0; aSize--)
{
if((*a-- += 1) != 0)
return 1;
}
return 0;
}
//
//
// _math__Dec()
//
// This function decrements a large, ENDIAN value by one.
//
LIB_EXPORT void
_math__Dec(
UINT32 aSize, // IN: size of a
BYTE *a // IN: a
)
{
for(a = &a[aSize-1]; aSize > 0; aSize--)
{
if((*a-- -= 1) != 0xff)
return;
}
return;
}
//
//
// _math__Mul()
//
// This function is used to multiply two large integers: p = a* b. If the size of p is not specified (pSize ==
// NULL), the size of the results p is assumed to be aSize + bSize and the results are de-normalized so that
// the resulting size is exactly aSize + bSize. If pSize is provided, then the actual size of the result is
// returned. The initial value for pSize must be at least aSize + pSize.
//
// Return Value Meaning
//
// <0 indicates an error
// >= 0 the size of the product
//
LIB_EXPORT int
_math__Mul(
const UINT32 aSize, // IN: size of a
const BYTE *a, // IN: a
const UINT32 bSize, // IN: size of b
const BYTE *b, // IN: b
UINT32 *pSize, // IN/OUT: size of the product
BYTE *p // OUT: product. length of product = aSize +
// bSize
)
{
BIGNUM *bnA;
BIGNUM *bnB;
BIGNUM *bnP;
BN_CTX *context;
int retVal = 0;
// First check that pSize is large enough if present
if((pSize != NULL) && (*pSize < (aSize + bSize)))
return CRYPT_PARAMETER;
pAssert(pSize == NULL || *pSize <= MAX_2B_BYTES);
//
//
// Allocate space for BIGNUM context
//
context = BN_CTX_new();
if(context == NULL)
FAIL(FATAL_ERROR_ALLOCATION);
bnA = BN_CTX_get(context);
bnB = BN_CTX_get(context);
bnP = BN_CTX_get(context);
if (bnP == NULL)
FAIL(FATAL_ERROR_ALLOCATION);
// Convert the inputs to BIGNUMs
//
if (BN_bin2bn(a, aSize, bnA) == NULL || BN_bin2bn(b, bSize, bnB) == NULL)
FAIL(FATAL_ERROR_INTERNAL);
// Perform the multiplication
//
if (BN_mul(bnP, bnA, bnB, context) != 1)
FAIL(FATAL_ERROR_INTERNAL);
// If the size of the results is allowed to float, then set the return
// size. Otherwise, it might be necessary to de-normalize the results
retVal = BN_num_bytes(bnP);
if(pSize == NULL)
{
BN_bn2bin(bnP, &p[aSize + bSize - retVal]);
memset(p, 0, aSize + bSize - retVal);
retVal = aSize + bSize;
}
else
{
BN_bn2bin(bnP, p);
*pSize = retVal;
}
BN_CTX_end(context);
BN_CTX_free(context);
return retVal;
}
//
//
// _math__Div()
//
// Divide an integer (n) by an integer (d) producing a quotient (q) and a remainder (r). If q or r is not needed,
// then the pointer to them may be set to NULL.
//
// Return Value Meaning
//
// CRYPT_SUCCESS operation complete
// CRYPT_UNDERFLOW q or r is too small to receive the result
//
LIB_EXPORT CRYPT_RESULT
_math__Div(
const TPM2B *n, // IN: numerator
const TPM2B *d, // IN: denominator
TPM2B *q, // OUT: quotient
TPM2B *r // OUT: remainder
)
{
BIGNUM *bnN;
BIGNUM *bnD;
BIGNUM *bnQ;
BIGNUM *bnR;
BN_CTX *context;
CRYPT_RESULT retVal = CRYPT_SUCCESS;
// Get structures for the big number representations
context = BN_CTX_new();
if(context == NULL)
FAIL(FATAL_ERROR_ALLOCATION);
BN_CTX_start(context);
bnN = BN_CTX_get(context);
bnD = BN_CTX_get(context);
bnQ = BN_CTX_get(context);
bnR = BN_CTX_get(context);
// Errors in BN_CTX_get() are sticky so only need to check the last allocation
if ( bnR == NULL
|| BN_bin2bn(n->buffer, n->size, bnN) == NULL
|| BN_bin2bn(d->buffer, d->size, bnD) == NULL)
FAIL(FATAL_ERROR_INTERNAL);
// Check for divide by zero.
if(BN_num_bits(bnD) == 0)
FAIL(FATAL_ERROR_DIVIDE_ZERO);
// Perform the division
if (BN_div(bnQ, bnR, bnN, bnD, context) != 1)
FAIL(FATAL_ERROR_INTERNAL);
// Convert the BIGNUM result back to our format
if(q != NULL) // If the quotient is being returned
{
if(!BnTo2B(q, bnQ, q->size))
{
retVal = CRYPT_UNDERFLOW;
goto Done;
}
}
if(r != NULL) // If the remainder is being returned
{
if(!BnTo2B(r, bnR, r->size))
retVal = CRYPT_UNDERFLOW;
}
Done:
BN_CTX_end(context);
BN_CTX_free(context);
return retVal;
}
#endif // ! EMBEDDED_MODE
//
//
// _math__uComp()
//
// This function compare two unsigned values.
//
// Return Value Meaning
//
// 1 if (a > b)
// 0 if (a = b)
// -1 if (a < b)
//
LIB_EXPORT int
_math__uComp(
const UINT32 aSize, // IN: size of a
const BYTE *a, // IN: a
const UINT32 bSize, // IN: size of b
const BYTE *b // IN: b
)
{
int borrow = 0;
int notZero = 0;
int i;
// If a has more digits than b, then a is greater than b if
// any of the more significant bytes is non zero
if((i = (int)aSize - (int)bSize) > 0)
for(; i > 0; i--)
if(*a++) // means a > b
return 1;
// If b has more digits than a, then b is greater if any of the
// more significant bytes is non zero
if(i < 0) // Means that b is longer than a
for(; i < 0; i++)
if(*b++) // means that b > a
return -1;
// Either the vales are the same size or the upper bytes of a or b are
// all zero, so compare the rest
i = (aSize > bSize) ? bSize : aSize;
a = &a[i-1];
b = &b[i-1];
for(; i > 0; i--)
{
borrow = *a-- - *b-- + borrow;
notZero = notZero || borrow;
borrow >>= 8;
}
// if there is a borrow, then b > a
if(borrow)
return -1;
// either a > b or they are the same
return notZero;
}
//
//
// _math__Comp()
//
// Compare two signed integers:
//
// Return Value Meaning
//
// 1 if a > b
// 0 if a = b
// -1 if a < b
//
LIB_EXPORT int
_math__Comp(
const UINT32 aSize, // IN: size of a
const BYTE *a, // IN: a buffer
const UINT32 bSize, // IN: size of b
const BYTE *b // IN: b buffer
)
{
int signA, signB; // sign of a and b
// For positive or 0, sign_a is 1
// for negative, sign_a is 0
signA = ((a[0] & 0x80) == 0) ? 1 : 0;
// For positive or 0, sign_b is 1
// for negative, sign_b is 0
signB = ((b[0] & 0x80) == 0) ? 1 : 0;
if(signA != signB)
{
return signA - signB;
}
if(signA == 1)
// do unsigned compare function
return _math__uComp(aSize, a, bSize, b);
else
// do unsigned compare the other way
return 0 - _math__uComp(aSize, a, bSize, b);
}
//
//
// _math__ModExp
//
// This function is used to do modular exponentiation in support of RSA. The most typical uses are: c = m^e
// mod n (RSA encrypt) and m = c^d mod n (RSA decrypt). When doing decryption, the e parameter of the
// function will contain the private exponent d instead of the public exponent e.
// If the results will not fit in the provided buffer, an error is returned (CRYPT_ERROR_UNDERFLOW). If
// the results is smaller than the buffer, the results is de-normalized.
// This version is intended for use with RSA and requires that m be less than n.
//
// Return Value Meaning
//
// CRYPT_SUCCESS exponentiation succeeded
// CRYPT_PARAMETER number to exponentiate is larger than the modulus
// CRYPT_UNDERFLOW result will not fit into the provided buffer
//
#ifndef EMBEDDED_MODE
LIB_EXPORT CRYPT_RESULT
_math__ModExp(
UINT32 cSize, // IN: size of the result
BYTE *c, // OUT: results buffer
const UINT32 mSize, // IN: size of number to be exponentiated
const BYTE *m, // IN: number to be exponentiated
const UINT32 eSize, // IN: size of power
const BYTE *e, // IN: power
const UINT32 nSize, // IN: modulus size
const BYTE *n // IN: modulu
)
{
CRYPT_RESULT retVal = CRYPT_SUCCESS;
BN_CTX *context;
BIGNUM *bnC;
BIGNUM *bnM;
BIGNUM *bnE;
BIGNUM *bnN;
INT32 i;
context = BN_CTX_new();
if(context == NULL)
FAIL(FATAL_ERROR_ALLOCATION);
BN_CTX_start(context);
bnC = BN_CTX_get(context);
bnM = BN_CTX_get(context);
bnE = BN_CTX_get(context);
bnN = BN_CTX_get(context);
// Errors for BN_CTX_get are sticky so only need to check last allocation
if(bnN == NULL)
FAIL(FATAL_ERROR_ALLOCATION);
//convert arguments
if ( BN_bin2bn(m, mSize, bnM) == NULL
|| BN_bin2bn(e, eSize, bnE) == NULL
|| BN_bin2bn(n, nSize, bnN) == NULL)
FAIL(FATAL_ERROR_INTERNAL);
// Don't do exponentiation if the number being exponentiated is
// larger than the modulus.
if(BN_ucmp(bnM, bnN) >= 0)
{
retVal = CRYPT_PARAMETER;
goto Cleanup;
}
// Perform the exponentiation
if(!(BN_mod_exp(bnC, bnM, bnE, bnN, context)))
FAIL(FATAL_ERROR_INTERNAL);
// Convert the results
// Make sure that the results will fit in the provided buffer.
if((unsigned)BN_num_bytes(bnC) > cSize)
{
retVal = CRYPT_UNDERFLOW;
goto Cleanup;
}
i = cSize - BN_num_bytes(bnC);
BN_bn2bin(bnC, &c[i]);
memset(c, 0, i);
Cleanup:
// Free up allocated BN values
BN_CTX_end(context);
BN_CTX_free(context);
return retVal;
}
//
//
// _math__IsPrime()
//
// Check if an 32-bit integer is a prime.
//
// Return Value Meaning
//
// TRUE if the integer is probably a prime
// FALSE if the integer is definitely not a prime
//
LIB_EXPORT BOOL
_math__IsPrime(
const UINT32 prime
)
{
int isPrime;
BIGNUM *p;
// Assume the size variables are not overflow, which should not happen in
// the contexts that this function will be called.
if((p = BN_new()) == NULL)
FAIL(FATAL_ERROR_ALLOCATION);
if(!BN_set_word(p, prime))
FAIL(FATAL_ERROR_INTERNAL);
//
// BN_is_prime returning -1 means that it ran into an error.
//
// It should only return 0 or 1
//
if((isPrime = BN_is_prime_ex(p, BN_prime_checks, NULL, NULL)) < 0)
FAIL(FATAL_ERROR_INTERNAL);
if(p != NULL)
BN_clear_free(p);
return (isPrime == 1);
}
#endif // ! EMBEDDED_MODE