1// This file was extracted from the TCG Published 2// Trusted Platform Module Library 3// Part 4: Supporting Routines 4// Family "2.0" 5// Level 00 Revision 01.16 6// October 30, 2014 7 8#include <string.h> 9 10#include "OsslCryptoEngine.h" 11// 12// 13// Externally Accessible Functions 14// 15// _math__Normalize2B() 16// 17// This function will normalize the value in a TPM2B. If there are leading bytes of zero, the first non-zero 18// byte is shifted up. 19// 20// Return Value Meaning 21// 22// 0 no significant bytes, value is zero 23// >0 number of significant bytes 24// 25LIB_EXPORT UINT16 26_math__Normalize2B( 27 TPM2B *b // IN/OUT: number to normalize 28 ) 29{ 30 UINT16 from; 31 UINT16 to; 32 UINT16 size = b->size; 33 for(from = 0; b->buffer[from] == 0 && from < size; from++); 34 b->size -= from; 35 for(to = 0; from < size; to++, from++ ) 36 b->buffer[to] = b->buffer[from]; 37 return b->size; 38} 39// 40// 41// 42// _math__Denormalize2B() 43// 44// This function is used to adjust a TPM2B so that the number has the desired number of bytes. This is 45// accomplished by adding bytes of zero at the start of the number. 46// 47// Return Value Meaning 48// 49// TRUE number de-normalized 50// FALSE number already larger than the desired size 51// 52LIB_EXPORT BOOL 53_math__Denormalize2B( 54 TPM2B *in, // IN:OUT TPM2B number to de-normalize 55 UINT32 size // IN: the desired size 56 ) 57{ 58 UINT32 to; 59 UINT32 from; 60 // If the current size is greater than the requested size, see if this can be 61 // normalized to a value smaller than the requested size and then de-normalize 62 if(in->size > size) 63 { 64 _math__Normalize2B(in); 65 if(in->size > size) 66 return FALSE; 67 } 68 // If the size is already what is requested, leave 69 if(in->size == size) 70 return TRUE; 71 // move the bytes to the 'right' 72 for(from = in->size, to = size; from > 0;) 73 in->buffer[--to] = in->buffer[--from]; 74 // 'to' will always be greater than 0 because we checked for equal above. 75 for(; to > 0;) 76 in->buffer[--to] = 0; 77 in->size = (UINT16)size; 78 return TRUE; 79} 80// 81// 82// _math__sub() 83// 84// This function to subtract one unsigned value from another c = a - b. c may be the same as a or b. 85// 86// Return Value Meaning 87// 88// 1 if (a > b) so no borrow 89// 0 if (a = b) so no borrow and b == a 90// -1 if (a < b) so there was a borrow 91// 92LIB_EXPORT int 93_math__sub( 94 const UINT32 aSize, // IN: size of a 95 const BYTE *a, // IN: a 96 const UINT32 bSize, // IN: size of b 97 const BYTE *b, // IN: b 98 UINT16 *cSize, // OUT: set to MAX(aSize, bSize) 99 BYTE *c // OUT: the difference 100 ) 101{ 102 int borrow = 0; 103 int notZero = 0; 104 int i; 105 int i2; 106 // set c to the longer of a or b 107 *cSize = (UINT16)((aSize > bSize) ? aSize : bSize); 108 // pick the shorter of a and b 109 i = (aSize > bSize) ? bSize : aSize; 110 i2 = *cSize - i; 111 a = &a[aSize - 1]; 112 b = &b[bSize - 1]; 113 c = &c[*cSize - 1]; 114 for(; i > 0; i--) 115 { 116 borrow = *a-- - *b-- + borrow; 117 *c-- = (BYTE)borrow; 118 notZero = notZero || borrow; 119 borrow >>= 8; 120 } 121 if(aSize > bSize) 122 { 123 for(;i2 > 0; i2--) 124 { 125 borrow = *a-- + borrow; 126 *c-- = (BYTE)borrow; 127 notZero = notZero || borrow; 128 borrow >>= 8; 129 } 130 } 131 else if(aSize < bSize) 132 { 133 for(;i2 > 0; i2--) 134 { 135 borrow = 0 - *b-- + borrow; 136 *c-- = (BYTE)borrow; 137 notZero = notZero || borrow; 138 borrow >>= 8; 139 } 140 } 141 // if there is a borrow, then b > a 142 if(borrow) 143 return -1; 144 // either a > b or they are the same 145 return notZero; 146} 147// 148// 149// _math__Inc() 150// 151// This function increments a large, big-endian number value by one. 152// 153// Return Value Meaning 154// 155// 0 result is zero 156// !0 result is not zero 157// 158LIB_EXPORT int 159_math__Inc( 160 UINT32 aSize, // IN: size of a 161 BYTE *a // IN: a 162 ) 163{ 164// 165 for(a = &a[aSize-1];aSize > 0; aSize--) 166 { 167 if((*a-- += 1) != 0) 168 return 1; 169 } 170 return 0; 171} 172// 173// 174// _math__Dec() 175// 176// This function decrements a large, ENDIAN value by one. 177// 178LIB_EXPORT void 179_math__Dec( 180 UINT32 aSize, // IN: size of a 181 BYTE *a // IN: a 182 ) 183{ 184 for(a = &a[aSize-1]; aSize > 0; aSize--) 185 { 186 if((*a-- -= 1) != 0xff) 187 return; 188 } 189 return; 190} 191// 192// 193// _math__Mul() 194// 195// This function is used to multiply two large integers: p = a* b. If the size of p is not specified (pSize == 196// NULL), the size of the results p is assumed to be aSize + bSize and the results are de-normalized so that 197// the resulting size is exactly aSize + bSize. If pSize is provided, then the actual size of the result is 198// returned. The initial value for pSize must be at least aSize + pSize. 199// 200// Return Value Meaning 201// 202// <0 indicates an error 203// >= 0 the size of the product 204// 205LIB_EXPORT int 206_math__Mul( 207 const UINT32 aSize, // IN: size of a 208 const BYTE *a, // IN: a 209 const UINT32 bSize, // IN: size of b 210 const BYTE *b, // IN: b 211 UINT32 *pSize, // IN/OUT: size of the product 212 BYTE *p // OUT: product. length of product = aSize + 213 // bSize 214 ) 215{ 216 BIGNUM *bnA; 217 BIGNUM *bnB; 218 BIGNUM *bnP; 219 BN_CTX *context; 220 int retVal = 0; 221 // First check that pSize is large enough if present 222 if((pSize != NULL) && (*pSize < (aSize + bSize))) 223 return CRYPT_PARAMETER; 224 pAssert(pSize == NULL || *pSize <= MAX_2B_BYTES); 225 // 226// 227 // Allocate space for BIGNUM context 228 // 229 context = BN_CTX_new(); 230 if(context == NULL) 231 FAIL(FATAL_ERROR_ALLOCATION); 232 bnA = BN_CTX_get(context); 233 bnB = BN_CTX_get(context); 234 bnP = BN_CTX_get(context); 235 if (bnP == NULL) 236 FAIL(FATAL_ERROR_ALLOCATION); 237 // Convert the inputs to BIGNUMs 238 // 239 if (BN_bin2bn(a, aSize, bnA) == NULL || BN_bin2bn(b, bSize, bnB) == NULL) 240 FAIL(FATAL_ERROR_INTERNAL); 241 // Perform the multiplication 242 // 243 if (BN_mul(bnP, bnA, bnB, context) != 1) 244 FAIL(FATAL_ERROR_INTERNAL); 245 // If the size of the results is allowed to float, then set the return 246 // size. Otherwise, it might be necessary to de-normalize the results 247 retVal = BN_num_bytes(bnP); 248 if(pSize == NULL) 249 { 250 BN_bn2bin(bnP, &p[aSize + bSize - retVal]); 251 memset(p, 0, aSize + bSize - retVal); 252 retVal = aSize + bSize; 253 } 254 else 255 { 256 BN_bn2bin(bnP, p); 257 *pSize = retVal; 258 } 259 BN_CTX_end(context); 260 BN_CTX_free(context); 261 return retVal; 262} 263// 264// 265// _math__Div() 266// 267// Divide an integer (n) by an integer (d) producing a quotient (q) and a remainder (r). If q or r is not needed, 268// then the pointer to them may be set to NULL. 269// 270// Return Value Meaning 271// 272// CRYPT_SUCCESS operation complete 273// CRYPT_UNDERFLOW q or r is too small to receive the result 274// 275LIB_EXPORT CRYPT_RESULT 276_math__Div( 277 const TPM2B *n, // IN: numerator 278 const TPM2B *d, // IN: denominator 279 TPM2B *q, // OUT: quotient 280 TPM2B *r // OUT: remainder 281 ) 282{ 283 BIGNUM *bnN; 284 BIGNUM *bnD; 285 BIGNUM *bnQ; 286 BIGNUM *bnR; 287 BN_CTX *context; 288 CRYPT_RESULT retVal = CRYPT_SUCCESS; 289 // Get structures for the big number representations 290 context = BN_CTX_new(); 291 if(context == NULL) 292 FAIL(FATAL_ERROR_ALLOCATION); 293 BN_CTX_start(context); 294 bnN = BN_CTX_get(context); 295 bnD = BN_CTX_get(context); 296 bnQ = BN_CTX_get(context); 297 bnR = BN_CTX_get(context); 298 // Errors in BN_CTX_get() are sticky so only need to check the last allocation 299 if ( bnR == NULL 300 || BN_bin2bn(n->buffer, n->size, bnN) == NULL 301 || BN_bin2bn(d->buffer, d->size, bnD) == NULL) 302 FAIL(FATAL_ERROR_INTERNAL); 303 // Check for divide by zero. 304 if(BN_num_bits(bnD) == 0) 305 FAIL(FATAL_ERROR_DIVIDE_ZERO); 306 // Perform the division 307 if (BN_div(bnQ, bnR, bnN, bnD, context) != 1) 308 FAIL(FATAL_ERROR_INTERNAL); 309 // Convert the BIGNUM result back to our format 310 if(q != NULL) // If the quotient is being returned 311 { 312 if(!BnTo2B(q, bnQ, q->size)) 313 { 314 retVal = CRYPT_UNDERFLOW; 315 goto Done; 316 } 317 } 318 if(r != NULL) // If the remainder is being returned 319 { 320 if(!BnTo2B(r, bnR, r->size)) 321 retVal = CRYPT_UNDERFLOW; 322 } 323Done: 324 BN_CTX_end(context); 325 BN_CTX_free(context); 326 return retVal; 327} 328// 329// 330// _math__uComp() 331// 332// This function compare two unsigned values. 333// 334// Return Value Meaning 335// 336// 1 if (a > b) 337// 0 if (a = b) 338// -1 if (a < b) 339// 340LIB_EXPORT int 341_math__uComp( 342 const UINT32 aSize, // IN: size of a 343 const BYTE *a, // IN: a 344 const UINT32 bSize, // IN: size of b 345 const BYTE *b // IN: b 346 ) 347{ 348 int borrow = 0; 349 int notZero = 0; 350 int i; 351 // If a has more digits than b, then a is greater than b if 352 // any of the more significant bytes is non zero 353 if((i = (int)aSize - (int)bSize) > 0) 354 for(; i > 0; i--) 355 if(*a++) // means a > b 356 return 1; 357 // If b has more digits than a, then b is greater if any of the 358 // more significant bytes is non zero 359 if(i < 0) // Means that b is longer than a 360 for(; i < 0; i++) 361 if(*b++) // means that b > a 362 return -1; 363 // Either the vales are the same size or the upper bytes of a or b are 364 // all zero, so compare the rest 365 i = (aSize > bSize) ? bSize : aSize; 366 a = &a[i-1]; 367 b = &b[i-1]; 368 for(; i > 0; i--) 369 { 370 borrow = *a-- - *b-- + borrow; 371 notZero = notZero || borrow; 372 borrow >>= 8; 373 } 374 // if there is a borrow, then b > a 375 if(borrow) 376 return -1; 377 // either a > b or they are the same 378 return notZero; 379} 380// 381// 382// _math__Comp() 383// 384// Compare two signed integers: 385// 386// Return Value Meaning 387// 388// 1 if a > b 389// 0 if a = b 390// -1 if a < b 391// 392LIB_EXPORT int 393_math__Comp( 394 const UINT32 aSize, // IN: size of a 395 const BYTE *a, // IN: a buffer 396 const UINT32 bSize, // IN: size of b 397 const BYTE *b // IN: b buffer 398 ) 399{ 400 int signA, signB; // sign of a and b 401 // For positive or 0, sign_a is 1 402 // for negative, sign_a is 0 403 signA = ((a[0] & 0x80) == 0) ? 1 : 0; 404 // For positive or 0, sign_b is 1 405 // for negative, sign_b is 0 406 signB = ((b[0] & 0x80) == 0) ? 1 : 0; 407 if(signA != signB) 408 { 409 return signA - signB; 410 } 411 if(signA == 1) 412 // do unsigned compare function 413 return _math__uComp(aSize, a, bSize, b); 414 else 415 // do unsigned compare the other way 416 return 0 - _math__uComp(aSize, a, bSize, b); 417} 418// 419// 420// _math__ModExp 421// 422// This function is used to do modular exponentiation in support of RSA. The most typical uses are: c = m^e 423// mod n (RSA encrypt) and m = c^d mod n (RSA decrypt). When doing decryption, the e parameter of the 424// function will contain the private exponent d instead of the public exponent e. 425// If the results will not fit in the provided buffer, an error is returned (CRYPT_ERROR_UNDERFLOW). If 426// the results is smaller than the buffer, the results is de-normalized. 427// This version is intended for use with RSA and requires that m be less than n. 428// 429// Return Value Meaning 430// 431// CRYPT_SUCCESS exponentiation succeeded 432// CRYPT_PARAMETER number to exponentiate is larger than the modulus 433// CRYPT_UNDERFLOW result will not fit into the provided buffer 434// 435LIB_EXPORT CRYPT_RESULT 436_math__ModExp( 437 UINT32 cSize, // IN: size of the result 438 BYTE *c, // OUT: results buffer 439 const UINT32 mSize, // IN: size of number to be exponentiated 440 const BYTE *m, // IN: number to be exponentiated 441 const UINT32 eSize, // IN: size of power 442 const BYTE *e, // IN: power 443 const UINT32 nSize, // IN: modulus size 444 const BYTE *n // IN: modulu 445 ) 446{ 447 CRYPT_RESULT retVal = CRYPT_SUCCESS; 448 BN_CTX *context; 449 BIGNUM *bnC; 450 BIGNUM *bnM; 451 BIGNUM *bnE; 452 BIGNUM *bnN; 453 INT32 i; 454 context = BN_CTX_new(); 455 if(context == NULL) 456 FAIL(FATAL_ERROR_ALLOCATION); 457 BN_CTX_start(context); 458 bnC = BN_CTX_get(context); 459 bnM = BN_CTX_get(context); 460 bnE = BN_CTX_get(context); 461 bnN = BN_CTX_get(context); 462 // Errors for BN_CTX_get are sticky so only need to check last allocation 463 if(bnN == NULL) 464 FAIL(FATAL_ERROR_ALLOCATION); 465 //convert arguments 466 if ( BN_bin2bn(m, mSize, bnM) == NULL 467 || BN_bin2bn(e, eSize, bnE) == NULL 468 || BN_bin2bn(n, nSize, bnN) == NULL) 469 FAIL(FATAL_ERROR_INTERNAL); 470 // Don't do exponentiation if the number being exponentiated is 471 // larger than the modulus. 472 if(BN_ucmp(bnM, bnN) >= 0) 473 { 474 retVal = CRYPT_PARAMETER; 475 goto Cleanup; 476 } 477 // Perform the exponentiation 478 if(!(BN_mod_exp(bnC, bnM, bnE, bnN, context))) 479 FAIL(FATAL_ERROR_INTERNAL); 480 // Convert the results 481 // Make sure that the results will fit in the provided buffer. 482 if((unsigned)BN_num_bytes(bnC) > cSize) 483 { 484 retVal = CRYPT_UNDERFLOW; 485 goto Cleanup; 486 } 487 i = cSize - BN_num_bytes(bnC); 488 BN_bn2bin(bnC, &c[i]); 489 memset(c, 0, i); 490Cleanup: 491 // Free up allocated BN values 492 BN_CTX_end(context); 493 BN_CTX_free(context); 494 return retVal; 495} 496// 497// 498// _math__IsPrime() 499// 500// Check if an 32-bit integer is a prime. 501// 502// Return Value Meaning 503// 504// TRUE if the integer is probably a prime 505// FALSE if the integer is definitely not a prime 506// 507LIB_EXPORT BOOL 508_math__IsPrime( 509 const UINT32 prime 510 ) 511{ 512 int isPrime; 513 BIGNUM *p; 514 // Assume the size variables are not overflow, which should not happen in 515 // the contexts that this function will be called. 516 if((p = BN_new()) == NULL) 517 FAIL(FATAL_ERROR_ALLOCATION); 518 if(!BN_set_word(p, prime)) 519 FAIL(FATAL_ERROR_INTERNAL); 520 // 521 // BN_is_prime returning -1 means that it ran into an error. 522// 523 // It should only return 0 or 1 524 // 525 if((isPrime = BN_is_prime_ex(p, BN_prime_checks, NULL, NULL)) < 0) 526 FAIL(FATAL_ERROR_INTERNAL); 527 if(p != NULL) 528 BN_clear_free(p); 529 return (isPrime == 1); 530} 531