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