Lines Matching +full:- +full:x
2 * Multi-precision integer library
5 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
9 * The following sources were referenced in the design of this Multi-precision
12 * [1] Handbook of Applied Cryptography - 1997
15 * [2] Multi-Precision Math
19 * [3] GNU Multi-Precision Arithmetic Library
48 * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid
54 return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1; in mbedtls_ct_mpi_sign_if()
60 int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X, in mbedtls_mpi_lt_mpi_ct() argument
66 if (X->n != Y->n) { in mbedtls_mpi_lt_mpi_ct()
72 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0. in mbedtls_mpi_lt_mpi_ct()
74 X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1); in mbedtls_mpi_lt_mpi_ct()
75 Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1); in mbedtls_mpi_lt_mpi_ct()
79 * That is if X is negative (X_is_negative == 1), then X < Y is true and it in mbedtls_mpi_lt_mpi_ct()
80 * is false if X is positive (X_is_negative == 0). in mbedtls_mpi_lt_mpi_ct()
86 * Assuming signs are the same, compare X and Y. We switch the comparison in mbedtls_mpi_lt_mpi_ct()
92 void * const p[2] = { X->p, Y->p }; in mbedtls_mpi_lt_mpi_ct()
94 mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n); in mbedtls_mpi_lt_mpi_ct()
109 * Conditionally assign X = Y, without leaking information
111 * (Leaking information about the respective sizes of X and Y is ok however.)
117 …* https://developercommunity.visualstudio.com/t/c-compiler-miscompiles-part-of-mbedtls-library-on/…
121 int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X, in mbedtls_mpi_safe_cond_assign() argument
127 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n)); in mbedtls_mpi_safe_cond_assign()
132 X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s); in mbedtls_mpi_safe_cond_assign()
134 mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign); in mbedtls_mpi_safe_cond_assign()
137 for (size_t i = Y->n; i < X->n; i++) { in mbedtls_mpi_safe_cond_assign()
138 X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]); in mbedtls_mpi_safe_cond_assign()
147 * Conditionally swap X and Y, without leaking information
150 * different memory access patterns when X and Y are used afterwards.
152 int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X, in mbedtls_mpi_safe_cond_swap() argument
159 if (X == Y) { in mbedtls_mpi_safe_cond_swap()
165 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n)); in mbedtls_mpi_safe_cond_swap()
166 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n)); in mbedtls_mpi_safe_cond_swap()
168 s = X->s; in mbedtls_mpi_safe_cond_swap()
169 X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s); in mbedtls_mpi_safe_cond_swap()
170 Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s); in mbedtls_mpi_safe_cond_swap()
172 mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap); in mbedtls_mpi_safe_cond_swap()
190 static void mpi_init(mbedtls_mpi *X, short use_mempool) in mpi_init() argument
192 X->s = 1; in mpi_init()
193 X->use_mempool = use_mempool; in mpi_init()
194 X->n = 0; in mpi_init()
195 X->p = NULL; in mpi_init()
198 void mbedtls_mpi_init(mbedtls_mpi *X) in mbedtls_mpi_init() argument
200 mpi_init(X, 0 /*use_mempool*/); in mbedtls_mpi_init()
203 void mbedtls_mpi_init_mempool(mbedtls_mpi *X) in mbedtls_mpi_init_mempool() argument
205 mpi_init(X, !!mbedtls_mpi_mempool /*use_mempool*/); in mbedtls_mpi_init_mempool()
211 void mbedtls_mpi_free(mbedtls_mpi *X) in mbedtls_mpi_free() argument
213 if (X == NULL) { in mbedtls_mpi_free()
217 if (X->p != NULL) { in mbedtls_mpi_free()
218 if(X->use_mempool) { in mbedtls_mpi_free()
219 mbedtls_mpi_zeroize(X->p, X->n); in mbedtls_mpi_free()
220 mempool_free(mbedtls_mpi_mempool, X->p); in mbedtls_mpi_free()
222 mbedtls_mpi_zeroize_and_free(X->p, X->n); in mbedtls_mpi_free()
226 X->s = 1; in mbedtls_mpi_free()
227 X->n = 0; in mbedtls_mpi_free()
228 X->p = NULL; in mbedtls_mpi_free()
234 int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs) in mbedtls_mpi_grow() argument
242 if (X->n < nblimbs) { in mbedtls_mpi_grow()
243 if(X->use_mempool) { in mbedtls_mpi_grow()
254 if (X->p != NULL) { in mbedtls_mpi_grow()
255 memcpy(p, X->p, X->n * ciL); in mbedtls_mpi_grow()
257 if (X->use_mempool) { in mbedtls_mpi_grow()
258 mbedtls_mpi_zeroize(X->p, X->n); in mbedtls_mpi_grow()
259 mempool_free(mbedtls_mpi_mempool, X->p); in mbedtls_mpi_grow()
261 mbedtls_mpi_zeroize_and_free(X->p, X->n); in mbedtls_mpi_grow()
267 X->n = (unsigned short) nblimbs; in mbedtls_mpi_grow()
268 X->p = p; in mbedtls_mpi_grow()
278 int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs) in mbedtls_mpi_shrink() argument
288 if (X->n <= nblimbs) { in mbedtls_mpi_shrink()
289 return mbedtls_mpi_grow(X, nblimbs); in mbedtls_mpi_shrink()
291 /* After this point, then X->n > nblimbs and in particular X->n > 0. */ in mbedtls_mpi_shrink()
293 for (i = X->n - 1; i > 0; i--) { in mbedtls_mpi_shrink()
294 if (X->p[i] != 0) { in mbedtls_mpi_shrink()
304 if (X->use_mempool) { in mbedtls_mpi_shrink()
314 if (X->p != NULL) { in mbedtls_mpi_shrink()
315 memcpy(p, X->p, i * ciL); in mbedtls_mpi_shrink()
317 if (X->use_mempool) { in mbedtls_mpi_shrink()
318 mbedtls_mpi_zeroize(X->p, X->n); in mbedtls_mpi_shrink()
319 mempool_free(mbedtls_mpi_mempool, X->p); in mbedtls_mpi_shrink()
322 mbedtls_mpi_zeroize_and_free(X->p, X->n); in mbedtls_mpi_shrink()
328 X->n = (unsigned short) i; in mbedtls_mpi_shrink()
329 X->p = p; in mbedtls_mpi_shrink()
334 /* Resize X to have exactly n limbs and set it to 0. */
335 static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs) in mbedtls_mpi_resize_clear() argument
338 mbedtls_mpi_free(X); in mbedtls_mpi_resize_clear()
340 } else if (X->n == limbs) { in mbedtls_mpi_resize_clear()
341 memset(X->p, 0, limbs * ciL); in mbedtls_mpi_resize_clear()
342 X->s = 1; in mbedtls_mpi_resize_clear()
345 mbedtls_mpi_free(X); in mbedtls_mpi_resize_clear()
346 return mbedtls_mpi_grow(X, limbs); in mbedtls_mpi_resize_clear()
351 * Copy the contents of Y into X.
353 * This function is not constant-time. Leading zeros in Y may be removed.
355 * Ensure that X does not shrink. This is not guaranteed by the public API,
358 int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y) in mbedtls_mpi_copy() argument
363 if (X == Y) { in mbedtls_mpi_copy()
367 if (Y->n == 0) { in mbedtls_mpi_copy()
368 if (X->n != 0) { in mbedtls_mpi_copy()
369 X->s = 1; in mbedtls_mpi_copy()
370 memset(X->p, 0, X->n * ciL); in mbedtls_mpi_copy()
375 for (i = Y->n - 1; i > 0; i--) { in mbedtls_mpi_copy()
376 if (Y->p[i] != 0) { in mbedtls_mpi_copy()
382 X->s = Y->s; in mbedtls_mpi_copy()
384 if (X->n < i) { in mbedtls_mpi_copy()
385 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i)); in mbedtls_mpi_copy()
387 memset(X->p + i, 0, (X->n - i) * ciL); in mbedtls_mpi_copy()
390 memcpy(X->p, Y->p, i * ciL); in mbedtls_mpi_copy()
398 * Swap the contents of X and Y
400 void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y) in mbedtls_mpi_swap() argument
404 memcpy(&T, X, sizeof(mbedtls_mpi)); in mbedtls_mpi_swap()
405 memcpy(X, Y, sizeof(mbedtls_mpi)); in mbedtls_mpi_swap()
414 /* Take care to handle the most negative value (-2^(biL-1)) correctly. in mpi_sint_abs()
415 * A naive -z would have undefined behavior. in mpi_sint_abs()
418 return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z; in mpi_sint_abs()
421 /* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
422 * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
423 #define TO_SIGN(x) ((mbedtls_mpi_sint) (((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1) argument
428 int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z) in mbedtls_mpi_lset() argument
432 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1)); in mbedtls_mpi_lset()
433 memset(X->p, 0, X->n * ciL); in mbedtls_mpi_lset()
435 X->p[0] = mpi_sint_abs(z); in mbedtls_mpi_lset()
436 X->s = TO_SIGN(z); in mbedtls_mpi_lset()
446 int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos) in mbedtls_mpi_get_bit() argument
448 if (X->n * biL <= pos) { in mbedtls_mpi_get_bit()
452 return (X->p[pos / biL] >> (pos % biL)) & 0x01; in mbedtls_mpi_get_bit()
458 int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val) in mbedtls_mpi_set_bit() argument
468 if (X->n * biL <= pos) { in mbedtls_mpi_set_bit()
473 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1)); in mbedtls_mpi_set_bit()
476 X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx); in mbedtls_mpi_set_bit()
477 X->p[off] |= (mbedtls_mpi_uint) val << idx; in mbedtls_mpi_set_bit()
485 * Return the number of less significant zero-bits
487 size_t mbedtls_mpi_lsb(const mbedtls_mpi *X) in mbedtls_mpi_lsb() argument
502 for (i = 0; i < X->n; i++) { in mbedtls_mpi_lsb()
503 if (X->p[i] != 0) { in mbedtls_mpi_lsb()
504 return i * biL + mbedtls_mpi_uint_ctz(X->p[i]); in mbedtls_mpi_lsb()
509 for (i = 0; i < X->n; i++) { in mbedtls_mpi_lsb()
511 if (((X->p[i] >> j) & 1) != 0) { in mbedtls_mpi_lsb()
524 size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X) in mbedtls_mpi_bitlen() argument
526 return mbedtls_mpi_core_bitlen(X->p, X->n); in mbedtls_mpi_bitlen()
532 size_t mbedtls_mpi_size(const mbedtls_mpi *X) in mbedtls_mpi_size() argument
534 return (mbedtls_mpi_bitlen(X) + 7) >> 3; in mbedtls_mpi_size()
545 *d = c - 0x30; in mpi_get_digit()
548 *d = c - 0x37; in mpi_get_digit()
551 *d = c - 0x57; in mpi_get_digit()
564 int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s) in mbedtls_mpi_read_string() argument
579 mbedtls_mpi_free(X); in mbedtls_mpi_read_string()
583 if (s[0] == '-') { in mbedtls_mpi_read_string()
585 sign = -1; in mbedtls_mpi_read_string()
597 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n)); in mbedtls_mpi_read_string()
598 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); in mbedtls_mpi_read_string()
600 for (i = slen, j = 0; i > 0; i--, j++) { in mbedtls_mpi_read_string()
601 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1])); in mbedtls_mpi_read_string()
602 X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2); in mbedtls_mpi_read_string()
605 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); in mbedtls_mpi_read_string()
609 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix)); in mbedtls_mpi_read_string()
610 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d)); in mbedtls_mpi_read_string()
614 if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) { in mbedtls_mpi_read_string()
615 X->s = -1; in mbedtls_mpi_read_string()
626 * Helper to write the digits high-order first.
628 static int mpi_write_hlp(mbedtls_mpi *X, int radix, in mpi_write_hlp() argument
641 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix)); in mpi_write_hlp()
642 MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix)); in mpi_write_hlp()
647 *(--p_end) = (char) ('0' + r); in mpi_write_hlp()
649 *(--p_end) = (char) ('A' + (r - 0xA)); in mpi_write_hlp()
653 } while (mbedtls_mpi_cmp_int(X, 0) != 0); in mpi_write_hlp()
666 int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix, in mbedtls_mpi_write_string() argument
678 n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */ in mbedtls_mpi_write_string()
680 n >>= 1; /* Number of 4-adic digits necessary to present in mbedtls_mpi_write_string()
683 * radix-adic digits needed to present `n`. */ in mbedtls_mpi_write_string()
693 n += 1; /* Potential '-'-sign. */ in mbedtls_mpi_write_string()
695 * which always uses an even number of hex-digits. */ in mbedtls_mpi_write_string()
705 if (X->s == -1) { in mbedtls_mpi_write_string()
706 *p++ = '-'; in mbedtls_mpi_write_string()
707 buflen--; in mbedtls_mpi_write_string()
714 for (i = X->n, k = 0; i > 0; i--) { in mbedtls_mpi_write_string()
715 for (j = ciL; j > 0; j--) { in mbedtls_mpi_write_string()
716 c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF; in mbedtls_mpi_write_string()
728 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X)); in mbedtls_mpi_write_string()
730 if (T.s == -1) { in mbedtls_mpi_write_string()
738 *olen = (size_t) (p - buf); in mbedtls_mpi_write_string()
749 * Read X from an opened file
751 int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin) in mbedtls_mpi_read_file() argument
767 if (fgets(s, sizeof(s) - 1, fin) == NULL) { in mbedtls_mpi_read_file()
772 if (slen == sizeof(s) - 2) { in mbedtls_mpi_read_file()
776 if (slen > 0 && s[slen - 1] == '\n') { in mbedtls_mpi_read_file()
777 slen--; s[slen] = '\0'; in mbedtls_mpi_read_file()
779 if (slen > 0 && s[slen - 1] == '\r') { in mbedtls_mpi_read_file()
780 slen--; s[slen] = '\0'; in mbedtls_mpi_read_file()
784 while (p-- > s) { in mbedtls_mpi_read_file()
790 return mbedtls_mpi_read_string(X, radix, p + 1); in mbedtls_mpi_read_file()
794 * Write X into an opened file (or stdout if fout == NULL)
796 int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout) in mbedtls_mpi_write_file() argument
812 MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n)); in mbedtls_mpi_write_file()
839 * Import X from unsigned binary data, little endian
844 int mbedtls_mpi_read_binary_le(mbedtls_mpi *X, in mbedtls_mpi_read_binary_le() argument
851 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); in mbedtls_mpi_read_binary_le()
853 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen)); in mbedtls_mpi_read_binary_le()
866 * Import X from unsigned binary data, big endian
871 int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen) in mbedtls_mpi_read_binary() argument
877 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); in mbedtls_mpi_read_binary()
879 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen)); in mbedtls_mpi_read_binary()
892 * Export X into unsigned binary data, little endian
894 int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X, in mbedtls_mpi_write_binary_le() argument
897 return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen); in mbedtls_mpi_write_binary_le()
901 * Export X into unsigned binary data, big endian
903 int mbedtls_mpi_write_binary(const mbedtls_mpi *X, in mbedtls_mpi_write_binary() argument
906 return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen); in mbedtls_mpi_write_binary()
910 * Left-shift: X <<= count
912 int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count) in mbedtls_mpi_shift_l() argument
917 i = mbedtls_mpi_bitlen(X) + count; in mbedtls_mpi_shift_l()
919 if (X->n * biL < i) { in mbedtls_mpi_shift_l()
920 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i))); in mbedtls_mpi_shift_l()
925 mbedtls_mpi_core_shift_l(X->p, X->n, count); in mbedtls_mpi_shift_l()
932 * Right-shift: X >>= count
934 int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count) in mbedtls_mpi_shift_r() argument
936 if (X->n != 0) { in mbedtls_mpi_shift_r()
937 mbedtls_mpi_core_shift_r(X->p, X->n, count); in mbedtls_mpi_shift_r()
945 int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y) in mbedtls_mpi_cmp_abs() argument
949 for (i = X->n; i > 0; i--) { in mbedtls_mpi_cmp_abs()
950 if (X->p[i - 1] != 0) { in mbedtls_mpi_cmp_abs()
955 for (j = Y->n; j > 0; j--) { in mbedtls_mpi_cmp_abs()
956 if (Y->p[j - 1] != 0) { in mbedtls_mpi_cmp_abs()
961 /* If i == j == 0, i.e. abs(X) == abs(Y), in mbedtls_mpi_cmp_abs()
968 return -1; in mbedtls_mpi_cmp_abs()
971 for (; i > 0; i--) { in mbedtls_mpi_cmp_abs()
972 if (X->p[i - 1] > Y->p[i - 1]) { in mbedtls_mpi_cmp_abs()
975 if (X->p[i - 1] < Y->p[i - 1]) { in mbedtls_mpi_cmp_abs()
976 return -1; in mbedtls_mpi_cmp_abs()
986 int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y) in mbedtls_mpi_cmp_mpi() argument
990 for (i = X->n; i > 0; i--) { in mbedtls_mpi_cmp_mpi()
991 if (X->p[i - 1] != 0) { in mbedtls_mpi_cmp_mpi()
996 for (j = Y->n; j > 0; j--) { in mbedtls_mpi_cmp_mpi()
997 if (Y->p[j - 1] != 0) { in mbedtls_mpi_cmp_mpi()
1007 return X->s; in mbedtls_mpi_cmp_mpi()
1010 return -Y->s; in mbedtls_mpi_cmp_mpi()
1013 if (X->s > 0 && Y->s < 0) { in mbedtls_mpi_cmp_mpi()
1016 if (Y->s > 0 && X->s < 0) { in mbedtls_mpi_cmp_mpi()
1017 return -1; in mbedtls_mpi_cmp_mpi()
1020 for (; i > 0; i--) { in mbedtls_mpi_cmp_mpi()
1021 if (X->p[i - 1] > Y->p[i - 1]) { in mbedtls_mpi_cmp_mpi()
1022 return X->s; in mbedtls_mpi_cmp_mpi()
1024 if (X->p[i - 1] < Y->p[i - 1]) { in mbedtls_mpi_cmp_mpi()
1025 return -X->s; in mbedtls_mpi_cmp_mpi()
1035 int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z) in mbedtls_mpi_cmp_int() argument
1045 return mbedtls_mpi_cmp_mpi(X, &Y); in mbedtls_mpi_cmp_int()
1049 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1051 int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_add_abs() argument
1058 if (X == B) { in mbedtls_mpi_add_abs()
1059 const mbedtls_mpi *T = A; A = X; B = T; in mbedtls_mpi_add_abs()
1062 if (X != A) { in mbedtls_mpi_add_abs()
1063 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); in mbedtls_mpi_add_abs()
1067 * X must always be positive as a result of unsigned additions. in mbedtls_mpi_add_abs()
1069 X->s = 1; in mbedtls_mpi_add_abs()
1071 for (j = B->n; j > 0; j--) { in mbedtls_mpi_add_abs()
1072 if (B->p[j - 1] != 0) { in mbedtls_mpi_add_abs()
1077 /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0 in mbedtls_mpi_add_abs()
1083 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j)); in mbedtls_mpi_add_abs()
1085 /* j is the number of non-zero limbs of B. Add those to X. */ in mbedtls_mpi_add_abs()
1087 p = X->p; in mbedtls_mpi_add_abs()
1089 c = mbedtls_mpi_core_add(p, p, B->p, j); in mbedtls_mpi_add_abs()
1096 if (j >= X->n) { in mbedtls_mpi_add_abs()
1097 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1)); in mbedtls_mpi_add_abs()
1098 p = X->p + j; in mbedtls_mpi_add_abs()
1110 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1112 int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_sub_abs() argument
1118 for (n = B->n; n > 0; n--) { in mbedtls_mpi_sub_abs()
1119 if (B->p[n - 1] != 0) { in mbedtls_mpi_sub_abs()
1123 if (n > A->n) { in mbedtls_mpi_sub_abs()
1129 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n)); in mbedtls_mpi_sub_abs()
1131 /* Set the high limbs of X to match A. Don't touch the lower limbs in mbedtls_mpi_sub_abs()
1132 * because X might be aliased to B, and we must not overwrite the in mbedtls_mpi_sub_abs()
1134 if (A->n > n && A != X) { in mbedtls_mpi_sub_abs()
1135 memcpy(X->p + n, A->p + n, (A->n - n) * ciL); in mbedtls_mpi_sub_abs()
1137 if (X->n > A->n) { in mbedtls_mpi_sub_abs()
1138 memset(X->p + A->n, 0, (X->n - A->n) * ciL); in mbedtls_mpi_sub_abs()
1141 carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n); in mbedtls_mpi_sub_abs()
1143 /* Propagate the carry through the rest of X. */ in mbedtls_mpi_sub_abs()
1144 carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n); in mbedtls_mpi_sub_abs()
1153 /* X should always be positive as a result of unsigned subtractions. */ in mbedtls_mpi_sub_abs()
1154 X->s = 1; in mbedtls_mpi_sub_abs()
1161 * Calculate A + B * flip_B where flip_B is 1 or -1.
1163 static int add_sub_mpi(mbedtls_mpi *X, in add_sub_mpi() argument
1169 s = A->s; in add_sub_mpi()
1170 if (A->s * B->s * flip_B < 0) { in add_sub_mpi()
1173 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B)); in add_sub_mpi()
1177 X->s = cmp == 0 ? 1 : s; in add_sub_mpi()
1179 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A)); in add_sub_mpi()
1181 X->s = -s; in add_sub_mpi()
1184 MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B)); in add_sub_mpi()
1185 X->s = s; in add_sub_mpi()
1194 * Signed addition: X = A + B
1196 int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_add_mpi() argument
1198 return add_sub_mpi(X, A, B, 1); in mbedtls_mpi_add_mpi()
1202 * Signed subtraction: X = A - B
1204 int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_sub_mpi() argument
1206 return add_sub_mpi(X, A, B, -1); in mbedtls_mpi_sub_mpi()
1210 * Signed addition: X = A + b
1212 int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) in mbedtls_mpi_add_int() argument
1222 return mbedtls_mpi_add_mpi(X, A, &B); in mbedtls_mpi_add_int()
1226 * Signed subtraction: X = A - b
1228 int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) in mbedtls_mpi_sub_int() argument
1238 return mbedtls_mpi_sub_mpi(X, A, &B); in mbedtls_mpi_sub_int()
1242 * Baseline multiplication: X = A * B (HAC 14.12)
1244 int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_mul_mpi() argument
1254 if (X == A) { in mbedtls_mpi_mul_mpi()
1257 if (X == B) { in mbedtls_mpi_mul_mpi()
1261 for (i = A->n; i > 0; i--) { in mbedtls_mpi_mul_mpi()
1262 if (A->p[i - 1] != 0) { in mbedtls_mpi_mul_mpi()
1270 for (j = B->n; j > 0; j--) { in mbedtls_mpi_mul_mpi()
1271 if (B->p[j - 1] != 0) { in mbedtls_mpi_mul_mpi()
1279 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j)); in mbedtls_mpi_mul_mpi()
1280 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); in mbedtls_mpi_mul_mpi()
1282 mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j); in mbedtls_mpi_mul_mpi()
1285 * but does not eliminate side channels leaking the zero-ness. We do in mbedtls_mpi_mul_mpi()
1287 * not fully support an MPI object with a value of 0 and s == -1. */ in mbedtls_mpi_mul_mpi()
1289 X->s = 1; in mbedtls_mpi_mul_mpi()
1291 X->s = A->s * B->s; in mbedtls_mpi_mul_mpi()
1302 * Baseline multiplication: X = A * b
1304 int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b) in mbedtls_mpi_mul_int() argument
1306 size_t n = A->n; in mbedtls_mpi_mul_int()
1307 while (n > 0 && A->p[n - 1] == 0) { in mbedtls_mpi_mul_int()
1308 --n; in mbedtls_mpi_mul_int()
1313 return mbedtls_mpi_lset(X, 0); in mbedtls_mpi_mul_int()
1316 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */ in mbedtls_mpi_mul_int()
1319 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same in mbedtls_mpi_mul_int()
1327 * Note that calculating A*b as 0 + A*b doesn't work as-is because in mbedtls_mpi_mul_int()
1328 * A,X can be the same. */ in mbedtls_mpi_mul_int()
1329 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1)); in mbedtls_mpi_mul_int()
1330 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); in mbedtls_mpi_mul_int()
1331 mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1); in mbedtls_mpi_mul_int()
1338 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1350 const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1; in mbedtls_int_div_int()
1371 if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) { in mbedtls_int_div_int()
1372 quotient = ((mbedtls_t_udbl) 1 << biL) - 1; in mbedtls_int_div_int()
1376 *r = (mbedtls_mpi_uint) (dividend - (quotient * d)); in mbedtls_int_div_int()
1383 * Algorithm D, Section 4.3.1 - The Art of Computer Programming in mbedtls_int_div_int()
1384 * Vol. 2 - Seminumerical Algorithms, Knuth in mbedtls_int_div_int()
1394 u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1)); in mbedtls_int_div_int()
1407 r0 = u1 - d1 * q1; in mbedtls_int_div_int()
1410 q1 -= 1; in mbedtls_int_div_int()
1418 rAX = (u1 * radix) + (u0_msw - q1 * d); in mbedtls_int_div_int()
1420 r0 = rAX - q0 * d1; in mbedtls_int_div_int()
1423 q0 -= 1; in mbedtls_int_div_int()
1432 *r = (rAX * radix + u0_lsw - q0 * d) >> s; in mbedtls_int_div_int()
1449 mbedtls_mpi X, Y, Z, T1, T2; in mbedtls_mpi_div_mpi() local
1456 mbedtls_mpi_init_mempool(&X); mbedtls_mpi_init_mempool(&Y); in mbedtls_mpi_div_mpi()
1459 * Avoid dynamic memory allocations for constant-size T2. in mbedtls_mpi_div_mpi()
1462 * so nobody increase the size of the MPI and we're safe to use an on-stack in mbedtls_mpi_div_mpi()
1479 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A)); in mbedtls_mpi_div_mpi()
1481 X.s = Y.s = 1; in mbedtls_mpi_div_mpi()
1483 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2)); in mbedtls_mpi_div_mpi()
1485 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2)); in mbedtls_mpi_div_mpi()
1488 if (k < biL - 1) { in mbedtls_mpi_div_mpi()
1489 k = biL - 1 - k; in mbedtls_mpi_div_mpi()
1490 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k)); in mbedtls_mpi_div_mpi()
1496 n = X.n - 1; in mbedtls_mpi_div_mpi()
1497 t = Y.n - 1; in mbedtls_mpi_div_mpi()
1498 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t))); in mbedtls_mpi_div_mpi()
1500 while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) { in mbedtls_mpi_div_mpi()
1501 Z.p[n - t]++; in mbedtls_mpi_div_mpi()
1502 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y)); in mbedtls_mpi_div_mpi()
1504 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t))); in mbedtls_mpi_div_mpi()
1506 for (i = n; i > t; i--) { in mbedtls_mpi_div_mpi()
1507 if (X.p[i] >= Y.p[t]) { in mbedtls_mpi_div_mpi()
1508 Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u; in mbedtls_mpi_div_mpi()
1510 Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1], in mbedtls_mpi_div_mpi()
1514 T2.p[0] = (i < 2) ? 0 : X.p[i - 2]; in mbedtls_mpi_div_mpi()
1515 T2.p[1] = (i < 1) ? 0 : X.p[i - 1]; in mbedtls_mpi_div_mpi()
1516 T2.p[2] = X.p[i]; in mbedtls_mpi_div_mpi()
1518 Z.p[i - t - 1]++; in mbedtls_mpi_div_mpi()
1520 Z.p[i - t - 1]--; in mbedtls_mpi_div_mpi()
1523 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1]; in mbedtls_mpi_div_mpi()
1525 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1])); in mbedtls_mpi_div_mpi()
1528 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1])); in mbedtls_mpi_div_mpi()
1529 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); in mbedtls_mpi_div_mpi()
1530 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1)); in mbedtls_mpi_div_mpi()
1532 if (mbedtls_mpi_cmp_int(&X, 0) < 0) { in mbedtls_mpi_div_mpi()
1534 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); in mbedtls_mpi_div_mpi()
1535 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1)); in mbedtls_mpi_div_mpi()
1536 Z.p[i - t - 1]--; in mbedtls_mpi_div_mpi()
1542 Q->s = A->s * B->s; in mbedtls_mpi_div_mpi()
1546 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k)); in mbedtls_mpi_div_mpi()
1547 X.s = A->s; in mbedtls_mpi_div_mpi()
1548 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X)); in mbedtls_mpi_div_mpi()
1551 R->s = 1; in mbedtls_mpi_div_mpi()
1557 mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z); in mbedtls_mpi_div_mpi()
1614 mbedtls_mpi_uint x, y, z; in mbedtls_mpi_mod_int() local
1627 if (b == 1 || A->n == 0) { in mbedtls_mpi_mod_int()
1633 *r = A->p[0] & 1; in mbedtls_mpi_mod_int()
1640 for (i = A->n, y = 0; i > 0; i--) { in mbedtls_mpi_mod_int()
1641 x = A->p[i - 1]; in mbedtls_mpi_mod_int()
1642 y = (y << biH) | (x >> biH); in mbedtls_mpi_mod_int()
1644 y -= z * b; in mbedtls_mpi_mod_int()
1646 x <<= biH; in mbedtls_mpi_mod_int()
1647 y = (y << biH) | (x >> biH); in mbedtls_mpi_mod_int()
1649 y -= z * b; in mbedtls_mpi_mod_int()
1656 if (A->s < 0 && y != 0) { in mbedtls_mpi_mod_int()
1657 y = b - y; in mbedtls_mpi_mod_int()
1671 *mm = mbedtls_mpi_core_montmul_init(N->p); in mbedtls_mpi_montg_init()
1674 /** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1678 * (A->n >= N->n), and any limbs beyond n are ignored.
1680 * the multiplication A * B * R^-1 mod N where
1684 * (B->n <= N->n).
1687 * This is -N^-1 mod 2^ciL.
1690 * (T->n >= 2 * N->n + 1).
1701 mbedtls_mpi_core_montmul(A->p, A->p, B->p, B->n, N->p, N->n, mm, T->p); in mbedtls_mpi_montmul()
1705 * Montgomery reduction: A = A * R^-1 mod N
1728 static int mbedtls_mpi_exp_mod_optionally_safe(mbedtls_mpi *X, const mbedtls_mpi *A, in mbedtls_mpi_exp_mod_optionally_safe() argument
1734 if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) { in mbedtls_mpi_exp_mod_optionally_safe()
1750 if (E->n == 0) { in mbedtls_mpi_exp_mod_optionally_safe()
1751 ret = mbedtls_mpi_lset(X, 1); in mbedtls_mpi_exp_mod_optionally_safe()
1758 size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n); in mbedtls_mpi_exp_mod_optionally_safe()
1769 * If 1st call, pre-compute R^2 mod N in mbedtls_mpi_exp_mod_optionally_safe()
1771 if (prec_RR == NULL || prec_RR->p == NULL) { in mbedtls_mpi_exp_mod_optionally_safe()
1778 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n)); in mbedtls_mpi_exp_mod_optionally_safe()
1783 * To preserve constness we need to make a copy of A. Using X for this to in mbedtls_mpi_exp_mod_optionally_safe()
1786 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); in mbedtls_mpi_exp_mod_optionally_safe()
1791 X->s = 1; in mbedtls_mpi_exp_mod_optionally_safe()
1794 * Make sure that X is in a form that is safe for consumption by in mbedtls_mpi_exp_mod_optionally_safe()
1797 * - The core functions will not touch the limbs of X above N->n. The in mbedtls_mpi_exp_mod_optionally_safe()
1800 * - Also, X must have at least as many limbs as N for the calls to the in mbedtls_mpi_exp_mod_optionally_safe()
1803 if (mbedtls_mpi_cmp_mpi(X, N) >= 0) { in mbedtls_mpi_exp_mod_optionally_safe()
1804 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N)); in mbedtls_mpi_exp_mod_optionally_safe()
1806 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n)); in mbedtls_mpi_exp_mod_optionally_safe()
1812 mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p); in mbedtls_mpi_exp_mod_optionally_safe()
1813 mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T); in mbedtls_mpi_exp_mod_optionally_safe()
1815 mbedtls_mpi_core_exp_mod_unsafe(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); in mbedtls_mpi_exp_mod_optionally_safe()
1817 mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); in mbedtls_mpi_exp_mod_optionally_safe()
1819 mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T); in mbedtls_mpi_exp_mod_optionally_safe()
1825 if (A->s == -1 && (E->p[0] & 1) != 0) { in mbedtls_mpi_exp_mod_optionally_safe()
1826 mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n); in mbedtls_mpi_exp_mod_optionally_safe()
1827 X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1); in mbedtls_mpi_exp_mod_optionally_safe()
1829 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X)); in mbedtls_mpi_exp_mod_optionally_safe()
1837 if (prec_RR == NULL || prec_RR->p == NULL) { in mbedtls_mpi_exp_mod_optionally_safe()
1844 int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A, in mbedtls_mpi_exp_mod() argument
1850 return mbedtls_mpi_exp_mod_unsafe(X, A, E, N, prec_RR); in mbedtls_mpi_exp_mod()
1852 return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR); in mbedtls_mpi_exp_mod()
1858 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1860 int mbedtls_mpi_exp_mod_unsafe(mbedtls_mpi *X, const mbedtls_mpi *A, in mbedtls_mpi_exp_mod_unsafe() argument
1864 return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_PUBLIC, N, prec_RR); in mbedtls_mpi_exp_mod_unsafe()
1901 * - Sequences of multiplications or divisions by 2 are grouped into a in mbedtls_mpi_gcd()
1903 * - The procedure in HAC assumes that 0 < TB <= TA. in mbedtls_mpi_gcd()
1904 * - The condition TB <= TA is not actually necessary for correctness. in mbedtls_mpi_gcd()
1909 * - If TA = 0, the loop goes through 0 iterations and the result is in mbedtls_mpi_gcd()
1911 * - The case TB = 0 was short-circuited above. in mbedtls_mpi_gcd()
1915 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1 in mbedtls_mpi_gcd()
1916 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1 in mbedtls_mpi_gcd()
1926 * At each iteration, either the right-shift by 1 is made on a nonzero in mbedtls_mpi_gcd()
1928 * by at least 1, or the right-shift by 1 is made on zero and then in mbedtls_mpi_gcd()
1929 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted in mbedtls_mpi_gcd()
1930 * since in that case TB is calculated from TB-TA with the condition TB>TA). in mbedtls_mpi_gcd()
1937 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd, in mbedtls_mpi_gcd()
1938 * TA-TB is even so the division by 2 has an integer result. in mbedtls_mpi_gcd()
1940 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2 in mbedtls_mpi_gcd()
1941 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also in mbedtls_mpi_gcd()
1956 * - If there was at least one loop iteration, then one of TA or TB is odd, in mbedtls_mpi_gcd()
1959 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B. in mbedtls_mpi_gcd()
1974 * Fill X with size bytes of random.
1979 int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size, in mbedtls_mpi_fill_random() argument
1987 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); in mbedtls_mpi_fill_random()
1992 ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng); in mbedtls_mpi_fill_random()
1998 int mbedtls_mpi_random(mbedtls_mpi *X, in mbedtls_mpi_random() argument
2014 int ret = mbedtls_mpi_resize_clear(X, N->n); in mbedtls_mpi_random()
2019 return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng); in mbedtls_mpi_random()
2023 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2025 int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N) in mbedtls_mpi_inv_mod() argument
2101 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1)); in mbedtls_mpi_inv_mod()
2141 * Small divisors test (X must be positive)
2146 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2149 static int mpi_check_small_factors(const mbedtls_mpi *X) in mpi_check_small_factors() argument
2156 if ((X->p[0] & 1) == 0) { in mpi_check_small_factors()
2161 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p)); in mpi_check_small_factors()
2163 if (mbedtls_mpi_cmp_int(X, p) == 0) { in mpi_check_small_factors()
2176 * Miller-Rabin pseudo-primality test (HAC 4.24)
2178 static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds, in mpi_miller_rabin() argument
2191 * W = |X| - 1 in mpi_miller_rabin()
2194 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1)); in mpi_miller_rabin()
2201 * pick a random A, 1 < A < |X| - 1 in mpi_miller_rabin()
2205 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng)); in mpi_miller_rabin()
2210 A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1; in mpi_miller_rabin()
2222 * A = A^R mod |X| in mpi_miller_rabin()
2224 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR)); in mpi_miller_rabin()
2234 * A = A * A mod |X| in mpi_miller_rabin()
2237 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X)); in mpi_miller_rabin()
2247 * not prime if A != |X| - 1 or A == 1 in mpi_miller_rabin()
2265 * Pseudo-primality test: small factors, then Miller-Rabin
2267 int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds, in mbedtls_mpi_is_prime_ext() argument
2275 XX.n = X->n; in mbedtls_mpi_is_prime_ext()
2276 XX.p = X->p; in mbedtls_mpi_is_prime_ext()
2301 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2305 int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags, in mbedtls_mpi_gen_prime() argument
2332 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 in mbedtls_mpi_gen_prime()
2339 * 2^-100 error probability, number of rounds computed based on HAC, in mbedtls_mpi_gen_prime()
2349 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng)); in mbedtls_mpi_gen_prime()
2350 … /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */ in mbedtls_mpi_gen_prime()
2351 if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) { in mbedtls_mpi_gen_prime()
2357 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits)); in mbedtls_mpi_gen_prime()
2359 X->p[0] |= 1; in mbedtls_mpi_gen_prime()
2362 ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng); in mbedtls_mpi_gen_prime()
2369 * A necessary condition for Y and X = 2Y + 1 to be prime in mbedtls_mpi_gen_prime()
2370 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). in mbedtls_mpi_gen_prime()
2371 * Make sure it is satisfied, while keeping X = 3 mod 4 in mbedtls_mpi_gen_prime()
2374 X->p[0] |= 2; in mbedtls_mpi_gen_prime()
2376 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3)); in mbedtls_mpi_gen_prime()
2378 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8)); in mbedtls_mpi_gen_prime()
2380 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4)); in mbedtls_mpi_gen_prime()
2383 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ in mbedtls_mpi_gen_prime()
2384 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X)); in mbedtls_mpi_gen_prime()
2389 * First, check small factors for X and Y in mbedtls_mpi_gen_prime()
2390 * before doing Miller-Rabin on any of them in mbedtls_mpi_gen_prime()
2392 if ((ret = mpi_check_small_factors(X)) == 0 && in mbedtls_mpi_gen_prime()
2394 (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng)) in mbedtls_mpi_gen_prime()
2406 * Next candidates. We want to preserve Y = (X-1) / 2 and in mbedtls_mpi_gen_prime()
2407 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) in mbedtls_mpi_gen_prime()
2408 * so up Y by 6 and X by 12. in mbedtls_mpi_gen_prime()
2410 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12)); in mbedtls_mpi_gen_prime()
2442 mbedtls_mpi A, E, N, X, Y, U, V; in mbedtls_mpi_self_test() local
2445 mbedtls_mpi_init_mempool(&N); mbedtls_mpi_init_mempool(&X); in mbedtls_mpi_self_test()
2466 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N)); in mbedtls_mpi_self_test()
2481 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { in mbedtls_mpi_self_test()
2494 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N)); in mbedtls_mpi_self_test()
2508 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 || in mbedtls_mpi_self_test()
2522 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL)); in mbedtls_mpi_self_test()
2533 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { in mbedtls_mpi_self_test()
2546 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N)); in mbedtls_mpi_self_test()
2557 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { in mbedtls_mpi_self_test()
2575 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0])); in mbedtls_mpi_self_test()
2578 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y)); in mbedtls_mpi_self_test()
2597 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret); in mbedtls_mpi_self_test()
2600 mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X); in mbedtls_mpi_self_test()