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