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// 33void 34ClearBit( 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// 47void 48SetBit( 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// 69UINT32 70IsBitSet( 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// 83int 84BitsInArray( 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// 101UINT32 102FindNthSetBit( 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// 146void 147RandomForRsa( 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// 205UINT32 206MillerRabinRounds( 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// 228BOOL 229MillerRabin( 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. 272step4point1: 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. 307step4point6: 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. 314step4point7: 315 continue; 316 } 317// 5. Return PROBABLY PRIME 318 ret = TRUE; 319end: 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// 330UINT32 331NextPrime( 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// 347UINT32 348AdjustNumberOfPrimes( 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// 366UINT32 367PrimeInit( 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// 398BOOL 399IsPrimeWord( 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} 436typedef struct { 437 UINT16 prime; 438 UINT16 count; 439} SIEVE_MARKS; 440const 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// 452UINT32 453PrimeSieve( 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 } 544done: 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// 561BOOL 562PrimeSelectWithSieve( 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// 661void 662AdjustPrimeCandidate( 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// 679void 680GenerateRandomPrime( 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} 716KDFa_CONTEXT * 717KDFaContextStart( 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} 742void 743KDFaContextEnd( 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// 775LIB_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; 942end: 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