/********************************************************************************/ /* */ /* 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; }