summaryrefslogtreecommitdiffstats
path: root/src/tpm2/BnMath.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/tpm2/BnMath.c651
1 files changed, 651 insertions, 0 deletions
diff --git a/src/tpm2/BnMath.c b/src/tpm2/BnMath.c
new file mode 100644
index 0000000..0154fb5
--- /dev/null
+++ b/src/tpm2/BnMath.c
@@ -0,0 +1,651 @@
+/********************************************************************************/
+/* */
+/* Simple Operations on Big Numbers */
+/* Written by Ken Goldman */
+/* IBM Thomas J. Watson Research Center */
+/* $Id: BnMath.c 1529 2019-11-21 23:29:01Z kgoldman $ */
+/* */
+/* Licenses and Notices */
+/* */
+/* 1. Copyright Licenses: */
+/* */
+/* - Trusted Computing Group (TCG) grants to the user of the source code in */
+/* this specification (the "Source Code") a worldwide, irrevocable, */
+/* nonexclusive, royalty free, copyright license to reproduce, create */
+/* derivative works, distribute, display and perform the Source Code and */
+/* derivative works thereof, and to grant others the rights granted herein. */
+/* */
+/* - The TCG grants to the user of the other parts of the specification */
+/* (other than the Source Code) the rights to reproduce, distribute, */
+/* display, and perform the specification solely for the purpose of */
+/* developing products based on such documents. */
+/* */
+/* 2. Source Code Distribution Conditions: */
+/* */
+/* - Redistributions of Source Code must retain the above copyright licenses, */
+/* this list of conditions and the following disclaimers. */
+/* */
+/* - Redistributions in binary form must reproduce the above copyright */
+/* licenses, this list of conditions and the following disclaimers in the */
+/* documentation and/or other materials provided with the distribution. */
+/* */
+/* 3. Disclaimers: */
+/* */
+/* - THE COPYRIGHT LICENSES SET FORTH ABOVE DO NOT REPRESENT ANY FORM OF */
+/* LICENSE OR WAIVER, EXPRESS OR IMPLIED, BY ESTOPPEL OR OTHERWISE, WITH */
+/* RESPECT TO PATENT RIGHTS HELD BY TCG MEMBERS (OR OTHER THIRD PARTIES) */
+/* THAT MAY BE NECESSARY TO IMPLEMENT THIS SPECIFICATION OR OTHERWISE. */
+/* Contact TCG Administration (admin@trustedcomputinggroup.org) for */
+/* information on specification licensing rights available through TCG */
+/* membership agreements. */
+/* */
+/* - THIS SPECIFICATION IS PROVIDED "AS IS" WITH NO EXPRESS OR IMPLIED */
+/* WARRANTIES WHATSOEVER, INCLUDING ANY WARRANTY OF MERCHANTABILITY OR */
+/* FITNESS FOR A PARTICULAR PURPOSE, ACCURACY, COMPLETENESS, OR */
+/* NONINFRINGEMENT OF INTELLECTUAL PROPERTY RIGHTS, OR ANY WARRANTY */
+/* OTHERWISE ARISING OUT OF ANY PROPOSAL, SPECIFICATION OR SAMPLE. */
+/* */
+/* - Without limitation, TCG and its members and licensors disclaim all */
+/* liability, including liability for infringement of any proprietary */
+/* rights, relating to use of information in this specification and to the */
+/* implementation of this specification, and TCG disclaims all liability for */
+/* cost of procurement of substitute goods or services, lost profits, loss */
+/* of use, loss of data or any incidental, consequential, direct, indirect, */
+/* or special damages, whether under contract, tort, warranty or otherwise, */
+/* arising in any way out of use or reliance upon this specification or any */
+/* information herein. */
+/* */
+/* (c) Copyright IBM Corp. and others, 2016 - 2019 */
+/* */
+/********************************************************************************/
+
+/* 10.2.3 BnMath.c */
+
+/* 10.2.3.1 Introduction */
+/* The simulator code uses the canonical form whenever possible in order to make the code in Part 3
+ more accessible. The canonical data formats are simple and not well suited for complex big number
+ computations. When operating on big numbers, the data format is changed for easier
+ manipulation. The format is native words in little-endian format. As the magnitude of the number
+ decreases, the length of the array containing the number decreases but the starting address
+ doesn't change. */
+/* The functions in this file perform simple operations on these big numbers. Only the more complex
+ operations are passed to the underlying support library. Although the support library would have
+ most of these functions, the interface code to convert the format for the values is greater than
+ the size of the code to implement the functions here. So, rather than incur the overhead of
+ conversion, they are done here. */
+/* If an implementer would prefer, the underlying library can be used simply by making code
+ substitutions here. */
+/* NOTE: There is an intention to continue to augment these functions so that there would be no need
+ to use an external big number library. */
+/* Many of these functions have no error returns and will always return TRUE. This is to allow them
+ to be used in guarded sequences. That is: OK = OK || BnSomething(s); where the BnSomething()
+ function should not be called if OK isn't true. */
+
+/* 10.2.3.2 Includes */
+#include "Tpm.h"
+/* A constant value of zero as a stand in for NULL bigNum values */
+const bignum_t BnConstZero = {1, 0, {0}};
+/* 10.2.3.3 Functions */
+/* 10.2.3.3.1 AddSame() */
+/* Adds two values that are the same size. This function allows result to be the same as either of
+ the addends. This is a nice function to put into assembly because handling the carry for
+ multi-precision stuff is not as easy in C (unless there is a REALLY smart compiler). It would be
+ nice if there were idioms in a language that a compiler could recognize what is going on and
+ optimize loops like this. */
+/* Return Values Meaning */
+/* 0 no carry out */
+/* 1 carry out */
+static BOOL
+AddSame(
+ crypt_uword_t *result,
+ const crypt_uword_t *op1,
+ const crypt_uword_t *op2,
+ int count
+ )
+{
+ int carry = 0;
+ int i;
+ for(i = 0; i < count; i++)
+ {
+ crypt_uword_t a = op1[i];
+ crypt_uword_t sum = a + op2[i];
+ result[i] = sum + carry;
+ // generate a carry if the sum is less than either of the inputs
+ // propagate a carry if there was a carry and the sum + carry is zero
+ // do this using bit operations rather than logical operations so that
+ // the time is about the same.
+ // propagate term | generate term
+ carry = ((result[i] == 0) & carry) | (sum < a);
+ }
+ return carry;
+}
+/* 10.2.3.3.2 CarryProp() */
+/* Propagate a carry */
+static int
+CarryProp(
+ crypt_uword_t *result,
+ const crypt_uword_t *op,
+ int count,
+ int carry
+ )
+{
+ for(; count; count--)
+ carry = ((*result++ = *op++ + carry) == 0) & carry;
+ return carry;
+}
+static void
+CarryResolve(
+ bigNum result,
+ int stop,
+ int carry
+ )
+{
+ if(carry)
+ {
+ pAssert((unsigned)stop < result->allocated);
+ result->d[stop++] = 1;
+ }
+ BnSetTop(result, stop);
+}
+/* 10.2.3.3.3 BnAdd() */
+/* This function adds two bigNum values. Always returns TRUE */
+LIB_EXPORT BOOL
+BnAdd(
+ bigNum result,
+ bigConst op1,
+ bigConst op2
+ )
+{
+ crypt_uword_t stop;
+ int carry;
+ const bignum_t *n1 = op1;
+ const bignum_t *n2 = op2;
+ //
+ if(n2->size > n1->size)
+ {
+ n1 = op2;
+ n2 = op1;
+ }
+ pAssert(result->allocated >= n1->size);
+ stop = MIN(n1->size, n2->allocated);
+ carry = (int)AddSame(result->d, n1->d, n2->d, (int)stop);
+ if(n1->size > stop)
+ carry = CarryProp(&result->d[stop], &n1->d[stop], (int)(n1->size - stop), carry);
+ CarryResolve(result, (int)n1->size, carry);
+ return TRUE;
+}
+/* 10.2.3.3.4 BnAddWord() */
+/* Adds a word value to a bigNum. */
+LIB_EXPORT BOOL
+BnAddWord(
+ bigNum result,
+ bigConst op,
+ crypt_uword_t word
+ )
+{
+ int carry;
+ //
+ carry = (result->d[0] = op->d[0] + word) < word;
+ carry = CarryProp(&result->d[1], &op->d[1], (int)(op->size - 1), carry);
+ CarryResolve(result, (int)op->size, carry);
+ return TRUE;
+}
+/* 10.2.3.3.5 SubSame() */
+/* Subtract two values that have the same size. */
+static int
+SubSame(
+ crypt_uword_t *result,
+ const crypt_uword_t *op1,
+ const crypt_uword_t *op2,
+ int count
+ )
+{
+ int borrow = 0;
+ int i;
+ for(i = 0; i < count; i++)
+ {
+ crypt_uword_t a = op1[i];
+ crypt_uword_t diff = a - op2[i];
+ result[i] = diff - borrow;
+ // generate | propagate
+ borrow = (diff > a) | ((diff == 0) & borrow);
+ }
+ return borrow;
+}
+/* 10.2.3.3.6 BorrowProp() */
+/* This propagates a borrow. If borrow is true when the end of the array is reached, then it means
+ that op2 was larger than op1 and we don't handle that case so an assert is generated. This design
+ choice was made because our only bigNum computations are on large positive numbers (primes) or on
+ fields. Propagate a borrow. */
+static int
+BorrowProp(
+ crypt_uword_t *result,
+ const crypt_uword_t *op,
+ int size,
+ int borrow
+ )
+{
+ for(; size > 0; size--)
+ borrow = ((*result++ = *op++ - borrow) == MAX_CRYPT_UWORD) && borrow;
+ return borrow;
+}
+/* 10.2.3.3.7 BnSub() */
+/* This function does subtraction of two bigNum values and returns result = op1 - op2 when op1 is
+ greater than op2. If op2 is greater than op1, then a fault is generated. This function always
+ returns TRUE. */
+
+LIB_EXPORT BOOL
+BnSub(
+ bigNum result,
+ bigConst op1,
+ bigConst op2
+ )
+{
+ int borrow;
+ int stop = (int)MIN(op1->size, op2->allocated);
+ //
+ // Make sure that op2 is not obviously larger than op1
+ pAssert(op1->size >= op2->size);
+ borrow = SubSame(result->d, op1->d, op2->d, stop);
+ if(op1->size > (crypt_uword_t)stop)
+ borrow = BorrowProp(&result->d[stop], &op1->d[stop], (int)(op1->size - stop),
+ borrow);
+ pAssert(!borrow);
+ BnSetTop(result, op1->size);
+ return TRUE;
+}
+/* 10.2.3.3.8 BnSubWord() */
+/* This function subtracts a word value from a bigNum. This function always returns TRUE. */
+LIB_EXPORT BOOL
+BnSubWord(
+ bigNum result,
+ bigConst op,
+ crypt_uword_t word
+ )
+{
+ int borrow;
+ //
+ pAssert(op->size > 1 || word <= op->d[0]);
+ borrow = word > op->d[0];
+ result->d[0] = op->d[0] - word;
+ borrow = BorrowProp(&result->d[1], &op->d[1], (int)(op->size - 1), borrow);
+ pAssert(!borrow);
+ BnSetTop(result, op->size);
+ return TRUE;
+}
+/* 10.2.3.3.9 BnUnsignedCmp() */
+/* This function performs a comparison of op1 to op2. The compare is approximately constant time if
+ the size of the values used in the compare is consistent across calls (from the same line in the
+ calling code). */
+/* Return Values Meaning */
+/* < 0 op1 is less than op2 */
+/* 0 op1 is equal to op2 */
+/* > 0 op1 is greater than op2 */
+LIB_EXPORT int
+BnUnsignedCmp(
+ bigConst op1,
+ bigConst op2
+ )
+{
+ int retVal;
+ int diff;
+ int i;
+ //
+ pAssert((op1 != NULL) && (op2 != NULL));
+ retVal = (int)(op1->size - op2->size);
+ if(retVal == 0)
+ {
+ for(i = (int)(op1->size - 1); i >= 0; i--)
+ {
+ diff = (op1->d[i] < op2->d[i]) ? -1 : (op1->d[i] != op2->d[i]);
+ retVal = retVal == 0 ? diff : retVal;
+ }
+ }
+ else
+ retVal = (retVal < 0) ? -1 : 1;
+ return retVal;
+}
+/* 10.2.3.3.10 BnUnsignedCmpWord() */
+/* Compare a bigNum to a crypt_uword_t. */
+/* Return Value Meaning */
+/* -1 op1 is less that word */
+/* 0 op1 is equal to word */
+/* 1 op1 is greater than word */
+LIB_EXPORT int
+BnUnsignedCmpWord(
+ bigConst op1,
+ crypt_uword_t word
+ )
+{
+ if(op1->size > 1)
+ return 1;
+ else if(op1->size == 1)
+ return (op1->d[0] < word) ? -1 : (op1->d[0] > word);
+ else // op1 is zero
+ // equal if word is zero
+ return (word == 0) ? 0 : -1;
+}
+/* 10.2.3.3.11 BnModWord() */
+/* This function does modular division of a big number when the modulus is a word value. */
+LIB_EXPORT crypt_word_t
+BnModWord(
+ bigConst numerator,
+ crypt_word_t modulus
+ )
+{
+ BN_MAX(remainder);
+ BN_VAR(mod, RADIX_BITS);
+ //
+ mod->d[0] = modulus;
+ mod->size = (modulus != 0);
+ BnDiv(NULL, remainder, numerator, mod);
+ return remainder->d[0];
+}
+/* 10.2.3.3.12 Msb() */
+/* Returns the bit number of the most significant bit of a crypt_uword_t. The number for the least
+ significant bit of any bigNum value is 0. The maximum return value is RADIX_BITS - 1, */
+/* Return Values Meaning */
+/* -1 the word was zero */
+/* n the bit number of the most significant bit in the word */
+LIB_EXPORT int
+Msb(
+ crypt_uword_t word
+ )
+{
+ int retVal = -1;
+ //
+#if RADIX_BITS == 64
+ if(word & 0xffffffff00000000) { retVal += 32; word >>= 32; }
+#endif
+ if(word & 0xffff0000) { retVal += 16; word >>= 16; }
+ if(word & 0x0000ff00) { retVal += 8; word >>= 8; }
+ if(word & 0x000000f0) { retVal += 4; word >>= 4; }
+ if(word & 0x0000000c) { retVal += 2; word >>= 2; }
+ if(word & 0x00000002) { retVal += 1; word >>= 1; }
+ return retVal + (int)word;
+}
+/* 10.2.3.3.13 BnMsb() */
+/* This function returns the number of the MSb() of a bigNum value. */
+/* Return Value Meaning */
+/* -1 the word was zero or bn was NULL */
+/* n the bit number of the most significant bit in the word */
+
+LIB_EXPORT int
+BnMsb(
+ bigConst bn
+ )
+{
+ // If the value is NULL, or the size is zero then treat as zero and return -1
+ if(bn != NULL && bn->size > 0)
+ {
+ int retVal = Msb(bn->d[bn->size - 1]);
+ retVal += (int)(bn->size - 1) * RADIX_BITS;
+ return retVal;
+ }
+ else
+ return -1;
+}
+/* 10.2.3.3.14 BnSizeInBits() */
+/* Returns the number of bits required to hold a number. It is one greater than the Msb. */
+LIB_EXPORT unsigned
+BnSizeInBits(
+ bigConst n
+ )
+{
+ int bits = BnMsb(n) + 1;
+ //
+ return bits < 0 ? 0 : (unsigned)bits;
+}
+/* 10.2.3.3.15 BnSetWord() */
+/* Change the value of a bignum_t to a word value. */
+LIB_EXPORT bigNum
+BnSetWord(
+ bigNum n,
+ crypt_uword_t w
+ )
+{
+ if(n != NULL)
+ {
+ pAssert(n->allocated > 1);
+ n->d[0] = w;
+ BnSetTop(n, (w != 0) ? 1 : 0);
+ }
+ return n;
+}
+/* 10.2.3.3.16 BnSetBit() */
+/* SET a bit in a bigNum. Bit 0 is the least-significant bit in the 0th digit_t. The function always
+ return TRUE */
+LIB_EXPORT BOOL
+BnSetBit(
+ bigNum bn, // IN/OUT: big number to modify
+ unsigned int bitNum // IN: Bit number to SET
+ )
+{
+ crypt_uword_t offset = bitNum / RADIX_BITS;
+ pAssert(bn->allocated * RADIX_BITS >= bitNum);
+ // Grow the number if necessary to set the bit.
+ while(bn->size <= offset)
+ bn->d[bn->size++] = 0;
+ bn->d[offset] |= (crypt_uword_t)(1 << RADIX_MOD(bitNum));
+ return TRUE;
+}
+/* 10.2.3.3.17 BnTestBit() */
+/* Check to see if a bit is SET in a bignum_t. The 0th bit is the LSb() of d[0]. */
+/* Return Values Meaning */
+/* TRUE the bit is set */
+/* FALSE the bit is not set or the number is out of range */
+LIB_EXPORT BOOL
+BnTestBit(
+ bigNum bn, // IN: number to check
+ unsigned int bitNum // IN: bit to test
+ )
+{
+ crypt_uword_t offset = RADIX_DIV(bitNum);
+ //
+ if(bn->size > offset)
+ return ((bn->d[offset] & (((crypt_uword_t)1) << RADIX_MOD(bitNum))) != 0);
+ else
+ return FALSE;
+}
+/* 10.2.3.3.18 BnMaskBits() */
+/* Function to mask off high order bits of a big number. The returned value will have no more than
+ maskBit bits set. */
+/* NOTE: There is a requirement that unused words of a bignum_t are set to zero. */
+/* Return Values Meaning */
+/* TRUE result masked */
+/* FALSE the input was not as large as the mask */
+LIB_EXPORT BOOL
+BnMaskBits(
+ bigNum bn, // IN/OUT: number to mask
+ crypt_uword_t maskBit // IN: the bit number for the mask.
+ )
+{
+ crypt_uword_t finalSize;
+ BOOL retVal;
+ finalSize = BITS_TO_CRYPT_WORDS(maskBit);
+ retVal = (finalSize <= bn->allocated);
+ if(retVal && (finalSize > 0))
+ {
+ crypt_uword_t mask;
+ mask = ~((crypt_uword_t)0) >> RADIX_MOD(maskBit);
+ bn->d[finalSize - 1] &= mask;
+ }
+ BnSetTop(bn, finalSize);
+ return retVal;
+}
+/* 10.2.3.3.19 BnShiftRight() */
+/* Function will shift a bigNum to the right by the shiftAmount. This function always returns
+ TRUE. */
+LIB_EXPORT BOOL
+BnShiftRight(
+ bigNum result,
+ bigConst toShift,
+ uint32_t shiftAmount
+ )
+{
+ uint32_t offset = (shiftAmount >> RADIX_LOG2);
+ uint32_t i;
+ uint32_t shiftIn;
+ crypt_uword_t finalSize;
+ //
+ shiftAmount = shiftAmount & RADIX_MASK;
+ shiftIn = RADIX_BITS - shiftAmount;
+ // The end size is toShift->size - offset less one additional
+ // word if the shiftAmount would make the upper word == 0
+ if(toShift->size > offset)
+ {
+ finalSize = toShift->size - offset;
+ finalSize -= (toShift->d[toShift->size - 1] >> shiftAmount) == 0 ? 1 : 0;
+ }
+ else
+ finalSize = 0;
+ pAssert(finalSize <= result->allocated);
+ if(finalSize != 0)
+ {
+ for(i = 0; i < finalSize; i++)
+ {
+ result->d[i] = (toShift->d[i + offset] >> shiftAmount)
+ | (toShift->d[i + offset + 1] << shiftIn);
+ }
+ if(offset == 0)
+ result->d[i] = toShift->d[i] >> shiftAmount;
+ }
+ BnSetTop(result, finalSize);
+ return TRUE;
+}
+/* 10.2.3.3.20 BnGetRandomBits() */
+/* Return Value Meaning */
+/* TRUE(1) success */
+/* FALSE(0) failure */
+LIB_EXPORT BOOL
+BnGetRandomBits(
+ bigNum n,
+ size_t bits,
+ RAND_STATE *rand
+ )
+{
+ // Since this could be used for ECC key generation using the extra bits method,
+ // make sure that the value is large enough
+ TPM2B_TYPE(LARGEST, LARGEST_NUMBER + 8);
+ TPM2B_LARGEST large;
+ //
+ large.b.size = (UINT16)BITS_TO_BYTES(bits);
+ if(DRBG_Generate(rand, large.t.buffer, large.t.size) == large.t.size)
+ {
+ if(BnFrom2B(n, &large.b) != NULL)
+ {
+ if(BnMaskBits(n, (crypt_uword_t)bits))
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+/* 10.2.3.3.21 BnGenerateRandomInRange() */
+/* Function to generate a random number r in the range 1 <= r < limit. The function gets a random
+ number of bits that is the size of limit. There is some some probability that the returned number
+ is going to be greater than or equal to the limit. If it is, try again. There is no more than 50%
+ chance that the next number is also greater, so try again. We keep trying until we get a value
+ that meets the criteria. Since limit is very often a number with a LOT of high order ones, this
+ rarely would need a second try. */
+/* Return Value Meaning */
+/* TRUE(1) success */
+/* FALSE(0) failure */
+LIB_EXPORT BOOL
+BnGenerateRandomInRange(
+ bigNum dest,
+ bigConst limit,
+ RAND_STATE *rand
+ )
+{
+ size_t bits = BnSizeInBits(limit);
+ //
+ if(bits < 2)
+ {
+ BnSetWord(dest, 0);
+ return FALSE;
+ }
+ else
+ {
+ while(BnGetRandomBits(dest, bits, rand)
+ && (BnEqualZero(dest) || (BnUnsignedCmp(dest, limit) >= 0)));
+ }
+ return !g_inFailureMode;
+}
+
+// libtpms added begin
+
+// This version of BnSizeInBits skips any leading zero bytes in bigConst
+// and thus calculates the bits that OpenSSL will work with after truncating
+// the leading zeros
+static LIB_EXPORT unsigned
+BnSizeInBitsSkipLeadingZeros(
+ bigConst n
+ )
+{
+ int firstByte;
+ unsigned bitSize = BnSizeInBits(n);
+ crypt_uword_t i;
+
+ if (bitSize <= 8)
+ return bitSize;
+
+ // search for the first limb that is non-zero
+ for (i = 0; i < n->size; i++) {
+ if (n->d[i] != 0)
+ break;
+ }
+ if (i >= n->size)
+ return 0; // should never happen
+
+ // get the first byte in this limb that is non-zero
+ firstByte = (RADIX_BITS - 1 - Msb(n->d[i])) >> 3;
+
+ return bitSize - i * sizeof(n->d[0]) - (firstByte << 3);
+}
+
+
+/* This is a version of BnGenerateRandomInRange that ensures that the upper most
+ byte is non-zero, so that the number will not be shortened and subsequent operations
+ will not have a timing-sidechannel
+ */
+LIB_EXPORT BOOL
+BnGenerateRandomInRangeAllBytes(
+ bigNum dest,
+ bigConst limit,
+ RAND_STATE *rand
+ )
+{
+ BOOL OK;
+ int repeats = 0;
+ int maxRepeats;
+ unsigned requestedBits;
+ unsigned requestedBytes;
+ unsigned numBytes;
+
+ if (rand)
+ return BnGenerateRandomInRange(dest, limit, rand);
+
+ // a 'limit' like 'BN_P638_n' has leading zeros and we only need 73 bytes not 80
+ requestedBits = BnSizeInBitsSkipLeadingZeros(limit);
+ requestedBytes = BITS_TO_BYTES(requestedBits);
+ maxRepeats = 8;
+ if (requestedBits & 7)
+ maxRepeats += (9 - (requestedBits & 7));
+
+ while (true) {
+ OK = BnGenerateRandomInRange(dest, limit, rand);
+ if (!OK)
+ break;
+ if (repeats < maxRepeats) {
+ numBytes = BITS_TO_BYTES(BnSizeInBitsSkipLeadingZeros(dest));
+ if (numBytes < requestedBytes) {
+ repeats++;
+ continue;
+ }
+ }
+ break;
+ }
+
+ return OK;
+}
+// libtpms added end
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-02 05:19:00 +0000