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