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 "OsslCryptoEngine.h" 9 #ifdef TPM_ALG_RSA 10 // 11 // This file produces no code unless the compile switch is set to cause it to generate code. 12 // 13 #ifdef RSA_KEY_SIEVE //% 14 #include "RsaKeySieve.h" 15 // 16 // This next line will show up in the header file for this code. It will make the local functions public when 17 // debugging. 18 // 19 //%#ifdef RSA_DEBUG 20 // 21 // 22 // Bit Manipulation Functions 23 // 24 // Introduction 25 // 26 // These functions operate on a bit array. A bit array is an array of bytes with the 0th byte being the byte 27 // with the lowest memory address. Within the byte, bit 0 is the least significant bit. 28 // 29 // ClearBit() 30 // 31 // This function will CLEAR a bit in a bit array. 32 // 33 void 34 ClearBit( 35 unsigned char *a, // IN: A pointer to an array of byte 36 int i // IN: the number of the bit to CLEAR 37 ) 38 { 39 a[i >> 3] &= 0xff ^ (1 << (i & 7)); 40 } 41 // 42 // 43 // SetBit() 44 // 45 // Function to SET a bit in a bit array. 46 // 47 void 48 SetBit( 49 unsigned char *a, // IN: A pointer to an array of byte 50 int i // IN: the number of the bit to SET 51 ) 52 { 53 a[i >> 3] |= (1 << (i & 7)); 54 } 55 // 56 // 57 // IsBitSet() 58 // 59 // Function to test if a bit in a bit array is SET. 60 // 61 // 62 // 63 // 64 // Return Value Meaning 65 // 66 // 0 bit is CLEAR 67 // 1 bit is SET 68 // 69 UINT32 70 IsBitSet( 71 unsigned char *a, // IN: A pointer to an array of byte 72 int i // IN: the number of the bit to test 73 ) 74 { 75 return ((a[i >> 3] & (1 << (i & 7))) != 0); 76 } 77 // 78 // 79 // BitsInArry() 80 // 81 // This function counts the number of bits set in an array of bytes. 82 // 83 int 84 BitsInArray( 85 unsigned char *a, // IN: A pointer to an array of byte 86 int i // IN: the number of bytes to sum 87 ) 88 { 89 int j = 0; 90 for(; i ; i--) 91 j += bitsInByte[*a++]; 92 return j; 93 } 94 // 95 // 96 // FindNthSetBit() 97 // 98 // This function finds the nth SET bit in a bit array. The caller should check that the offset of the returned 99 // value is not out of range. If called when the array does not have n bits set, it will return a fatal error 100 // 101 UINT32 102 FindNthSetBit( 103 const UINT16 aSize, // IN: the size of the array to check 104 const BYTE *a, // IN: the array to check 105 const UINT32 n // IN, the number of the SET bit 106 ) 107 { 108 UINT32 i; 109 const BYTE *pA = a; 110 UINT32 retValue; 111 BYTE sel; 112 (aSize); 113 //find the bit 114 for(i = 0; i < n; i += bitsInByte[*pA++]); 115 // The chosen bit is in the byte that was just accessed 116 // Compute the offset to the start of that byte 117 pA--; 118 retValue = (UINT32)(pA - a) * 8; 119 // Subtract the bits in the last byte added. 120 i -= bitsInByte[*pA]; 121 // Now process the byte, one bit at a time. 122 for(sel = *pA; sel != 0 ; sel = sel >> 1) 123 { 124 if(sel & 1) 125 { 126 i += 1; 127 if(i == n) 128 return retValue; 129 } 130 retValue += 1; 131 } 132 FAIL(FATAL_ERROR_INTERNAL); 133 } 134 // 135 // 136 // Miscellaneous Functions 137 // 138 // RandomForRsa() 139 // 140 // This function uses a special form of KDFa() to produces a pseudo random sequence. It's input is a 141 // structure that contains pointers to a pre-computed set of hash contexts that are set up for the HMAC 142 // computations using the seed. 143 // This function will test that ktx.outer will not wrap to zero if incremented. If so, the function returns FALSE. 144 // Otherwise, the ktx.outer is incremented before each number is generated. 145 // 146 void 147 RandomForRsa( 148 KDFa_CONTEXT *ktx, // IN: a context for the KDF 149 const char *label, // IN: a use qualifying label 150 TPM2B *p // OUT: the pseudo random result 151 ) 152 { 153 INT16 i; 154 UINT32 inner; 155 BYTE swapped[4]; 156 UINT16 fill; 157 BYTE *pb; 158 UINT16 lLen = 0; 159 UINT16 digestSize = _cpri__GetDigestSize(ktx->hashAlg); 160 CPRI_HASH_STATE h; // the working hash context 161 if(label != NULL) 162 for(lLen = 0; label[lLen++];); 163 fill = digestSize; 164 pb = p->buffer; 165 inner = 0; 166 *(ktx->outer) += 1; 167 for(i = p->size; i > 0; i -= digestSize) 168 { 169 inner++; 170 // Initialize the HMAC with saved state 171 _cpri__CopyHashState(&h, &(ktx->iPadCtx)); 172 // Hash the inner counter (the one that changes on each HMAC iteration) 173 UINT32_TO_BYTE_ARRAY(inner, swapped); 174 _cpri__UpdateHash(&h, 4, swapped); 175 if(lLen != 0) 176 _cpri__UpdateHash(&h, lLen, (BYTE *)label); 177 // Is there any party 1 data 178 if(ktx->extra != NULL) 179 _cpri__UpdateHash(&h, ktx->extra->size, ktx->extra->buffer); 180 // Include the outer counter (the one that changes on each prime 181 // prime candidate generation 182 UINT32_TO_BYTE_ARRAY(*(ktx->outer), swapped); 183 _cpri__UpdateHash(&h, 4, swapped); 184 _cpri__UpdateHash(&h, 2, (BYTE *)&ktx->keySizeInBits); 185 if(i < fill) 186 fill = i; 187 _cpri__CompleteHash(&h, fill, pb); 188 // Restart the oPad hash 189 _cpri__CopyHashState(&h, &(ktx->oPadCtx)); 190 // Add the last hashed data 191 _cpri__UpdateHash(&h, fill, pb); 192 // gives a completed HMAC 193 _cpri__CompleteHash(&h, fill, pb); 194 pb += fill; 195 } 196 return; 197 } 198 // 199 // 200 // MillerRabinRounds() 201 // 202 // Function returns the number of Miller-Rabin rounds necessary to give an error probability equal to the 203 // security strength of the prime. These values are from FIPS 186-3. 204 // 205 UINT32 206 MillerRabinRounds( 207 UINT32 bits // IN: Number of bits in the RSA prime 208 ) 209 { 210 if(bits < 511) return 8; // don't really expect this 211 if(bits < 1536) return 5; // for 512 and 1K primes 212 return 4; // for 3K public modulus and greater 213 } 214 // 215 // 216 // MillerRabin() 217 // 218 // This function performs a Miller-Rabin test from FIPS 186-3. It does iterations trials on the number. I all 219 // likelihood, if the number is not prime, the first test fails. 220 // If a KDFa(), PRNG context is provide (ktx), then it is used to provide the random values. Otherwise, the 221 // random numbers are retrieved from the random number generator. 222 // 223 // Return Value Meaning 224 // 225 // TRUE probably prime 226 // FALSE composite 227 // 228 BOOL 229 MillerRabin( 230 BIGNUM *bnW, 231 int iterations, 232 KDFa_CONTEXT *ktx, 233 BN_CTX *context 234 ) 235 { 236 BIGNUM *bnWm1; 237 BIGNUM *bnM; 238 BIGNUM *bnB; 239 BIGNUM *bnZ; 240 BOOL ret = FALSE; // Assumed composite for easy exit 241 TPM2B_TYPE(MAX_PRIME, MAX_RSA_KEY_BYTES/2); 242 TPM2B_MAX_PRIME b; 243 int a; 244 int j; 245 int wLen; 246 int i; 247 pAssert(BN_is_bit_set(bnW, 0)); 248 INSTRUMENT_INC(MillerRabinTrials); // Instrumentation 249 BN_CTX_start(context); 250 bnWm1 = BN_CTX_get(context); 251 bnB = BN_CTX_get(context); 252 bnZ = BN_CTX_get(context); 253 bnM = BN_CTX_get(context); 254 if(bnM == NULL) 255 FAIL(FATAL_ERROR_ALLOCATION); 256 // Let a be the largest integer such that 2^a divides w1. 257 BN_copy(bnWm1, bnW); 258 BN_sub_word(bnWm1, 1); 259 // Since w is odd (w-1) is even so start at bit number 1 rather than 0 260 for(a = 1; !BN_is_bit_set(bnWm1, a); a++); 261 // 2. m = (w1) / 2^a 262 BN_rshift(bnM, bnWm1, a); 263 // 3. wlen = len (w). 264 wLen = BN_num_bits(bnW); 265 pAssert((wLen & 7) == 0); 266 // Set the size for the random number 267 b.b.size = (UINT16)(wLen + 7)/8; 268 // 4. For i = 1 to iterations do 269 for(i = 0; i < iterations ; i++) 270 { 271 // Obtain a string b of wlen bits from an RBG. 272 step4point1: 273 // In the reference implementation, wLen is always a multiple of 8 274 if(ktx != NULL) 275 RandomForRsa(ktx, "Miller-Rabin witness", &b.b); 276 else 277 _cpri__GenerateRandom(b.t.size, b.t.buffer); 278 if(BN_bin2bn(b.t.buffer, b.t.size, bnB) == NULL) 279 FAIL(FATAL_ERROR_ALLOCATION); 280 // If ((b 1) or (b w1)), then go to step 4.1. 281 if(BN_is_zero(bnB)) 282 goto step4point1; 283 if(BN_is_one(bnB)) 284 goto step4point1; 285 if(BN_ucmp(bnB, bnWm1) >= 0) 286 goto step4point1; 287 // z = b^m mod w. 288 if(BN_mod_exp(bnZ, bnB, bnM, bnW, context) != 1) 289 FAIL(FATAL_ERROR_ALLOCATION); 290 // If ((z = 1) or (z = w 1)), then go to step 4.7. 291 if(BN_is_one(bnZ) || BN_ucmp(bnZ, bnWm1) == 0) 292 goto step4point7; 293 // For j = 1 to a 1 do. 294 for(j = 1; j < a; j++) 295 { 296 // z = z^2 mod w. 297 if(BN_mod_mul(bnZ, bnZ, bnZ, bnW, context) != 1) 298 FAIL(FATAL_ERROR_ALLOCATION); 299 // If (z = w1), then go to step 4.7. 300 if(BN_ucmp(bnZ, bnWm1) == 0) 301 goto step4point7; 302 // If (z = 1), then go to step 4.6. 303 if(BN_is_one(bnZ)) 304 goto step4point6; 305 } 306 // Return COMPOSITE. 307 step4point6: 308 if(i > 9) 309 INSTRUMENT_INC(failedAtIteration[9]); 310 else 311 INSTRUMENT_INC(failedAtIteration[i]); 312 goto end; 313 // Continue. Comment: Increment i for the do-loop in step 4. 314 step4point7: 315 continue; 316 } 317 // 5. Return PROBABLY PRIME 318 ret = TRUE; 319 end: 320 BN_CTX_end(context); 321 return ret; 322 } 323 // 324 // 325 // NextPrime() 326 // 327 // This function is used to access the next prime number in the sequence of primes. It requires a pre- 328 // initialized iterator. 329 // 330 UINT32 331 NextPrime( 332 PRIME_ITERATOR *iter 333 ) 334 { 335 if(iter->index >= iter->final) 336 return (iter->lastPrime = 0); 337 return (iter->lastPrime += primeDiffTable[iter->index++]); 338 } 339 // 340 // 341 // AdjustNumberOfPrimes() 342 // 343 // Modifies the input parameter to be a valid value for the number of primes. The adjusted value is either the 344 // input value rounded up to the next 512 bytes boundary or the maximum value of the implementation. If 345 // the input is 0, the return is set to the maximum. 346 // 347 UINT32 348 AdjustNumberOfPrimes( 349 UINT32 p 350 ) 351 { 352 p = ((p + 511) / 512) * 512; 353 // 354 if(p == 0 || p > PRIME_DIFF_TABLE_BYTES) 355 p = PRIME_DIFF_TABLE_BYTES; 356 return p; 357 } 358 // 359 // 360 // PrimeInit() 361 // 362 // This function is used to initialize the prime sequence generator iterator. The iterator is initialized and 363 // returns the first prime that is equal to the requested starting value. If the starting value is no a prime, then 364 // the iterator is initialized to the next higher prime number. 365 // 366 UINT32 367 PrimeInit( 368 UINT32 first, // IN: the initial prime 369 PRIME_ITERATOR *iter, // IN/OUT: the iterator structure 370 UINT32 primes // IN: the table length 371 ) 372 { 373 iter->lastPrime = 1; 374 iter->index = 0; 375 iter->final = AdjustNumberOfPrimes(primes); 376 while(iter->lastPrime < first) 377 NextPrime(iter); 378 return iter->lastPrime; 379 } 380 // 381 // 382 // SetDefaultNumberOfPrimes() 383 // 384 // This macro sets the default number of primes to the indicated value. 385 // 386 //%#define SetDefaultNumberOfPrimes(p) (primeTableBytes = AdjustNumberOfPrimes(p)) 387 // 388 // 389 // IsPrimeWord() 390 // 391 // Checks to see if a UINT32 is prime 392 // 393 // Return Value Meaning 394 // 395 // TRUE number is prime 396 // FAIL number is not prime 397 // 398 BOOL 399 IsPrimeWord( 400 UINT32 p // IN: number to test 401 ) 402 { 403 #if defined RSA_KEY_SIEVE && (PRIME_DIFF_TABLE_BYTES >= 6542) 404 UINT32 test; 405 UINT32 index; 406 UINT32 stop; 407 if((p & 1) == 0) 408 return FALSE; 409 if(p == 1 || p == 3) 410 return TRUE; 411 // Get a high value for the stopping point 412 for(index = p, stop = 0; index; index >>= 2) 413 stop = (stop << 1) + 1; 414 stop++; 415 // If the full prime difference value table is present, can check here 416 test = 3; 417 for(index = 1; index < PRIME_DIFF_TABLE_BYTES; index += 1) 418 { 419 if((p % test) == 0) 420 return (p == test); 421 if(test > stop) 422 return TRUE; 423 test += primeDiffTable[index]; 424 } 425 return TRUE; 426 #else 427 BYTE b[4]; 428 if(p == RSA_DEFAULT_PUBLIC_EXPONENT || p == 1 || p == 3 ) 429 return TRUE; 430 if((p & 1) == 0) 431 return FALSE; 432 UINT32_TO_BYTE_ARRAY(p,b); 433 return _math__IsPrime(p); 434 #endif 435 } 436 typedef struct { 437 UINT16 prime; 438 UINT16 count; 439 } SIEVE_MARKS; 440 const SIEVE_MARKS sieveMarks[5] = { 441 {31, 7}, {73, 5}, {241, 4}, {1621, 3}, {UINT16_MAX, 2}}; 442 // 443 // 444 // PrimeSieve() 445 // 446 // This function does a prime sieve over the input field which has as its starting address the value in bnN. 447 // Since this initializes the Sieve using a pre-computed field with the bits associated with 3, 5 and 7 already 448 // turned off, the value of pnN may need to be adjusted by a few counts to allow the pre-computed field to 449 // be used without modification. The fieldSize parameter must be 2^N + 1 and is probably not useful if it is 450 // less than 129 bytes (1024 bits). 451 // 452 UINT32 453 PrimeSieve( 454 BIGNUM *bnN, // IN/OUT: number to sieve 455 UINT32 fieldSize, // IN: size of the field area in bytes 456 BYTE *field, // IN: field 457 UINT32 primes // IN: the number of primes to use 458 ) 459 { 460 UINT32 i; 461 UINT32 j; 462 UINT32 fieldBits = fieldSize * 8; 463 UINT32 r; 464 const BYTE *p1; 465 BYTE *p2; 466 PRIME_ITERATOR iter; 467 UINT32 adjust; 468 UINT32 mark = 0; 469 UINT32 count = sieveMarks[0].count; 470 UINT32 stop = sieveMarks[0].prime; 471 UINT32 composite; 472 // UINT64 test; //DEBUG 473 pAssert(field != NULL && bnN != NULL); 474 // Need to have a field that has a size of 2^n + 1 bytes 475 pAssert(BitsInArray((BYTE *)&fieldSize, 2) == 2); 476 primes = AdjustNumberOfPrimes(primes); 477 // If the remainder is odd, then subtracting the value 478 // will give an even number, but we want an odd number, 479 // so subtract the 105+rem. Otherwise, just subtract 480 // the even remainder. 481 adjust = BN_mod_word(bnN,105); 482 if(adjust & 1) 483 adjust += 105; 484 // seed the field 485 // This starts the pointer at the nearest byte to the input value 486 p1 = &seedValues[adjust/16]; 487 // Reduce the number of bytes to transfer by the amount skipped 488 j = sizeof(seedValues) - adjust/16; 489 adjust = adjust % 16; 490 BN_sub_word(bnN, adjust); 491 adjust >>= 1; 492 // This offsets the field 493 p2 = field; 494 for(i = fieldSize; i > 0; i--) 495 { 496 *p2++ = *p1++; 497 if(--j == 0) 498 { 499 j = sizeof(seedValues); 500 p1 = seedValues; 501 } 502 } 503 // Mask the first bits in the field and the last byte in order to eliminate 504 // bytes not in the field from consideration. 505 field[0] &= 0xff << adjust; 506 field[fieldSize-1] &= 0xff >> (8 - adjust); 507 // Cycle through the primes, clearing bits 508 // Have already done 3, 5, and 7 509 PrimeInit(7, &iter, primes); 510 // Get the next N primes where N is determined by the mark in the sieveMarks 511 while((composite = NextPrime(&iter)) != 0) 512 { 513 UINT32 pList[8]; 514 UINT32 next = 0; 515 i = count; 516 pList[i--] = composite; 517 for(; i > 0; i--) 518 { 519 next = NextPrime(&iter); 520 pList[i] = next; 521 if(next != 0) 522 composite *= next; 523 } 524 composite = BN_mod_word(bnN, composite); 525 for(i = count; i > 0; i--) 526 { 527 next = pList[i]; 528 if(next == 0) 529 goto done; 530 r = composite % next; 531 if(r & 1) j = (next - r)/2; 532 else if(r == 0) j = 0; 533 else j = next - r/2; 534 for(; j < fieldBits; j += next) 535 ClearBit(field, j); 536 } 537 if(next >= stop) 538 { 539 mark++; 540 count = sieveMarks[mark].count; 541 stop = sieveMarks[mark].prime; 542 } 543 } 544 done: 545 INSTRUMENT_INC(totalFieldsSieved); 546 i = BitsInArray(field, fieldSize); 547 if(i == 0) INSTRUMENT_INC(emptyFieldsSieved); 548 return i; 549 } 550 // 551 // 552 // PrimeSelectWithSieve() 553 // 554 // This function will sieve the field around the input prime candidate. If the sieve field is not empty, one of 555 // the one bits in the field is chosen for testing with Miller-Rabin. If the value is prime, pnP is updated with 556 // this value and the function returns success. If this value is not prime, another pseudo-random candidate 557 // is chosen and tested. This process repeats until all values in the field have been checked. If all bits in the 558 // field have been checked and none is prime, the function returns FALSE and a new random value needs 559 // to be chosen. 560 // 561 BOOL 562 PrimeSelectWithSieve( 563 BIGNUM *bnP, // IN/OUT: The candidate to filter 564 KDFa_CONTEXT *ktx, // IN: KDFa iterator structure 565 UINT32 e, // IN: the exponent 566 BN_CTX *context // IN: the big number context to play in 567 #ifdef RSA_DEBUG //% 568 ,UINT16 fieldSize, // IN: number of bytes in the field, as 569 // determined by the caller 570 UINT16 primes // IN: number of primes to use. 571 #endif //% 572 ) 573 { 574 BYTE field[MAX_FIELD_SIZE]; 575 UINT32 first; 576 UINT32 ones; 577 INT32 chosen; 578 UINT32 rounds = MillerRabinRounds(BN_num_bits(bnP)); 579 #ifndef RSA_DEBUG 580 UINT32 primes; 581 UINT32 fieldSize; 582 // Adjust the field size and prime table list to fit the size of the prime 583 // being tested. 584 primes = BN_num_bits(bnP); 585 if(primes <= 512) 586 { 587 primes = AdjustNumberOfPrimes(2048); 588 fieldSize = 65; 589 } 590 else if(primes <= 1024) 591 { 592 primes = AdjustNumberOfPrimes(4096); 593 fieldSize = 129; 594 } 595 // 596 else 597 { 598 primes = AdjustNumberOfPrimes(0); // Set to the maximum 599 fieldSize = MAX_FIELD_SIZE; 600 } 601 if(fieldSize > MAX_FIELD_SIZE) 602 fieldSize = MAX_FIELD_SIZE; 603 #endif 604 // Save the low-order word to use as a search generator and make sure that 605 // it has some interesting range to it 606 first = bnP->d[0] | 0x80000000; 607 // Align to field boundary 608 bnP->d[0] &= ~((UINT32)(fieldSize-3)); 609 pAssert(BN_is_bit_set(bnP, 0)); 610 bnP->d[0] &= (UINT32_MAX << (FIELD_POWER + 1)) + 1; 611 ones = PrimeSieve(bnP, fieldSize, field, primes); 612 #ifdef RSA_FILTER_DEBUG 613 pAssert(ones == BitsInArray(field, defaultFieldSize)); 614 #endif 615 for(; ones > 0; ones--) 616 { 617 #ifdef RSA_FILTER_DEBUG 618 if(ones != BitsInArray(field, defaultFieldSize)) 619 FAIL(FATAL_ERROR_INTERNAL); 620 #endif 621 // Decide which bit to look at and find its offset 622 if(ones == 1) 623 ones = ones; 624 chosen = FindNthSetBit(defaultFieldSize, field,((first % ones) + 1)); 625 if(chosen >= ((defaultFieldSize) * 8)) 626 FAIL(FATAL_ERROR_INTERNAL); 627 // Set this as the trial prime 628 BN_add_word(bnP, chosen * 2); 629 // Use MR to see if this is prime 630 if(MillerRabin(bnP, rounds, ktx, context)) 631 { 632 // Final check is to make sure that 0 != (p-1) mod e 633 // This is the same as -1 != p mod e ; or 634 // (e - 1) != p mod e 635 if((e <= 3) || (BN_mod_word(bnP, e) != (e-1))) 636 return TRUE; 637 } 638 // Back out the bit number 639 BN_sub_word(bnP, chosen * 2); 640 // Clear the bit just tested 641 ClearBit(field, chosen); 642 } 643 // Ran out of bits and couldn't find a prime in this field 644 INSTRUMENT_INC(noPrimeFields); 645 return FALSE; 646 } 647 // 648 // 649 // AdjustPrimeCandiate() 650 // 651 // This function adjusts the candidate prime so that it is odd and > root(2)/2. This allows the product of these 652 // two numbers to be .5, which, in fixed point notation means that the most significant bit is 1. For this 653 // routine, the root(2)/2 is approximated with 0xB505 which is, in fixed point is 0.7071075439453125 or an 654 // error of 0.0001%. Just setting the upper two bits would give a value > 0.75 which is an error of > 6%. 655 // 656 // 657 // Given the amount of time all the other computations take, reducing the error is not much of a cost, but it 658 // isn't totally required either. 659 // The function also puts the number on a field boundary. 660 // 661 void 662 AdjustPrimeCandidate( 663 BYTE *a, 664 UINT16 len 665 ) 666 { 667 UINT16 highBytes; 668 highBytes = BYTE_ARRAY_TO_UINT16(a); 669 // This is fixed point arithmetic on 16-bit values 670 highBytes = ((UINT32)highBytes * (UINT32)0x4AFB) >> 16; 671 highBytes += 0xB505; 672 UINT16_TO_BYTE_ARRAY(highBytes, a); 673 a[len-1] |= 1; 674 } 675 // 676 // 677 // GeneratateRamdomPrime() 678 // 679 void 680 GenerateRandomPrime( 681 TPM2B *p, 682 BN_CTX *ctx 683 #ifdef RSA_DEBUG //% 684 ,UINT16 field, 685 UINT16 primes 686 #endif //% 687 ) 688 { 689 BIGNUM *bnP; 690 BN_CTX *context; 691 if(ctx == NULL) context = BN_CTX_new(); 692 else context = ctx; 693 if(context == NULL) 694 FAIL(FATAL_ERROR_ALLOCATION); 695 BN_CTX_start(context); 696 bnP = BN_CTX_get(context); 697 while(TRUE) 698 { 699 _cpri__GenerateRandom(p->size, p->buffer); 700 p->buffer[p->size-1] |= 1; 701 p->buffer[0] |= 0x80; 702 BN_bin2bn(p->buffer, p->size, bnP); 703 #ifdef RSA_DEBUG 704 if(PrimeSelectWithSieve(bnP, NULL, 0, context, field, primes)) 705 #else 706 if(PrimeSelectWithSieve(bnP, NULL, 0, context)) 707 #endif 708 break; 709 } 710 BnTo2B(p, bnP, (UINT16)BN_num_bytes(bnP)); 711 BN_CTX_end(context); 712 if(ctx == NULL) 713 BN_CTX_free(context); 714 return; 715 } 716 KDFa_CONTEXT * 717 KDFaContextStart( 718 KDFa_CONTEXT *ktx, // IN/OUT: the context structure to initialize 719 TPM2B *seed, // IN: the seed for the digest proce 720 TPM_ALG_ID hashAlg, // IN: the hash algorithm 721 TPM2B *extra, // IN: the extra data 722 UINT32 *outer, // IN: the outer iteration counter 723 UINT16 keySizeInBit 724 ) 725 { 726 UINT16 digestSize = _cpri__GetDigestSize(hashAlg); 727 TPM2B_HASH_BLOCK oPadKey; 728 if(seed == NULL) 729 return NULL; 730 pAssert(ktx != NULL && outer != NULL && digestSize != 0); 731 // Start the hash using the seed and get the intermediate hash value 732 _cpri__StartHMAC(hashAlg, FALSE, &(ktx->iPadCtx), seed->size, seed->buffer, 733 &oPadKey.b); 734 _cpri__StartHash(hashAlg, FALSE, &(ktx->oPadCtx)); 735 _cpri__UpdateHash(&(ktx->oPadCtx), oPadKey.b.size, oPadKey.b.buffer); 736 ktx->extra = extra; 737 ktx->hashAlg = hashAlg; 738 ktx->outer = outer; 739 ktx->keySizeInBits = keySizeInBits; 740 return ktx; 741 } 742 void 743 KDFaContextEnd( 744 KDFa_CONTEXT *ktx // IN/OUT: the context structure to close 745 ) 746 { 747 if(ktx != NULL) 748 { 749 // Close out the hash sessions 750 _cpri__CompleteHash(&(ktx->iPadCtx), 0, NULL); 751 _cpri__CompleteHash(&(ktx->oPadCtx), 0, NULL); 752 } 753 } 754 //%#endif 755 // 756 // 757 // Public Function 758 // 759 // Introduction 760 // 761 // This is the external entry for this replacement function. All this file provides is the substitute function to 762 // generate an RSA key. If the compiler settings are set appropriately, this this function will be used instead 763 // of the similarly named function in CpriRSA.c. 764 // 765 // _cpri__GenerateKeyRSA() 766 // 767 // Generate an RSA key from a provided seed 768 // 769 // Return Value Meaning 770 // 771 // CRYPT_FAIL exponent is not prime or is less than 3; or could not find a prime using 772 // the provided parameters 773 // CRYPT_CANCEL operation was canceled 774 // 775 LIB_EXPORT CRYPT_RESULT 776 _cpri__GenerateKeyRSA( 777 TPM2B *n, // OUT: The public modulus 778 TPM2B *p, // OUT: One of the prime factors of n 779 UINT16 keySizeInBits, // IN: Size of the public modulus in bits 780 UINT32 e, // IN: The public exponent 781 TPM_ALG_ID hashAlg, // IN: hash algorithm to use in the key 782 // generation process 783 TPM2B *seed, // IN: the seed to use 784 const char *label, // IN: A label for the generation process. 785 TPM2B *extra, // IN: Party 1 data for the KDF 786 UINT32 *counter // IN/OUT: Counter value to allow KDF 787 // iteration to be propagated across 788 // multiple routines 789 #ifdef RSA_DEBUG //% 790 ,UINT16 primes, // IN: number of primes to test 791 UINT16 fieldSize // IN: the field size to use 792 #endif //% 793 ) 794 { 795 CRYPT_RESULT retVal; 796 UINT32 myCounter = 0; 797 UINT32 *pCtr = (counter == NULL) ? &myCounter : counter; 798 KDFa_CONTEXT ktx; 799 KDFa_CONTEXT *ktxPtr; 800 UINT32 i; 801 BIGNUM *bnP; 802 BIGNUM *bnQ; 803 BIGNUM *bnT; 804 BIGNUM *bnE; 805 BIGNUM *bnN; 806 BN_CTX *context; 807 // Make sure that the required pointers are provided 808 pAssert(n != NULL && p != NULL); 809 // If the seed is provided, then use KDFa for generation of the 'random' 810 // values 811 ktxPtr = KDFaContextStart(&ktx, seed, hashAlg, extra, pCtr, keySizeInBits); 812 n->size = keySizeInBits/8; 813 p->size = n->size / 2; 814 // Validate exponent 815 if(e == 0 || e == RSA_DEFAULT_PUBLIC_EXPONENT) 816 e = RSA_DEFAULT_PUBLIC_EXPONENT; 817 else 818 if(!IsPrimeWord(e)) 819 return CRYPT_FAIL; 820 // Get structures for the big number representations 821 context = BN_CTX_new(); 822 BN_CTX_start(context); 823 bnP = BN_CTX_get(context); 824 bnQ = BN_CTX_get(context); 825 bnT = BN_CTX_get(context); 826 bnE = BN_CTX_get(context); 827 bnN = BN_CTX_get(context); 828 if(bnN == NULL) 829 FAIL(FATAL_ERROR_INTERNAL); 830 // Set Q to zero. This is used as a flag. The prime is computed in P. When a 831 // new prime is found, Q is checked to see if it is zero. If so, P is copied 832 // to Q and a new P is found. When both P and Q are non-zero, the modulus and 833 // private exponent are computed and a trial encryption/decryption is 834 // performed. If the encrypt/decrypt fails, assume that at least one of the 835 // primes is composite. Since we don't know which one, set Q to zero and start 836 // over and find a new pair of primes. 837 BN_zero(bnQ); 838 BN_set_word(bnE, e); 839 // Each call to generate a random value will increment ktx.outer 840 // it doesn't matter if ktx.outer wraps. This lets the caller 841 // use the initial value of the counter for additional entropy. 842 for(i = 0; i < UINT32_MAX; i++) 843 { 844 if(_plat__IsCanceled()) 845 { 846 retVal = CRYPT_CANCEL; 847 goto end; 848 } 849 // Get a random prime candidate. 850 if(seed == NULL) 851 _cpri__GenerateRandom(p->size, p->buffer); 852 else 853 RandomForRsa(&ktx, label, p); 854 AdjustPrimeCandidate(p->buffer, p->size); 855 // Convert the candidate to a BN 856 if(BN_bin2bn(p->buffer, p->size, bnP) == NULL) 857 FAIL(FATAL_ERROR_INTERNAL); 858 // If this is the second prime, make sure that it differs from the 859 // first prime by at least 2^100. Since BIGNUMS use words, the check 860 // below will make sure they are different by at least 128 bits 861 if(!BN_is_zero(bnQ)) 862 { // bnQ is non-zero, we have a first value 863 UINT32 *pP = (UINT32 *)(&bnP->d[4]); 864 UINT32 *pQ = (UINT32 *)(&bnQ->d[4]); 865 INT32 k = ((INT32)bnP->top) - 4; 866 for(;k > 0; k--) 867 if(*pP++ != *pQ++) 868 break; 869 // Didn't find any difference so go get a new value 870 if(k == 0) 871 continue; 872 } 873 // If PrimeSelectWithSieve returns success, bnP is a prime, 874 #ifdef RSA_DEBUG 875 if(!PrimeSelectWithSieve(bnP, ktxPtr, e, context, fieldSize, primes)) 876 #else 877 if(!PrimeSelectWithSieve(bnP, ktxPtr, e, context)) 878 #endif 879 continue; // If not, get another 880 // Found a prime, is this the first or second. 881 if(BN_is_zero(bnQ)) 882 { // copy p to q and compute another prime in p 883 BN_copy(bnQ, bnP); 884 continue; 885 } 886 //Form the public modulus 887 if( BN_mul(bnN, bnP, bnQ, context) != 1 888 || BN_num_bits(bnN) != keySizeInBits) 889 FAIL(FATAL_ERROR_INTERNAL); 890 // Save the public modulus 891 BnTo2B(n, bnN, n->size); 892 // And one prime 893 BnTo2B(p, bnP, p->size); 894 #ifdef EXTENDED_CHECKS 895 // Finish by making sure that we can form the modular inverse of PHI 896 // with respect to the public exponent 897 // Compute PHI = (p - 1)(q - 1) = n - p - q + 1 898 // Make sure that we can form the modular inverse 899 if( BN_sub(bnT, bnN, bnP) != 1 900 || BN_sub(bnT, bnT, bnQ) != 1 901 || BN_add_word(bnT, 1) != 1) 902 FAIL(FATAL_ERROR_INTERNAL); 903 // find d such that (Phi * d) mod e ==1 904 // If there isn't then we are broken because we took the step 905 // of making sure that the prime != 1 mod e so the modular inverse 906 // must exist 907 if( BN_mod_inverse(bnT, bnE, bnT, context) == NULL 908 || BN_is_zero(bnT)) 909 FAIL(FATAL_ERROR_INTERNAL); 910 // And, finally, do a trial encryption decryption 911 { 912 TPM2B_TYPE(RSA_KEY, MAX_RSA_KEY_BYTES); 913 TPM2B_RSA_KEY r; 914 r.t.size = sizeof(r.t.buffer); 915 // If we are using a seed, then results must be reproducible on each 916 // call. Otherwise, just get a random number 917 if(seed == NULL) 918 _cpri__GenerateRandom(keySizeInBits/8, r.t.buffer); 919 else 920 RandomForRsa(&ktx, label, &r.b); 921 // Make sure that the number is smaller than the public modulus 922 r.t.buffer[0] &= 0x7F; 923 // Convert 924 if( BN_bin2bn(r.t.buffer, r.t.size, bnP) == NULL 925 // Encrypt with the public exponent 926 || BN_mod_exp(bnQ, bnP, bnE, bnN, context) != 1 927 // Decrypt with the private exponent 928 || BN_mod_exp(bnQ, bnQ, bnT, bnN, context) != 1) 929 FAIL(FATAL_ERROR_INTERNAL); 930 // If the starting and ending values are not the same, start over )-; 931 if(BN_ucmp(bnP, bnQ) != 0) 932 { 933 BN_zero(bnQ); 934 continue; 935 } 936 } 937 #endif // EXTENDED_CHECKS 938 retVal = CRYPT_SUCCESS; 939 goto end; 940 } 941 retVal = CRYPT_FAIL; 942 end: 943 KDFaContextEnd(&ktx); 944 // Free up allocated BN values 945 BN_CTX_end(context); 946 BN_CTX_free(context); 947 return retVal; 948 } 949 #endif //% 950 #endif // TPM_ALG_RSA 951
