1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
|
/********************************************************************************/
/* */
/* Simple Operations on Big Numbers */
/* Written by Ken Goldman */
/* IBM Thomas J. Watson Research Center */
/* $Id: BnMath.c 1529 2019-11-21 23:29:01Z kgoldman $ */
/* */
/* Licenses and Notices */
/* */
/* 1. Copyright Licenses: */
/* */
/* - Trusted Computing Group (TCG) grants to the user of the source code in */
/* this specification (the "Source Code") a worldwide, irrevocable, */
/* nonexclusive, royalty free, copyright license to reproduce, create */
/* derivative works, distribute, display and perform the Source Code and */
/* derivative works thereof, and to grant others the rights granted herein. */
/* */
/* - The TCG grants to the user of the other parts of the specification */
/* (other than the Source Code) the rights to reproduce, distribute, */
/* display, and perform the specification solely for the purpose of */
/* developing products based on such documents. */
/* */
/* 2. Source Code Distribution Conditions: */
/* */
/* - Redistributions of Source Code must retain the above copyright licenses, */
/* this list of conditions and the following disclaimers. */
/* */
/* - Redistributions in binary form must reproduce the above copyright */
/* licenses, this list of conditions and the following disclaimers in the */
/* documentation and/or other materials provided with the distribution. */
/* */
/* 3. Disclaimers: */
/* */
/* - THE COPYRIGHT LICENSES SET FORTH ABOVE DO NOT REPRESENT ANY FORM OF */
/* LICENSE OR WAIVER, EXPRESS OR IMPLIED, BY ESTOPPEL OR OTHERWISE, WITH */
/* RESPECT TO PATENT RIGHTS HELD BY TCG MEMBERS (OR OTHER THIRD PARTIES) */
/* THAT MAY BE NECESSARY TO IMPLEMENT THIS SPECIFICATION OR OTHERWISE. */
/* Contact TCG Administration (admin@trustedcomputinggroup.org) for */
/* information on specification licensing rights available through TCG */
/* membership agreements. */
/* */
/* - THIS SPECIFICATION IS PROVIDED "AS IS" WITH NO EXPRESS OR IMPLIED */
/* WARRANTIES WHATSOEVER, INCLUDING ANY WARRANTY OF MERCHANTABILITY OR */
/* FITNESS FOR A PARTICULAR PURPOSE, ACCURACY, COMPLETENESS, OR */
/* NONINFRINGEMENT OF INTELLECTUAL PROPERTY RIGHTS, OR ANY WARRANTY */
/* OTHERWISE ARISING OUT OF ANY PROPOSAL, SPECIFICATION OR SAMPLE. */
/* */
/* - Without limitation, TCG and its members and licensors disclaim all */
/* liability, including liability for infringement of any proprietary */
/* rights, relating to use of information in this specification and to the */
/* implementation of this specification, and TCG disclaims all liability for */
/* cost of procurement of substitute goods or services, lost profits, loss */
/* of use, loss of data or any incidental, consequential, direct, indirect, */
/* or special damages, whether under contract, tort, warranty or otherwise, */
/* arising in any way out of use or reliance upon this specification or any */
/* information herein. */
/* */
/* (c) Copyright IBM Corp. and others, 2016 - 2019 */
/* */
/********************************************************************************/
/* 10.2.3 BnMath.c */
/* 10.2.3.1 Introduction */
/* The simulator code uses the canonical form whenever possible in order to make the code in Part 3
more accessible. The canonical data formats are simple and not well suited for complex big number
computations. When operating on big numbers, the data format is changed for easier
manipulation. The format is native words in little-endian format. As the magnitude of the number
decreases, the length of the array containing the number decreases but the starting address
doesn't change. */
/* The functions in this file perform simple operations on these big numbers. Only the more complex
operations are passed to the underlying support library. Although the support library would have
most of these functions, the interface code to convert the format for the values is greater than
the size of the code to implement the functions here. So, rather than incur the overhead of
conversion, they are done here. */
/* If an implementer would prefer, the underlying library can be used simply by making code
substitutions here. */
/* NOTE: There is an intention to continue to augment these functions so that there would be no need
to use an external big number library. */
/* Many of these functions have no error returns and will always return TRUE. This is to allow them
to be used in guarded sequences. That is: OK = OK || BnSomething(s); where the BnSomething()
function should not be called if OK isn't true. */
/* 10.2.3.2 Includes */
#include "Tpm.h"
/* A constant value of zero as a stand in for NULL bigNum values */
const bignum_t BnConstZero = {1, 0, {0}};
/* 10.2.3.3 Functions */
/* 10.2.3.3.1 AddSame() */
/* Adds two values that are the same size. This function allows result to be the same as either of
the addends. This is a nice function to put into assembly because handling the carry for
multi-precision stuff is not as easy in C (unless there is a REALLY smart compiler). It would be
nice if there were idioms in a language that a compiler could recognize what is going on and
optimize loops like this. */
/* Return Values Meaning */
/* 0 no carry out */
/* 1 carry out */
static BOOL
AddSame(
crypt_uword_t *result,
const crypt_uword_t *op1,
const crypt_uword_t *op2,
int count
)
{
int carry = 0;
int i;
for(i = 0; i < count; i++)
{
crypt_uword_t a = op1[i];
crypt_uword_t sum = a + op2[i];
result[i] = sum + carry;
// generate a carry if the sum is less than either of the inputs
// propagate a carry if there was a carry and the sum + carry is zero
// do this using bit operations rather than logical operations so that
// the time is about the same.
// propagate term | generate term
carry = ((result[i] == 0) & carry) | (sum < a);
}
return carry;
}
/* 10.2.3.3.2 CarryProp() */
/* Propagate a carry */
static int
CarryProp(
crypt_uword_t *result,
const crypt_uword_t *op,
int count,
int carry
)
{
for(; count; count--)
carry = ((*result++ = *op++ + carry) == 0) & carry;
return carry;
}
static void
CarryResolve(
bigNum result,
int stop,
int carry
)
{
if(carry)
{
pAssert((unsigned)stop < result->allocated);
result->d[stop++] = 1;
}
BnSetTop(result, stop);
}
/* 10.2.3.3.3 BnAdd() */
/* This function adds two bigNum values. Always returns TRUE */
LIB_EXPORT BOOL
BnAdd(
bigNum result,
bigConst op1,
bigConst op2
)
{
crypt_uword_t stop;
int carry;
const bignum_t *n1 = op1;
const bignum_t *n2 = op2;
//
if(n2->size > n1->size)
{
n1 = op2;
n2 = op1;
}
pAssert(result->allocated >= n1->size);
stop = MIN(n1->size, n2->allocated);
carry = (int)AddSame(result->d, n1->d, n2->d, (int)stop);
if(n1->size > stop)
carry = CarryProp(&result->d[stop], &n1->d[stop], (int)(n1->size - stop), carry);
CarryResolve(result, (int)n1->size, carry);
return TRUE;
}
/* 10.2.3.3.4 BnAddWord() */
/* Adds a word value to a bigNum. */
LIB_EXPORT BOOL
BnAddWord(
bigNum result,
bigConst op,
crypt_uword_t word
)
{
int carry;
//
carry = (result->d[0] = op->d[0] + word) < word;
carry = CarryProp(&result->d[1], &op->d[1], (int)(op->size - 1), carry);
CarryResolve(result, (int)op->size, carry);
return TRUE;
}
/* 10.2.3.3.5 SubSame() */
/* Subtract two values that have the same size. */
static int
SubSame(
crypt_uword_t *result,
const crypt_uword_t *op1,
const crypt_uword_t *op2,
int count
)
{
int borrow = 0;
int i;
for(i = 0; i < count; i++)
{
crypt_uword_t a = op1[i];
crypt_uword_t diff = a - op2[i];
result[i] = diff - borrow;
// generate | propagate
borrow = (diff > a) | ((diff == 0) & borrow);
}
return borrow;
}
/* 10.2.3.3.6 BorrowProp() */
/* This propagates a borrow. If borrow is true when the end of the array is reached, then it means
that op2 was larger than op1 and we don't handle that case so an assert is generated. This design
choice was made because our only bigNum computations are on large positive numbers (primes) or on
fields. Propagate a borrow. */
static int
BorrowProp(
crypt_uword_t *result,
const crypt_uword_t *op,
int size,
int borrow
)
{
for(; size > 0; size--)
borrow = ((*result++ = *op++ - borrow) == MAX_CRYPT_UWORD) && borrow;
return borrow;
}
/* 10.2.3.3.7 BnSub() */
/* This function does subtraction of two bigNum values and returns result = op1 - op2 when op1 is
greater than op2. If op2 is greater than op1, then a fault is generated. This function always
returns TRUE. */
LIB_EXPORT BOOL
BnSub(
bigNum result,
bigConst op1,
bigConst op2
)
{
int borrow;
int stop = (int)MIN(op1->size, op2->allocated);
//
// Make sure that op2 is not obviously larger than op1
pAssert(op1->size >= op2->size);
borrow = SubSame(result->d, op1->d, op2->d, stop);
if(op1->size > (crypt_uword_t)stop)
borrow = BorrowProp(&result->d[stop], &op1->d[stop], (int)(op1->size - stop),
borrow);
pAssert(!borrow);
BnSetTop(result, op1->size);
return TRUE;
}
/* 10.2.3.3.8 BnSubWord() */
/* This function subtracts a word value from a bigNum. This function always returns TRUE. */
LIB_EXPORT BOOL
BnSubWord(
bigNum result,
bigConst op,
crypt_uword_t word
)
{
int borrow;
//
pAssert(op->size > 1 || word <= op->d[0]);
borrow = word > op->d[0];
result->d[0] = op->d[0] - word;
borrow = BorrowProp(&result->d[1], &op->d[1], (int)(op->size - 1), borrow);
pAssert(!borrow);
BnSetTop(result, op->size);
return TRUE;
}
/* 10.2.3.3.9 BnUnsignedCmp() */
/* This function performs a comparison of op1 to op2. The compare is approximately constant time if
the size of the values used in the compare is consistent across calls (from the same line in the
calling code). */
/* Return Values Meaning */
/* < 0 op1 is less than op2 */
/* 0 op1 is equal to op2 */
/* > 0 op1 is greater than op2 */
LIB_EXPORT int
BnUnsignedCmp(
bigConst op1,
bigConst op2
)
{
int retVal;
int diff;
int i;
//
pAssert((op1 != NULL) && (op2 != NULL));
retVal = (int)(op1->size - op2->size);
if(retVal == 0)
{
for(i = (int)(op1->size - 1); i >= 0; i--)
{
diff = (op1->d[i] < op2->d[i]) ? -1 : (op1->d[i] != op2->d[i]);
retVal = retVal == 0 ? diff : retVal;
}
}
else
retVal = (retVal < 0) ? -1 : 1;
return retVal;
}
/* 10.2.3.3.10 BnUnsignedCmpWord() */
/* Compare a bigNum to a crypt_uword_t. */
/* Return Value Meaning */
/* -1 op1 is less that word */
/* 0 op1 is equal to word */
/* 1 op1 is greater than word */
LIB_EXPORT int
BnUnsignedCmpWord(
bigConst op1,
crypt_uword_t word
)
{
if(op1->size > 1)
return 1;
else if(op1->size == 1)
return (op1->d[0] < word) ? -1 : (op1->d[0] > word);
else // op1 is zero
// equal if word is zero
return (word == 0) ? 0 : -1;
}
/* 10.2.3.3.11 BnModWord() */
/* This function does modular division of a big number when the modulus is a word value. */
LIB_EXPORT crypt_word_t
BnModWord(
bigConst numerator,
crypt_word_t modulus
)
{
BN_MAX(remainder);
BN_VAR(mod, RADIX_BITS);
//
mod->d[0] = modulus;
mod->size = (modulus != 0);
BnDiv(NULL, remainder, numerator, mod);
return remainder->d[0];
}
/* 10.2.3.3.12 Msb() */
/* Returns the bit number of the most significant bit of a crypt_uword_t. The number for the least
significant bit of any bigNum value is 0. The maximum return value is RADIX_BITS - 1, */
/* Return Values Meaning */
/* -1 the word was zero */
/* n the bit number of the most significant bit in the word */
LIB_EXPORT int
Msb(
crypt_uword_t word
)
{
int retVal = -1;
//
#if RADIX_BITS == 64
if(word & 0xffffffff00000000) { retVal += 32; word >>= 32; }
#endif
if(word & 0xffff0000) { retVal += 16; word >>= 16; }
if(word & 0x0000ff00) { retVal += 8; word >>= 8; }
if(word & 0x000000f0) { retVal += 4; word >>= 4; }
if(word & 0x0000000c) { retVal += 2; word >>= 2; }
if(word & 0x00000002) { retVal += 1; word >>= 1; }
return retVal + (int)word;
}
/* 10.2.3.3.13 BnMsb() */
/* This function returns the number of the MSb() of a bigNum value. */
/* Return Value Meaning */
/* -1 the word was zero or bn was NULL */
/* n the bit number of the most significant bit in the word */
LIB_EXPORT int
BnMsb(
bigConst bn
)
{
// If the value is NULL, or the size is zero then treat as zero and return -1
if(bn != NULL && bn->size > 0)
{
int retVal = Msb(bn->d[bn->size - 1]);
retVal += (int)(bn->size - 1) * RADIX_BITS;
return retVal;
}
else
return -1;
}
/* 10.2.3.3.14 BnSizeInBits() */
/* Returns the number of bits required to hold a number. It is one greater than the Msb. */
LIB_EXPORT unsigned
BnSizeInBits(
bigConst n
)
{
int bits = BnMsb(n) + 1;
//
return bits < 0 ? 0 : (unsigned)bits;
}
/* 10.2.3.3.15 BnSetWord() */
/* Change the value of a bignum_t to a word value. */
LIB_EXPORT bigNum
BnSetWord(
bigNum n,
crypt_uword_t w
)
{
if(n != NULL)
{
pAssert(n->allocated > 1);
n->d[0] = w;
BnSetTop(n, (w != 0) ? 1 : 0);
}
return n;
}
/* 10.2.3.3.16 BnSetBit() */
/* SET a bit in a bigNum. Bit 0 is the least-significant bit in the 0th digit_t. The function always
return TRUE */
LIB_EXPORT BOOL
BnSetBit(
bigNum bn, // IN/OUT: big number to modify
unsigned int bitNum // IN: Bit number to SET
)
{
crypt_uword_t offset = bitNum / RADIX_BITS;
pAssert(bn->allocated * RADIX_BITS >= bitNum);
// Grow the number if necessary to set the bit.
while(bn->size <= offset)
bn->d[bn->size++] = 0;
bn->d[offset] |= (crypt_uword_t)(1 << RADIX_MOD(bitNum));
return TRUE;
}
/* 10.2.3.3.17 BnTestBit() */
/* Check to see if a bit is SET in a bignum_t. The 0th bit is the LSb() of d[0]. */
/* Return Values Meaning */
/* TRUE the bit is set */
/* FALSE the bit is not set or the number is out of range */
LIB_EXPORT BOOL
BnTestBit(
bigNum bn, // IN: number to check
unsigned int bitNum // IN: bit to test
)
{
crypt_uword_t offset = RADIX_DIV(bitNum);
//
if(bn->size > offset)
return ((bn->d[offset] & (((crypt_uword_t)1) << RADIX_MOD(bitNum))) != 0);
else
return FALSE;
}
/* 10.2.3.3.18 BnMaskBits() */
/* Function to mask off high order bits of a big number. The returned value will have no more than
maskBit bits set. */
/* NOTE: There is a requirement that unused words of a bignum_t are set to zero. */
/* Return Values Meaning */
/* TRUE result masked */
/* FALSE the input was not as large as the mask */
LIB_EXPORT BOOL
BnMaskBits(
bigNum bn, // IN/OUT: number to mask
crypt_uword_t maskBit // IN: the bit number for the mask.
)
{
crypt_uword_t finalSize;
BOOL retVal;
finalSize = BITS_TO_CRYPT_WORDS(maskBit);
retVal = (finalSize <= bn->allocated);
if(retVal && (finalSize > 0))
{
crypt_uword_t mask;
mask = ~((crypt_uword_t)0) >> RADIX_MOD(maskBit);
bn->d[finalSize - 1] &= mask;
}
BnSetTop(bn, finalSize);
return retVal;
}
/* 10.2.3.3.19 BnShiftRight() */
/* Function will shift a bigNum to the right by the shiftAmount. This function always returns
TRUE. */
LIB_EXPORT BOOL
BnShiftRight(
bigNum result,
bigConst toShift,
uint32_t shiftAmount
)
{
uint32_t offset = (shiftAmount >> RADIX_LOG2);
uint32_t i;
uint32_t shiftIn;
crypt_uword_t finalSize;
//
shiftAmount = shiftAmount & RADIX_MASK;
shiftIn = RADIX_BITS - shiftAmount;
// The end size is toShift->size - offset less one additional
// word if the shiftAmount would make the upper word == 0
if(toShift->size > offset)
{
finalSize = toShift->size - offset;
finalSize -= (toShift->d[toShift->size - 1] >> shiftAmount) == 0 ? 1 : 0;
}
else
finalSize = 0;
pAssert(finalSize <= result->allocated);
if(finalSize != 0)
{
for(i = 0; i < finalSize; i++)
{
result->d[i] = (toShift->d[i + offset] >> shiftAmount)
| (toShift->d[i + offset + 1] << shiftIn);
}
if(offset == 0)
result->d[i] = toShift->d[i] >> shiftAmount;
}
BnSetTop(result, finalSize);
return TRUE;
}
/* 10.2.3.3.20 BnGetRandomBits() */
/* Return Value Meaning */
/* TRUE(1) success */
/* FALSE(0) failure */
LIB_EXPORT BOOL
BnGetRandomBits(
bigNum n,
size_t bits,
RAND_STATE *rand
)
{
// Since this could be used for ECC key generation using the extra bits method,
// make sure that the value is large enough
TPM2B_TYPE(LARGEST, LARGEST_NUMBER + 8);
TPM2B_LARGEST large;
//
large.b.size = (UINT16)BITS_TO_BYTES(bits);
if(DRBG_Generate(rand, large.t.buffer, large.t.size) == large.t.size)
{
if(BnFrom2B(n, &large.b) != NULL)
{
if(BnMaskBits(n, (crypt_uword_t)bits))
return TRUE;
}
}
return FALSE;
}
/* 10.2.3.3.21 BnGenerateRandomInRange() */
/* Function to generate a random number r in the range 1 <= r < limit. The function gets a random
number of bits that is the size of limit. There is some some probability that the returned number
is going to be greater than or equal to the limit. If it is, try again. There is no more than 50%
chance that the next number is also greater, so try again. We keep trying until we get a value
that meets the criteria. Since limit is very often a number with a LOT of high order ones, this
rarely would need a second try. */
/* Return Value Meaning */
/* TRUE(1) success */
/* FALSE(0) failure */
LIB_EXPORT BOOL
BnGenerateRandomInRange(
bigNum dest,
bigConst limit,
RAND_STATE *rand
)
{
size_t bits = BnSizeInBits(limit);
//
if(bits < 2)
{
BnSetWord(dest, 0);
return FALSE;
}
else
{
while(BnGetRandomBits(dest, bits, rand)
&& (BnEqualZero(dest) || (BnUnsignedCmp(dest, limit) >= 0)));
}
return !g_inFailureMode;
}
// libtpms added begin
// This version of BnSizeInBits skips any leading zero bytes in bigConst
// and thus calculates the bits that OpenSSL will work with after truncating
// the leading zeros
static LIB_EXPORT unsigned
BnSizeInBitsSkipLeadingZeros(
bigConst n
)
{
int firstByte;
unsigned bitSize = BnSizeInBits(n);
crypt_uword_t i;
if (bitSize <= 8)
return bitSize;
// search for the first limb that is non-zero
for (i = 0; i < n->size; i++) {
if (n->d[i] != 0)
break;
}
if (i >= n->size)
return 0; // should never happen
// get the first byte in this limb that is non-zero
firstByte = (RADIX_BITS - 1 - Msb(n->d[i])) >> 3;
return bitSize - i * sizeof(n->d[0]) - (firstByte << 3);
}
/* This is a version of BnGenerateRandomInRange that ensures that the upper most
byte is non-zero, so that the number will not be shortened and subsequent operations
will not have a timing-sidechannel
*/
LIB_EXPORT BOOL
BnGenerateRandomInRangeAllBytes(
bigNum dest,
bigConst limit,
RAND_STATE *rand
)
{
BOOL OK;
int repeats = 0;
int maxRepeats;
unsigned requestedBits;
unsigned requestedBytes;
unsigned numBytes;
if (rand)
return BnGenerateRandomInRange(dest, limit, rand);
// a 'limit' like 'BN_P638_n' has leading zeros and we only need 73 bytes not 80
requestedBits = BnSizeInBitsSkipLeadingZeros(limit);
requestedBytes = BITS_TO_BYTES(requestedBits);
maxRepeats = 8;
if (requestedBits & 7)
maxRepeats += (9 - (requestedBits & 7));
while (true) {
OK = BnGenerateRandomInRange(dest, limit, rand);
if (!OK)
break;
if (repeats < maxRepeats) {
numBytes = BITS_TO_BYTES(BnSizeInBitsSkipLeadingZeros(dest));
if (numBytes < requestedBytes) {
repeats++;
continue;
}
}
break;
}
return OK;
}
// libtpms added end
|