1 /**************************************************************************/
2 /* */
3 /* Copyright (c) Microsoft Corporation. All rights reserved. */
4 /* */
5 /* This software is licensed under the Microsoft Software License */
6 /* Terms for Microsoft Azure RTOS. Full text of the license can be */
7 /* found in the LICENSE file at https://aka.ms/AzureRTOS_EULA */
8 /* and in the root directory of this software. */
9 /* */
10 /**************************************************************************/
11
12
13 /**************************************************************************/
14 /**************************************************************************/
15 /** */
16 /** NetX Crypto Component */
17 /** */
18 /** Huge Number */
19 /** */
20 /**************************************************************************/
21 /**************************************************************************/
22
23 #define NX_CRYPTO_SOURCE_CODE
24
25
26 /* Include necessary system files. */
27 #include "stdio.h"
28 #include "nx_crypto.h"
29 #include "nx_crypto_huge_number.h"
30
31 /**************************************************************************/
32 /* */
33 /* FUNCTION RELEASE */
34 /* */
35 /* _nx_crypto_huge_number_is_zero PORTABLE C */
36 /* 6.1 */
37 /* AUTHOR */
38 /* */
39 /* Timothy Stapko, Microsoft Corporation */
40 /* */
41 /* DESCRIPTION */
42 /* */
43 /* This function returns whether number x is zero or not. */
44 /* */
45 /* INPUT */
46 /* */
47 /* x Huge number x */
48 /* */
49 /* OUTPUT */
50 /* */
51 /* Status NX_CRYPTO_TRUE: x is zero */
52 /* NX_CRYPTO_FALSE: x is nonzero */
53 /* */
54 /* CALLS */
55 /* */
56 /* None */
57 /* */
58 /* CALLED BY */
59 /* */
60 /* _nx_crypto_ec_point_is_infinite Check if the point is infinite*/
61 /* _nx_crypto_ec_secp192r1_reduce Reduce the value of curve */
62 /* secp192r1 */
63 /* _nx_crypto_ec_secp224r1_reduce Reduce the value of curve */
64 /* secp224r1 */
65 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
66 /* secp256r1 */
67 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
68 /* secp384r1 */
69 /* _nx_crypto_ec_secp521r1_reduce Reduce the value of curve */
70 /* secp521r1 */
71 /* _nx_crypto_huge_number_inverse_modulus */
72 /* Perform an inverse modulus */
73 /* operation */
74 /* _nx_crypto_huge_number_inverse_modulus_prime */
75 /* Perform an inverse modulus */
76 /* operation for prime number */
77 /* */
78 /* RELEASE HISTORY */
79 /* */
80 /* DATE NAME DESCRIPTION */
81 /* */
82 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
83 /* 09-30-2020 Timothy Stapko Modified comment(s), */
84 /* resulting in version 6.1 */
85 /* */
86 /**************************************************************************/
_nx_crypto_huge_number_is_zero(NX_CRYPTO_HUGE_NUMBER * x)87 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_is_zero(NX_CRYPTO_HUGE_NUMBER *x)
88 {
89 UINT i;
90
91 for (i = 0; i < x -> nx_crypto_huge_number_size; i++)
92 {
93 if (x -> nx_crypto_huge_number_data[i])
94 {
95
96 /* Found one value that is not zero. */
97 return(NX_CRYPTO_FALSE);
98 }
99 }
100
101 /* All values are zero. */
102 return(NX_CRYPTO_TRUE);
103 }
104
105 /**************************************************************************/
106 /* */
107 /* FUNCTION RELEASE */
108 /* */
109 /* _nx_crypto_huge_number_add PORTABLE C */
110 /* 6.1 */
111 /* AUTHOR */
112 /* */
113 /* Timothy Stapko, Microsoft Corporation */
114 /* */
115 /* DESCRIPTION */
116 /* */
117 /* This function calculates addition for huge numbers. */
118 /* */
119 /* Note: Result is stored in left. */
120 /* */
121 /* INPUT */
122 /* */
123 /* left Huge number left */
124 /* right Huge number right */
125 /* */
126 /* OUTPUT */
127 /* */
128 /* None */
129 /* */
130 /* CALLS */
131 /* */
132 /* _nx_crypto_huge_number_add_unsigned Calculate addition for */
133 /* unsigned huge numbers */
134 /* _nx_crypto_huge_number_subtract_unsigned */
135 /* Calculate subtraction for */
136 /* unsigned huge numbers */
137 /* _nx_crypto_huge_number_compare_unsigned */
138 /* Compare two unsigned */
139 /* huge numbers */
140 /* */
141 /* CALLED BY */
142 /* */
143 /* _nx_crypto_ec_secp192r1_reduce Reduce the value of curve */
144 /* secp192r1 */
145 /* _nx_crypto_ec_secp224r1_reduce Reduce the value of curve */
146 /* secp224r1 */
147 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
148 /* secp256r1 */
149 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
150 /* secp384r1 */
151 /* _nx_crypto_ec_secp521r1_reduce Reduce the value of curve */
152 /* secp521r1 */
153 /* _nx_crypto_huge_number_modulus Perform a modulus operation */
154 /* _nx_crypto_huge_number_inverse_modulus */
155 /* Perform an inverse modulus */
156 /* operation */
157 /* _nx_crypto_huge_number_inverse_modulus_prime */
158 /* Perform an inverse modulus */
159 /* operation for prime number */
160 /* _nx_crypto_huge_number_crt_power_modulus */
161 /* Raise a huge number for CRT */
162 /* */
163 /* RELEASE HISTORY */
164 /* */
165 /* DATE NAME DESCRIPTION */
166 /* */
167 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
168 /* 09-30-2020 Timothy Stapko Modified comment(s), */
169 /* resulting in version 6.1 */
170 /* */
171 /**************************************************************************/
_nx_crypto_huge_number_add(NX_CRYPTO_HUGE_NUMBER * left,NX_CRYPTO_HUGE_NUMBER * right)172 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_add(NX_CRYPTO_HUGE_NUMBER *left, NX_CRYPTO_HUGE_NUMBER *right)
173 {
174 UINT cmp;
175
176 cmp = _nx_crypto_huge_number_compare_unsigned(left, right);
177
178 if (left -> nx_crypto_huge_number_is_negative == right -> nx_crypto_huge_number_is_negative)
179 {
180 _nx_crypto_huge_number_add_unsigned(left, right);
181 }
182 else
183 {
184
185 if (cmp == NX_CRYPTO_HUGE_NUMBER_EQUAL)
186 {
187 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(left, 0);
188 }
189 else if (cmp == NX_CRYPTO_HUGE_NUMBER_LESS)
190 {
191 _nx_crypto_huge_number_subtract_unsigned(right, left, left);
192 left -> nx_crypto_huge_number_is_negative = right -> nx_crypto_huge_number_is_negative;
193 }
194 else
195 {
196 _nx_crypto_huge_number_subtract_unsigned(left, right, left);
197 }
198 }
199 }
200
201 /**************************************************************************/
202 /* */
203 /* FUNCTION RELEASE */
204 /* */
205 /* _nx_crypto_huge_number_subtract PORTABLE C */
206 /* 6.1.10 */
207 /* AUTHOR */
208 /* */
209 /* Timothy Stapko, Microsoft Corporation */
210 /* */
211 /* DESCRIPTION */
212 /* */
213 /* This function calculates subtraction for huge numbers. */
214 /* */
215 /* Note: Result is stored in left. */
216 /* */
217 /* INPUT */
218 /* */
219 /* left Huge number left */
220 /* right Huge number right */
221 /* */
222 /* OUTPUT */
223 /* */
224 /* None */
225 /* */
226 /* CALLS */
227 /* */
228 /* _nx_crypto_huge_number_add_unsigned Calculate addition for */
229 /* unsigned huge numbers */
230 /* _nx_crypto_huge_number_subtract_unsigned */
231 /* Calculate subtraction for */
232 /* unsigned huge numbers */
233 /* _nx_crypto_huge_number_compare_unsigned */
234 /* Compare two unsigned */
235 /* huge numbers */
236 /* */
237 /* CALLED BY */
238 /* */
239 /* Perform Schnorr ZKP generation*/
240 /* _nx_crypto_ec_secp224r1_reduce Reduce the value of curve */
241 /* secp224r1 */
242 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
243 /* secp256r1 */
244 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
245 /* secp384r1 */
246 /* _nx_crypto_ecjpake_schnorr_zkp_generate */
247 /* _nx_crypto_huge_number_inverse_modulus */
248 /* Perform an inverse modulus */
249 /* operation */
250 /* _nx_crypto_huge_number_inverse_modulus_prime */
251 /* Perform an inverse modulus */
252 /* operation for prime number */
253 /* _nx_crypto_huge_number_mont Perform Montgomery reduction */
254 /* for multiplication */
255 /* _nx_crypto_huge_number_crt_power_modulus */
256 /* Raise a huge number for CRT */
257 /* */
258 /* RELEASE HISTORY */
259 /* */
260 /* DATE NAME DESCRIPTION */
261 /* */
262 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
263 /* 09-30-2020 Timothy Stapko Modified comment(s), */
264 /* resulting in version 6.1 */
265 /* 01-31-2022 Timothy Stapko Modified comment(s), and */
266 /* improved performance, */
267 /* resulting in version 6.1.10 */
268 /* */
269 /**************************************************************************/
_nx_crypto_huge_number_subtract(NX_CRYPTO_HUGE_NUMBER * left,NX_CRYPTO_HUGE_NUMBER * right)270 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_subtract(NX_CRYPTO_HUGE_NUMBER *left, NX_CRYPTO_HUGE_NUMBER *right)
271 {
272 UINT cmp;
273
274 cmp = _nx_crypto_huge_number_compare_unsigned(left, right);
275
276 if (left -> nx_crypto_huge_number_is_negative != right -> nx_crypto_huge_number_is_negative)
277 {
278 _nx_crypto_huge_number_add_unsigned(left, right);
279 }
280 else
281 {
282
283 if (cmp == NX_CRYPTO_HUGE_NUMBER_EQUAL)
284 {
285 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(left, 0);
286 }
287 else if (cmp == NX_CRYPTO_HUGE_NUMBER_LESS)
288 {
289 _nx_crypto_huge_number_subtract_unsigned(right, left, left);
290 left -> nx_crypto_huge_number_is_negative = !(right -> nx_crypto_huge_number_is_negative);
291 }
292 else
293 {
294 _nx_crypto_huge_number_subtract_unsigned(left, right, left);
295 }
296 }
297 }
298
299 /**************************************************************************/
300 /* */
301 /* FUNCTION RELEASE */
302 /* */
303 /* _nx_crypto_huge_number_add_unsigned PORTABLE C */
304 /* 6.1 */
305 /* AUTHOR */
306 /* */
307 /* Timothy Stapko, Microsoft Corporation */
308 /* */
309 /* DESCRIPTION */
310 /* */
311 /* This function calculates addition for unsigned huge numbers. */
312 /* */
313 /* Note: Result is stored in left. */
314 /* */
315 /* INPUT */
316 /* */
317 /* left Huge number left */
318 /* right Huge number right */
319 /* */
320 /* OUTPUT */
321 /* */
322 /* None */
323 /* */
324 /* CALLS */
325 /* */
326 /* None */
327 /* */
328 /* CALLED BY */
329 /* */
330 /* _nx_crypto_ec_add_reduce Perform addition between */
331 /* two huge numbers */
332 /* _nx_crypto_ec_subtract_digit_reduce Perform subtraction between */
333 /* huge number and digit number*/
334 /* _nx_crypto_ec_subtract_reduce Perform subtraction between */
335 /* two huge numbers */
336 /* _nx_crypto_huge_number_add Calculate addition for */
337 /* huge numbers */
338 /* _nx_crypto_huge_number_subtract Calculate subtraction for */
339 /* huge numbers */
340 /* */
341 /* RELEASE HISTORY */
342 /* */
343 /* DATE NAME DESCRIPTION */
344 /* */
345 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
346 /* 09-30-2020 Timothy Stapko Modified comment(s), */
347 /* resulting in version 6.1 */
348 /* */
349 /**************************************************************************/
_nx_crypto_huge_number_add_unsigned(NX_CRYPTO_HUGE_NUMBER * left,NX_CRYPTO_HUGE_NUMBER * right)350 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_add_unsigned(NX_CRYPTO_HUGE_NUMBER *left, NX_CRYPTO_HUGE_NUMBER *right)
351 {
352 UINT i;
353 HN_UBASE2 product;
354 HN_UBASE *left_buffer;
355 HN_UBASE *right_buffer;
356 HN_UBASE *result_buffer = left -> nx_crypto_huge_number_data;
357 UINT left_size;
358 UINT right_size;
359
360 product = 0;
361
362 /* Make sure the size of left is no less than the size of right. */
363 if (left -> nx_crypto_huge_number_size < right -> nx_crypto_huge_number_size)
364 {
365 left_buffer = right -> nx_crypto_huge_number_data;
366 right_buffer = left -> nx_crypto_huge_number_data;
367 left_size = right -> nx_crypto_huge_number_size;
368 right_size = left -> nx_crypto_huge_number_size;
369 }
370 else
371 {
372 left_buffer = left -> nx_crypto_huge_number_data;
373 right_buffer = right -> nx_crypto_huge_number_data;
374 left_size = left -> nx_crypto_huge_number_size;
375 right_size = right -> nx_crypto_huge_number_size;
376 }
377
378 /* Calculate the result for common length. */
379 for (i = 0; i < right_size; i++)
380 {
381 product = (product >> HN_SHIFT) + left_buffer[i] + right_buffer[i];
382 result_buffer[i] = product & HN_MASK;
383 }
384
385 /* Calculate the carry. */
386 for (; i < left_size; i++)
387 {
388 product = (product >> HN_SHIFT) + left_buffer[i];
389 result_buffer[i] = product & HN_MASK;
390 }
391
392 /* Save or drop the carry? */
393 if ((product >> HN_SHIFT) &&
394 ((i << HN_SIZE_SHIFT) < left -> nx_crypto_huge_buffer_size))
395 {
396
397 /* Save the carry. */
398 result_buffer[i] = 1;
399 left -> nx_crypto_huge_number_size = i + 1;
400 }
401 else
402 {
403 left -> nx_crypto_huge_number_size = i;
404 }
405 }
406
407 /**************************************************************************/
408 /* */
409 /* FUNCTION RELEASE */
410 /* */
411 /* _nx_crypto_huge_number_subtract_unsigned PORTABLE C */
412 /* 6.1 */
413 /* AUTHOR */
414 /* */
415 /* Timothy Stapko, Microsoft Corporation */
416 /* */
417 /* DESCRIPTION */
418 /* */
419 /* This function calculates subtraction for unsigned huge numbers. */
420 /* */
421 /* Note: Left must be no less than right. */
422 /* */
423 /* INPUT */
424 /* */
425 /* left Huge number left */
426 /* right Huge number right */
427 /* result Huge number result */
428 /* */
429 /* OUTPUT */
430 /* */
431 /* None */
432 /* */
433 /* CALLS */
434 /* */
435 /* _nx_crypto_huge_number_adjust_size Adjust the size of a huge */
436 /* number to remove leading */
437 /* zeroes */
438 /* */
439 /* CALLED BY */
440 /* */
441 /* _nx_crypto_huge_number_add Calculate addition for */
442 /* huge numbers */
443 /* _nx_crypto_huge_number_subtract Calculate subtraction for */
444 /* huge numbers */
445 /* */
446 /* RELEASE HISTORY */
447 /* */
448 /* DATE NAME DESCRIPTION */
449 /* */
450 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
451 /* 09-30-2020 Timothy Stapko Modified comment(s), */
452 /* resulting in version 6.1 */
453 /* */
454 /**************************************************************************/
_nx_crypto_huge_number_subtract_unsigned(NX_CRYPTO_HUGE_NUMBER * left,NX_CRYPTO_HUGE_NUMBER * right,NX_CRYPTO_HUGE_NUMBER * result)455 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_subtract_unsigned(NX_CRYPTO_HUGE_NUMBER *left,
456 NX_CRYPTO_HUGE_NUMBER *right,
457 NX_CRYPTO_HUGE_NUMBER *result)
458 {
459 UINT i;
460 HN_UBASE2 product;
461 HN_UBASE *left_buffer = left -> nx_crypto_huge_number_data;
462 HN_UBASE *right_buffer = right -> nx_crypto_huge_number_data;
463 HN_UBASE *result_buffer = result -> nx_crypto_huge_number_data;
464
465 /* Note, in following loops,
466 * borrow = 1 - (product >> HN_SHIFT) */
467 product = HN_RADIX;
468
469 /* Calculate the result for common length. */
470 for (i = 0; i < right -> nx_crypto_huge_number_size; i++)
471 {
472 product >>= HN_SHIFT;
473 product += (HN_UBASE2)((HN_RADIX - 1) + left_buffer[i] - right_buffer[i]);
474 result_buffer[i] = (product & HN_MASK);
475 }
476
477 /* Calculate the borrow. */
478 for (; i < left -> nx_crypto_huge_number_size; i++)
479 {
480 product >>= HN_SHIFT;
481 product += (HN_UBASE2)((HN_RADIX - 1) + left_buffer[i]);
482 result_buffer[i] = (product & HN_MASK);
483 }
484
485 result -> nx_crypto_huge_number_size = left -> nx_crypto_huge_number_size;
486 _nx_crypto_huge_number_adjust_size(result);
487 }
488
489 /**************************************************************************/
490 /* */
491 /* FUNCTION RELEASE */
492 /* */
493 /* _nx_crypto_huge_number_add_digit_unsigned PORTABLE C */
494 /* 6.1 */
495 /* AUTHOR */
496 /* */
497 /* Timothy Stapko, Microsoft Corporation */
498 /* */
499 /* DESCRIPTION */
500 /* */
501 /* This function calculates addition for unsigned huge number and */
502 /* digit. */
503 /* */
504 /* Note: Result is stored in value. */
505 /* */
506 /* INPUT */
507 /* */
508 /* value Huge number number */
509 /* digit Digit value */
510 /* */
511 /* OUTPUT */
512 /* */
513 /* None */
514 /* */
515 /* CALLS */
516 /* */
517 /* None */
518 /* */
519 /* CALLED BY */
520 /* */
521 /* _nx_crypto_huge_number_add_digit */
522 /* _nx_crypto_huge_number_subtract_digit */
523 /* */
524 /* RELEASE HISTORY */
525 /* */
526 /* DATE NAME DESCRIPTION */
527 /* */
528 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
529 /* 09-30-2020 Timothy Stapko Modified comment(s), */
530 /* resulting in version 6.1 */
531 /* */
532 /**************************************************************************/
_nx_crypto_huge_number_add_digit_unsigned(NX_CRYPTO_HUGE_NUMBER * value,HN_UBASE digit)533 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_add_digit_unsigned(NX_CRYPTO_HUGE_NUMBER *value, HN_UBASE digit)
534 {
535 UINT i;
536 HN_UBASE2 product;
537 HN_UBASE *buffer = value -> nx_crypto_huge_number_data;
538 UINT size = value -> nx_crypto_huge_number_size;
539
540 product = (HN_UBASE2)buffer[0] + digit;
541 buffer[0] = product & HN_MASK;
542
543 /* Process carry. */
544 for (i = 1; (i < size) && ((product >> HN_SHIFT) != 0); i++)
545 {
546 product = (HN_UBASE)buffer[i] + 1;
547 buffer[i] = product & HN_MASK;
548 }
549
550 /* Save or drop the carry? */
551 if ((product >> HN_SHIFT) && (i == size))
552 {
553 buffer[i] = 1;
554 value -> nx_crypto_huge_number_size = i + 1;
555 }
556 }
557
558 /**************************************************************************/
559 /* */
560 /* FUNCTION RELEASE */
561 /* */
562 /* _nx_crypto_huge_number_subtract_digit_unsigned PORTABLE C */
563 /* 6.1 */
564 /* AUTHOR */
565 /* */
566 /* Timothy Stapko, Microsoft Corporation */
567 /* */
568 /* DESCRIPTION */
569 /* */
570 /* This function calculates subtraction for unsigned huge number and */
571 /* digit. */
572 /* */
573 /* Note: Result is stored in value. Left must be no less than right. */
574 /* */
575 /* INPUT */
576 /* */
577 /* value Huge number number */
578 /* digit Digit value */
579 /* */
580 /* OUTPUT */
581 /* */
582 /* None */
583 /* */
584 /* CALLS */
585 /* */
586 /* _nx_crypto_huge_number_adjust_size Adjust the size of a huge */
587 /* number to remove leading */
588 /* zeroes */
589 /* */
590 /* CALLED BY */
591 /* */
592 /* _nx_crypto_ec_subtract_digit_reduce Perform subtraction between */
593 /* huge number and digit number*/
594 /* _nx_crypto_huge_number_add_digit Calculate addition for */
595 /* huge number and digit */
596 /* _nx_crypto_huge_number_subtract_digit Calculate subtraction for */
597 /* huge number and digit */
598 /* */
599 /* RELEASE HISTORY */
600 /* */
601 /* DATE NAME DESCRIPTION */
602 /* */
603 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
604 /* 09-30-2020 Timothy Stapko Modified comment(s), */
605 /* resulting in version 6.1 */
606 /* */
607 /**************************************************************************/
_nx_crypto_huge_number_subtract_digit_unsigned(NX_CRYPTO_HUGE_NUMBER * value,HN_UBASE digit)608 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_subtract_digit_unsigned(NX_CRYPTO_HUGE_NUMBER *value, HN_UBASE digit)
609 {
610 UINT i;
611 HN_UBASE2 product;
612 HN_UBASE *buffer = value -> nx_crypto_huge_number_data;
613 UINT size = value -> nx_crypto_huge_number_size;
614
615 product = (HN_UBASE2)(HN_RADIX + buffer[0] - digit);
616 buffer[0] = product & HN_MASK;
617
618 /* Process borrow. */
619 for (i = 1; (i < size) && ((product >> HN_SHIFT) == 0); i++)
620 {
621 product = (HN_UBASE2)(HN_RADIX + (HN_UBASE)buffer[i] - 1);
622 buffer[i] = product & HN_MASK;
623 }
624
625 _nx_crypto_huge_number_adjust_size(value);
626 }
627
628 /**************************************************************************/
629 /* */
630 /* FUNCTION RELEASE */
631 /* */
632 /* _nx_crypto_huge_number_left PORTABLE C */
633 /* 6.1 */
634 /* AUTHOR */
635 /* */
636 /* Timothy Stapko, Microsoft Corporation */
637 /* */
638 /* DESCRIPTION */
639 /* */
640 /* This function shifts left N bits. The shift must be less than */
641 /* the value of HN_SHIFT. */
642 /* */
643 /* INPUT */
644 /* */
645 /* x Huge number x */
646 /* */
647 /* OUTPUT */
648 /* */
649 /* None */
650 /* */
651 /* CALLS */
652 /* */
653 /* None */
654 /* */
655 /* CALLED BY */
656 /* */
657 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
658 /* secp256r1 */
659 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
660 /* secp384r1 */
661 /* */
662 /* RELEASE HISTORY */
663 /* */
664 /* DATE NAME DESCRIPTION */
665 /* */
666 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
667 /* 09-30-2020 Timothy Stapko Modified comment(s), */
668 /* resulting in version 6.1 */
669 /* */
670 /**************************************************************************/
_nx_crypto_huge_number_shift_left(NX_CRYPTO_HUGE_NUMBER * x,UINT shift)671 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_shift_left(NX_CRYPTO_HUGE_NUMBER *x, UINT shift)
672 {
673 UINT i;
674 HN_UBASE *x_buffer = x -> nx_crypto_huge_number_data;
675
676 /* Left shift. */
677 i = x -> nx_crypto_huge_number_size;
678 x_buffer[i] = x_buffer[i - 1] >> (HN_SHIFT - shift);
679 for (i--; i > 0; i--)
680 {
681 x_buffer[i] = (x_buffer[i - 1] >> (HN_SHIFT - shift)) | (x_buffer[i] << shift);
682 }
683 x_buffer[0] <<= shift;
684
685 if (x_buffer[x -> nx_crypto_huge_number_size] != 0)
686 {
687 x -> nx_crypto_huge_number_size++;
688 }
689 }
690
691 /**************************************************************************/
692 /* */
693 /* FUNCTION RELEASE */
694 /* */
695 /* _nx_crypto_huge_number_shift_right PORTABLE C */
696 /* 6.1 */
697 /* AUTHOR */
698 /* */
699 /* Timothy Stapko, Microsoft Corporation */
700 /* */
701 /* DESCRIPTION */
702 /* */
703 /* This function shifts right N bits. The shift must be less than */
704 /* the value of HN_SHIFT. */
705 /* */
706 /* INPUT */
707 /* */
708 /* x Huge number x */
709 /* shift Bits to shift right */
710 /* */
711 /* OUTPUT */
712 /* */
713 /* None */
714 /* */
715 /* CALLS */
716 /* */
717 /* _nx_crypto_huge_number_adjust_size Adjust the size of a huge */
718 /* number to remove leading */
719 /* zeroes */
720 /* */
721 /* CALLED BY */
722 /* */
723 /* _nx_crypto_huge_number_inverse_modulus */
724 /* Perform an inverse modulus */
725 /* operation */
726 /* _nx_crypto_huge_number_inverse_modulus_prime */
727 /* Perform an inverse modulus */
728 /* operation for prime number */
729 /* _nx_crypto_ec_secp521r1_reduce Reduce the value of curve */
730 /* secp521r1 */
731 /* */
732 /* RELEASE HISTORY */
733 /* */
734 /* DATE NAME DESCRIPTION */
735 /* */
736 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
737 /* 09-30-2020 Timothy Stapko Modified comment(s), */
738 /* resulting in version 6.1 */
739 /* */
740 /**************************************************************************/
_nx_crypto_huge_number_shift_right(NX_CRYPTO_HUGE_NUMBER * x,UINT shift)741 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_shift_right(NX_CRYPTO_HUGE_NUMBER *x, UINT shift)
742 {
743 UINT i;
744 HN_UBASE *x_buffer = x -> nx_crypto_huge_number_data;
745
746 /* Right shift. */
747 for (i = 0; i < x -> nx_crypto_huge_number_size - 1; i++)
748 {
749 x_buffer[i] = (x_buffer[i + 1] << (HN_SHIFT - shift)) | (x_buffer[i] >> shift);
750 }
751 x_buffer[i] >>= shift;
752
753 _nx_crypto_huge_number_adjust_size(x);
754 }
755
756 /**************************************************************************/
757 /* */
758 /* FUNCTION RELEASE */
759 /* */
760 /* _nx_crypto_huge_number_adjust_size PORTABLE C */
761 /* 6.1 */
762 /* AUTHOR */
763 /* */
764 /* Timothy Stapko, Microsoft Corporation */
765 /* */
766 /* DESCRIPTION */
767 /* */
768 /* This function adjusts the size of a huge number to include only */
769 /* those bytes which are actually significant to the value - */
770 /* essentially removing leading zero bytes. */
771 /* */
772 /* INPUT */
773 /* */
774 /* val Pointer to huge number */
775 /* */
776 /* OUTPUT */
777 /* */
778 /* None */
779 /* */
780 /* CALLS */
781 /* */
782 /* None */
783 /* */
784 /* CALLED BY */
785 /* */
786 /* _nx_crypto_huge_number_setup Setup huge number */
787 /* _nx_crypto_huge_number_subtract_unsigned */
788 /* Calculate subtraction for */
789 /* unsigned huge numbers */
790 /* _nx_crypto_huge_number_subtract_digit_unsigned */
791 /* Calculate subtraction for */
792 /* unsigned huge numbers */
793 /* _nx_crypto_huge_number_shift_right Shift right for huge number */
794 /* _nx_crypto_huge_number_multiply Multiply two huge numbers */
795 /* _nx_crypto_huge_number_square Compute the square of a value */
796 /* _nx_crypto_huge_number_mont Perform Montgomery reduction */
797 /* for multiplication */
798 /* _nx_crypto_huge_number_mont_power_modulus */
799 /* Raise a huge number for */
800 /* montgomery reduction */
801 /* RELEASE HISTORY */
802 /* */
803 /* DATE NAME DESCRIPTION */
804 /* */
805 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
806 /* 09-30-2020 Timothy Stapko Modified comment(s), */
807 /* resulting in version 6.1 */
808 /* */
809 /**************************************************************************/
_nx_crypto_huge_number_adjust_size(NX_CRYPTO_HUGE_NUMBER * val)810 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_adjust_size(NX_CRYPTO_HUGE_NUMBER *val)
811 {
812
813 INT size;
814
815 /* Start at the most significant "digit" and work backwards. */
816 for (size = (INT)(val -> nx_crypto_huge_number_size - 1); size >= 0; size--)
817 {
818 if (val -> nx_crypto_huge_number_data[size] != 0)
819 {
820
821 /* Size is now the index of the last non-zero byte,
822 so the size is one more than that. */
823 val -> nx_crypto_huge_number_size = (UINT)(size + 1);
824 return;
825 }
826 }
827
828 /* The result is zero. */
829 val -> nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
830 val -> nx_crypto_huge_number_size = 1;
831 }
832
833 /**************************************************************************/
834 /* */
835 /* FUNCTION RELEASE */
836 /* */
837 /* _nx_crypto_huge_number_compare PORTABLE C */
838 /* 6.1 */
839 /* AUTHOR */
840 /* */
841 /* Timothy Stapko, Microsoft Corporation */
842 /* */
843 /* DESCRIPTION */
844 /* */
845 /* This function compares two huge numbers and returns equal, less- */
846 /* than, or greater-than. */
847 /* */
848 /* INPUT */
849 /* */
850 /* left First operand */
851 /* right Second operand */
852 /* */
853 /* OUTPUT */
854 /* */
855 /* Result Equal, less-than, greater */
856 /* */
857 /* CALLS */
858 /* */
859 /* _nx_crypto_huge_number_compare_unsigned */
860 /* Compare two unsigned */
861 /* huge numbers */
862 /* */
863 /* CALLED BY */
864 /* */
865 /* _nx_crypto_ec_point_is_infinite Check if the point is infinite*/
866 /* _nx_crypto_ec_secp192r1_reduce Reduce the value of curve */
867 /* secp192r1 */
868 /* _nx_crypto_ec_secp224r1_reduce Reduce the value of curve */
869 /* secp224r1 */
870 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
871 /* secp256r1 */
872 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
873 /* secp384r1 */
874 /* _nx_crypto_ec_secp521r1_reduce Reduce the value of curve */
875 /* secp521r1 */
876 /* _nx_crypto_ecjpake_schnorr_zkp_generate */
877 /* Perform Schnorr ZKP generation*/
878 /* _nx_crypto_huge_number_inverse_modulus */
879 /* Perform an inverse modulus */
880 /* operation */
881 /* _nx_crypto_huge_number_inverse_modulus_prime */
882 /* Perform an inverse modulus */
883 /* operation for prime number */
884 /* _nx_crypto_huge_number_mont Perform Montgomery reduction */
885 /* for multiplication */
886 /* */
887 /* RELEASE HISTORY */
888 /* */
889 /* DATE NAME DESCRIPTION */
890 /* */
891 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
892 /* 09-30-2020 Timothy Stapko Modified comment(s), */
893 /* resulting in version 6.1 */
894 /* */
895 /**************************************************************************/
_nx_crypto_huge_number_compare(NX_CRYPTO_HUGE_NUMBER * left,NX_CRYPTO_HUGE_NUMBER * right)896 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_compare(NX_CRYPTO_HUGE_NUMBER *left, NX_CRYPTO_HUGE_NUMBER *right)
897 {
898 if (left -> nx_crypto_huge_number_is_negative != right -> nx_crypto_huge_number_is_negative)
899 {
900 if (left -> nx_crypto_huge_number_is_negative)
901 {
902 return(NX_CRYPTO_HUGE_NUMBER_LESS);
903 }
904 else
905 {
906 return(NX_CRYPTO_HUGE_NUMBER_GREATER);
907 }
908 }
909
910 if (left -> nx_crypto_huge_number_is_negative)
911 {
912 return(_nx_crypto_huge_number_compare_unsigned(right, left));
913 }
914 else
915 {
916 return(_nx_crypto_huge_number_compare_unsigned(left, right));
917 }
918 }
919
920
921 /**************************************************************************/
922 /* */
923 /* FUNCTION RELEASE */
924 /* */
925 /* _nx_crypto_huge_number_compare_unsigned PORTABLE C */
926 /* 6.1 */
927 /* AUTHOR */
928 /* */
929 /* Timothy Stapko, Microsoft Corporation */
930 /* */
931 /* DESCRIPTION */
932 /* */
933 /* This function compares two huge numbers and returns equal, less- */
934 /* than, or greater-than. Sign is ignored. Results are in relation to */
935 /* the first operand (e.g. left > right returns greater-than). The */
936 /* algorithm properly handles leading zeroes so operands with different*/
937 /* buffer sizes are handled properly. */
938 /* */
939 /* The shift component is a specialty optimization for the fast */
940 /* modulus routine (_nx_crypto_huge_number_modulus). */
941 /* */
942 /* INPUT */
943 /* */
944 /* left First operand */
945 /* right Second operand */
946 /* */
947 /* OUTPUT */
948 /* */
949 /* Result Equal, less-than, greater */
950 /* */
951 /* CALLS */
952 /* */
953 /* None */
954 /* */
955 /* CALLED BY */
956 /* */
957 /* _nx_crypto_ec_add_digit_reduce Perform addition between huge */
958 /* number and digit number */
959 /* _nx_crypto_ec_add_reduce Perform addition between */
960 /* two huge numbers */
961 /* _nx_crypto_ec_secp192r1_reduce Reduce the value of curve */
962 /* secp192r1 */
963 /* _nx_crypto_ec_secp224r1_reduce Reduce the value of curve */
964 /* secp224r1 */
965 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
966 /* secp256r1 */
967 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
968 /* secp384r1 */
969 /* _nx_crypto_ec_secp521r1_reduce Reduce the value of curve */
970 /* secp521r1 */
971 /* _nx_crypto_huge_number_add Calculate addition for */
972 /* huge numbers */
973 /* _nx_crypto_huge_number_subtract Calculate subtraction for */
974 /* huge numbers */
975 /* _nx_crypto_huge_number_compare Compare two huge numbers */
976 /* _nx_crypto_huge_number_modulus Perform a modulus operation */
977 /* */
978 /* RELEASE HISTORY */
979 /* */
980 /* DATE NAME DESCRIPTION */
981 /* */
982 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
983 /* 09-30-2020 Timothy Stapko Modified comment(s), */
984 /* resulting in version 6.1 */
985 /* */
986 /**************************************************************************/
_nx_crypto_huge_number_compare_unsigned(NX_CRYPTO_HUGE_NUMBER * left,NX_CRYPTO_HUGE_NUMBER * right)987 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_compare_unsigned(NX_CRYPTO_HUGE_NUMBER *left,
988 NX_CRYPTO_HUGE_NUMBER *right)
989 {
990
991 INT i;
992 UINT left_size;
993 UINT right_size;
994
995 left_size = left -> nx_crypto_huge_number_size;
996 right_size = right -> nx_crypto_huge_number_size;
997
998 /* Adjust the size for zero at the front. */
999 while (left_size && (left -> nx_crypto_huge_number_data[left_size - 1] == 0))
1000 {
1001 left_size--;
1002 }
1003 while (right_size && (right -> nx_crypto_huge_number_data[right_size - 1] == 0))
1004 {
1005 right_size--;
1006 }
1007
1008 if (left_size > right_size)
1009 {
1010 return(NX_CRYPTO_HUGE_NUMBER_GREATER);
1011 }
1012 if (right_size > left_size)
1013 {
1014 return(NX_CRYPTO_HUGE_NUMBER_LESS);
1015 }
1016
1017 /* Keep comparing bytes while they are equal and we have indexes left. */
1018 for (i = (INT)left_size - 1; i >= 0; i--)
1019 {
1020 if (left -> nx_crypto_huge_number_data[i] > right -> nx_crypto_huge_number_data[i])
1021 {
1022 return(NX_CRYPTO_HUGE_NUMBER_GREATER);
1023 }
1024 else if (right -> nx_crypto_huge_number_data[i] > left -> nx_crypto_huge_number_data[i])
1025 {
1026 return(NX_CRYPTO_HUGE_NUMBER_LESS);
1027 }
1028 }
1029
1030 /* If we reach here, the numbers are equal. */
1031 return(NX_CRYPTO_HUGE_NUMBER_EQUAL);
1032 }
1033
1034
1035 /**************************************************************************/
1036 /* */
1037 /* FUNCTION RELEASE */
1038 /* */
1039 /* _nx_crypto_huge_number_multiply PORTABLE C */
1040 /* 6.1 */
1041 /* AUTHOR */
1042 /* */
1043 /* Timothy Stapko, Microsoft Corporation */
1044 /* */
1045 /* DESCRIPTION */
1046 /* */
1047 /* This function multiplies two huge numbers and places the result */
1048 /* in the result buffer which must be large enough to hold the */
1049 /* resulting value. */
1050 /* */
1051 /* INPUT */
1052 /* */
1053 /* left First operand */
1054 /* right Second operand */
1055 /* result Result */
1056 /* */
1057 /* OUTPUT */
1058 /* */
1059 /* Status Operation result status */
1060 /* */
1061 /* CALLS */
1062 /* */
1063 /* _nx_crypto_huge_number_adjust_size Adjust the size of a huge */
1064 /* number to remove leading */
1065 /* zeroes */
1066 /* */
1067 /* CALLED BY */
1068 /* */
1069 /* _nx_crypto_ecjpake_public_key_generate */
1070 /* Perform public key generation */
1071 /* _nx_crypto_ecjpake_schnorr_zkp_generate */
1072 /* Perform Schnorr ZKP generation*/
1073 /* _nx_crypto_huge_number_power_modulus Raise a huge number */
1074 /* _nx_crypto_huge_number_crt_power_modulus */
1075 /* Raise a huge number for CRT */
1076 /* */
1077 /* RELEASE HISTORY */
1078 /* */
1079 /* DATE NAME DESCRIPTION */
1080 /* */
1081 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1082 /* 09-30-2020 Timothy Stapko Modified comment(s), */
1083 /* resulting in version 6.1 */
1084 /* */
1085 /**************************************************************************/
_nx_crypto_huge_number_multiply(NX_CRYPTO_HUGE_NUMBER * left,NX_CRYPTO_HUGE_NUMBER * right,NX_CRYPTO_HUGE_NUMBER * result)1086 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_multiply(NX_CRYPTO_HUGE_NUMBER *left,
1087 NX_CRYPTO_HUGE_NUMBER *right,
1088 NX_CRYPTO_HUGE_NUMBER *result)
1089 {
1090
1091 UINT index, right_index; /* Loop variables */
1092 HN_UBASE *left_buffer, *right_buffer;
1093 HN_UBASE2 product;
1094 UINT left_size, right_size;
1095 HN_UBASE *result_buffer;
1096 HN_UBASE *temp_ptr;
1097
1098 left_size = left -> nx_crypto_huge_number_size;
1099 right_size = right -> nx_crypto_huge_number_size;
1100 left_buffer = left -> nx_crypto_huge_number_data;
1101 right_buffer = right -> nx_crypto_huge_number_data;
1102
1103 /* The temp buffer serves as "buckets". During each itegration, the products of two digits are accumucated into
1104 this buckets. Since each "digit" is 16-bit, by using 32-bit buckets, the carry can be accumulated in to the
1105 top 16-bits of the bucket. Therefore, we don't need to worry about "carry" bit during each iteration. */
1106
1107 result_buffer = result -> nx_crypto_huge_number_data;
1108 result -> nx_crypto_huge_number_size = (left_size + right_size);
1109
1110 /* Zero out the buckets since we are going to accumulate "digits" there. */
1111 NX_CRYPTO_MEMSET(result_buffer, 0, (left_size + right_size) << HN_SIZE_SHIFT);
1112
1113 /* Loop over the operands, grabbing a "digit" at a time and calculating the product accounting for carry. */
1114 for (index = 0; index < left_size; ++index)
1115 {
1116
1117 /* If the "digit" on the left is zero, there is no need to loop through the "digits" on the right. */
1118 if (left_buffer[index] == 0)
1119 {
1120 /* Yes the digit ont he left is zero. Continue to the next iteration. */
1121 continue;
1122 }
1123
1124 product = 0;
1125 temp_ptr = result_buffer + index;
1126 for (right_index = 0; right_index < right_size; ++right_index, ++temp_ptr)
1127 {
1128 /* Multiple "digit" from the left with the one the left. */
1129 product >>= HN_SHIFT;
1130 product += (HN_UBASE2)left_buffer[index] * (HN_UBASE2)right_buffer[right_index] + *temp_ptr;
1131
1132 /* The result (in product) could be two parts: the top digit the the lower digit. */
1133 /* Accumulate the lower digit into the "bucket" and the top digit to the next "bucket". */
1134 *temp_ptr = (product & HN_MASK);
1135 }
1136 *temp_ptr = (HN_UBASE)((product >> HN_SHIFT));
1137 }
1138
1139 /* Set is_negative. */
1140 if (left -> nx_crypto_huge_number_is_negative == right -> nx_crypto_huge_number_is_negative)
1141 {
1142 result -> nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
1143 }
1144 else
1145 {
1146 result -> nx_crypto_huge_number_is_negative = NX_CRYPTO_TRUE;
1147 }
1148
1149 _nx_crypto_huge_number_adjust_size(result);
1150
1151 return;
1152 }
1153
1154 /**************************************************************************/
1155 /* */
1156 /* FUNCTION RELEASE */
1157 /* */
1158 /* _nx_crypto_huge_number_multiply_digit PORTABLE C */
1159 /* 6.1 */
1160 /* AUTHOR */
1161 /* */
1162 /* Timothy Stapko, Microsoft Corporation */
1163 /* */
1164 /* DESCRIPTION */
1165 /* */
1166 /* This function multiplies huge number with digit and replace the */
1167 /* result in the result buffer which must be large enough to hold the */
1168 /* resulting value. */
1169 /* */
1170 /* INPUT */
1171 /* */
1172 /* value Huge number number */
1173 /* digit Digit value */
1174 /* result Result */
1175 /* */
1176 /* OUTPUT */
1177 /* */
1178 /* Status Operation result status */
1179 /* */
1180 /* CALLS */
1181 /* */
1182 /* None */
1183 /* */
1184 /* CALLED BY */
1185 /* */
1186 /* Application Code */
1187 /* */
1188 /* RELEASE HISTORY */
1189 /* */
1190 /* DATE NAME DESCRIPTION */
1191 /* */
1192 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1193 /* 09-30-2020 Timothy Stapko Modified comment(s), */
1194 /* resulting in version 6.1 */
1195 /* */
1196 /**************************************************************************/
_nx_crypto_huge_number_multiply_digit(NX_CRYPTO_HUGE_NUMBER * value,HN_UBASE digit,NX_CRYPTO_HUGE_NUMBER * result)1197 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_multiply_digit(NX_CRYPTO_HUGE_NUMBER *value,
1198 HN_UBASE digit,
1199 NX_CRYPTO_HUGE_NUMBER *result)
1200 {
1201
1202 UINT i;
1203 UINT size;
1204 HN_UBASE2 product;
1205 HN_UBASE *value_buffer;
1206 HN_UBASE *result_buffer;
1207
1208 if (digit == 0)
1209 {
1210 result -> nx_crypto_huge_number_data[0] = 0;
1211 result -> nx_crypto_huge_number_size = 1;
1212 result -> nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
1213 return;
1214 }
1215
1216 size = value -> nx_crypto_huge_number_size;
1217 value_buffer = value -> nx_crypto_huge_number_data;
1218 result_buffer = result -> nx_crypto_huge_number_data;
1219
1220 /* Loop over the operands, grabbing a "digit" at a time and calculating the product accounting for carry. */
1221 product = 0;
1222 for (i = 0; i < size; i++)
1223 {
1224 product >>= HN_SHIFT;
1225 product += (HN_UBASE2)value_buffer[i] * digit;
1226 result_buffer[i] = (product & HN_MASK);
1227 }
1228 if ((product >> HN_SHIFT) != 0)
1229 {
1230 result -> nx_crypto_huge_number_size = value -> nx_crypto_huge_number_size + 1;
1231 result_buffer[i] = (HN_UBASE)(product >> HN_SHIFT);
1232 }
1233 else
1234 {
1235 result -> nx_crypto_huge_number_size = value -> nx_crypto_huge_number_size;
1236 }
1237 result -> nx_crypto_huge_number_is_negative = value -> nx_crypto_huge_number_is_negative;
1238
1239 return;
1240 }
1241
1242 /**************************************************************************/
1243 /* */
1244 /* FUNCTION RELEASE */
1245 /* */
1246 /* _nx_crypto_huge_number_square PORTABLE C */
1247 /* 6.1 */
1248 /* AUTHOR */
1249 /* */
1250 /* Timothy Stapko, Microsoft Corporation */
1251 /* */
1252 /* DESCRIPTION */
1253 /* */
1254 /* This function computes the square of a value, and places the */
1255 /* result in the result buffer. The value buffer must be large enough */
1256 /* to hold the computed result. */
1257 /* */
1258 /* INPUT */
1259 /* */
1260 /* value Value buffer */
1261 /* result Result buffer */
1262 /* */
1263 /* OUTPUT */
1264 /* */
1265 /* None */
1266 /* */
1267 /* CALLS */
1268 /* */
1269 /* _nx_crypto_huge_number_adjust_size Adjust the size of a huge */
1270 /* number to remove leading */
1271 /* zeroes */
1272 /* */
1273 /* CALLED BY */
1274 /* */
1275 /* _nx_crypto_huge_number_power_modulus Raise a huge number */
1276 /* _nx_crypto_huge_number_mont_power_modulus */
1277 /* Raise a huge number for */
1278 /* montgomery reduction */
1279 /* */
1280 /* RELEASE HISTORY */
1281 /* */
1282 /* DATE NAME DESCRIPTION */
1283 /* */
1284 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1285 /* 09-30-2020 Timothy Stapko Modified comment(s), */
1286 /* resulting in version 6.1 */
1287 /* */
1288 /**************************************************************************/
_nx_crypto_huge_number_square(NX_CRYPTO_HUGE_NUMBER * value,NX_CRYPTO_HUGE_NUMBER * result)1289 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_square(NX_CRYPTO_HUGE_NUMBER *value, NX_CRYPTO_HUGE_NUMBER *result)
1290 {
1291 HN_UBASE2 product;
1292 UINT value_size;
1293 UINT result_size;
1294 HN_UBASE *value_buffer;
1295 HN_UBASE *result_buffer;
1296 UINT i, j;
1297
1298 /* Using Yang et al.'s squaring algorithm. */
1299 value_size = value -> nx_crypto_huge_number_size;
1300 result_size = (value_size << 1);
1301 result -> nx_crypto_huge_number_size = result_size;
1302 value_buffer = value -> nx_crypto_huge_number_data;
1303 result_buffer = result -> nx_crypto_huge_number_data;
1304
1305 NX_CRYPTO_MEMSET(result_buffer, 0, result_size << HN_SIZE_SHIFT);
1306
1307 for (i = 0; i < value_size; i++)
1308 {
1309 product = 0;
1310 for (j = i + 1; j < value_size; j++)
1311 {
1312 product >>= HN_SHIFT;
1313 product += result_buffer[i + j] + (HN_UBASE2)value_buffer[i] * value_buffer[j];
1314 result_buffer[i + j] = product & HN_MASK;
1315 }
1316 result_buffer[i + j] = (HN_UBASE)(product >> HN_SHIFT);
1317 }
1318
1319 for (i = result_size - 1; i > 0; i--)
1320 {
1321 result_buffer[i] = (result_buffer[i] << 1) | (result_buffer[i - 1] >> (HN_SHIFT - 1));
1322 }
1323 result_buffer[0] <<= 1;
1324
1325 product = 0;
1326 for (i = 0; i < value_size; i++)
1327 {
1328 product >>= HN_SHIFT;
1329 product += result_buffer[i << 1] + (HN_UBASE2)value_buffer[i] * value_buffer[i];
1330 result_buffer[i << 1] = product & HN_MASK;
1331 product >>= HN_SHIFT;
1332 product += result_buffer[(i << 1) + 1];
1333 result_buffer[(i << 1) + 1] = product & HN_MASK;
1334 }
1335
1336 result -> nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
1337 _nx_crypto_huge_number_adjust_size(result);
1338 }
1339
1340 /**************************************************************************/
1341 /* */
1342 /* FUNCTION RELEASE */
1343 /* */
1344 /* _nx_crypto_huge_number_modulus PORTABLE C */
1345 /* 6.1.11 */
1346 /* AUTHOR */
1347 /* */
1348 /* Timothy Stapko, Microsoft Corporation */
1349 /* */
1350 /* DESCRIPTION */
1351 /* */
1352 /* This function performs a modulus operation on the dividend and */
1353 /* divisor operands and places the remainder in the dividend buffer. */
1354 /* */
1355 /* The algorithm uses a digit-based division, with a 16-bit short */
1356 /* as a "digit". */
1357 /* */
1358 /* NORE: The dividend operand is destroyed during the operation. */
1359 /* The divisor is preserved. No additional scratch buffer */
1360 /* required during this operation. */
1361 /* */
1362 /* */
1363 /* INPUT */
1364 /* */
1365 /* dividend First operand */
1366 /* divisor Second operand */
1367 /* */
1368 /* OUTPUT */
1369 /* */
1370 /* None */
1371 /* */
1372 /* CALLS */
1373 /* */
1374 /* _nx_crypto_huge_number_compare_unsigned */
1375 /* Compare two unsigned */
1376 /* huge numbers */
1377 /* _nx_crypto_huge_number_add Calculate addition for */
1378 /* huge numbers */
1379 /* */
1380 /* CALLED BY */
1381 /* */
1382 /* _nx_crypto_ec_fp_reduce Reduce huge number for */
1383 /* common prime field */
1384 /* _nx_crypto_ecjpake_key_exchange_generate */
1385 /* Generate key exchange message */
1386 /* _nx_crypto_ecjpake_key_exchange_process */
1387 /* Process key exchange message */
1388 /* _nx_crypto_ecjpake_public_key_generate */
1389 /* Perform public key generation */
1390 /* _nx_crypto_ecjpake_schnorr_zkp_generate */
1391 /* Perform Schnorr ZKP generation*/
1392 /* _nx_crypto_ecjpake_schnorr_zkp_hash Perform Schnorr ZKP hash */
1393 /* calculation */
1394 /* _nx_crypto_huge_number_power_modulus Raise a huge number */
1395 /* _nx_crypto_huge_number_inverse_modulus */
1396 /* Perform an inverse modulus */
1397 /* operation */
1398 /* _nx_crypto_huge_number_inverse_modulus_prime */
1399 /* Perform an inverse modulus */
1400 /* operation for prime number */
1401 /* _nx_crypto_huge_number_mont_power_modulus */
1402 /* Raise a huge number for */
1403 /* montgomery reduction */
1404 /* _nx_crypto_huge_number_crt_power_modulus */
1405 /* Raise a huge number for CRT */
1406 /* */
1407 /* RELEASE HISTORY */
1408 /* */
1409 /* DATE NAME DESCRIPTION */
1410 /* */
1411 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1412 /* 09-30-2020 Timothy Stapko Modified comment(s), and */
1413 /* fixed variable type issue, */
1414 /* resulting in version 6.1 */
1415 /* 04-25-2022 Yuxin Zhou Modified comment(s), */
1416 /* fixed division by zero bug, */
1417 /* resulting in version 6.1.11 */
1418 /* */
1419 /**************************************************************************/
_nx_crypto_huge_number_modulus(NX_CRYPTO_HUGE_NUMBER * dividend,NX_CRYPTO_HUGE_NUMBER * divisor)1420 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_modulus(NX_CRYPTO_HUGE_NUMBER *dividend, NX_CRYPTO_HUGE_NUMBER *divisor)
1421 {
1422 UINT result_length, divisor_length; /* In number of USHORT words. */
1423 UINT compare_value;
1424 UINT i;
1425 UINT shift; /* In number of USHORT words. */
1426 HN_UBASE *result_buffer, *divisor_buffer;
1427 HN_UBASE2 scale;
1428 HN_UBASE divisor_msb;
1429 HN_UBASE dividend_msb;
1430 HN_UBASE2 product;
1431 HN_UBASE2 value, carry;
1432 HN_UBASE borrow;
1433 UINT index;
1434 NX_CRYPTO_HUGE_NUMBER *result;
1435
1436
1437 /* The algorithm used here is an implementation of the traditional long division.
1438 One 16-bit unsigned integer is treated as a "digit". It starts with the 2 most-significant digits
1439 of the dividend and the most significant digit of the divisor to come up with an estimate of a scale value. After
1440 subtracting the product of the scale and divisor.
1441
1442 To prevent the scale value from being too big, we also look into the second digit of the divisor.
1443 If the 2nd digit is greater or equal to 0x80, the scale value is reduced.
1444
1445 scale
1446 ____________________________
1447 BBbbxxxx )AAAAxxxxxxxxxxxxxxxxxx
1448 / CCCCxxxxxx
1449
1450 In the figure above, AAAA (dividend_msb) is the top 2 digits picked up from the dividend.
1451 BB isthe top digit picked up from the divisor. To prevent overflow, the next digit bb is
1452 examined. If bb equals or is greater than 0x80, BB is incremented by 1, effectively reducing
1453 the scale.
1454
1455 Then dividend subtracts the product of divisor and scale (with a left "shift").
1456
1457 keep going through this operation till the remainder is less than the divisor.
1458 */
1459
1460 /* Copy dividend into result */
1461 result = dividend;
1462
1463 /* If the dividend is smaller than the divisor, the remainder is simply the dividend so we are done. */
1464 compare_value = _nx_crypto_huge_number_compare_unsigned(result, divisor);
1465 if (compare_value == NX_CRYPTO_HUGE_NUMBER_LESS)
1466 {
1467 if (result -> nx_crypto_huge_number_is_negative)
1468 {
1469 _nx_crypto_huge_number_add(result, divisor);
1470 }
1471 return;
1472 }
1473
1474 /* Get divisor_length and result_legnth, which are converted to number of USHORT */
1475 divisor_length = divisor -> nx_crypto_huge_number_size - 1;
1476 result_length = result -> nx_crypto_huge_number_size - 1;
1477
1478 /* Get local pointers into our buffers for easier reading. */
1479 result_buffer = result -> nx_crypto_huge_number_data;
1480 divisor_buffer = divisor -> nx_crypto_huge_number_data;
1481
1482 // divisor_buffer[divisor_length + 1] = 0;
1483
1484 /* First, obtain our divisor_msb value. */
1485 while (divisor_buffer[divisor_length] == 0)
1486 {
1487 divisor_length--;
1488 }
1489 divisor_msb = divisor_buffer[divisor_length] >> (HN_SHIFT >> 1);
1490
1491
1492 divisor_msb++;
1493
1494 /* Going through the scale/subtraction loop till the dividend is less than
1495 divisor. At this point the value in the dividend buffer is the remainder. */
1496
1497 /* Obtain reuslt_length */
1498 result_length = result -> nx_crypto_huge_number_size - 1;
1499 while (compare_value != NX_CRYPTO_HUGE_NUMBER_LESS)
1500 {
1501 dividend_msb = result_buffer[result_length] >> (HN_SHIFT >> 1);
1502 shift = result_length - divisor_length;
1503
1504 if (shift && (dividend_msb < divisor_msb))
1505 {
1506 dividend_msb = result_buffer[result_length];
1507 shift--;
1508
1509 if (dividend_msb < divisor_msb)
1510 {
1511 dividend_msb = (result_buffer[result_length] << (HN_SHIFT >> 1)) |
1512 (result_buffer[result_length - 1] >> (HN_SHIFT >> 1));
1513 scale = dividend_msb / divisor_msb;
1514 }
1515 else
1516 {
1517 scale = ((HN_UBASE2)(dividend_msb / divisor_msb)) << (HN_SHIFT >> 1);
1518 }
1519 }
1520 else if (shift)
1521 {
1522 scale = dividend_msb / divisor_msb;
1523 }
1524 else
1525 {
1526 scale = result_buffer[result_length] / ((HN_UBASE2)divisor_buffer[divisor_length] + 1);
1527 if (scale == 0)
1528 {
1529 scale = 1;
1530 }
1531 }
1532
1533
1534 carry = 0;
1535 borrow = 0;
1536 i = 0;
1537
1538 for (index = shift; index < result_length; index++)
1539 {
1540 product = divisor_buffer[i] * scale;
1541 product += carry;
1542
1543 carry = product >> HN_SHIFT; /* The carry bits used for the next itegration. */
1544
1545 value = result_buffer[index] + (HN_UBASE2)(HN_BASE)borrow;
1546 value = value - (product & HN_MASK);
1547
1548 borrow = (HN_UBASE)(value >> HN_SHIFT); /* The borrow bit used for the next itegration. */
1549
1550 result_buffer[index] = (HN_UBASE)(value & HN_MASK);
1551
1552 i++;
1553 }
1554
1555 if (i <= divisor_length)
1556 {
1557 product = divisor_buffer[i] * scale + carry;
1558 }
1559 else
1560 {
1561 product = carry;
1562 }
1563
1564 value = result_buffer[index] + (HN_UBASE2)(HN_BASE)borrow;
1565 value = value - (product & HN_MASK);
1566
1567 borrow = (HN_UBASE)(value >> HN_SHIFT); /* The borrow bit used for the next itegration. */
1568
1569 result_buffer[index] = (HN_UBASE)(value & HN_MASK);
1570
1571 while ((index > 0) && (result_buffer[index] == 0))
1572 {
1573 index--;
1574 }
1575 result_length = index;
1576
1577 result -> nx_crypto_huge_number_size = index + 1;
1578 if (result_length <= divisor_length)
1579 {
1580
1581 compare_value = _nx_crypto_huge_number_compare_unsigned(result, divisor);
1582 }
1583 }
1584
1585 if (result -> nx_crypto_huge_number_is_negative)
1586 {
1587 _nx_crypto_huge_number_add(result, divisor);
1588 }
1589 return;
1590 }
1591
1592 /**************************************************************************/
1593 /* */
1594 /* FUNCTION RELEASE */
1595 /* */
1596 /* _nx_crypto_huge_number_setup PORTABLE C */
1597 /* 6.1 */
1598 /* AUTHOR */
1599 /* */
1600 /* Timothy Stapko, Microsoft Corporation */
1601 /* */
1602 /* DESCRIPTION */
1603 /* */
1604 /* This function raises a huge number to the power of a second huge */
1605 /* number using a third huge number as a modulus. The result is placed */
1606 /* in a fourth huge number. */
1607 /* */
1608 /* NOTE: This function makes use of the Huge Number scratch buffers. */
1609 /* Each operand and the result must have the */
1610 /* nx_crypto_huge_number_scratch member set to point to a buffer */
1611 /* of size equal to the number data buffer and that size stored */
1612 /* in the nx_crypto_huge_buffer_size member. */
1613 /* INPUT */
1614 /* */
1615 /* number Number being exponentiated */
1616 /* exponent Exponent number */
1617 /* modulus Modulus number */
1618 /* result Result buffer */
1619 /* */
1620 /* OUTPUT */
1621 /* */
1622 /* Status Operation result status */
1623 /* */
1624 /* CALLS */
1625 /* */
1626 /* None */
1627 /* */
1628 /* CALLED BY */
1629 /* */
1630 /* _nx_crypto_dh_compute_secret Computes the Diffie-Hellman */
1631 /* shared secret */
1632 /* _nx_crypto_ec_point_setup Set up point from byte steam */
1633 /* _nx_crypto_ec_secp192r1_reduce Reduce the value of curve */
1634 /* secp192r1 */
1635 /* _nx_crypto_ec_secp224r1_reduce Reduce the value of curve */
1636 /* secp224r1 */
1637 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
1638 /* secp256r1 */
1639 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
1640 /* secp384r1 */
1641 /* _nx_crypto_ec_secp521r1_reduce Reduce the value of curve */
1642 /* secp521r1 */
1643 /* _nx_crypto_ecjpake_hello_process Process hello message */
1644 /* _nx_crypto_ecjpake_key_exchange_generate */
1645 /* Generate key exchange message */
1646 /* _nx_crypto_ecjpake_key_exchange_process */
1647 /* Process key exchange message */
1648 /* _nx_crypto_ecjpake_schnorr_zkp_hash Perform Schnorr ZKP hash */
1649 /* calculation */
1650 /* _nx_crypto_rsa_operation Perform an RSA operation */
1651 /* */
1652 /* RELEASE HISTORY */
1653 /* */
1654 /* DATE NAME DESCRIPTION */
1655 /* */
1656 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1657 /* 09-30-2020 Timothy Stapko Modified comment(s), */
1658 /* resulting in version 6.1 */
1659 /* */
1660 /**************************************************************************/
_nx_crypto_huge_number_setup(NX_CRYPTO_HUGE_NUMBER * number,const UCHAR * byte_stream,UINT size)1661 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_setup(NX_CRYPTO_HUGE_NUMBER *number, const UCHAR *byte_stream, UINT size)
1662 {
1663
1664 UINT i = 0;
1665 HN_UBASE *destination;
1666 HN_UBASE word;
1667 UINT num_words;
1668
1669 /* Remove leading zeros in the byte stream. */
1670 while (size > 0 && *byte_stream == 0)
1671 {
1672 size--;
1673 byte_stream++;
1674 }
1675
1676 /* Handle the case when the huge number is zero. */
1677 if (size == 0)
1678 {
1679 if (number -> nx_crypto_huge_buffer_size < sizeof(HN_UBASE))
1680 {
1681 return(NX_CRYPTO_SIZE_ERROR);
1682 }
1683
1684 number -> nx_crypto_huge_number_data[0] = 0;
1685 number -> nx_crypto_huge_number_size = 1;
1686 number -> nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
1687
1688 return(NX_CRYPTO_SUCCESS);
1689 }
1690
1691 num_words = (size + HN_SIZE_ROUND) >> HN_SIZE_SHIFT;
1692
1693 /* Make sure the huge number buffer size is large enough to hold the value. */
1694 if (number -> nx_crypto_huge_buffer_size < (num_words << HN_SIZE_SHIFT))
1695 {
1696 return(NX_CRYPTO_SIZE_ERROR);
1697 }
1698
1699 destination = number -> nx_crypto_huge_number_data + num_words - 1;
1700
1701
1702 if (size & HN_SIZE_ROUND)
1703 {
1704 #if (NX_CRYPTO_HUGE_NUMBER_BITS == 16)
1705 word = byte_stream[0];
1706 i++;
1707 #else /* NX_CRYPTO_HUGE_NUMBER_BITS == 32 */
1708 if ((size & HN_SIZE_ROUND) == 1)
1709 {
1710 word = byte_stream[0];
1711 i++;
1712 }
1713 else if ((size & HN_SIZE_ROUND) == 2)
1714 {
1715 word = (HN_UBASE)((byte_stream[0] << 8) | byte_stream[1]);
1716 i += 2;
1717 }
1718 else
1719 {
1720 word = (HN_UBASE)((byte_stream[0] << 16) | (byte_stream[1] << 8) | byte_stream[2]);
1721 i += 3;
1722 }
1723 #endif
1724 *destination = word;
1725 destination--;
1726 }
1727
1728 for (; i < size; i += sizeof(HN_UBASE))
1729 {
1730 #if (NX_CRYPTO_HUGE_NUMBER_BITS == 16)
1731 word = (HN_UBASE)((byte_stream[i] << 8) | (byte_stream[i + 1]));
1732 #else /* NX_CRYPTO_HUGE_NUMBER_BITS == 32 */
1733 word = (HN_UBASE)((byte_stream[i] << 24) |
1734 (byte_stream[i + 1] << 16) |
1735 (byte_stream[i + 2] << 8) |
1736 (byte_stream[i + 3]));
1737 #endif
1738 *destination = word;
1739 destination--;
1740 }
1741
1742 number -> nx_crypto_huge_number_size = num_words;
1743 number -> nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
1744
1745 return(NX_CRYPTO_SUCCESS);
1746 }
1747
1748 /**************************************************************************/
1749 /* */
1750 /* FUNCTION RELEASE */
1751 /* */
1752 /* _nx_crypto_huge_number_rbg PORTABLE C */
1753 /* 6.1 */
1754 /* AUTHOR */
1755 /* */
1756 /* Timothy Stapko, Microsoft Corporation */
1757 /* */
1758 /* DESCRIPTION */
1759 /* */
1760 /* This function generates random huge number with specified bits. */
1761 /* The result buffer must be large enough to hold random huge number. */
1762 /* */
1763 /* INPUT */
1764 /* */
1765 /* bits Random number bits */
1766 /* result Pointer to random number */
1767 /* */
1768 /* OUTPUT */
1769 /* */
1770 /* None */
1771 /* */
1772 /* CALLS */
1773 /* */
1774 /* None */
1775 /* */
1776 /* CALLED BY */
1777 /* */
1778 /* Application */
1779 /* */
1780 /* RELEASE HISTORY */
1781 /* */
1782 /* DATE NAME DESCRIPTION */
1783 /* */
1784 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1785 /* 09-30-2020 Timothy Stapko Modified comment(s), */
1786 /* resulting in version 6.1 */
1787 /* */
1788 /**************************************************************************/
_nx_crypto_huge_number_rbg(UINT bits,UCHAR * result)1789 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_rbg(UINT bits, UCHAR *result)
1790 {
1791 UCHAR *ptr = result;
1792 UINT random_number;
1793 UINT temp;
1794 UINT mask;
1795
1796 while (bits >= 32)
1797 {
1798
1799 /* Generate random number for each 32 bits. */
1800 random_number = (UINT)NX_CRYPTO_RAND();
1801 ptr[0] = (UCHAR)(random_number & 0xFF);
1802 ptr[1] = (UCHAR)((random_number >> 8) & 0xFF);
1803 ptr[2] = (UCHAR)((random_number >> 16) & 0xFF);
1804 ptr[3] = (UCHAR)((random_number >> 24) & 0xFF);
1805 bits -= 32;
1806 ptr += 4;
1807 }
1808
1809 if (bits == 0)
1810 {
1811
1812 /* Every bits are generated. */
1813 return(NX_CRYPTO_SUCCESS);
1814 }
1815
1816 /* Process left bits between 1 and 31. */
1817 random_number = (UINT)NX_CRYPTO_RAND();
1818
1819 /* Get remaining bits. */
1820 temp = (bits + 7) >> 3;
1821 switch (temp)
1822 {
1823 case 4:
1824 *ptr++ = (UCHAR)(random_number & 0xFF);
1825 random_number >>= 8;
1826 /* fallthrough */
1827 case 3:
1828 *ptr++ = (UCHAR)(random_number & 0xFF);
1829 random_number >>= 8;
1830 /* fallthrough */
1831 case 2:
1832 *ptr++ = (UCHAR)(random_number & 0xFF);
1833 random_number >>= 8;
1834 /* fallthrough */
1835 case 1:
1836 *ptr++ = (UCHAR)(random_number & 0xFF);
1837 random_number >>= 8;
1838 /* fallthrough */
1839 default:
1840 break;
1841 }
1842
1843 /* Zero out extra bits generated. */
1844 bits = bits & 7;
1845 if (bits)
1846 {
1847 mask = (UINT)((1 << bits) - 1);
1848 result[0] = (UCHAR)(result[0] & mask);
1849 }
1850
1851 return(NX_CRYPTO_SUCCESS);
1852 }
1853
1854 /**************************************************************************/
1855 /* */
1856 /* FUNCTION RELEASE */
1857 /* */
1858 /* _nx_crypto_huge_number_extract PORTABLE C */
1859 /* 6.1 */
1860 /* AUTHOR */
1861 /* */
1862 /* Timothy Stapko, Microsoft Corporation */
1863 /* */
1864 /* DESCRIPTION */
1865 /* */
1866 /* This function extracts huge number to buffer. */
1867 /* */
1868 /* INPUT */
1869 /* */
1870 /* number Huge number */
1871 /* byte_stream Output buffer */
1872 /* byte_stream_size Size of output buffer */
1873 /* huge_number_size Size of huge number in bytes */
1874 /* */
1875 /* OUTPUT */
1876 /* */
1877 /* Status Operation result status */
1878 /* */
1879 /* CALLS */
1880 /* */
1881 /* None */
1882 /* */
1883 /* CALLED BY */
1884 /* */
1885 /* _nx_crypto_dh_compute_secret Computes the Diffie-Hellman */
1886 /* shared secret */
1887 /* _nx_crypto_dh_setup Set up Diffie-Hellman context */
1888 /* _nx_crypto_ec_point_extract_uncompressed */
1889 /* Extract point to byte stream */
1890 /* in uncompressed format */
1891 /* _nx_crypto_ec_secp192r1_reduce Reduce the value of curve */
1892 /* secp192r1 */
1893 /* _nx_crypto_ec_secp224r1_reduce Reduce the value of curve */
1894 /* secp224r1 */
1895 /* _nx_crypto_ec_secp256r1_reduce Reduce the value of curve */
1896 /* secp256r1 */
1897 /* _nx_crypto_ec_secp384r1_reduce Reduce the value of curve */
1898 /* secp384r1 */
1899 /* _nx_crypto_ec_secp521r1_reduce Reduce the value of curve */
1900 /* secp521r1 */
1901 /* _nx_crypto_ecjpake_hello_generate Generate hello message */
1902 /* _nx_crypto_ecjpake_key_exchange_generate */
1903 /* Generate key exchange message */
1904 /* _nx_crypto_ecjpake_pre_master_secret_generate */
1905 /* Generate pre master secret */
1906 /* _nx_crypto_rsa_operation Perform an RSA operation */
1907 /* */
1908 /* RELEASE HISTORY */
1909 /* */
1910 /* DATE NAME DESCRIPTION */
1911 /* */
1912 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1913 /* 09-30-2020 Timothy Stapko Modified comment(s), */
1914 /* resulting in version 6.1 */
1915 /* */
1916 /**************************************************************************/
_nx_crypto_huge_number_extract(NX_CRYPTO_HUGE_NUMBER * number,UCHAR * byte_stream,UINT byte_stream_size,UINT * huge_number_size)1917 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_extract(NX_CRYPTO_HUGE_NUMBER *number, UCHAR *byte_stream,
1918 UINT byte_stream_size, UINT *huge_number_size)
1919 {
1920 INT i = 0;
1921 HN_UBASE *word;
1922 HN_UBASE value;
1923 UCHAR *bytes;
1924
1925
1926 if ((number -> nx_crypto_huge_number_size << HN_SIZE_SHIFT) > byte_stream_size)
1927 {
1928 /* User byte stream buffer too small. */
1929 return(NX_CRYPTO_NOT_SUCCESSFUL);
1930 }
1931
1932 bytes = byte_stream;
1933
1934 word = number -> nx_crypto_huge_number_data;
1935 for (i = (INT)(number -> nx_crypto_huge_number_size - 1); i >= 0; i--)
1936 {
1937 value = word[i];
1938 #if (NX_CRYPTO_HUGE_NUMBER_BITS == 16)
1939 *bytes = value >> 8;
1940 *(bytes + 1) = value & 0xFF;
1941 #else /* NX_CRYPTO_HUGE_NUMBER_BITS == 32 */
1942 *bytes = (UCHAR)(value >> 24);
1943 *(bytes + 1) = (value >> 16) & 0xFF;
1944 *(bytes + 2) = (value >> 8) & 0xFF;
1945 *(bytes + 3) = value & 0xFF;
1946 #endif
1947 bytes += sizeof(HN_UBASE);
1948 }
1949 *huge_number_size = (number -> nx_crypto_huge_number_size << HN_SIZE_SHIFT);
1950
1951 return(NX_CRYPTO_SUCCESS);
1952 }
1953
1954 /**************************************************************************/
1955 /* */
1956 /* FUNCTION RELEASE */
1957 /* */
1958 /* _nx_crypto_huge_number_extract_fixed_size PORTABLE C */
1959 /* 6.1 */
1960 /* AUTHOR */
1961 /* */
1962 /* Timothy Stapko, Microsoft Corporation */
1963 /* */
1964 /* DESCRIPTION */
1965 /* */
1966 /* This function extracts huge number to a buffer with fixed size. */
1967 /* */
1968 /* INPUT */
1969 /* */
1970 /* number Huge number */
1971 /* byte_stream Output buffer */
1972 /* byte_stream_size Size of output buffer */
1973 /* */
1974 /* OUTPUT */
1975 /* */
1976 /* Status Operation result status */
1977 /* */
1978 /* CALLS */
1979 /* */
1980 /* None */
1981 /* */
1982 /* CALLED BY */
1983 /* */
1984 /* _nx_crypto_ecdsa_sign Sign hash data using ECDSA. */
1985 /* */
1986 /* RELEASE HISTORY */
1987 /* */
1988 /* DATE NAME DESCRIPTION */
1989 /* */
1990 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
1991 /* 09-30-2020 Timothy Stapko Modified comment(s), */
1992 /* resulting in version 6.1 */
1993 /* */
1994 /**************************************************************************/
_nx_crypto_huge_number_extract_fixed_size(NX_CRYPTO_HUGE_NUMBER * number,UCHAR * byte_stream,UINT byte_stream_size)1995 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_extract_fixed_size(NX_CRYPTO_HUGE_NUMBER *number,
1996 UCHAR *byte_stream, UINT byte_stream_size)
1997 {
1998 INT i = 0;
1999 HN_UBASE *word;
2000 HN_UBASE value;
2001 UCHAR *bytes;
2002 UINT leading_count = 0;
2003 UINT num_size_adjusted;
2004
2005 word = number -> nx_crypto_huge_number_data;
2006
2007 num_size_adjusted = number -> nx_crypto_huge_number_size;
2008 do
2009 {
2010 num_size_adjusted--;
2011 value = word[num_size_adjusted];
2012 } while (value == 0 && num_size_adjusted > 0);
2013 num_size_adjusted++;
2014
2015 #if (NX_CRYPTO_HUGE_NUMBER_BITS == 16)
2016 if ((value & 0xFF00) == 0)
2017 {
2018 leading_count = 1;
2019 }
2020 #else
2021 if ((value & 0xFFFFFF00) == 0)
2022 {
2023 leading_count = 3;
2024 }
2025 else if ((value & 0xFFFF0000) == 0)
2026 {
2027 leading_count = 2;
2028 }
2029 else if ((value & 0xFF000000) == 0)
2030 {
2031 leading_count = 1;
2032 }
2033 #endif
2034
2035 if ((num_size_adjusted << HN_SIZE_SHIFT) - leading_count > byte_stream_size)
2036 {
2037 /* User byte stream buffer too small. */
2038 return(NX_CRYPTO_SIZE_ERROR);
2039 }
2040
2041 byte_stream_size -= (num_size_adjusted << HN_SIZE_SHIFT) - leading_count;
2042
2043 if (byte_stream_size > 0)
2044 {
2045 NX_CRYPTO_MEMSET(byte_stream, 0, byte_stream_size);
2046 }
2047
2048 bytes = byte_stream + byte_stream_size;
2049
2050 #if (NX_CRYPTO_HUGE_NUMBER_BITS == 16)
2051 if (leading_count == 0)
2052 {
2053 *bytes = (UCHAR)(value >> 8);
2054 bytes++;
2055 }
2056 #else
2057 if (leading_count == 0)
2058 {
2059 *bytes = (UCHAR)(value >> 24);
2060 bytes++;
2061 }
2062 if (leading_count <= 1)
2063 {
2064 *bytes = (UCHAR)((value >> 16) & 0xFF);
2065 bytes++;
2066 }
2067 if (leading_count <= 2)
2068 {
2069 *bytes = (UCHAR)((value >> 8) & 0xFF);
2070 bytes++;
2071 }
2072 #endif
2073
2074 *bytes = (UCHAR)(value & 0xFF);
2075 bytes++;
2076
2077 for (i = (INT)(num_size_adjusted - 2); i >= 0; i--)
2078 {
2079 value = word[i];
2080 #if (NX_CRYPTO_HUGE_NUMBER_BITS == 16)
2081 *bytes = value >> 8;
2082 *(bytes + 1) = value & 0xFF;
2083 #else /* NX_CRYPTO_HUGE_NUMBER_BITS == 32 */
2084 *bytes = (UCHAR)(value >> 24);
2085 *(bytes + 1) = (value >> 16) & 0xFF;
2086 *(bytes + 2) = (value >> 8) & 0xFF;
2087 *(bytes + 3) = value & 0xFF;
2088 #endif
2089 bytes += sizeof(HN_UBASE);
2090 }
2091
2092 return(NX_CRYPTO_SUCCESS);
2093 }
2094
2095 /**************************************************************************/
2096 /* */
2097 /* FUNCTION RELEASE */
2098 /* */
2099 /* _nx_crypto_huge_number_inverse_modulus_prime */
2100 /* PORTABLE C */
2101 /* 6.1 */
2102 /* AUTHOR */
2103 /* */
2104 /* Timothy Stapko, Microsoft Corporation */
2105 /* */
2106 /* DESCRIPTION */
2107 /* */
2108 /* This function performs an inverse modulus operation. The size of */
2109 /* scratch is required to be larger than 4 * (max(len(p), len(a)) + 1) */
2110 /* times of size of radix. p must be prime number. */
2111 /* r = a ^ (-1) mod p */
2112 /* */
2113 /* INPUT */
2114 /* */
2115 /* a Huge number a */
2116 /* p Huge number modulo p */
2117 /* r Huge number r */
2118 /* scratch Buffer used to hold */
2119 /* intermediate data */
2120 /* */
2121 /* OUTPUT */
2122 /* */
2123 /* Status Operation result status */
2124 /* */
2125 /* CALLS */
2126 /* */
2127 /* NX_CRYPTO_HUGE_NUMBER_COPY Copy huge number */
2128 /* NX_CRYPTO_HUGE_NUMBER_INITIALIZE Initialize the buffer of */
2129 /* huge number */
2130 /* NX_CRYPTO_HUGE_NUMBER_SET_DIGIT Set value of huge number */
2131 /* between 0 and (HN_RADIX - 1)*/
2132 /* _nx_crypto_huge_number_is_zero Check if number is zero or not*/
2133 /* _nx_crypto_huge_number_add Calculate addition for */
2134 /* huge numbers */
2135 /* _nx_crypto_huge_number_subtract Calculate subtraction for */
2136 /* huge numbers */
2137 /* _nx_crypto_huge_number_shift_right Shift right for huge number */
2138 /* _nx_crypto_huge_number_compare Compare two huge numbers */
2139 /* _nx_crypto_huge_number_modulus Perform a modulus operation */
2140 /* */
2141 /* CALLED BY */
2142 /* */
2143 /* _nx_crypto_ec_fp_affine_add Perform addition for points of*/
2144 /* affine */
2145 /* _nx_crypto_ec_point_fp_projective_to_affine */
2146 /* Convert point from projective */
2147 /* to affine */
2148 /* _nx_crypto_huge_number_crt_power_modulus */
2149 /* Raise a huge number for CRT */
2150 /* */
2151 /* RELEASE HISTORY */
2152 /* */
2153 /* DATE NAME DESCRIPTION */
2154 /* */
2155 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
2156 /* 09-30-2020 Timothy Stapko Modified comment(s), */
2157 /* resulting in version 6.1 */
2158 /* */
2159 /**************************************************************************/
_nx_crypto_huge_number_inverse_modulus_prime(NX_CRYPTO_HUGE_NUMBER * a,NX_CRYPTO_HUGE_NUMBER * p,NX_CRYPTO_HUGE_NUMBER * r,HN_UBASE * scratch)2160 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_inverse_modulus_prime(NX_CRYPTO_HUGE_NUMBER *a,
2161 NX_CRYPTO_HUGE_NUMBER *p,
2162 NX_CRYPTO_HUGE_NUMBER *r,
2163 HN_UBASE *scratch)
2164 {
2165 NX_CRYPTO_HUGE_NUMBER u, v, A, C;
2166 UINT buffer_size;
2167
2168 if (p -> nx_crypto_huge_number_size > a -> nx_crypto_huge_number_size)
2169 {
2170 buffer_size = (p -> nx_crypto_huge_number_size + 1) << HN_SIZE_SHIFT;
2171 }
2172 else
2173 {
2174 buffer_size = (a -> nx_crypto_huge_number_size + 1) << HN_SIZE_SHIFT;
2175 }
2176
2177 /* Buffer usage: 6 * buffer_size */
2178 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&u, scratch, buffer_size);
2179 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&v, scratch, buffer_size);
2180 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&A, scratch, buffer_size);
2181 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&C, scratch, buffer_size);
2182
2183 NX_CRYPTO_HUGE_NUMBER_COPY(&u, a);
2184 NX_CRYPTO_HUGE_NUMBER_COPY(&v, p);
2185 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(&A, 1);
2186 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(&C, 0);
2187
2188 while (!_nx_crypto_huge_number_is_zero(&u))
2189 {
2190 while (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&u))
2191 {
2192 _nx_crypto_huge_number_shift_right(&u, 1);
2193 if (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&A))
2194 {
2195 _nx_crypto_huge_number_shift_right(&A, 1);
2196 }
2197 else
2198 {
2199 _nx_crypto_huge_number_add(&A, p);
2200 _nx_crypto_huge_number_shift_right(&A, 1);
2201 }
2202 }
2203
2204 while (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&v))
2205 {
2206 _nx_crypto_huge_number_shift_right(&v, 1);
2207 if (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&C))
2208 {
2209 _nx_crypto_huge_number_shift_right(&C, 1);
2210 }
2211 else
2212 {
2213 _nx_crypto_huge_number_add(&C, p);
2214 _nx_crypto_huge_number_shift_right(&C, 1);
2215 }
2216 }
2217
2218 if (_nx_crypto_huge_number_compare(&u, &v) != NX_CRYPTO_HUGE_NUMBER_LESS)
2219 {
2220 _nx_crypto_huge_number_subtract(&u, &v);
2221 _nx_crypto_huge_number_subtract(&A, &C);
2222 }
2223 else
2224 {
2225 _nx_crypto_huge_number_subtract(&v, &u);
2226 _nx_crypto_huge_number_subtract(&C, &A);
2227 }
2228 }
2229
2230 _nx_crypto_huge_number_modulus(&C, p);
2231 NX_CRYPTO_HUGE_NUMBER_COPY(r, &C);
2232
2233 return(NX_CRYPTO_SUCCESS);
2234 }
2235
2236 /**************************************************************************/
2237 /* */
2238 /* FUNCTION RELEASE */
2239 /* */
2240 /* _nx_crypto_huge_number_inverse_modulus PORTABLE C */
2241 /* 6.1 */
2242 /* AUTHOR */
2243 /* */
2244 /* Timothy Stapko, Microsoft Corporation */
2245 /* */
2246 /* DESCRIPTION */
2247 /* */
2248 /* This function performs an inverse modulus operation. The size of */
2249 /* scratch is required to be larger than 6 * (max(len(m), len(a)) + 1) */
2250 /* times of size of radix. */
2251 /* r = a ^ (-1) mod m */
2252 /* */
2253 /* INPUT */
2254 /* */
2255 /* a Huge number a */
2256 /* m Huge number modulo */
2257 /* r Huge number r */
2258 /* scratch Buffer used to hold */
2259 /* intermediate data */
2260 /* */
2261 /* OUTPUT */
2262 /* */
2263 /* Status Operation result status */
2264 /* */
2265 /* CALLS */
2266 /* */
2267 /* NX_CRYPTO_HUGE_NUMBER_COPY Copy huge number */
2268 /* NX_CRYPTO_HUGE_NUMBER_INITIALIZE Initialize the buffer of */
2269 /* huge number */
2270 /* NX_CRYPTO_HUGE_NUMBER_SET_DIGIT Set value of huge number */
2271 /* between 0 and (HN_RADIX - 1)*/
2272 /* _nx_crypto_huge_number_is_zero Check if number is zero or not*/
2273 /* _nx_crypto_huge_number_add Calculate addition for */
2274 /* huge numbers */
2275 /* _nx_crypto_huge_number_subtract Calculate subtraction for */
2276 /* huge numbers */
2277 /* _nx_crypto_huge_number_shift_right Shift right for huge number */
2278 /* _nx_crypto_huge_number_compare Compare two huge numbers */
2279 /* _nx_crypto_huge_number_modulus Perform a modulus operation */
2280 /* */
2281 /* CALLED BY */
2282 /* */
2283 /* _nx_crypto_huge_number_mont_power_modulus */
2284 /* Raise a huge number for */
2285 /* montgomery reduction */
2286 /* */
2287 /* RELEASE HISTORY */
2288 /* */
2289 /* DATE NAME DESCRIPTION */
2290 /* */
2291 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
2292 /* 09-30-2020 Timothy Stapko Modified comment(s), and */
2293 /* fixed input validation, */
2294 /* resulting in version 6.1 */
2295 /* */
2296 /**************************************************************************/
_nx_crypto_huge_number_inverse_modulus(NX_CRYPTO_HUGE_NUMBER * a,NX_CRYPTO_HUGE_NUMBER * m,NX_CRYPTO_HUGE_NUMBER * r,HN_UBASE * scratch)2297 NX_CRYPTO_KEEP UINT _nx_crypto_huge_number_inverse_modulus(NX_CRYPTO_HUGE_NUMBER *a,
2298 NX_CRYPTO_HUGE_NUMBER *m,
2299 NX_CRYPTO_HUGE_NUMBER *r,
2300 HN_UBASE *scratch)
2301 {
2302 NX_CRYPTO_HUGE_NUMBER u, v, A, B, C, D;
2303 UINT buffer_size;
2304
2305 if (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(m) && NX_CRYPTO_HUGE_NUMBER_IS_EVEN(a))
2306 {
2307
2308 /* gcd(m, a) <> 1.
2309 * a is not invertible modulo m. */
2310 return(NX_CRYPTO_NOT_SUCCESSFUL);
2311 }
2312
2313 if(_nx_crypto_huge_number_is_zero(a))
2314 {
2315
2316 /* zero is not invertible */
2317 return(NX_CRYPTO_NOT_SUCCESSFUL);
2318 }
2319
2320 if (m -> nx_crypto_huge_number_size > a -> nx_crypto_huge_number_size)
2321 {
2322 buffer_size = (m -> nx_crypto_huge_number_size + 1) << HN_SIZE_SHIFT;
2323 }
2324 else
2325 {
2326 buffer_size = (a -> nx_crypto_huge_number_size + 1) << HN_SIZE_SHIFT;
2327 }
2328
2329 /* Buffer usage: 6 * buffer_size */
2330 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&u, scratch, buffer_size);
2331 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&v, scratch, buffer_size);
2332 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&A, scratch, buffer_size);
2333 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&B, scratch, buffer_size);
2334 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&C, scratch, buffer_size);
2335 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&D, scratch, buffer_size);
2336
2337 NX_CRYPTO_HUGE_NUMBER_COPY(&u, m);
2338 NX_CRYPTO_HUGE_NUMBER_COPY(&v, a);
2339 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(&A, 1);
2340 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(&B, 0);
2341 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(&C, 0);
2342 NX_CRYPTO_HUGE_NUMBER_SET_DIGIT(&D, 1);
2343
2344 for (;;)
2345 {
2346 while (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&u))
2347 {
2348 _nx_crypto_huge_number_shift_right(&u, 1);
2349
2350 if (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&A) && NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&B))
2351 {
2352 _nx_crypto_huge_number_shift_right(&A, 1);
2353 _nx_crypto_huge_number_shift_right(&B, 1);
2354 }
2355 else
2356 {
2357 _nx_crypto_huge_number_add(&A, a);
2358 _nx_crypto_huge_number_shift_right(&A, 1);
2359 _nx_crypto_huge_number_subtract(&B, m);
2360 _nx_crypto_huge_number_shift_right(&B, 1);
2361 }
2362 }
2363
2364 while (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&v))
2365 {
2366 _nx_crypto_huge_number_shift_right(&v, 1);
2367 if (NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&C) && NX_CRYPTO_HUGE_NUMBER_IS_EVEN(&D))
2368 {
2369 _nx_crypto_huge_number_shift_right(&C, 1);
2370 _nx_crypto_huge_number_shift_right(&D, 1);
2371 }
2372 else
2373 {
2374 _nx_crypto_huge_number_add(&C, a);
2375 _nx_crypto_huge_number_shift_right(&C, 1);
2376 _nx_crypto_huge_number_subtract(&D, m);
2377 _nx_crypto_huge_number_shift_right(&D, 1);
2378 }
2379 }
2380
2381 if (_nx_crypto_huge_number_compare(&u, &v) != NX_CRYPTO_HUGE_NUMBER_LESS)
2382 {
2383 _nx_crypto_huge_number_subtract(&u, &v);
2384 _nx_crypto_huge_number_subtract(&A, &C);
2385 _nx_crypto_huge_number_subtract(&B, &D);
2386 }
2387 else
2388 {
2389 _nx_crypto_huge_number_subtract(&v, &u);
2390 _nx_crypto_huge_number_subtract(&C, &A);
2391 _nx_crypto_huge_number_subtract(&D, &B);
2392 }
2393
2394 if (_nx_crypto_huge_number_is_zero(&u))
2395 {
2396 _nx_crypto_huge_number_modulus(&D, m);
2397 NX_CRYPTO_HUGE_NUMBER_COPY(r, &D);
2398 break;
2399 }
2400 }
2401
2402 return(NX_CRYPTO_SUCCESS);
2403 }
2404
2405 /**************************************************************************/
2406 /* */
2407 /* FUNCTION RELEASE */
2408 /* */
2409 /* _nx_crypto_huge_number_mont PORTABLE C */
2410 /* 6.1 */
2411 /* AUTHOR */
2412 /* */
2413 /* Timothy Stapko, Microsoft Corporation */
2414 /* */
2415 /* DESCRIPTION */
2416 /* */
2417 /* This function performs Montgomery reduction for multiplication. */
2418 /* r = (x * y) * R ^ (-1) mod m */
2419 /* */
2420 /* INPUT */
2421 /* */
2422 /* m Huge number m */
2423 /* mi mi = -m ^ (-1) mod radix */
2424 /* x Huge number x */
2425 /* y Huge number y */
2426 /* result Huge number r */
2427 /* */
2428 /* OUTPUT */
2429 /* */
2430 /* None */
2431 /* */
2432 /* CALLS */
2433 /* */
2434 /* _nx_crypto_huge_number_subtract Calculate subtraction for */
2435 /* huge numbers */
2436 /* _nx_crypto_huge_number_adjust_size Adjust the size of a huge */
2437 /* number to remove leading */
2438 /* zeroes */
2439 /* _nx_crypto_huge_number_compare Compare two huge numbers */
2440 /* */
2441 /* CALLED BY */
2442 /* */
2443 /* _nx_crypto_huge_number_mont_power_modulus */
2444 /* Raise a huge number for */
2445 /* montgomery reduction */
2446 /* */
2447 /* RELEASE HISTORY */
2448 /* */
2449 /* DATE NAME DESCRIPTION */
2450 /* */
2451 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
2452 /* 09-30-2020 Timothy Stapko Modified comment(s), */
2453 /* resulting in version 6.1 */
2454 /* */
2455 /**************************************************************************/
_nx_crypto_huge_number_mont(NX_CRYPTO_HUGE_NUMBER * m,UINT mi,NX_CRYPTO_HUGE_NUMBER * x,NX_CRYPTO_HUGE_NUMBER * y,NX_CRYPTO_HUGE_NUMBER * result)2456 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_mont(NX_CRYPTO_HUGE_NUMBER *m, UINT mi,
2457 NX_CRYPTO_HUGE_NUMBER *x,
2458 NX_CRYPTO_HUGE_NUMBER *y,
2459 NX_CRYPTO_HUGE_NUMBER *result)
2460 {
2461 UINT i, j;
2462 HN_UBASE u;
2463 HN_UBASE xi;
2464 HN_UBASE2 product;
2465 UINT m_len = m -> nx_crypto_huge_number_size;
2466 UINT x_len = x -> nx_crypto_huge_number_size;
2467 UINT y_len = y -> nx_crypto_huge_number_size;
2468 HN_UBASE *m_buffer = m -> nx_crypto_huge_number_data;
2469 HN_UBASE *x_buffer = x -> nx_crypto_huge_number_data;
2470 HN_UBASE *y_buffer = y -> nx_crypto_huge_number_data;
2471 HN_UBASE *result_buffer = result -> nx_crypto_huge_number_data;
2472
2473 NX_CRYPTO_MEMSET(result -> nx_crypto_huge_number_data, 0, (m_len + 1) * sizeof(HN_UBASE));
2474
2475 for (i = 0; i < x_len; i++)
2476 {
2477
2478 xi = x_buffer[i];
2479
2480 /* r = (r + x[i] * y + u * m) / radix */
2481 product = 0;
2482 for (j = 0; j < y_len; j++)
2483 {
2484 product >>= HN_SHIFT;
2485 product += result_buffer[j] + (HN_UBASE2)xi * y_buffer[j];
2486 result_buffer[j] = (product & HN_MASK);
2487 }
2488 for (; j < (m_len + 1); j++)
2489 {
2490 product >>= HN_SHIFT;
2491 product += result_buffer[j];
2492 result_buffer[j] = (product & HN_MASK);
2493 }
2494
2495 /* u = (r[0] + x[i] * y[0]) * mi mod radix */
2496 u = result_buffer[0] * mi;
2497
2498 product = result_buffer[0] + (HN_UBASE2)u * m_buffer[0];
2499 for (j = 1; j < m_len; j++)
2500 {
2501 product >>= HN_SHIFT;
2502 product += result_buffer[j] + (HN_UBASE2)u * m_buffer[j];
2503 result_buffer[j - 1] = (product & HN_MASK);
2504 }
2505 product >>= HN_SHIFT;
2506 product += result_buffer[j];
2507 result_buffer[j - 1] = (product & HN_MASK);
2508 result_buffer[j] = (HN_UBASE)(product >> HN_SHIFT);
2509 }
2510
2511 for (; i < m_len; i++)
2512 {
2513
2514 /* u = (r[0] + x[i] * y[0]) * mi mod radix */
2515 u = ((result_buffer[0] * mi) & HN_MASK);
2516
2517 /* r = (r + x[i] * y + u * m) / radix */
2518 product = result_buffer[0] + (HN_UBASE2)u * m_buffer[0];
2519 for (j = 1; j < m_len; j++)
2520 {
2521 product >>= HN_SHIFT;
2522 product += result_buffer[j] + (HN_UBASE2)u * m_buffer[j];
2523 result_buffer[j - 1] = (product & HN_MASK);
2524 }
2525 product >>= HN_SHIFT;
2526 product += result_buffer[j];
2527 result_buffer[j - 1] = (product & HN_MASK);
2528 result_buffer[j] = (HN_UBASE)(product >> HN_SHIFT);
2529 }
2530
2531 /* Set result size. */
2532 result -> nx_crypto_huge_number_size = m_len + 1;
2533 _nx_crypto_huge_number_adjust_size(result);
2534
2535 if (_nx_crypto_huge_number_compare(result, m) != NX_CRYPTO_HUGE_NUMBER_LESS)
2536 {
2537
2538 /* r = r - m. */
2539 _nx_crypto_huge_number_subtract(result, m);
2540 }
2541 }
2542
2543 /**************************************************************************/
2544 /* */
2545 /* FUNCTION RELEASE */
2546 /* */
2547 /* _nx_crypto_huge_number_mont_power_modulus PORTABLE C */
2548 /* 6.1.9 */
2549 /* AUTHOR */
2550 /* */
2551 /* Timothy Stapko, Microsoft Corporation */
2552 /* */
2553 /* DESCRIPTION */
2554 /* */
2555 /* This function raises a huge number to the power of a second huge */
2556 /* number using a third huge number as a modulus. The result is placed */
2557 /* in a fourth huge number. Montgomery reduction is used. */
2558 /* scratch is required to be larger than twice of buffer size of m */
2559 /* plus 8 bytes. */
2560 /* */
2561 /* INPUT */
2562 /* */
2563 /* x Number being exponentiated */
2564 /* e Exponent number */
2565 /* m Modulus number */
2566 /* result Result buffer */
2567 /* scratch Buffer used to hold */
2568 /* intermediate data */
2569 /* */
2570 /* OUTPUT */
2571 /* */
2572 /* Status Operation result status */
2573 /* */
2574 /* CALLS */
2575 /* */
2576 /* NX_CRYPTO_HUGE_NUMBER_COPY Copy huge number */
2577 /* NX_CRYPTO_HUGE_NUMBER_INITIALIZE Initialize the buffer of */
2578 /* huge number */
2579 /* NX_CRYPTO_HUGE_NUMBER_SET_DIGIT Set value of huge number */
2580 /* between 0 and (HN_RADIX - 1)*/
2581 /* _nx_crypto_huge_number_adjust_size Adjust the size of a huge */
2582 /* number to remove leading */
2583 /* zeroes */
2584 /* _nx_crypto_huge_number_modulus Perform a modulus operation */
2585 /* _nx_crypto_huge_number_inverse_modulus */
2586 /* Perform an inverse modulus */
2587 /* operation */
2588 /* _nx_crypto_huge_number_mont Perform Montgomery reduction */
2589 /* for multiplication */
2590 /* _nx_crypto_huge_number_square Compute the square of a value */
2591 /* */
2592 /* CALLED BY */
2593 /* */
2594 /* _nx_crypto_dh_compute_secret Computes the Diffie-Hellman */
2595 /* shared secret */
2596 /* _nx_crypto_dh_setup Set up Diffie-Hellman context */
2597 /* _nx_crypto_huge_number_crt_power_modulus */
2598 /* Raise a huge number for CRT */
2599 /* _nx_crypto_rsa_operation Perform an RSA operation */
2600 /* */
2601 /* RELEASE HISTORY */
2602 /* */
2603 /* DATE NAME DESCRIPTION */
2604 /* */
2605 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
2606 /* 09-30-2020 Timothy Stapko Modified comment(s), */
2607 /* resulting in version 6.1 */
2608 /* 10-15-2021 Bhupendra Naphade Modified comment(s), */
2609 /* resulting in version 6.1.9 */
2610 /* */
2611 /**************************************************************************/
_nx_crypto_huge_number_mont_power_modulus(NX_CRYPTO_HUGE_NUMBER * x,NX_CRYPTO_HUGE_NUMBER * e,NX_CRYPTO_HUGE_NUMBER * m,NX_CRYPTO_HUGE_NUMBER * result,HN_UBASE * scratch)2612 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_mont_power_modulus(NX_CRYPTO_HUGE_NUMBER *x,
2613 NX_CRYPTO_HUGE_NUMBER *e,
2614 NX_CRYPTO_HUGE_NUMBER *m,
2615 NX_CRYPTO_HUGE_NUMBER *result,
2616 HN_UBASE *scratch)
2617 {
2618 UINT m_len;
2619 NX_CRYPTO_HUGE_NUMBER xx;
2620 NX_CRYPTO_HUGE_NUMBER temp;
2621 NX_CRYPTO_HUGE_NUMBER digit;
2622 NX_CRYPTO_HUGE_NUMBER radix;
2623 NX_CRYPTO_HUGE_NUMBER mi;
2624 NX_CRYPTO_HUGE_NUMBER m0;
2625 HN_UBASE digit_value;
2626 HN_UBASE *val;
2627 HN_UBASE radix_buffer[2] = {0, 1};
2628 HN_UBASE mm_buffer[2];
2629 HN_UBASE cur_block;
2630 UINT bit, exp_size;
2631 NX_CRYPTO_HUGE_NUMBER *operand, *temp_result, *temp_swap;
2632
2633 /* Adjust sizes before performing the calculation. */
2634 _nx_crypto_huge_number_adjust_size(x);
2635 _nx_crypto_huge_number_adjust_size(e);
2636 _nx_crypto_huge_number_adjust_size(m);
2637
2638 /* Initialize const huge numbers. */
2639 radix.nx_crypto_huge_number_data = radix_buffer;
2640 radix.nx_crypto_huge_number_size = 2;
2641 radix.nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
2642 radix.nx_crypto_huge_buffer_size = sizeof(radix_buffer);
2643 m0.nx_crypto_huge_number_data = m -> nx_crypto_huge_number_data;
2644 m0.nx_crypto_huge_number_size = 1;
2645 m0.nx_crypto_huge_buffer_size = 4;
2646 m0.nx_crypto_huge_number_is_negative = NX_CRYPTO_FALSE;
2647 mi.nx_crypto_huge_number_data = mm_buffer;
2648 mi.nx_crypto_huge_buffer_size = sizeof(mm_buffer);
2649
2650 /* mi = -m^(-1) mod radix */
2651 _nx_crypto_huge_number_inverse_modulus(&m0, &radix, &mi, scratch);
2652 mm_buffer[0] = (HN_UBASE)(HN_RADIX - mm_buffer[0]);
2653
2654 /* Set buffers. */
2655 /* Buffer usage: 2 * buffer_size of m + 8 */
2656 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&xx, scratch, m -> nx_crypto_huge_buffer_size + sizeof(HN_UBASE));
2657 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&temp, scratch, m -> nx_crypto_huge_buffer_size + sizeof(HN_UBASE));
2658 NX_CRYPTO_HUGE_NUMBER_INITIALIZE_DIGIT(&digit, &digit_value, 1);
2659
2660
2661 /* x' = radix ^ m_len mod m */
2662 m_len = m -> nx_crypto_huge_number_size;
2663 val = temp.nx_crypto_huge_number_data;
2664 NX_CRYPTO_MEMSET(val, 0, (m_len << HN_SIZE_SHIFT));
2665 temp.nx_crypto_huge_number_size = m_len + 1;
2666 val[m_len] = 1;
2667 _nx_crypto_huge_number_modulus(&temp, m);
2668
2669 /* xx = mont(x, radix ^ (2 * m_len) mod m)*/
2670 _nx_crypto_huge_number_square(&temp, result);
2671 _nx_crypto_huge_number_modulus(result, m);
2672 _nx_crypto_huge_number_mont(m, mm_buffer[0], x, result, &xx);
2673
2674 /* result = x' */
2675 NX_CRYPTO_HUGE_NUMBER_COPY(result, &temp);
2676
2677 /* Clear out the result since we need it to start with a simple value. */
2678
2679 operand = result;
2680 temp_result = &temp;
2681
2682 exp_size = e -> nx_crypto_huge_number_size;
2683 val = e -> nx_crypto_huge_number_data + (exp_size - 1);
2684
2685 /* Loop through the bits of the exponent. For each bit set, multiply the result by the running square. */
2686 for (; (ULONG)val >= (ULONG)(e -> nx_crypto_huge_number_data); val--)
2687 {
2688 /* Current byte in the exponent determines whether we multiply or not. */
2689 cur_block = *val;
2690
2691 /* Loop over the bits in the current byte to see whether we add or not. */
2692 for (bit = 0; bit < HN_SHIFT; bit++)
2693 {
2694
2695 /* A non-zero bit means we need to multiply. */
2696 if (cur_block & (1u << (NX_CRYPTO_HUGE_NUMBER_BITS - (1 + bit))))
2697 {
2698
2699 /* result = mont(result, result) */
2700 _nx_crypto_huge_number_mont(m, mm_buffer[0], operand, operand, temp_result);
2701
2702 /* result = mont(result, xx) */
2703 _nx_crypto_huge_number_mont(m, mm_buffer[0], temp_result, &xx, operand);
2704 }
2705 else
2706 {
2707
2708 /* result = mont(result, result) */
2709 _nx_crypto_huge_number_mont(m, mm_buffer[0], operand, operand, temp_result);
2710 temp_swap = temp_result;
2711 temp_result = operand;
2712 operand = temp_swap;
2713 }
2714 }
2715 }
2716
2717 /* result = mont(result, 1) */
2718 _nx_crypto_huge_number_mont(m, mm_buffer[0], &digit, operand, temp_result);
2719 if (temp_result != result)
2720 {
2721 NX_CRYPTO_HUGE_NUMBER_COPY(result, &temp);
2722 }
2723 }
2724
2725 /**************************************************************************/
2726 /* */
2727 /* FUNCTION RELEASE */
2728 /* */
2729 /* _nx_crypto_huge_number_crt_power_modulus PORTABLE C */
2730 /* 6.1 */
2731 /* AUTHOR */
2732 /* */
2733 /* Timothy Stapko, Microsoft Corporation */
2734 /* */
2735 /* DESCRIPTION */
2736 /* */
2737 /* This function raises a huge number to the power of a second huge */
2738 /* number using a fifth huge number as a modulus. The result is placed */
2739 /* in a sixth huge number. Montgomery reduction and Chinese Remainder */
2740 /* Theorem are used. */
2741 /* */
2742 /* Requirement: */
2743 /* 1. m = p * q */
2744 /* 2. p and q are primes */
2745 /* 3. scratch is required to be no less than 4 times of buffer size */
2746 /* of m plus 24 bytes. */
2747 /* */
2748 /* INPUT */
2749 /* */
2750 /* x Number being exponentiated */
2751 /* e Exponent number */
2752 /* p Prime number p */
2753 /* q Prime number q */
2754 /* m Modulus number */
2755 /* result Result buffer */
2756 /* scratch Buffer used to hold */
2757 /* intermediate data */
2758 /* */
2759 /* OUTPUT */
2760 /* */
2761 /* None */
2762 /* */
2763 /* CALLS */
2764 /* */
2765 /* NX_CRYPTO_HUGE_NUMBER_COPY Copy huge number */
2766 /* NX_CRYPTO_HUGE_NUMBER_INITIALIZE Initialize the buffer of */
2767 /* huge number */
2768 /* NX_CRYPTO_HUGE_NUMBER_SET_DIGIT Set value of huge number */
2769 /* between 0 and (HN_RADIX - 1)*/
2770 /* _nx_crypto_huge_number_add Calculate addition for */
2771 /* huge numbers */
2772 /* _nx_crypto_huge_number_subtract Calculate subtraction for */
2773 /* huge numbers */
2774 /* _nx_crypto_huge_number_multiply Multiply two huge numbers */
2775 /* _nx_crypto_huge_number_modulus Perform a modulus operation */
2776 /* _nx_crypto_huge_number_inverse_modulus_prime */
2777 /* Perform an inverse modulus */
2778 /* operation for prime number */
2779 /* _nx_crypto_huge_number_mont_power_modulus */
2780 /* Raise a huge number for */
2781 /* montgomery reduction */
2782 /* */
2783 /* CALLED BY */
2784 /* */
2785 /* _nx_crypto_rsa_operation Perform an RSA operation */
2786 /* */
2787 /* RELEASE HISTORY */
2788 /* */
2789 /* DATE NAME DESCRIPTION */
2790 /* */
2791 /* 05-19-2020 Timothy Stapko Initial Version 6.0 */
2792 /* 09-30-2020 Timothy Stapko Modified comment(s), */
2793 /* resulting in version 6.1 */
2794 /* */
2795 /**************************************************************************/
_nx_crypto_huge_number_crt_power_modulus(NX_CRYPTO_HUGE_NUMBER * x,NX_CRYPTO_HUGE_NUMBER * e,NX_CRYPTO_HUGE_NUMBER * p,NX_CRYPTO_HUGE_NUMBER * q,NX_CRYPTO_HUGE_NUMBER * m,NX_CRYPTO_HUGE_NUMBER * result,HN_UBASE * scratch)2796 NX_CRYPTO_KEEP VOID _nx_crypto_huge_number_crt_power_modulus(NX_CRYPTO_HUGE_NUMBER *x,
2797 NX_CRYPTO_HUGE_NUMBER *e,
2798 NX_CRYPTO_HUGE_NUMBER *p,
2799 NX_CRYPTO_HUGE_NUMBER *q,
2800 NX_CRYPTO_HUGE_NUMBER *m,
2801 NX_CRYPTO_HUGE_NUMBER *result,
2802 HN_UBASE *scratch)
2803 {
2804 NX_CRYPTO_HUGE_NUMBER *ep, *eq, *xp, *xq, *m1, *m2;
2805 NX_CRYPTO_HUGE_NUMBER pi, qi;
2806 NX_CRYPTO_HUGE_NUMBER temp1, temp2, temp3;
2807 NX_CRYPTO_HUGE_NUMBER digit;
2808 HN_UBASE digit_value;
2809
2810 /*****************************************
2811 * ep = e mod (p - 1)
2812 * xp = x mod p
2813 * m1 = xp ^ ep mod p
2814 *
2815 * eq = e mod (q - 1)
2816 * xq = x mod q
2817 * m2 = xq ^ eq mod q
2818 *
2819 * pi = p ^ (-1) mod q
2820 * qi = q ^ (-1) mod p
2821 *
2822 * r = (m1 * qi * q + m2 * pi * p) mod m
2823 ****************************************/
2824
2825 /* Buffer usage: 1 * buffer size of m */
2826 /* temp1 is used to hold the result of pi * p * m2. So twice of m buffer size is used. */
2827 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&pi, scratch, p -> nx_crypto_huge_buffer_size);
2828 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&qi, scratch, q -> nx_crypto_huge_buffer_size);
2829
2830 /* qi = q ^ (-1) mod p */
2831 /* pi = p ^ (-1) mod q */
2832 /* Buffer usage: 2 * buffer_size of m + 24 bytes */
2833 _nx_crypto_huge_number_inverse_modulus_prime(q, p, &qi, scratch);
2834 _nx_crypto_huge_number_inverse_modulus_prime(p, q, &pi, scratch);
2835
2836 /* Buffer usage: 2 * buffer size of m */
2837 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&temp1, scratch, m -> nx_crypto_huge_buffer_size);
2838 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&temp2, scratch, p -> nx_crypto_huge_buffer_size);
2839 NX_CRYPTO_HUGE_NUMBER_INITIALIZE(&temp3, scratch, p -> nx_crypto_huge_buffer_size);
2840 NX_CRYPTO_HUGE_NUMBER_INITIALIZE_DIGIT(&digit, &digit_value, 1);
2841
2842 /* In the following calculation, buffer of temp3 is used by temp2. */
2843 /* ep = e mod (p - 1) */
2844 ep = &temp2;
2845 NX_CRYPTO_HUGE_NUMBER_COPY(ep, e);
2846 NX_CRYPTO_HUGE_NUMBER_COPY(&temp1, p);
2847 _nx_crypto_huge_number_subtract(&temp1, &digit);
2848 _nx_crypto_huge_number_modulus(ep, &temp1);
2849
2850 /* xp = x mod p */
2851 xp = &temp3;
2852 NX_CRYPTO_HUGE_NUMBER_COPY(xp, x);
2853 _nx_crypto_huge_number_modulus(xp, p);
2854
2855 /* m1 = xp ^ ep mod p */
2856 m1 = &temp1;
2857
2858 /* Buffer usage: 1 * buffer_size of m + 8 bytes */
2859 _nx_crypto_huge_number_mont_power_modulus(xp, ep, p, m1, scratch);
2860
2861 /* m1 * qi * q */
2862 _nx_crypto_huge_number_multiply(&qi, m1, &temp3);
2863 _nx_crypto_huge_number_multiply(&temp3, q, result);
2864
2865
2866 /* In the following calculation, buffer of temp3 is used by temp2. */
2867 /* eq = e mod (q - 1) */
2868 eq = &temp2;
2869 NX_CRYPTO_HUGE_NUMBER_COPY(eq, e);
2870 NX_CRYPTO_HUGE_NUMBER_COPY(&temp1, q);
2871 _nx_crypto_huge_number_subtract(&temp1, &digit);
2872 _nx_crypto_huge_number_modulus(eq, &temp1);
2873
2874 /* xq = x mod q */
2875 xq = &temp3;
2876 NX_CRYPTO_HUGE_NUMBER_COPY(xq, x);
2877 _nx_crypto_huge_number_modulus(xq, q);
2878
2879 /* m2 = xq ^ eq mod q */
2880 m2 = &temp1;
2881
2882 /* Buffer usage: 1 * buffer_size of m + 8 bytes */
2883 _nx_crypto_huge_number_mont_power_modulus(xq, eq, q, m2, scratch);
2884
2885 /* pi * p * m2 */
2886 _nx_crypto_huge_number_multiply(&pi, m2, &temp3);
2887
2888 /* Buffer of temp2 is not used anymore. It is used by temp1.
2889 * So buffer length of temp1 is 1.5 * buffer length of m.
2890 * It is large enough to hold the result of pi * p * m2 */
2891 _nx_crypto_huge_number_multiply(p, &temp3, &temp1);
2892
2893
2894 /* r = (m1 * qi * q + m2 * pi * p) mod m */
2895 _nx_crypto_huge_number_add(result, &temp1);
2896 _nx_crypto_huge_number_modulus(result, m);
2897 }
2898
2899
