NCBI C++ ToolKit
bignum.c
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /*
2  * Multi-precision integer library
3  *
4  * Copyright The Mbed TLS Contributors
5  * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6  */
7 
8 /*
9  * The following sources were referenced in the design of this Multi-precision
10  * Integer library:
11  *
12  * [1] Handbook of Applied Cryptography - 1997
13  * Menezes, van Oorschot and Vanstone
14  *
15  * [2] Multi-Precision Math
16  * Tom St Denis
17  * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
18  *
19  * [3] GNU Multi-Precision Arithmetic Library
20  * https://gmplib.org/manual/index.html
21  *
22  */
23 
24 #include "common.h"
25 
26 #if defined(MBEDTLS_BIGNUM_C)
27 
28 #include "mbedtls/bignum.h"
29 #include "bignum_core.h"
30 #include "bn_mul.h"
31 #include "mbedtls/platform_util.h"
32 #include "mbedtls/error.h"
33 #include "constant_time_internal.h"
34 
35 #include <limits.h>
36 #include <string.h>
37 
38 #include "mbedtls/platform.h"
39 
40 
41 
42 /*
43  * Conditionally select an MPI sign in constant time.
44  * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid
45  * values.)
46  */
47 static inline signed short mbedtls_ct_mpi_sign_if(mbedtls_ct_condition_t cond,
48  signed short sign1, signed short sign2)
49 {
50  return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1;
51 }
52 
53 /*
54  * Compare signed values in constant time
55  */
57  const mbedtls_mpi *Y,
58  unsigned *ret)
59 {
60  mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result;
61 
62  if (X->n != Y->n) {
64  }
65 
66  /*
67  * Set N_is_negative to MBEDTLS_CT_FALSE if N >= 0, MBEDTLS_CT_TRUE if N < 0.
68  * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
69  */
70  X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1);
71  Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1);
72 
73  /*
74  * If the signs are different, then the positive operand is the bigger.
75  * That is if X is negative (X_is_negative == 1), then X < Y is true and it
76  * is false if X is positive (X_is_negative == 0).
77  */
78  different_sign = mbedtls_ct_bool_ne(X_is_negative, Y_is_negative); // true if different sign
79  result = mbedtls_ct_bool_and(different_sign, X_is_negative);
80 
81  /*
82  * Assuming signs are the same, compare X and Y. We switch the comparison
83  * order if they are negative so that we get the right result, regardles of
84  * sign.
85  */
86 
87  /* This array is used to conditionally swap the pointers in const time */
88  void * const p[2] = { X->p, Y->p };
89  size_t i = mbedtls_ct_size_if_else_0(X_is_negative, 1);
91 
92  /*
93  * Store in result iff the signs are the same (i.e., iff different_sign == false). If
94  * the signs differ, result has already been set, so we don't change it.
95  */
97  mbedtls_ct_bool_and(mbedtls_ct_bool_not(different_sign), lt));
98 
100 
101  return 0;
102 }
103 
104 /*
105  * Conditionally assign X = Y, without leaking information
106  * about whether the assignment was made or not.
107  * (Leaking information about the respective sizes of X and Y is ok however.)
108  */
109 #if defined(_MSC_VER) && defined(MBEDTLS_PLATFORM_IS_WINDOWS_ON_ARM64) && \
110  (_MSC_FULL_VER < 193131103)
111 /*
112  * MSVC miscompiles this function if it's inlined prior to Visual Studio 2022 version 17.1. See:
113  * https://developercommunity.visualstudio.com/t/c-compiler-miscompiles-part-of-mbedtls-library-on/1646989
114  */
115 __declspec(noinline)
116 #endif
118  const mbedtls_mpi *Y,
119  unsigned char assign)
120 {
121  int ret = 0;
122 
124 
125  {
126  mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign);
127 
128  X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s);
129 
130  mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign);
131 
132  mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign);
133  for (size_t i = Y->n; i < X->n; i++) {
134  X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]);
135  }
136  }
137 
138 cleanup:
139  return ret;
140 }
141 
142 /*
143  * Conditionally swap X and Y, without leaking information
144  * about whether the swap was made or not.
145  * Here it is not ok to simply swap the pointers, which would lead to
146  * different memory access patterns when X and Y are used afterwards.
147  */
149  mbedtls_mpi *Y,
150  unsigned char swap)
151 {
152  int ret = 0;
153  int s;
154 
155  if (X == Y) {
156  return 0;
157  }
158 
160 
163 
164  s = X->s;
165  X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s);
166  Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s);
167 
168  mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap);
169 
170 cleanup:
171  return ret;
172 }
173 
174 /* Implementation that should never be optimized out by the compiler */
175 #define mbedtls_mpi_zeroize_and_free(v, n) mbedtls_zeroize_and_free(v, ciL * (n))
176 
177 /*
178  * Initialize one MPI
179  */
181 {
182  X->s = 1;
183  X->n = 0;
184  X->p = NULL;
185 }
186 
187 /*
188  * Unallocate one MPI
189  */
191 {
192  if (X == NULL) {
193  return;
194  }
195 
196  if (X->p != NULL) {
197  mbedtls_mpi_zeroize_and_free(X->p, X->n);
198  }
199 
200  X->s = 1;
201  X->n = 0;
202  X->p = NULL;
203 }
204 
205 /*
206  * Enlarge to the specified number of limbs
207  */
208 int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
209 {
210  mbedtls_mpi_uint *p;
211 
212  if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
214  }
215 
216  if (X->n < nblimbs) {
217  if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL)) == NULL) {
219  }
220 
221  if (X->p != NULL) {
222  memcpy(p, X->p, X->n * ciL);
223  mbedtls_mpi_zeroize_and_free(X->p, X->n);
224  }
225 
226  /* nblimbs fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
227  * fits, and we've checked that nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
228  X->n = (unsigned short) nblimbs;
229  X->p = p;
230  }
231 
232  return 0;
233 }
234 
235 /*
236  * Resize down as much as possible,
237  * while keeping at least the specified number of limbs
238  */
239 int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
240 {
241  mbedtls_mpi_uint *p;
242  size_t i;
243 
244  if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
246  }
247 
248  /* Actually resize up if there are currently fewer than nblimbs limbs. */
249  if (X->n <= nblimbs) {
250  return mbedtls_mpi_grow(X, nblimbs);
251  }
252  /* After this point, then X->n > nblimbs and in particular X->n > 0. */
253 
254  for (i = X->n - 1; i > 0; i--) {
255  if (X->p[i] != 0) {
256  break;
257  }
258  }
259  i++;
260 
261  if (i < nblimbs) {
262  i = nblimbs;
263  }
264 
265  if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL) {
267  }
268 
269  if (X->p != NULL) {
270  memcpy(p, X->p, i * ciL);
271  mbedtls_mpi_zeroize_and_free(X->p, X->n);
272  }
273 
274  /* i fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
275  * fits, and we've checked that i <= nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
276  X->n = (unsigned short) i;
277  X->p = p;
278 
279  return 0;
280 }
281 
282 /* Resize X to have exactly n limbs and set it to 0. */
283 static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
284 {
285  if (limbs == 0) {
286  mbedtls_mpi_free(X);
287  return 0;
288  } else if (X->n == limbs) {
289  memset(X->p, 0, limbs * ciL);
290  X->s = 1;
291  return 0;
292  } else {
293  mbedtls_mpi_free(X);
294  return mbedtls_mpi_grow(X, limbs);
295  }
296 }
297 
298 /*
299  * Copy the contents of Y into X.
300  *
301  * This function is not constant-time. Leading zeros in Y may be removed.
302  *
303  * Ensure that X does not shrink. This is not guaranteed by the public API,
304  * but some code in the bignum module might still rely on this property.
305  */
306 int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
307 {
308  int ret = 0;
309  size_t i;
310 
311  if (X == Y) {
312  return 0;
313  }
314 
315  if (Y->n == 0) {
316  if (X->n != 0) {
317  X->s = 1;
318  memset(X->p, 0, X->n * ciL);
319  }
320  return 0;
321  }
322 
323  for (i = Y->n - 1; i > 0; i--) {
324  if (Y->p[i] != 0) {
325  break;
326  }
327  }
328  i++;
329 
330  X->s = Y->s;
331 
332  if (X->n < i) {
334  } else {
335  memset(X->p + i, 0, (X->n - i) * ciL);
336  }
337 
338  memcpy(X->p, Y->p, i * ciL);
339 
340 cleanup:
341 
342  return ret;
343 }
344 
345 /*
346  * Swap the contents of X and Y
347  */
349 {
350  mbedtls_mpi T;
351 
352  memcpy(&T, X, sizeof(mbedtls_mpi));
353  memcpy(X, Y, sizeof(mbedtls_mpi));
354  memcpy(Y, &T, sizeof(mbedtls_mpi));
355 }
356 
357 static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
358 {
359  if (z >= 0) {
360  return z;
361  }
362  /* Take care to handle the most negative value (-2^(biL-1)) correctly.
363  * A naive -z would have undefined behavior.
364  * Write this in a way that makes popular compilers happy (GCC, Clang,
365  * MSVC). */
366  return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
367 }
368 
369 /* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
370  * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
371 #define TO_SIGN(x) ((mbedtls_mpi_sint) (((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1)
372 
373 /*
374  * Set value from integer
375  */
377 {
379 
381  memset(X->p, 0, X->n * ciL);
382 
383  X->p[0] = mpi_sint_abs(z);
384  X->s = TO_SIGN(z);
385 
386 cleanup:
387 
388  return ret;
389 }
390 
391 /*
392  * Get a specific bit
393  */
394 int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
395 {
396  if (X->n * biL <= pos) {
397  return 0;
398  }
399 
400  return (X->p[pos / biL] >> (pos % biL)) & 0x01;
401 }
402 
403 /*
404  * Set a bit to a specific value of 0 or 1
405  */
406 int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
407 {
408  int ret = 0;
409  size_t off = pos / biL;
410  size_t idx = pos % biL;
411 
412  if (val != 0 && val != 1) {
414  }
415 
416  if (X->n * biL <= pos) {
417  if (val == 0) {
418  return 0;
419  }
420 
421  MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1));
422  }
423 
424  X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx);
425  X->p[off] |= (mbedtls_mpi_uint) val << idx;
426 
427 cleanup:
428 
429  return ret;
430 }
431 
432 /*
433  * Return the number of less significant zero-bits
434  */
435 size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
436 {
437  size_t i;
438 
439 #if defined(__has_builtin)
440 #if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz)
441  #define mbedtls_mpi_uint_ctz __builtin_ctz
442 #elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl)
443  #define mbedtls_mpi_uint_ctz __builtin_ctzl
444 #elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll)
445  #define mbedtls_mpi_uint_ctz __builtin_ctzll
446 #endif
447 #endif
448 
449 #if defined(mbedtls_mpi_uint_ctz)
450  for (i = 0; i < X->n; i++) {
451  if (X->p[i] != 0) {
452  return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
453  }
454  }
455 #else
456  size_t count = 0;
457  for (i = 0; i < X->n; i++) {
458  for (size_t j = 0; j < biL; j++, count++) {
459  if (((X->p[i] >> j) & 1) != 0) {
460  return count;
461  }
462  }
463  }
464 #endif
465 
466  return 0;
467 }
468 
469 /*
470  * Return the number of bits
471  */
472 size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
473 {
474  return mbedtls_mpi_core_bitlen(X->p, X->n);
475 }
476 
477 /*
478  * Return the total size in bytes
479  */
480 size_t mbedtls_mpi_size(const mbedtls_mpi *X)
481 {
482  return (mbedtls_mpi_bitlen(X) + 7) >> 3;
483 }
484 
485 /*
486  * Convert an ASCII character to digit value
487  */
488 static int mpi_get_digit(mbedtls_mpi_uint *d, int radix, char c)
489 {
490  *d = 255;
491 
492  if (c >= 0x30 && c <= 0x39) {
493  *d = c - 0x30;
494  }
495  if (c >= 0x41 && c <= 0x46) {
496  *d = c - 0x37;
497  }
498  if (c >= 0x61 && c <= 0x66) {
499  *d = c - 0x57;
500  }
501 
502  if (*d >= (mbedtls_mpi_uint) radix) {
504  }
505 
506  return 0;
507 }
508 
509 /*
510  * Import from an ASCII string
511  */
512 int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
513 {
515  size_t i, j, slen, n;
516  int sign = 1;
518  mbedtls_mpi T;
519 
520  if (radix < 2 || radix > 16) {
522  }
523 
525 
526  if (s[0] == 0) {
527  mbedtls_mpi_free(X);
528  return 0;
529  }
530 
531  if (s[0] == '-') {
532  ++s;
533  sign = -1;
534  }
535 
536  slen = strlen(s);
537 
538  if (radix == 16) {
539  if (slen > SIZE_MAX >> 2) {
541  }
542 
543  n = BITS_TO_LIMBS(slen << 2);
544 
547 
548  for (i = slen, j = 0; i > 0; i--, j++) {
549  MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1]));
550  X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2);
551  }
552  } else {
554 
555  for (i = 0; i < slen; i++) {
556  MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i]));
559  }
560  }
561 
562  if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) {
563  X->s = -1;
564  }
565 
566 cleanup:
567 
569 
570  return ret;
571 }
572 
573 /*
574  * Helper to write the digits high-order first.
575  */
576 static int mpi_write_hlp(mbedtls_mpi *X, int radix,
577  char **p, const size_t buflen)
578 {
581  size_t length = 0;
582  char *p_end = *p + buflen;
583 
584  do {
585  if (length >= buflen) {
587  }
588 
591  /*
592  * Write the residue in the current position, as an ASCII character.
593  */
594  if (r < 0xA) {
595  *(--p_end) = (char) ('0' + r);
596  } else {
597  *(--p_end) = (char) ('A' + (r - 0xA));
598  }
599 
600  length++;
601  } while (mbedtls_mpi_cmp_int(X, 0) != 0);
602 
603  memmove(*p, p_end, length);
604  *p += length;
605 
606 cleanup:
607 
608  return ret;
609 }
610 
611 /*
612  * Export into an ASCII string
613  */
614 int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix,
615  char *buf, size_t buflen, size_t *olen)
616 {
617  int ret = 0;
618  size_t n;
619  char *p;
620  mbedtls_mpi T;
621 
622  if (radix < 2 || radix > 16) {
624  }
625 
626  n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */
627  if (radix >= 4) {
628  n >>= 1; /* Number of 4-adic digits necessary to present
629  * `n`. If radix > 4, this might be a strict
630  * overapproximation of the number of
631  * radix-adic digits needed to present `n`. */
632  }
633  if (radix >= 16) {
634  n >>= 1; /* Number of hexadecimal digits necessary to
635  * present `n`. */
636 
637  }
638  n += 1; /* Terminating null byte */
639  n += 1; /* Compensate for the divisions above, which round down `n`
640  * in case it's not even. */
641  n += 1; /* Potential '-'-sign. */
642  n += (n & 1); /* Make n even to have enough space for hexadecimal writing,
643  * which always uses an even number of hex-digits. */
644 
645  if (buflen < n) {
646  *olen = n;
648  }
649 
650  p = buf;
652 
653  if (X->s == -1) {
654  *p++ = '-';
655  buflen--;
656  }
657 
658  if (radix == 16) {
659  int c;
660  size_t i, j, k;
661 
662  for (i = X->n, k = 0; i > 0; i--) {
663  for (j = ciL; j > 0; j--) {
664  c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF;
665 
666  if (c == 0 && k == 0 && (i + j) != 2) {
667  continue;
668  }
669 
670  *(p++) = "0123456789ABCDEF" [c / 16];
671  *(p++) = "0123456789ABCDEF" [c % 16];
672  k = 1;
673  }
674  }
675  } else {
677 
678  if (T.s == -1) {
679  T.s = 1;
680  }
681 
682  MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen));
683  }
684 
685  *p++ = '\0';
686  *olen = (size_t) (p - buf);
687 
688 cleanup:
689 
691 
692  return ret;
693 }
694 
695 #if defined(MBEDTLS_FS_IO)
696 /*
697  * Read X from an opened file
698  */
699 int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin)
700 {
702  size_t slen;
703  char *p;
704  /*
705  * Buffer should have space for (short) label and decimal formatted MPI,
706  * newline characters and '\0'
707  */
709 
710  if (radix < 2 || radix > 16) {
712  }
713 
714  memset(s, 0, sizeof(s));
715  if (fgets(s, sizeof(s) - 1, fin) == NULL) {
717  }
718 
719  slen = strlen(s);
720  if (slen == sizeof(s) - 2) {
722  }
723 
724  if (slen > 0 && s[slen - 1] == '\n') {
725  slen--; s[slen] = '\0';
726  }
727  if (slen > 0 && s[slen - 1] == '\r') {
728  slen--; s[slen] = '\0';
729  }
730 
731  p = s + slen;
732  while (p-- > s) {
733  if (mpi_get_digit(&d, radix, *p) != 0) {
734  break;
735  }
736  }
737 
738  return mbedtls_mpi_read_string(X, radix, p + 1);
739 }
740 
741 /*
742  * Write X into an opened file (or stdout if fout == NULL)
743  */
744 int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout)
745 {
747  size_t n, slen, plen;
748  /*
749  * Buffer should have space for (short) label and decimal formatted MPI,
750  * newline characters and '\0'
751  */
753 
754  if (radix < 2 || radix > 16) {
756  }
757 
758  memset(s, 0, sizeof(s));
759 
760  MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n));
761 
762  if (p == NULL) {
763  p = "";
764  }
765 
766  plen = strlen(p);
767  slen = strlen(s);
768  s[slen++] = '\r';
769  s[slen++] = '\n';
770 
771  if (fout != NULL) {
772  if (fwrite(p, 1, plen, fout) != plen ||
773  fwrite(s, 1, slen, fout) != slen) {
775  }
776  } else {
777  mbedtls_printf("%s%s", p, s);
778  }
779 
780 cleanup:
781 
782  return ret;
783 }
784 #endif /* MBEDTLS_FS_IO */
785 
786 /*
787  * Import X from unsigned binary data, little endian
788  *
789  * This function is guaranteed to return an MPI with exactly the necessary
790  * number of limbs (in particular, it does not skip 0s in the input).
791  */
793  const unsigned char *buf, size_t buflen)
794 {
796  const size_t limbs = CHARS_TO_LIMBS(buflen);
797 
798  /* Ensure that target MPI has exactly the necessary number of limbs */
799  MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
800 
801  MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen));
802 
803 cleanup:
804 
805  /*
806  * This function is also used to import keys. However, wiping the buffers
807  * upon failure is not necessary because failure only can happen before any
808  * input is copied.
809  */
810  return ret;
811 }
812 
813 /*
814  * Import X from unsigned binary data, big endian
815  *
816  * This function is guaranteed to return an MPI with exactly the necessary
817  * number of limbs (in particular, it does not skip 0s in the input).
818  */
819 int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
820 {
822  const size_t limbs = CHARS_TO_LIMBS(buflen);
823 
824  /* Ensure that target MPI has exactly the necessary number of limbs */
825  MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
826 
827  MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
828 
829 cleanup:
830 
831  /*
832  * This function is also used to import keys. However, wiping the buffers
833  * upon failure is not necessary because failure only can happen before any
834  * input is copied.
835  */
836  return ret;
837 }
838 
839 /*
840  * Export X into unsigned binary data, little endian
841  */
843  unsigned char *buf, size_t buflen)
844 {
845  return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen);
846 }
847 
848 /*
849  * Export X into unsigned binary data, big endian
850  */
852  unsigned char *buf, size_t buflen)
853 {
854  return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
855 }
856 
857 /*
858  * Left-shift: X <<= count
859  */
860 int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
861 {
863  size_t i;
864 
865  i = mbedtls_mpi_bitlen(X) + count;
866 
867  if (X->n * biL < i) {
869  }
870 
871  ret = 0;
872 
873  mbedtls_mpi_core_shift_l(X->p, X->n, count);
874 cleanup:
875 
876  return ret;
877 }
878 
879 /*
880  * Right-shift: X >>= count
881  */
882 int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
883 {
884  if (X->n != 0) {
885  mbedtls_mpi_core_shift_r(X->p, X->n, count);
886  }
887  return 0;
888 }
889 
890 /*
891  * Compare unsigned values
892  */
893 int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
894 {
895  size_t i, j;
896 
897  for (i = X->n; i > 0; i--) {
898  if (X->p[i - 1] != 0) {
899  break;
900  }
901  }
902 
903  for (j = Y->n; j > 0; j--) {
904  if (Y->p[j - 1] != 0) {
905  break;
906  }
907  }
908 
909  /* If i == j == 0, i.e. abs(X) == abs(Y),
910  * we end up returning 0 at the end of the function. */
911 
912  if (i > j) {
913  return 1;
914  }
915  if (j > i) {
916  return -1;
917  }
918 
919  for (; i > 0; i--) {
920  if (X->p[i - 1] > Y->p[i - 1]) {
921  return 1;
922  }
923  if (X->p[i - 1] < Y->p[i - 1]) {
924  return -1;
925  }
926  }
927 
928  return 0;
929 }
930 
931 /*
932  * Compare signed values
933  */
934 int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
935 {
936  size_t i, j;
937 
938  for (i = X->n; i > 0; i--) {
939  if (X->p[i - 1] != 0) {
940  break;
941  }
942  }
943 
944  for (j = Y->n; j > 0; j--) {
945  if (Y->p[j - 1] != 0) {
946  break;
947  }
948  }
949 
950  if (i == 0 && j == 0) {
951  return 0;
952  }
953 
954  if (i > j) {
955  return X->s;
956  }
957  if (j > i) {
958  return -Y->s;
959  }
960 
961  if (X->s > 0 && Y->s < 0) {
962  return 1;
963  }
964  if (Y->s > 0 && X->s < 0) {
965  return -1;
966  }
967 
968  for (; i > 0; i--) {
969  if (X->p[i - 1] > Y->p[i - 1]) {
970  return X->s;
971  }
972  if (X->p[i - 1] < Y->p[i - 1]) {
973  return -X->s;
974  }
975  }
976 
977  return 0;
978 }
979 
980 /*
981  * Compare signed values
982  */
984 {
985  mbedtls_mpi Y;
986  mbedtls_mpi_uint p[1];
987 
988  *p = mpi_sint_abs(z);
989  Y.s = TO_SIGN(z);
990  Y.n = 1;
991  Y.p = p;
992 
993  return mbedtls_mpi_cmp_mpi(X, &Y);
994 }
995 
996 /*
997  * Unsigned addition: X = |A| + |B| (HAC 14.7)
998  */
999 int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1000 {
1002  size_t j;
1003  mbedtls_mpi_uint *p;
1004  mbedtls_mpi_uint c;
1005 
1006  if (X == B) {
1007  const mbedtls_mpi *T = A; A = X; B = T;
1008  }
1009 
1010  if (X != A) {
1012  }
1013 
1014  /*
1015  * X must always be positive as a result of unsigned additions.
1016  */
1017  X->s = 1;
1018 
1019  for (j = B->n; j > 0; j--) {
1020  if (B->p[j - 1] != 0) {
1021  break;
1022  }
1023  }
1024 
1025  /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
1026  * and B is 0 (of any size). */
1027  if (j == 0) {
1028  return 0;
1029  }
1030 
1032 
1033  /* j is the number of non-zero limbs of B. Add those to X. */
1034 
1035  p = X->p;
1036 
1037  c = mbedtls_mpi_core_add(p, p, B->p, j);
1038 
1039  p += j;
1040 
1041  /* Now propagate any carry */
1042 
1043  while (c != 0) {
1044  if (j >= X->n) {
1045  MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
1046  p = X->p + j;
1047  }
1048 
1049  *p += c; c = (*p < c); j++; p++;
1050  }
1051 
1052 cleanup:
1053 
1054  return ret;
1055 }
1056 
1057 /*
1058  * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1059  */
1060 int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1061 {
1063  size_t n;
1064  mbedtls_mpi_uint carry;
1065 
1066  for (n = B->n; n > 0; n--) {
1067  if (B->p[n - 1] != 0) {
1068  break;
1069  }
1070  }
1071  if (n > A->n) {
1072  /* B >= (2^ciL)^n > A */
1074  goto cleanup;
1075  }
1076 
1078 
1079  /* Set the high limbs of X to match A. Don't touch the lower limbs
1080  * because X might be aliased to B, and we must not overwrite the
1081  * significant digits of B. */
1082  if (A->n > n && A != X) {
1083  memcpy(X->p + n, A->p + n, (A->n - n) * ciL);
1084  }
1085  if (X->n > A->n) {
1086  memset(X->p + A->n, 0, (X->n - A->n) * ciL);
1087  }
1088 
1089  carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
1090  if (carry != 0) {
1091  /* Propagate the carry through the rest of X. */
1092  carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n);
1093 
1094  /* If we have further carry/borrow, the result is negative. */
1095  if (carry != 0) {
1097  goto cleanup;
1098  }
1099  }
1100 
1101  /* X should always be positive as a result of unsigned subtractions. */
1102  X->s = 1;
1103 
1104 cleanup:
1105  return ret;
1106 }
1107 
1108 /* Common function for signed addition and subtraction.
1109  * Calculate A + B * flip_B where flip_B is 1 or -1.
1110  */
1111 static int add_sub_mpi(mbedtls_mpi *X,
1112  const mbedtls_mpi *A, const mbedtls_mpi *B,
1113  int flip_B)
1114 {
1115  int ret, s;
1116 
1117  s = A->s;
1118  if (A->s * B->s * flip_B < 0) {
1119  int cmp = mbedtls_mpi_cmp_abs(A, B);
1120  if (cmp >= 0) {
1122  /* If |A| = |B|, the result is 0 and we must set the sign bit
1123  * to +1 regardless of which of A or B was negative. Otherwise,
1124  * since |A| > |B|, the sign is the sign of A. */
1125  X->s = cmp == 0 ? 1 : s;
1126  } else {
1128  /* Since |A| < |B|, the sign is the opposite of A. */
1129  X->s = -s;
1130  }
1131  } else {
1133  X->s = s;
1134  }
1135 
1136 cleanup:
1137 
1138  return ret;
1139 }
1140 
1141 /*
1142  * Signed addition: X = A + B
1143  */
1144 int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1145 {
1146  return add_sub_mpi(X, A, B, 1);
1147 }
1148 
1149 /*
1150  * Signed subtraction: X = A - B
1151  */
1152 int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1153 {
1154  return add_sub_mpi(X, A, B, -1);
1155 }
1156 
1157 /*
1158  * Signed addition: X = A + b
1159  */
1161 {
1162  mbedtls_mpi B;
1163  mbedtls_mpi_uint p[1];
1164 
1165  p[0] = mpi_sint_abs(b);
1166  B.s = TO_SIGN(b);
1167  B.n = 1;
1168  B.p = p;
1169 
1170  return mbedtls_mpi_add_mpi(X, A, &B);
1171 }
1172 
1173 /*
1174  * Signed subtraction: X = A - b
1175  */
1177 {
1178  mbedtls_mpi B;
1179  mbedtls_mpi_uint p[1];
1180 
1181  p[0] = mpi_sint_abs(b);
1182  B.s = TO_SIGN(b);
1183  B.n = 1;
1184  B.p = p;
1185 
1186  return mbedtls_mpi_sub_mpi(X, A, &B);
1187 }
1188 
1189 /*
1190  * Baseline multiplication: X = A * B (HAC 14.12)
1191  */
1192 int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1193 {
1195  size_t i, j;
1196  mbedtls_mpi TA, TB;
1197  int result_is_zero = 0;
1198 
1199  mbedtls_mpi_init(&TA);
1200  mbedtls_mpi_init(&TB);
1201 
1202  if (X == A) {
1203  MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
1204  }
1205  if (X == B) {
1206  MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
1207  }
1208 
1209  for (i = A->n; i > 0; i--) {
1210  if (A->p[i - 1] != 0) {
1211  break;
1212  }
1213  }
1214  if (i == 0) {
1215  result_is_zero = 1;
1216  }
1217 
1218  for (j = B->n; j > 0; j--) {
1219  if (B->p[j - 1] != 0) {
1220  break;
1221  }
1222  }
1223  if (j == 0) {
1224  result_is_zero = 1;
1225  }
1226 
1229 
1230  mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j);
1231 
1232  /* If the result is 0, we don't shortcut the operation, which reduces
1233  * but does not eliminate side channels leaking the zero-ness. We do
1234  * need to take care to set the sign bit properly since the library does
1235  * not fully support an MPI object with a value of 0 and s == -1. */
1236  if (result_is_zero) {
1237  X->s = 1;
1238  } else {
1239  X->s = A->s * B->s;
1240  }
1241 
1242 cleanup:
1243 
1245 
1246  return ret;
1247 }
1248 
1249 /*
1250  * Baseline multiplication: X = A * b
1251  */
1253 {
1254  size_t n = A->n;
1255  while (n > 0 && A->p[n - 1] == 0) {
1256  --n;
1257  }
1258 
1259  /* The general method below doesn't work if b==0. */
1260  if (b == 0 || n == 0) {
1261  return mbedtls_mpi_lset(X, 0);
1262  }
1263 
1264  /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
1266  /* In general, A * b requires 1 limb more than b. If
1267  * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1268  * number of limbs as A and the call to grow() is not required since
1269  * copy() will take care of the growth if needed. However, experimentally,
1270  * making the call to grow() unconditional causes slightly fewer
1271  * calls to calloc() in ECP code, presumably because it reuses the
1272  * same mpi for a while and this way the mpi is more likely to directly
1273  * grow to its final size.
1274  *
1275  * Note that calculating A*b as 0 + A*b doesn't work as-is because
1276  * A,X can be the same. */
1279  mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
1280 
1281 cleanup:
1282  return ret;
1283 }
1284 
1285 /*
1286  * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1287  * mbedtls_mpi_uint divisor, d
1288  */
1289 static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1,
1290  mbedtls_mpi_uint u0,
1291  mbedtls_mpi_uint d,
1293 {
1294 #if defined(MBEDTLS_HAVE_UDBL)
1295  mbedtls_t_udbl dividend, quotient;
1296 #else
1297  const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1298  const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1;
1299  mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1300  mbedtls_mpi_uint u0_msw, u0_lsw;
1301  size_t s;
1302 #endif
1303 
1304  /*
1305  * Check for overflow
1306  */
1307  if (0 == d || u1 >= d) {
1308  if (r != NULL) {
1309  *r = ~(mbedtls_mpi_uint) 0u;
1310  }
1311 
1312  return ~(mbedtls_mpi_uint) 0u;
1313  }
1314 
1315 #if defined(MBEDTLS_HAVE_UDBL)
1316  dividend = (mbedtls_t_udbl) u1 << biL;
1317  dividend |= (mbedtls_t_udbl) u0;
1318  quotient = dividend / d;
1319  if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) {
1320  quotient = ((mbedtls_t_udbl) 1 << biL) - 1;
1321  }
1322 
1323  if (r != NULL) {
1324  *r = (mbedtls_mpi_uint) (dividend - (quotient * d));
1325  }
1326 
1327  return (mbedtls_mpi_uint) quotient;
1328 #else
1329 
1330  /*
1331  * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1332  * Vol. 2 - Seminumerical Algorithms, Knuth
1333  */
1334 
1335  /*
1336  * Normalize the divisor, d, and dividend, u0, u1
1337  */
1338  s = mbedtls_mpi_core_clz(d);
1339  d = d << s;
1340 
1341  u1 = u1 << s;
1342  u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1));
1343  u0 = u0 << s;
1344 
1345  d1 = d >> biH;
1346  d0 = d & uint_halfword_mask;
1347 
1348  u0_msw = u0 >> biH;
1349  u0_lsw = u0 & uint_halfword_mask;
1350 
1351  /*
1352  * Find the first quotient and remainder
1353  */
1354  q1 = u1 / d1;
1355  r0 = u1 - d1 * q1;
1356 
1357  while (q1 >= radix || (q1 * d0 > radix * r0 + u0_msw)) {
1358  q1 -= 1;
1359  r0 += d1;
1360 
1361  if (r0 >= radix) {
1362  break;
1363  }
1364  }
1365 
1366  rAX = (u1 * radix) + (u0_msw - q1 * d);
1367  q0 = rAX / d1;
1368  r0 = rAX - q0 * d1;
1369 
1370  while (q0 >= radix || (q0 * d0 > radix * r0 + u0_lsw)) {
1371  q0 -= 1;
1372  r0 += d1;
1373 
1374  if (r0 >= radix) {
1375  break;
1376  }
1377  }
1378 
1379  if (r != NULL) {
1380  *r = (rAX * radix + u0_lsw - q0 * d) >> s;
1381  }
1382 
1383  quotient = q1 * radix + q0;
1384 
1385  return quotient;
1386 #endif
1387 }
1388 
1389 /*
1390  * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1391  */
1393  const mbedtls_mpi *B)
1394 {
1396  size_t i, n, t, k;
1397  mbedtls_mpi X, Y, Z, T1, T2;
1398  mbedtls_mpi_uint TP2[3];
1399 
1400  if (mbedtls_mpi_cmp_int(B, 0) == 0) {
1402  }
1403 
1405  mbedtls_mpi_init(&T1);
1406  /*
1407  * Avoid dynamic memory allocations for constant-size T2.
1408  *
1409  * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1410  * so nobody increase the size of the MPI and we're safe to use an on-stack
1411  * buffer.
1412  */
1413  T2.s = 1;
1414  T2.n = sizeof(TP2) / sizeof(*TP2);
1415  T2.p = TP2;
1416 
1417  if (mbedtls_mpi_cmp_abs(A, B) < 0) {
1418  if (Q != NULL) {
1420  }
1421  if (R != NULL) {
1423  }
1424  return 0;
1425  }
1426 
1429  X.s = Y.s = 1;
1430 
1431  MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2));
1433  MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2));
1434 
1435  k = mbedtls_mpi_bitlen(&Y) % biL;
1436  if (k < biL - 1) {
1437  k = biL - 1 - k;
1440  } else {
1441  k = 0;
1442  }
1443 
1444  n = X.n - 1;
1445  t = Y.n - 1;
1447 
1448  while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) {
1449  Z.p[n - t]++;
1450  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y));
1451  }
1453 
1454  for (i = n; i > t; i--) {
1455  if (X.p[i] >= Y.p[t]) {
1456  Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u;
1457  } else {
1458  Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1],
1459  Y.p[t], NULL);
1460  }
1461 
1462  T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1463  T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1464  T2.p[2] = X.p[i];
1465 
1466  Z.p[i - t - 1]++;
1467  do {
1468  Z.p[i - t - 1]--;
1469 
1471  T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1472  T1.p[1] = Y.p[t];
1473  MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1]));
1474  } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0);
1475 
1476  MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1]));
1477  MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1478  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1));
1479 
1480  if (mbedtls_mpi_cmp_int(&X, 0) < 0) {
1482  MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1483  MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1));
1484  Z.p[i - t - 1]--;
1485  }
1486  }
1487 
1488  if (Q != NULL) {
1490  Q->s = A->s * B->s;
1491  }
1492 
1493  if (R != NULL) {
1495  X.s = A->s;
1497 
1498  if (mbedtls_mpi_cmp_int(R, 0) == 0) {
1499  R->s = 1;
1500  }
1501  }
1502 
1503 cleanup:
1504 
1506  mbedtls_mpi_free(&T1);
1507  mbedtls_platform_zeroize(TP2, sizeof(TP2));
1508 
1509  return ret;
1510 }
1511 
1512 /*
1513  * Division by int: A = Q * b + R
1514  */
1516  const mbedtls_mpi *A,
1518 {
1519  mbedtls_mpi B;
1520  mbedtls_mpi_uint p[1];
1521 
1522  p[0] = mpi_sint_abs(b);
1523  B.s = TO_SIGN(b);
1524  B.n = 1;
1525  B.p = p;
1526 
1527  return mbedtls_mpi_div_mpi(Q, R, A, &B);
1528 }
1529 
1530 /*
1531  * Modulo: R = A mod B
1532  */
1533 int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
1534 {
1536 
1537  if (mbedtls_mpi_cmp_int(B, 0) < 0) {
1539  }
1540 
1542 
1543  while (mbedtls_mpi_cmp_int(R, 0) < 0) {
1545  }
1546 
1547  while (mbedtls_mpi_cmp_mpi(R, B) >= 0) {
1549  }
1550 
1551 cleanup:
1552 
1553  return ret;
1554 }
1555 
1556 /*
1557  * Modulo: r = A mod b
1558  */
1560 {
1561  size_t i;
1562  mbedtls_mpi_uint x, y, z;
1563 
1564  if (b == 0) {
1566  }
1567 
1568  if (b < 0) {
1570  }
1571 
1572  /*
1573  * handle trivial cases
1574  */
1575  if (b == 1 || A->n == 0) {
1576  *r = 0;
1577  return 0;
1578  }
1579 
1580  if (b == 2) {
1581  *r = A->p[0] & 1;
1582  return 0;
1583  }
1584 
1585  /*
1586  * general case
1587  */
1588  for (i = A->n, y = 0; i > 0; i--) {
1589  x = A->p[i - 1];
1590  y = (y << biH) | (x >> biH);
1591  z = y / b;
1592  y -= z * b;
1593 
1594  x <<= biH;
1595  y = (y << biH) | (x >> biH);
1596  z = y / b;
1597  y -= z * b;
1598  }
1599 
1600  /*
1601  * If A is negative, then the current y represents a negative value.
1602  * Flipping it to the positive side.
1603  */
1604  if (A->s < 0 && y != 0) {
1605  y = b - y;
1606  }
1607 
1608  *r = y;
1609 
1610  return 0;
1611 }
1612 
1614  const mbedtls_mpi *E, const mbedtls_mpi *N,
1615  mbedtls_mpi *prec_RR)
1616 {
1618 
1619  if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
1621  }
1622 
1623  if (mbedtls_mpi_cmp_int(E, 0) < 0) {
1625  }
1626 
1630  }
1631 
1632  /*
1633  * Ensure that the exponent that we are passing to the core is not NULL.
1634  */
1635  if (E->n == 0) {
1636  ret = mbedtls_mpi_lset(X, 1);
1637  return ret;
1638  }
1639 
1640  /*
1641  * Allocate working memory for mbedtls_mpi_core_exp_mod()
1642  */
1643  size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n);
1645  if (T == NULL) {
1647  }
1648 
1649  mbedtls_mpi RR;
1650  mbedtls_mpi_init(&RR);
1651 
1652  /*
1653  * If 1st call, pre-compute R^2 mod N
1654  */
1655  if (prec_RR == NULL || prec_RR->p == NULL) {
1657 
1658  if (prec_RR != NULL) {
1659  *prec_RR = RR;
1660  }
1661  } else {
1662  MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n));
1663  RR = *prec_RR;
1664  }
1665 
1666  /*
1667  * To preserve constness we need to make a copy of A. Using X for this to
1668  * save memory.
1669  */
1671 
1672  /*
1673  * Compensate for negative A (and correct at the end).
1674  */
1675  X->s = 1;
1676 
1677  /*
1678  * Make sure that X is in a form that is safe for consumption by
1679  * the core functions.
1680  *
1681  * - The core functions will not touch the limbs of X above N->n. The
1682  * result will be correct if those limbs are 0, which the mod call
1683  * ensures.
1684  * - Also, X must have at least as many limbs as N for the calls to the
1685  * core functions.
1686  */
1687  if (mbedtls_mpi_cmp_mpi(X, N) >= 0) {
1689  }
1691 
1692  /*
1693  * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod().
1694  */
1695  {
1697  mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T);
1698  mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1699  mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T);
1700  }
1701 
1702  /*
1703  * Correct for negative A.
1704  */
1705  if (A->s == -1 && (E->p[0] & 1) != 0) {
1706  mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n);
1707  X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1);
1708 
1710  }
1711 
1712 cleanup:
1713 
1714  mbedtls_mpi_zeroize_and_free(T, T_limbs);
1715 
1716  if (prec_RR == NULL || prec_RR->p == NULL) {
1717  mbedtls_mpi_free(&RR);
1718  }
1719 
1720  return ret;
1721 }
1722 
1723 /*
1724  * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1725  */
1726 int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
1727 {
1729  size_t lz, lzt;
1730  mbedtls_mpi TA, TB;
1731 
1733 
1736 
1737  lz = mbedtls_mpi_lsb(&TA);
1738  lzt = mbedtls_mpi_lsb(&TB);
1739 
1740  /* The loop below gives the correct result when A==0 but not when B==0.
1741  * So have a special case for B==0. Leverage the fact that we just
1742  * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
1743  * slightly more efficient than cmp_int(). */
1744  if (lzt == 0 && mbedtls_mpi_get_bit(&TB, 0) == 0) {
1745  ret = mbedtls_mpi_copy(G, A);
1746  goto cleanup;
1747  }
1748 
1749  if (lzt < lz) {
1750  lz = lzt;
1751  }
1752 
1753  TA.s = TB.s = 1;
1754 
1755  /* We mostly follow the procedure described in HAC 14.54, but with some
1756  * minor differences:
1757  * - Sequences of multiplications or divisions by 2 are grouped into a
1758  * single shift operation.
1759  * - The procedure in HAC assumes that 0 < TB <= TA.
1760  * - The condition TB <= TA is not actually necessary for correctness.
1761  * TA and TB have symmetric roles except for the loop termination
1762  * condition, and the shifts at the beginning of the loop body
1763  * remove any significance from the ordering of TA vs TB before
1764  * the shifts.
1765  * - If TA = 0, the loop goes through 0 iterations and the result is
1766  * correctly TB.
1767  * - The case TB = 0 was short-circuited above.
1768  *
1769  * For the correctness proof below, decompose the original values of
1770  * A and B as
1771  * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
1772  * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
1773  * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
1774  * and gcd(A',B') is odd or 0.
1775  *
1776  * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
1777  * The code maintains the following invariant:
1778  * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
1779  */
1780 
1781  /* Proof that the loop terminates:
1782  * At each iteration, either the right-shift by 1 is made on a nonzero
1783  * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
1784  * by at least 1, or the right-shift by 1 is made on zero and then
1785  * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
1786  * since in that case TB is calculated from TB-TA with the condition TB>TA).
1787  */
1788  while (mbedtls_mpi_cmp_int(&TA, 0) != 0) {
1789  /* Divisions by 2 preserve the invariant (I). */
1792 
1793  /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
1794  * TA-TB is even so the division by 2 has an integer result.
1795  * Invariant (I) is preserved since any odd divisor of both TA and TB
1796  * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
1797  * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
1798  * divides TA.
1799  */
1800  if (mbedtls_mpi_cmp_mpi(&TA, &TB) >= 0) {
1801  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TA, &TA, &TB));
1803  } else {
1804  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TB, &TB, &TA));
1806  }
1807  /* Note that one of TA or TB is still odd. */
1808  }
1809 
1810  /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
1811  * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
1812  * - If there was at least one loop iteration, then one of TA or TB is odd,
1813  * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
1814  * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
1815  * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
1816  * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
1817  */
1818 
1821 
1822 cleanup:
1823 
1825 
1826  return ret;
1827 }
1828 
1829 /*
1830  * Fill X with size bytes of random.
1831  * The bytes returned from the RNG are used in a specific order which
1832  * is suitable for deterministic ECDSA (see the specification of
1833  * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()).
1834  */
1836  int (*f_rng)(void *, unsigned char *, size_t),
1837  void *p_rng)
1838 {
1840  const size_t limbs = CHARS_TO_LIMBS(size);
1841 
1842  /* Ensure that target MPI has exactly the necessary number of limbs */
1843  MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
1844  if (size == 0) {
1845  return 0;
1846  }
1847 
1848  ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng);
1849 
1850 cleanup:
1851  return ret;
1852 }
1853 
1856  const mbedtls_mpi *N,
1857  int (*f_rng)(void *, unsigned char *, size_t),
1858  void *p_rng)
1859 {
1860  if (min < 0) {
1862  }
1863  if (mbedtls_mpi_cmp_int(N, min) <= 0) {
1865  }
1866 
1867  /* Ensure that target MPI has exactly the same number of limbs
1868  * as the upper bound, even if the upper bound has leading zeros.
1869  * This is necessary for mbedtls_mpi_core_random. */
1870  int ret = mbedtls_mpi_resize_clear(X, N->n);
1871  if (ret != 0) {
1872  return ret;
1873  }
1874 
1875  return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng);
1876 }
1877 
1878 /*
1879  * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1880  */
1881 int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
1882 {
1884  mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1885 
1886  if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
1888  }
1889 
1893 
1895 
1896  if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
1898  goto cleanup;
1899  }
1900 
1902  MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA));
1905 
1910 
1911  do {
1912  while ((TU.p[0] & 1) == 0) {
1914 
1915  if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) {
1916  MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB));
1917  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA));
1918  }
1919 
1922  }
1923 
1924  while ((TV.p[0] & 1) == 0) {
1926 
1927  if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) {
1928  MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB));
1929  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA));
1930  }
1931 
1934  }
1935 
1936  if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) {
1937  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV));
1938  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1));
1939  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2));
1940  } else {
1941  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU));
1942  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1));
1943  MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2));
1944  }
1945  } while (mbedtls_mpi_cmp_int(&TU, 0) != 0);
1946 
1947  while (mbedtls_mpi_cmp_int(&V1, 0) < 0) {
1949  }
1950 
1951  while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) {
1953  }
1954 
1956 
1957 cleanup:
1958 
1962 
1963  return ret;
1964 }
1965 
1966 #if defined(MBEDTLS_GENPRIME)
1967 
1968 /* Gaps between primes, starting at 3. https://oeis.org/A001223 */
1969 static const unsigned char small_prime_gaps[] = {
1970  2, 2, 4, 2, 4, 2, 4, 6,
1971  2, 6, 4, 2, 4, 6, 6, 2,
1972  6, 4, 2, 6, 4, 6, 8, 4,
1973  2, 4, 2, 4, 14, 4, 6, 2,
1974  10, 2, 6, 6, 4, 6, 6, 2,
1975  10, 2, 4, 2, 12, 12, 4, 2,
1976  4, 6, 2, 10, 6, 6, 6, 2,
1977  6, 4, 2, 10, 14, 4, 2, 4,
1978  14, 6, 10, 2, 4, 6, 8, 6,
1979  6, 4, 6, 8, 4, 8, 10, 2,
1980  10, 2, 6, 4, 6, 8, 4, 2,
1981  4, 12, 8, 4, 8, 4, 6, 12,
1982  2, 18, 6, 10, 6, 6, 2, 6,
1983  10, 6, 6, 2, 6, 6, 4, 2,
1984  12, 10, 2, 4, 6, 6, 2, 12,
1985  4, 6, 8, 10, 8, 10, 8, 6,
1986  6, 4, 8, 6, 4, 8, 4, 14,
1987  10, 12, 2, 10, 2, 4, 2, 10,
1988  14, 4, 2, 4, 14, 4, 2, 4,
1989  20, 4, 8, 10, 8, 4, 6, 6,
1990  14, 4, 6, 6, 8, 6, /*reaches 997*/
1991  0 /* the last entry is effectively unused */
1992 };
1993 
1994 /*
1995  * Small divisors test (X must be positive)
1996  *
1997  * Return values:
1998  * 0: no small factor (possible prime, more tests needed)
1999  * 1: certain prime
2000  * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2001  * other negative: error
2002  */
2003 static int mpi_check_small_factors(const mbedtls_mpi *X)
2004 {
2005  int ret = 0;
2006  size_t i;
2008  unsigned p = 3; /* The first odd prime */
2009 
2010  if ((X->p[0] & 1) == 0) {
2012  }
2013 
2014  for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) {
2016  if (r == 0) {
2017  if (mbedtls_mpi_cmp_int(X, p) == 0) {
2018  return 1;
2019  } else {
2021  }
2022  }
2023  }
2024 
2025 cleanup:
2026  return ret;
2027 }
2028 
2029 /*
2030  * Miller-Rabin pseudo-primality test (HAC 4.24)
2031  */
2032 static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds,
2033  int (*f_rng)(void *, unsigned char *, size_t),
2034  void *p_rng)
2035 {
2036  int ret, count;
2037  size_t i, j, k, s;
2038  mbedtls_mpi W, R, T, A, RR;
2039 
2042  mbedtls_mpi_init(&RR);
2043 
2044  /*
2045  * W = |X| - 1
2046  * R = W >> lsb( W )
2047  */
2049  s = mbedtls_mpi_lsb(&W);
2052 
2053  for (i = 0; i < rounds; i++) {
2054  /*
2055  * pick a random A, 1 < A < |X| - 1
2056  */
2057  count = 0;
2058  do {
2059  MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng));
2060 
2061  j = mbedtls_mpi_bitlen(&A);
2062  k = mbedtls_mpi_bitlen(&W);
2063  if (j > k) {
2064  A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1;
2065  }
2066 
2067  if (count++ > 30) {
2069  goto cleanup;
2070  }
2071 
2072  } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 ||
2073  mbedtls_mpi_cmp_int(&A, 1) <= 0);
2074 
2075  /*
2076  * A = A^R mod |X|
2077  */
2078  MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR));
2079 
2080  if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 ||
2081  mbedtls_mpi_cmp_int(&A, 1) == 0) {
2082  continue;
2083  }
2084 
2085  j = 1;
2086  while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) {
2087  /*
2088  * A = A * A mod |X|
2089  */
2092 
2093  if (mbedtls_mpi_cmp_int(&A, 1) == 0) {
2094  break;
2095  }
2096 
2097  j++;
2098  }
2099 
2100  /*
2101  * not prime if A != |X| - 1 or A == 1
2102  */
2103  if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 ||
2104  mbedtls_mpi_cmp_int(&A, 1) == 0) {
2106  break;
2107  }
2108  }
2109 
2110 cleanup:
2113  mbedtls_mpi_free(&RR);
2114 
2115  return ret;
2116 }
2117 
2118 /*
2119  * Pseudo-primality test: small factors, then Miller-Rabin
2120  */
2121 int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds,
2122  int (*f_rng)(void *, unsigned char *, size_t),
2123  void *p_rng)
2124 {
2126  mbedtls_mpi XX;
2127 
2128  XX.s = 1;
2129  XX.n = X->n;
2130  XX.p = X->p;
2131 
2132  if (mbedtls_mpi_cmp_int(&XX, 0) == 0 ||
2133  mbedtls_mpi_cmp_int(&XX, 1) == 0) {
2135  }
2136 
2137  if (mbedtls_mpi_cmp_int(&XX, 2) == 0) {
2138  return 0;
2139  }
2140 
2141  if ((ret = mpi_check_small_factors(&XX)) != 0) {
2142  if (ret == 1) {
2143  return 0;
2144  }
2145 
2146  return ret;
2147  }
2148 
2149  return mpi_miller_rabin(&XX, rounds, f_rng, p_rng);
2150 }
2151 
2152 /*
2153  * Prime number generation
2154  *
2155  * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2156  * be either 1024 bits or 1536 bits long, and flags must contain
2157  * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
2158  */
2159 int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags,
2160  int (*f_rng)(void *, unsigned char *, size_t),
2161  void *p_rng)
2162 {
2163 #ifdef MBEDTLS_HAVE_INT64
2164 // ceil(2^63.5)
2165 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2166 #else
2167 // ceil(2^31.5)
2168 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2169 #endif
2171  size_t k, n;
2172  int rounds;
2174  mbedtls_mpi Y;
2175 
2176  if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) {
2178  }
2179 
2180  mbedtls_mpi_init(&Y);
2181 
2182  n = BITS_TO_LIMBS(nbits);
2183 
2185  /*
2186  * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2187  */
2188  rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 :
2189  (nbits >= 650) ? 4 : (nbits >= 350) ? 8 :
2190  (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27);
2191  } else {
2192  /*
2193  * 2^-100 error probability, number of rounds computed based on HAC,
2194  * fact 4.48
2195  */
2196  rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 :
2197  (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 :
2198  (nbits >= 750) ? 8 : (nbits >= 500) ? 13 :
2199  (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51);
2200  }
2201 
2202  while (1) {
2203  MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng));
2204  /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2205  if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) {
2206  continue;
2207  }
2208 
2209  k = n * biL;
2210  if (k > nbits) {
2211  MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits));
2212  }
2213  X->p[0] |= 1;
2214 
2215  if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) {
2216  ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng);
2217 
2218  if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2219  goto cleanup;
2220  }
2221  } else {
2222  /*
2223  * A necessary condition for Y and X = 2Y + 1 to be prime
2224  * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2225  * Make sure it is satisfied, while keeping X = 3 mod 4
2226  */
2227 
2228  X->p[0] |= 2;
2229 
2231  if (r == 0) {
2233  } else if (r == 1) {
2235  }
2236 
2237  /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2240 
2241  while (1) {
2242  /*
2243  * First, check small factors for X and Y
2244  * before doing Miller-Rabin on any of them
2245  */
2246  if ((ret = mpi_check_small_factors(X)) == 0 &&
2247  (ret = mpi_check_small_factors(&Y)) == 0 &&
2248  (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng))
2249  == 0 &&
2250  (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng))
2251  == 0) {
2252  goto cleanup;
2253  }
2254 
2255  if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2256  goto cleanup;
2257  }
2258 
2259  /*
2260  * Next candidates. We want to preserve Y = (X-1) / 2 and
2261  * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2262  * so up Y by 6 and X by 12.
2263  */
2266  }
2267  }
2268  }
2269 
2270 cleanup:
2271 
2272  mbedtls_mpi_free(&Y);
2273 
2274  return ret;
2275 }
2276 
2277 #endif /* MBEDTLS_GENPRIME */
2278 
2279 #if defined(MBEDTLS_SELF_TEST)
2280 
2281 #define GCD_PAIR_COUNT 3
2282 
2283 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2284 {
2285  { 693, 609, 21 },
2286  { 1764, 868, 28 },
2287  { 768454923, 542167814, 1 }
2288 };
2289 
2290 /*
2291  * Checkup routine
2292  */
2293 int mbedtls_mpi_self_test(int verbose)
2294 {
2295  int ret, i;
2296  mbedtls_mpi A, E, N, X, Y, U, V;
2297 
2300 
2302  "EFE021C2645FD1DC586E69184AF4A31E" \
2303  "D5F53E93B5F123FA41680867BA110131" \
2304  "944FE7952E2517337780CB0DB80E61AA" \
2305  "E7C8DDC6C5C6AADEB34EB38A2F40D5E6"));
2306 
2308  "B2E7EFD37075B9F03FF989C7C5051C20" \
2309  "34D2A323810251127E7BF8625A4F49A5" \
2310  "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2311  "5B5C25763222FEFCCFC38B832366C29E"));
2312 
2314  "0066A198186C18C10B2F5ED9B522752A" \
2315  "9830B69916E535C8F047518A889A43A5" \
2316  "94B6BED27A168D31D4A52F88925AA8F5"));
2317 
2319 
2321  "602AB7ECA597A3D6B56FF9829A5E8B85" \
2322  "9E857EA95A03512E2BAE7391688D264A" \
2323  "A5663B0341DB9CCFD2C4C5F421FEC814" \
2324  "8001B72E848A38CAE1C65F78E56ABDEF" \
2325  "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2326  "ECF677152EF804370C1A305CAF3B5BF1" \
2327  "30879B56C61DE584A0F53A2447A51E"));
2328 
2329  if (verbose != 0) {
2330  mbedtls_printf(" MPI test #1 (mul_mpi): ");
2331  }
2332 
2333  if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2334  if (verbose != 0) {
2335  mbedtls_printf("failed\n");
2336  }
2337 
2338  ret = 1;
2339  goto cleanup;
2340  }
2341 
2342  if (verbose != 0) {
2343  mbedtls_printf("passed\n");
2344  }
2345 
2346  MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N));
2347 
2349  "256567336059E52CAE22925474705F39A94"));
2350 
2352  "6613F26162223DF488E9CD48CC132C7A" \
2353  "0AC93C701B001B092E4E5B9F73BCD27B" \
2354  "9EE50D0657C77F374E903CDFA4C642"));
2355 
2356  if (verbose != 0) {
2357  mbedtls_printf(" MPI test #2 (div_mpi): ");
2358  }
2359 
2360  if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 ||
2361  mbedtls_mpi_cmp_mpi(&Y, &V) != 0) {
2362  if (verbose != 0) {
2363  mbedtls_printf("failed\n");
2364  }
2365 
2366  ret = 1;
2367  goto cleanup;
2368  }
2369 
2370  if (verbose != 0) {
2371  mbedtls_printf("passed\n");
2372  }
2373 
2374  MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL));
2375 
2377  "36E139AEA55215609D2816998ED020BB" \
2378  "BD96C37890F65171D948E9BC7CBAA4D9" \
2379  "325D24D6A3C12710F10A09FA08AB87"));
2380 
2381  if (verbose != 0) {
2382  mbedtls_printf(" MPI test #3 (exp_mod): ");
2383  }
2384 
2385  if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2386  if (verbose != 0) {
2387  mbedtls_printf("failed\n");
2388  }
2389 
2390  ret = 1;
2391  goto cleanup;
2392  }
2393 
2394  if (verbose != 0) {
2395  mbedtls_printf("passed\n");
2396  }
2397 
2399 
2401  "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2402  "C3DBA76456363A10869622EAC2DD84EC" \
2403  "C5B8A74DAC4D09E03B5E0BE779F2DF61"));
2404 
2405  if (verbose != 0) {
2406  mbedtls_printf(" MPI test #4 (inv_mod): ");
2407  }
2408 
2409  if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2410  if (verbose != 0) {
2411  mbedtls_printf("failed\n");
2412  }
2413 
2414  ret = 1;
2415  goto cleanup;
2416  }
2417 
2418  if (verbose != 0) {
2419  mbedtls_printf("passed\n");
2420  }
2421 
2422  if (verbose != 0) {
2423  mbedtls_printf(" MPI test #5 (simple gcd): ");
2424  }
2425 
2426  for (i = 0; i < GCD_PAIR_COUNT; i++) {
2427  MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0]));
2428  MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1]));
2429 
2430  MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y));
2431 
2432  if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) {
2433  if (verbose != 0) {
2434  mbedtls_printf("failed at %d\n", i);
2435  }
2436 
2437  ret = 1;
2438  goto cleanup;
2439  }
2440  }
2441 
2442  if (verbose != 0) {
2443  mbedtls_printf("passed\n");
2444  }
2445 
2446 cleanup:
2447 
2448  if (ret != 0 && verbose != 0) {
2449  mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
2450  }
2451 
2454 
2455  if (verbose != 0) {
2456  mbedtls_printf("\n");
2457  }
2458 
2459  return ret;
2460 }
2461 
2462 #endif /* MBEDTLS_SELF_TEST */
2463 
2464 #endif /* MBEDTLS_BIGNUM_C */
Multi-precision integer library.
#define MBEDTLS_ERR_MPI_INVALID_CHARACTER
There is an invalid character in the digit string.
Definition: bignum.h:28
#define MBEDTLS_MPI_MAX_BITS
Maximum number of bits for usable MPIs.
Definition: bignum.h:76
int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
Import an MPI from an ASCII string.
int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a signed subtraction of MPIs: X = A - B.
int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a signed subtraction of an MPI and an integer: X = A - b.
int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a signed addition of an MPI and an integer: X = A + b.
int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap)
Perform a safe conditional swap which doesn't reveal whether the condition was true or not.
int mbedtls_mpi_read_binary_le(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, little endian.
int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
Enlarge an MPI to the specified number of limbs.
#define MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
The input arguments are not acceptable.
Definition: bignum.h:36
int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *prec_RR)
Perform a sliding-window exponentiation: X = A^E mod N.
int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Miller-Rabin primality test.
int32_t mbedtls_mpi_sint
The signed type corresponding to mbedtls_mpi_uint.
Definition: bignum.h:168
int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
Make a copy of an MPI.
#define MBEDTLS_ERR_MPI_BAD_INPUT_DATA
Bad input parameters to function.
Definition: bignum.h:26
int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
Modify a specific bit in an MPI.
int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a modular reduction with respect to an integer.
@ MBEDTLS_MPI_GEN_PRIME_FLAG_DH
(X-1)/2 is prime too
Definition: bignum.h:1042
@ MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR
lower error rate from 2-80 to 2-128
Definition: bignum.h:1043
#define MBEDTLS_MPI_MAX_LIMBS
Definition: bignum.h:50
size_t mbedtls_mpi_size(const mbedtls_mpi *X)
Return the total size of an MPI value in bytes.
int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, little endian.
#define MBEDTLS_ERR_MPI_FILE_IO_ERROR
An error occurred while reading from or writing to a file.
Definition: bignum.h:24
int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform an unsigned addition of MPIs: X = |A| + |B|.
int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a division with remainder of two MPIs: A = Q * B + R.
int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a signed addition of MPIs: X = A + B.
void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y)
Swap the contents of two MPIs.
int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign)
Perform a safe conditional copy of MPI which doesn't reveal whether the condition was true or not.
int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
Store integer value in MPI.
size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
Return the number of bits up to and including the most significant bit of value 1.
int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
Import an MPI from unsigned big endian binary data.
int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Compare two MPIs.
int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a modular reduction.
#define MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL
The buffer is too small to write to.
Definition: bignum.h:30
int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a division with remainder of an MPI by an integer: A = Q * b + R.
int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an MPI with a number of random bytes.
int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Compare the absolute values of two MPIs.
int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a prime number.
int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
Perform a left-shift on an MPI: X <<= count.
#define MBEDTLS_MPI_RW_BUFFER_SIZE
Definition: bignum.h:98
#define MBEDTLS_ERR_MPI_DIVISION_BY_ZERO
The input argument for division is zero, which is not allowed.
Definition: bignum.h:34
void mbedtls_mpi_init(mbedtls_mpi *X)
Initialize an MPI context.
#define MBEDTLS_ERR_MPI_ALLOC_FAILED
Memory allocation failed.
Definition: bignum.h:38
size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
Return the number of bits of value 0 before the least significant bit of value 1.
int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a multiplication of two MPIs: X = A * B.
uint32_t mbedtls_mpi_uint
The type of machine digits in a bignum, called _limbs_.
Definition: bignum.h:169
#define MBEDTLS_MPI_CHK(f)
Definition: bignum.h:40
int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix, char *buf, size_t buflen, size_t *olen)
Export an MPI to an ASCII string.
#define MBEDTLS_ERR_MPI_NEGATIVE_VALUE
The input arguments are negative or result in illegal output.
Definition: bignum.h:32
int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
This function resizes an MPI downwards, keeping at least the specified number of limbs.
int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
Compute the modular inverse: X = A^-1 mod N.
int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
Get a specific bit from an MPI.
void mbedtls_mpi_free(mbedtls_mpi *X)
This function frees the components of an MPI context.
int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
Perform a multiplication of an MPI with an unsigned integer: X = A * b.
int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned *ret)
Check if an MPI is less than the other in constant time.
int mbedtls_mpi_write_binary(const mbedtls_mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, big endian.
int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
Compare an MPI with an integer.
int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform an unsigned subtraction of MPIs: X = |A| - |B|.
int mbedtls_mpi_random(mbedtls_mpi *X, mbedtls_mpi_sint min, const mbedtls_mpi *N, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a random number uniformly in a range.
int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
Perform a right-shift on an MPI: X >>= count.
int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
Compute the greatest common divisor: G = gcd(A, B)
uint64_t mbedtls_t_udbl
Definition: bignum.h:172
void mbedtls_mpi_core_to_mont_rep(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *N, size_t AN_limbs, mbedtls_mpi_uint mm, const mbedtls_mpi_uint *rr, mbedtls_mpi_uint *T)
Convert an MPI into Montgomery form.
mbedtls_mpi_uint mbedtls_mpi_core_mla(mbedtls_mpi_uint *X, size_t X_limbs, const mbedtls_mpi_uint *A, size_t A_limbs, mbedtls_mpi_uint b)
Perform a fixed-size multiply accumulate operation: X += b * A.
int mbedtls_mpi_core_write_be(const mbedtls_mpi_uint *A, size_t A_limbs, unsigned char *output, size_t output_length)
Export A into unsigned binary data, big-endian.
#define biL
Definition: bignum_core.h:80
void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs, size_t count)
Shift an MPI in-place right by a number of bits.
#define ciL
Core bignum functions.
Definition: bignum_core.h:79
mbedtls_ct_condition_t mbedtls_mpi_core_lt_ct(const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *B, size_t limbs)
Check if one unsigned MPI is less than another in constant time.
mbedtls_mpi_uint mbedtls_mpi_core_sub(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *B, size_t limbs)
Subtract two fixed-size large unsigned integers, returning the borrow.
mbedtls_ct_condition_t mbedtls_mpi_core_check_zero_ct(const mbedtls_mpi_uint *A, size_t limbs)
Determine if a given MPI has the value 0 in constant time with respect to the value (but not with res...
void mbedtls_mpi_core_from_mont_rep(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *N, size_t AN_limbs, mbedtls_mpi_uint mm, mbedtls_mpi_uint *T)
Convert an MPI from Montgomery form.
#define biH
Definition: bignum_core.h:81
int mbedtls_mpi_core_read_be(mbedtls_mpi_uint *X, size_t X_limbs, const unsigned char *input, size_t input_length)
Import X from unsigned binary data, big-endian.
void mbedtls_mpi_core_exp_mod(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *N, size_t AN_limbs, const mbedtls_mpi_uint *E, size_t E_limbs, const mbedtls_mpi_uint *RR, mbedtls_mpi_uint *T)
Perform a modular exponentiation with secret exponent: X = A^E mod N, where A is already in Montgomer...
mbedtls_mpi_uint mbedtls_mpi_core_add(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *B, size_t limbs)
Add two fixed-size large unsigned integers, returning the carry.
void mbedtls_mpi_core_mul(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, size_t A_limbs, const mbedtls_mpi_uint *B, size_t B_limbs)
Perform a known-size multiplication.
void mbedtls_mpi_core_cond_swap(mbedtls_mpi_uint *X, mbedtls_mpi_uint *Y, size_t limbs, mbedtls_ct_condition_t swap)
Perform a safe conditional swap of two MPIs which doesn't reveal whether the swap was done or not.
int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X, const mbedtls_mpi *N)
Calculate the square of the Montgomery constant.
void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs, size_t count)
Shift an MPI in-place left by a number of bits.
void mbedtls_mpi_core_cond_assign(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, size_t limbs, mbedtls_ct_condition_t assign)
Perform a safe conditional copy of an MPI which doesn't reveal whether assignment was done or not.
mbedtls_mpi_uint mbedtls_mpi_core_sub_int(mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, mbedtls_mpi_uint b, size_t limbs)
Subtract unsigned integer from known-size large unsigned integers.
int mbedtls_mpi_core_read_le(mbedtls_mpi_uint *X, size_t X_limbs, const unsigned char *input, size_t input_length)
Import X from unsigned binary data, little-endian.
size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a)
Count leading zero bits in a given integer.
int mbedtls_mpi_core_write_le(const mbedtls_mpi_uint *A, size_t A_limbs, unsigned char *output, size_t output_length)
Export A into unsigned binary data, little-endian.
size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs)
Return the minimum number of bits required to represent the value held in the MPI.
int mbedtls_mpi_core_fill_random(mbedtls_mpi_uint *X, size_t X_limbs, size_t bytes, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an integer with a number of random bytes.
#define BITS_TO_LIMBS(i)
Definition: bignum_core.h:87
#define CHARS_TO_LIMBS(i)
Definition: bignum_core.h:88
mbedtls_mpi_uint mbedtls_mpi_core_montmul_init(const mbedtls_mpi_uint *N)
Calculate initialisation value for fast Montgomery modular multiplication.
size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs)
Returns the number of limbs of working memory required for a call to `mbedtls_mpi_core_exp_mod()`.
int mbedtls_mpi_core_random(mbedtls_mpi_uint *X, mbedtls_mpi_uint min, const mbedtls_mpi_uint *N, size_t limbs, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a random number uniformly in a range.
Multi-precision integer library.
static mbedtls_ct_condition_t mbedtls_ct_bool(mbedtls_ct_uint_t x)
static mbedtls_ct_condition_t mbedtls_ct_bool_or(mbedtls_ct_condition_t x, mbedtls_ct_condition_t y)
static mbedtls_ct_condition_t mbedtls_ct_bool_not(mbedtls_ct_condition_t x)
static mbedtls_ct_condition_t mbedtls_ct_bool_and(mbedtls_ct_condition_t x, mbedtls_ct_condition_t y)
static unsigned mbedtls_ct_uint_if(mbedtls_ct_condition_t condition, unsigned if1, unsigned if0)
static mbedtls_ct_condition_t mbedtls_ct_bool_ne(mbedtls_ct_condition_t x, mbedtls_ct_condition_t y)
static size_t mbedtls_ct_size_if_else_0(mbedtls_ct_condition_t condition, size_t if1)
static unsigned mbedtls_ct_uint_if_else_0(mbedtls_ct_condition_t condition, unsigned if1)
size_t mbedtls_ct_condition_t
Constant-time functions.
static uch flags
#define T(s)
Definition: common.h:230
static void cleanup(void)
Definition: ct_dynamic.c:30
#define G(x, y, z)
Definition: md4.c:179
void swap(NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair1, NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair2)
Definition: ncbimisc.hpp:1508
#define NULL
Definition: ncbistd.hpp:225
#define SIZE_MAX
Definition: ncbistd.hpp:217
#define Z
printf format modifier for size_t
Definition: mdb.c:334
char * buf
int i
yy_size_t n
const struct ncbi::grid::netcache::search::fields::SIZE size
EIPRangeType t
Definition: ncbi_localip.c:101
#define mbedtls_platform_zeroize
#define mbedtls_mpi_write_file
#define mbedtls_mpi_read_file
const double E
T min(T x_, T y_)
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
#define memmove(a, b, c)
This file contains the definitions and functions of the Mbed TLS platform abstraction layer.
#define mbedtls_calloc
Definition: platform.h:167
#define mbedtls_printf
Definition: platform.h:219
Common and shared functions used by multiple modules in the Mbed TLS library.
true_type verbose
Definition: processing.cpp:890
Error to string translation.
#define MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED
This is a bug in the library.
Definition: error.h:100
union __declspec(align(16)) SIMDVec
Definition: sse2neon.h:347
MPI structure.
Definition: bignum.h:207
else result
Definition: token2.c:20
#define N
Definition: crc32.c:57
#define W
Definition: crc32.c:85
Modified on Sat May 25 14:22:51 2024 by modify_doxy.py rev. 669887