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 <string.h>
9
10 #include "OsslCryptoEngine.h"
11 //
12 //
13 // Externally Accessible Functions
14 //
15 // _math__Normalize2B()
16 //
17 // This function will normalize the value in a TPM2B. If there are leading bytes of zero, the first non-zero
18 // byte is shifted up.
19 //
20 // Return Value Meaning
21 //
22 // 0 no significant bytes, value is zero
23 // >0 number of significant bytes
24 //
25 LIB_EXPORT UINT16
_math__Normalize2B(TPM2B * b)26 _math__Normalize2B(
27 TPM2B *b // IN/OUT: number to normalize
28 )
29 {
30 UINT16 from;
31 UINT16 to;
32 UINT16 size = b->size;
33 for(from = 0; b->buffer[from] == 0 && from < size; from++);
34 b->size -= from;
35 for(to = 0; from < size; to++, from++ )
36 b->buffer[to] = b->buffer[from];
37 return b->size;
38 }
39 //
40 //
41 //
42 // _math__Denormalize2B()
43 //
44 // This function is used to adjust a TPM2B so that the number has the desired number of bytes. This is
45 // accomplished by adding bytes of zero at the start of the number.
46 //
47 // Return Value Meaning
48 //
49 // TRUE number de-normalized
50 // FALSE number already larger than the desired size
51 //
52 LIB_EXPORT BOOL
_math__Denormalize2B(TPM2B * in,UINT32 size)53 _math__Denormalize2B(
54 TPM2B *in, // IN:OUT TPM2B number to de-normalize
55 UINT32 size // IN: the desired size
56 )
57 {
58 UINT32 to;
59 UINT32 from;
60 // If the current size is greater than the requested size, see if this can be
61 // normalized to a value smaller than the requested size and then de-normalize
62 if(in->size > size)
63 {
64 _math__Normalize2B(in);
65 if(in->size > size)
66 return FALSE;
67 }
68 // If the size is already what is requested, leave
69 if(in->size == size)
70 return TRUE;
71 // move the bytes to the 'right'
72 for(from = in->size, to = size; from > 0;)
73 in->buffer[--to] = in->buffer[--from];
74 // 'to' will always be greater than 0 because we checked for equal above.
75 for(; to > 0;)
76 in->buffer[--to] = 0;
77 in->size = (UINT16)size;
78 return TRUE;
79 }
80 //
81 //
82 // _math__sub()
83 //
84 // This function to subtract one unsigned value from another c = a - b. c may be the same as a or b.
85 //
86 // Return Value Meaning
87 //
88 // 1 if (a > b) so no borrow
89 // 0 if (a = b) so no borrow and b == a
90 // -1 if (a < b) so there was a borrow
91 //
92 LIB_EXPORT int
_math__sub(const UINT32 aSize,const BYTE * a,const UINT32 bSize,const BYTE * b,UINT16 * cSize,BYTE * c)93 _math__sub(
94 const UINT32 aSize, // IN: size of a
95 const BYTE *a, // IN: a
96 const UINT32 bSize, // IN: size of b
97 const BYTE *b, // IN: b
98 UINT16 *cSize, // OUT: set to MAX(aSize, bSize)
99 BYTE *c // OUT: the difference
100 )
101 {
102 int borrow = 0;
103 int notZero = 0;
104 int i;
105 int i2;
106 // set c to the longer of a or b
107 *cSize = (UINT16)((aSize > bSize) ? aSize : bSize);
108 // pick the shorter of a and b
109 i = (aSize > bSize) ? bSize : aSize;
110 i2 = *cSize - i;
111 a = &a[aSize - 1];
112 b = &b[bSize - 1];
113 c = &c[*cSize - 1];
114 for(; i > 0; i--)
115 {
116 borrow = *a-- - *b-- + borrow;
117 *c-- = (BYTE)borrow;
118 notZero = notZero || borrow;
119 borrow >>= 8;
120 }
121 if(aSize > bSize)
122 {
123 for(;i2 > 0; i2--)
124 {
125 borrow = *a-- + borrow;
126 *c-- = (BYTE)borrow;
127 notZero = notZero || borrow;
128 borrow >>= 8;
129 }
130 }
131 else if(aSize < bSize)
132 {
133 for(;i2 > 0; i2--)
134 {
135 borrow = 0 - *b-- + borrow;
136 *c-- = (BYTE)borrow;
137 notZero = notZero || borrow;
138 borrow >>= 8;
139 }
140 }
141 // if there is a borrow, then b > a
142 if(borrow)
143 return -1;
144 // either a > b or they are the same
145 return notZero;
146 }
147 //
148 //
149 // _math__Inc()
150 //
151 // This function increments a large, big-endian number value by one.
152 //
153 // Return Value Meaning
154 //
155 // 0 result is zero
156 // !0 result is not zero
157 //
158 LIB_EXPORT int
_math__Inc(UINT32 aSize,BYTE * a)159 _math__Inc(
160 UINT32 aSize, // IN: size of a
161 BYTE *a // IN: a
162 )
163 {
164 //
165 for(a = &a[aSize-1];aSize > 0; aSize--)
166 {
167 if((*a-- += 1) != 0)
168 return 1;
169 }
170 return 0;
171 }
172 //
173 //
174 // _math__Dec()
175 //
176 // This function decrements a large, ENDIAN value by one.
177 //
178 LIB_EXPORT void
_math__Dec(UINT32 aSize,BYTE * a)179 _math__Dec(
180 UINT32 aSize, // IN: size of a
181 BYTE *a // IN: a
182 )
183 {
184 for(a = &a[aSize-1]; aSize > 0; aSize--)
185 {
186 if((*a-- -= 1) != 0xff)
187 return;
188 }
189 return;
190 }
191 //
192 //
193 // _math__Mul()
194 //
195 // This function is used to multiply two large integers: p = a* b. If the size of p is not specified (pSize ==
196 // NULL), the size of the results p is assumed to be aSize + bSize and the results are de-normalized so that
197 // the resulting size is exactly aSize + bSize. If pSize is provided, then the actual size of the result is
198 // returned. The initial value for pSize must be at least aSize + pSize.
199 //
200 // Return Value Meaning
201 //
202 // <0 indicates an error
203 // >= 0 the size of the product
204 //
205 LIB_EXPORT int
_math__Mul(const UINT32 aSize,const BYTE * a,const UINT32 bSize,const BYTE * b,UINT32 * pSize,BYTE * p)206 _math__Mul(
207 const UINT32 aSize, // IN: size of a
208 const BYTE *a, // IN: a
209 const UINT32 bSize, // IN: size of b
210 const BYTE *b, // IN: b
211 UINT32 *pSize, // IN/OUT: size of the product
212 BYTE *p // OUT: product. length of product = aSize +
213 // bSize
214 )
215 {
216 BIGNUM *bnA;
217 BIGNUM *bnB;
218 BIGNUM *bnP;
219 BN_CTX *context;
220 int retVal = 0;
221 // First check that pSize is large enough if present
222 if((pSize != NULL) && (*pSize < (aSize + bSize)))
223 return CRYPT_PARAMETER;
224 pAssert(pSize == NULL || *pSize <= MAX_2B_BYTES);
225 //
226 //
227 // Allocate space for BIGNUM context
228 //
229 context = BN_CTX_new();
230 if(context == NULL)
231 FAIL(FATAL_ERROR_ALLOCATION);
232 bnA = BN_CTX_get(context);
233 bnB = BN_CTX_get(context);
234 bnP = BN_CTX_get(context);
235 if (bnP == NULL)
236 FAIL(FATAL_ERROR_ALLOCATION);
237 // Convert the inputs to BIGNUMs
238 //
239 if (BN_bin2bn(a, aSize, bnA) == NULL || BN_bin2bn(b, bSize, bnB) == NULL)
240 FAIL(FATAL_ERROR_INTERNAL);
241 // Perform the multiplication
242 //
243 if (BN_mul(bnP, bnA, bnB, context) != 1)
244 FAIL(FATAL_ERROR_INTERNAL);
245 // If the size of the results is allowed to float, then set the return
246 // size. Otherwise, it might be necessary to de-normalize the results
247 retVal = BN_num_bytes(bnP);
248 if(pSize == NULL)
249 {
250 BN_bn2bin(bnP, &p[aSize + bSize - retVal]);
251 memset(p, 0, aSize + bSize - retVal);
252 retVal = aSize + bSize;
253 }
254 else
255 {
256 BN_bn2bin(bnP, p);
257 *pSize = retVal;
258 }
259 BN_CTX_end(context);
260 BN_CTX_free(context);
261 return retVal;
262 }
263 //
264 //
265 // _math__Div()
266 //
267 // Divide an integer (n) by an integer (d) producing a quotient (q) and a remainder (r). If q or r is not needed,
268 // then the pointer to them may be set to NULL.
269 //
270 // Return Value Meaning
271 //
272 // CRYPT_SUCCESS operation complete
273 // CRYPT_UNDERFLOW q or r is too small to receive the result
274 //
275 LIB_EXPORT CRYPT_RESULT
_math__Div(const TPM2B * n,const TPM2B * d,TPM2B * q,TPM2B * r)276 _math__Div(
277 const TPM2B *n, // IN: numerator
278 const TPM2B *d, // IN: denominator
279 TPM2B *q, // OUT: quotient
280 TPM2B *r // OUT: remainder
281 )
282 {
283 BIGNUM *bnN;
284 BIGNUM *bnD;
285 BIGNUM *bnQ;
286 BIGNUM *bnR;
287 BN_CTX *context;
288 CRYPT_RESULT retVal = CRYPT_SUCCESS;
289 // Get structures for the big number representations
290 context = BN_CTX_new();
291 if(context == NULL)
292 FAIL(FATAL_ERROR_ALLOCATION);
293 BN_CTX_start(context);
294 bnN = BN_CTX_get(context);
295 bnD = BN_CTX_get(context);
296 bnQ = BN_CTX_get(context);
297 bnR = BN_CTX_get(context);
298 // Errors in BN_CTX_get() are sticky so only need to check the last allocation
299 if ( bnR == NULL
300 || BN_bin2bn(n->buffer, n->size, bnN) == NULL
301 || BN_bin2bn(d->buffer, d->size, bnD) == NULL)
302 FAIL(FATAL_ERROR_INTERNAL);
303 // Check for divide by zero.
304 if(BN_num_bits(bnD) == 0)
305 FAIL(FATAL_ERROR_DIVIDE_ZERO);
306 // Perform the division
307 if (BN_div(bnQ, bnR, bnN, bnD, context) != 1)
308 FAIL(FATAL_ERROR_INTERNAL);
309 // Convert the BIGNUM result back to our format
310 if(q != NULL) // If the quotient is being returned
311 {
312 if(!BnTo2B(q, bnQ, q->size))
313 {
314 retVal = CRYPT_UNDERFLOW;
315 goto Done;
316 }
317 }
318 if(r != NULL) // If the remainder is being returned
319 {
320 if(!BnTo2B(r, bnR, r->size))
321 retVal = CRYPT_UNDERFLOW;
322 }
323 Done:
324 BN_CTX_end(context);
325 BN_CTX_free(context);
326 return retVal;
327 }
328 //
329 //
330 // _math__uComp()
331 //
332 // This function compare two unsigned values.
333 //
334 // Return Value Meaning
335 //
336 // 1 if (a > b)
337 // 0 if (a = b)
338 // -1 if (a < b)
339 //
340 LIB_EXPORT int
_math__uComp(const UINT32 aSize,const BYTE * a,const UINT32 bSize,const BYTE * b)341 _math__uComp(
342 const UINT32 aSize, // IN: size of a
343 const BYTE *a, // IN: a
344 const UINT32 bSize, // IN: size of b
345 const BYTE *b // IN: b
346 )
347 {
348 int borrow = 0;
349 int notZero = 0;
350 int i;
351 // If a has more digits than b, then a is greater than b if
352 // any of the more significant bytes is non zero
353 if((i = (int)aSize - (int)bSize) > 0)
354 for(; i > 0; i--)
355 if(*a++) // means a > b
356 return 1;
357 // If b has more digits than a, then b is greater if any of the
358 // more significant bytes is non zero
359 if(i < 0) // Means that b is longer than a
360 for(; i < 0; i++)
361 if(*b++) // means that b > a
362 return -1;
363 // Either the vales are the same size or the upper bytes of a or b are
364 // all zero, so compare the rest
365 i = (aSize > bSize) ? bSize : aSize;
366 a = &a[i-1];
367 b = &b[i-1];
368 for(; i > 0; i--)
369 {
370 borrow = *a-- - *b-- + borrow;
371 notZero = notZero || borrow;
372 borrow >>= 8;
373 }
374 // if there is a borrow, then b > a
375 if(borrow)
376 return -1;
377 // either a > b or they are the same
378 return notZero;
379 }
380 //
381 //
382 // _math__Comp()
383 //
384 // Compare two signed integers:
385 //
386 // Return Value Meaning
387 //
388 // 1 if a > b
389 // 0 if a = b
390 // -1 if a < b
391 //
392 LIB_EXPORT int
_math__Comp(const UINT32 aSize,const BYTE * a,const UINT32 bSize,const BYTE * b)393 _math__Comp(
394 const UINT32 aSize, // IN: size of a
395 const BYTE *a, // IN: a buffer
396 const UINT32 bSize, // IN: size of b
397 const BYTE *b // IN: b buffer
398 )
399 {
400 int signA, signB; // sign of a and b
401 // For positive or 0, sign_a is 1
402 // for negative, sign_a is 0
403 signA = ((a[0] & 0x80) == 0) ? 1 : 0;
404 // For positive or 0, sign_b is 1
405 // for negative, sign_b is 0
406 signB = ((b[0] & 0x80) == 0) ? 1 : 0;
407 if(signA != signB)
408 {
409 return signA - signB;
410 }
411 if(signA == 1)
412 // do unsigned compare function
413 return _math__uComp(aSize, a, bSize, b);
414 else
415 // do unsigned compare the other way
416 return 0 - _math__uComp(aSize, a, bSize, b);
417 }
418 //
419 //
420 // _math__ModExp
421 //
422 // This function is used to do modular exponentiation in support of RSA. The most typical uses are: c = m^e
423 // mod n (RSA encrypt) and m = c^d mod n (RSA decrypt). When doing decryption, the e parameter of the
424 // function will contain the private exponent d instead of the public exponent e.
425 // If the results will not fit in the provided buffer, an error is returned (CRYPT_ERROR_UNDERFLOW). If
426 // the results is smaller than the buffer, the results is de-normalized.
427 // This version is intended for use with RSA and requires that m be less than n.
428 //
429 // Return Value Meaning
430 //
431 // CRYPT_SUCCESS exponentiation succeeded
432 // CRYPT_PARAMETER number to exponentiate is larger than the modulus
433 // CRYPT_UNDERFLOW result will not fit into the provided buffer
434 //
435 LIB_EXPORT CRYPT_RESULT
_math__ModExp(UINT32 cSize,BYTE * c,const UINT32 mSize,const BYTE * m,const UINT32 eSize,const BYTE * e,const UINT32 nSize,const BYTE * n)436 _math__ModExp(
437 UINT32 cSize, // IN: size of the result
438 BYTE *c, // OUT: results buffer
439 const UINT32 mSize, // IN: size of number to be exponentiated
440 const BYTE *m, // IN: number to be exponentiated
441 const UINT32 eSize, // IN: size of power
442 const BYTE *e, // IN: power
443 const UINT32 nSize, // IN: modulus size
444 const BYTE *n // IN: modulu
445 )
446 {
447 CRYPT_RESULT retVal = CRYPT_SUCCESS;
448 BN_CTX *context;
449 BIGNUM *bnC;
450 BIGNUM *bnM;
451 BIGNUM *bnE;
452 BIGNUM *bnN;
453 INT32 i;
454 context = BN_CTX_new();
455 if(context == NULL)
456 FAIL(FATAL_ERROR_ALLOCATION);
457 BN_CTX_start(context);
458 bnC = BN_CTX_get(context);
459 bnM = BN_CTX_get(context);
460 bnE = BN_CTX_get(context);
461 bnN = BN_CTX_get(context);
462 // Errors for BN_CTX_get are sticky so only need to check last allocation
463 if(bnN == NULL)
464 FAIL(FATAL_ERROR_ALLOCATION);
465 //convert arguments
466 if ( BN_bin2bn(m, mSize, bnM) == NULL
467 || BN_bin2bn(e, eSize, bnE) == NULL
468 || BN_bin2bn(n, nSize, bnN) == NULL)
469 FAIL(FATAL_ERROR_INTERNAL);
470 // Don't do exponentiation if the number being exponentiated is
471 // larger than the modulus.
472 if(BN_ucmp(bnM, bnN) >= 0)
473 {
474 retVal = CRYPT_PARAMETER;
475 goto Cleanup;
476 }
477 // Perform the exponentiation
478 if(!(BN_mod_exp(bnC, bnM, bnE, bnN, context)))
479 FAIL(FATAL_ERROR_INTERNAL);
480 // Convert the results
481 // Make sure that the results will fit in the provided buffer.
482 if((unsigned)BN_num_bytes(bnC) > cSize)
483 {
484 retVal = CRYPT_UNDERFLOW;
485 goto Cleanup;
486 }
487 i = cSize - BN_num_bytes(bnC);
488 BN_bn2bin(bnC, &c[i]);
489 memset(c, 0, i);
490 Cleanup:
491 // Free up allocated BN values
492 BN_CTX_end(context);
493 BN_CTX_free(context);
494 return retVal;
495 }
496 //
497 //
498 // _math__IsPrime()
499 //
500 // Check if an 32-bit integer is a prime.
501 //
502 // Return Value Meaning
503 //
504 // TRUE if the integer is probably a prime
505 // FALSE if the integer is definitely not a prime
506 //
507 LIB_EXPORT BOOL
_math__IsPrime(const UINT32 prime)508 _math__IsPrime(
509 const UINT32 prime
510 )
511 {
512 int isPrime;
513 BIGNUM *p;
514 // Assume the size variables are not overflow, which should not happen in
515 // the contexts that this function will be called.
516 if((p = BN_new()) == NULL)
517 FAIL(FATAL_ERROR_ALLOCATION);
518 if(!BN_set_word(p, prime))
519 FAIL(FATAL_ERROR_INTERNAL);
520 //
521 // BN_is_prime returning -1 means that it ran into an error.
522 //
523 // It should only return 0 or 1
524 //
525 if((isPrime = BN_is_prime_ex(p, BN_prime_checks, NULL, NULL)) < 0)
526 FAIL(FATAL_ERROR_INTERNAL);
527 if(p != NULL)
528 BN_clear_free(p);
529 return (isPrime == 1);
530 }
531