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 // 25 LIB_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 // 52 LIB_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 // 92 LIB_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 // 158 LIB_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 // 178 LIB_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 // 205 LIB_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 // 275 LIB_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 } 323 Done: 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 // 340 LIB_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 // 392 LIB_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 // 435 LIB_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); 490 Cleanup: 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 // 507 LIB_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
