blob: f3044ff3bfc2c4a4d5cb420858e1be9a05ddb654 [file] [log] [blame]
Vadim Bendebury56797522015-05-20 10:32:25 -07001// 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#else
950static void noFuntion(
951 void
952 )
953{
954 pAssert(1);
955}
956#endif //%
957#endif // TPM_ALG_RSA