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 // 28 LIB_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 // 55 LIB_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 // 95 LIB_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 // 161 LIB_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 // 181 LIB_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 // 208 LIB_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 // 278 LIB_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 } 326 Done: 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 // 344 LIB_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 // 396 LIB_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 440 LIB_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); 495 Cleanup: 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 // 512 LIB_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
