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
ClearBit(unsigned char * a,int i)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
SetBit(unsigned char * a,int i)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
IsBitSet(unsigned char * a,int i)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
BitsInArray(unsigned char * a,int i)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
FindNthSetBit(const UINT16 aSize,const BYTE * a,const UINT32 n)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
RandomForRsa(KDFa_CONTEXT * ktx,const char * label,TPM2B * p)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
MillerRabinRounds(UINT32 bits)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
MillerRabin(BIGNUM * bnW,int iterations,KDFa_CONTEXT * ktx,BN_CTX * context)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
NextPrime(PRIME_ITERATOR * iter)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
AdjustNumberOfPrimes(UINT32 p)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
PrimeInit(UINT32 first,PRIME_ITERATOR * iter,UINT32 primes)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
IsPrimeWord(UINT32 p)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
PrimeSieve(BIGNUM * bnN,UINT32 fieldSize,BYTE * field,UINT32 primes)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
PrimeSelectWithSieve(BIGNUM * bnP,KDFa_CONTEXT * ktx,UINT32 e,BN_CTX * context,UINT16 fieldSize,UINT16 primes)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
AdjustPrimeCandidate(BYTE * a,UINT16 len)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
GenerateRandomPrime(TPM2B * p,BN_CTX * ctx,UINT16 field,UINT16 primes)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 *
KDFaContextStart(KDFa_CONTEXT * ktx,TPM2B * seed,TPM_ALG_ID hashAlg,TPM2B * extra,UINT32 * outer,UINT16 keySizeInBit)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
KDFaContextEnd(KDFa_CONTEXT * ktx)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
_cpri__GenerateKeyRSA(TPM2B * n,TPM2B * p,UINT16 keySizeInBits,UINT32 e,TPM_ALG_ID hashAlg,TPM2B * seed,const char * label,TPM2B * extra,UINT32 * counter,UINT16 primes,UINT16 fieldSize)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