Lines Matching +full:- +full:s
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
44 * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid
50 return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1; in mbedtls_ct_mpi_sign_if()
62 if (X->n != Y->n) { in mbedtls_mpi_lt_mpi_ct()
68 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0. in mbedtls_mpi_lt_mpi_ct()
70 X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1); in mbedtls_mpi_lt_mpi_ct()
71 Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1); in mbedtls_mpi_lt_mpi_ct()
88 void * const p[2] = { X->p, Y->p }; in mbedtls_mpi_lt_mpi_ct()
90 mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n); in mbedtls_mpi_lt_mpi_ct()
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/…
123 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n)); in mbedtls_mpi_safe_cond_assign()
128 X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s); in mbedtls_mpi_safe_cond_assign()
130 mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign); in mbedtls_mpi_safe_cond_assign()
133 for (size_t i = Y->n; i < X->n; i++) { in mbedtls_mpi_safe_cond_assign()
134 X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]); in mbedtls_mpi_safe_cond_assign()
153 int s; in mbedtls_mpi_safe_cond_swap() local
161 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n)); in mbedtls_mpi_safe_cond_swap()
162 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n)); in mbedtls_mpi_safe_cond_swap()
164 s = X->s; in mbedtls_mpi_safe_cond_swap()
165 X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s); in mbedtls_mpi_safe_cond_swap()
166 Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s); in mbedtls_mpi_safe_cond_swap()
168 mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap); in mbedtls_mpi_safe_cond_swap()
182 X->s = 1; in mbedtls_mpi_init()
183 X->n = 0; in mbedtls_mpi_init()
184 X->p = NULL; in mbedtls_mpi_init()
196 if (X->p != NULL) { in mbedtls_mpi_free()
197 mbedtls_mpi_zeroize_and_free(X->p, X->n); in mbedtls_mpi_free()
200 X->s = 1; in mbedtls_mpi_free()
201 X->n = 0; in mbedtls_mpi_free()
202 X->p = NULL; in mbedtls_mpi_free()
216 if (X->n < nblimbs) { in mbedtls_mpi_grow()
221 if (X->p != NULL) { in mbedtls_mpi_grow()
222 memcpy(p, X->p, X->n * ciL); in mbedtls_mpi_grow()
223 mbedtls_mpi_zeroize_and_free(X->p, X->n); in mbedtls_mpi_grow()
228 X->n = (unsigned short) nblimbs; in mbedtls_mpi_grow()
229 X->p = p; in mbedtls_mpi_grow()
249 if (X->n <= nblimbs) { in mbedtls_mpi_shrink()
252 /* After this point, then X->n > nblimbs and in particular X->n > 0. */ in mbedtls_mpi_shrink()
254 for (i = X->n - 1; i > 0; i--) { in mbedtls_mpi_shrink()
255 if (X->p[i] != 0) { in mbedtls_mpi_shrink()
269 if (X->p != NULL) { in mbedtls_mpi_shrink()
270 memcpy(p, X->p, i * ciL); in mbedtls_mpi_shrink()
271 mbedtls_mpi_zeroize_and_free(X->p, X->n); in mbedtls_mpi_shrink()
276 X->n = (unsigned short) i; in mbedtls_mpi_shrink()
277 X->p = p; in mbedtls_mpi_shrink()
288 } else if (X->n == limbs) { in mbedtls_mpi_resize_clear()
289 memset(X->p, 0, limbs * ciL); in mbedtls_mpi_resize_clear()
290 X->s = 1; in mbedtls_mpi_resize_clear()
301 * This function is not constant-time. Leading zeros in Y may be removed.
315 if (Y->n == 0) { in mbedtls_mpi_copy()
316 if (X->n != 0) { in mbedtls_mpi_copy()
317 X->s = 1; in mbedtls_mpi_copy()
318 memset(X->p, 0, X->n * ciL); in mbedtls_mpi_copy()
323 for (i = Y->n - 1; i > 0; i--) { in mbedtls_mpi_copy()
324 if (Y->p[i] != 0) { in mbedtls_mpi_copy()
330 X->s = Y->s; in mbedtls_mpi_copy()
332 if (X->n < i) { in mbedtls_mpi_copy()
335 memset(X->p + i, 0, (X->n - i) * ciL); in mbedtls_mpi_copy()
338 memcpy(X->p, Y->p, i * ciL); in mbedtls_mpi_copy()
362 /* Take care to handle the most negative value (-2^(biL-1)) correctly. in mpi_sint_abs()
363 * A naive -z would have undefined behavior. in mpi_sint_abs()
366 return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z; in mpi_sint_abs()
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)
381 memset(X->p, 0, X->n * ciL); in mbedtls_mpi_lset()
383 X->p[0] = mpi_sint_abs(z); in mbedtls_mpi_lset()
384 X->s = TO_SIGN(z); in mbedtls_mpi_lset()
396 if (X->n * biL <= pos) { in mbedtls_mpi_get_bit()
400 return (X->p[pos / biL] >> (pos % biL)) & 0x01; in mbedtls_mpi_get_bit()
416 if (X->n * biL <= pos) { in mbedtls_mpi_set_bit()
424 X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx); in mbedtls_mpi_set_bit()
425 X->p[off] |= (mbedtls_mpi_uint) val << idx; in mbedtls_mpi_set_bit()
433 * Return the number of less significant zero-bits
450 for (i = 0; i < X->n; i++) { in mbedtls_mpi_lsb()
451 if (X->p[i] != 0) { in mbedtls_mpi_lsb()
452 return i * biL + mbedtls_mpi_uint_ctz(X->p[i]); in mbedtls_mpi_lsb()
457 for (i = 0; i < X->n; i++) { in mbedtls_mpi_lsb()
459 if (((X->p[i] >> j) & 1) != 0) { in mbedtls_mpi_lsb()
474 return mbedtls_mpi_core_bitlen(X->p, X->n); in mbedtls_mpi_bitlen()
493 *d = c - 0x30; in mpi_get_digit()
496 *d = c - 0x37; in mpi_get_digit()
499 *d = c - 0x57; in mpi_get_digit()
512 int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s) in mbedtls_mpi_read_string() argument
526 if (s[0] == 0) { in mbedtls_mpi_read_string()
531 if (s[0] == '-') { in mbedtls_mpi_read_string()
532 ++s; in mbedtls_mpi_read_string()
533 sign = -1; in mbedtls_mpi_read_string()
536 slen = strlen(s); in mbedtls_mpi_read_string()
548 for (i = slen, j = 0; i > 0; i--, j++) { in mbedtls_mpi_read_string()
549 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1])); in mbedtls_mpi_read_string()
550 X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2); in mbedtls_mpi_read_string()
556 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i])); in mbedtls_mpi_read_string()
563 X->s = -1; in mbedtls_mpi_read_string()
574 * Helper to write the digits high-order first.
595 *(--p_end) = (char) ('0' + r); in mpi_write_hlp()
597 *(--p_end) = (char) ('A' + (r - 0xA)); in mpi_write_hlp()
628 n >>= 1; /* Number of 4-adic digits necessary to present in mbedtls_mpi_write_string()
631 * radix-adic digits needed to present `n`. */ in mbedtls_mpi_write_string()
640 * in case it's not even. */ in mbedtls_mpi_write_string()
641 n += 1; /* Potential '-'-sign. */ in mbedtls_mpi_write_string()
643 * which always uses an even number of hex-digits. */ in mbedtls_mpi_write_string()
653 if (X->s == -1) { in mbedtls_mpi_write_string()
654 *p++ = '-'; in mbedtls_mpi_write_string()
655 buflen--; in mbedtls_mpi_write_string()
662 for (i = X->n, k = 0; i > 0; i--) { in mbedtls_mpi_write_string()
663 for (j = ciL; j > 0; j--) { in mbedtls_mpi_write_string()
664 c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF; in mbedtls_mpi_write_string()
678 if (T.s == -1) { in mbedtls_mpi_write_string()
679 T.s = 1; in mbedtls_mpi_write_string()
686 *olen = (size_t) (p - buf); in mbedtls_mpi_write_string()
708 char s[MBEDTLS_MPI_RW_BUFFER_SIZE]; in mbedtls_mpi_read_file() local
714 memset(s, 0, sizeof(s)); in mbedtls_mpi_read_file()
715 if (fgets(s, sizeof(s) - 1, fin) == NULL) { in mbedtls_mpi_read_file()
719 slen = strlen(s); in mbedtls_mpi_read_file()
720 if (slen == sizeof(s) - 2) { in mbedtls_mpi_read_file()
724 if (slen > 0 && s[slen - 1] == '\n') { in mbedtls_mpi_read_file()
725 slen--; s[slen] = '\0'; in mbedtls_mpi_read_file()
727 if (slen > 0 && s[slen - 1] == '\r') { in mbedtls_mpi_read_file()
728 slen--; s[slen] = '\0'; in mbedtls_mpi_read_file()
731 p = s + slen; in mbedtls_mpi_read_file()
732 while (p-- > s) { in mbedtls_mpi_read_file()
752 char s[MBEDTLS_MPI_RW_BUFFER_SIZE]; in mbedtls_mpi_write_file() local
758 memset(s, 0, sizeof(s)); in mbedtls_mpi_write_file()
760 MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n)); in mbedtls_mpi_write_file()
767 slen = strlen(s); in mbedtls_mpi_write_file()
768 s[slen++] = '\r'; in mbedtls_mpi_write_file()
769 s[slen++] = '\n'; in mbedtls_mpi_write_file()
773 fwrite(s, 1, slen, fout) != slen) { in mbedtls_mpi_write_file()
777 mbedtls_printf("%s%s", p, s); in mbedtls_mpi_write_file()
790 * number of limbs (in particular, it does not skip 0s in the input).
801 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen)); in mbedtls_mpi_read_binary_le()
817 * number of limbs (in particular, it does not skip 0s in the input).
827 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen)); in mbedtls_mpi_read_binary()
845 return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen); in mbedtls_mpi_write_binary_le()
854 return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen); in mbedtls_mpi_write_binary()
858 * Left-shift: X <<= count
867 if (X->n * biL < i) { in mbedtls_mpi_shift_l()
873 mbedtls_mpi_core_shift_l(X->p, X->n, count); in mbedtls_mpi_shift_l()
880 * Right-shift: X >>= count
884 if (X->n != 0) { in mbedtls_mpi_shift_r()
885 mbedtls_mpi_core_shift_r(X->p, X->n, count); in mbedtls_mpi_shift_r()
897 for (i = X->n; i > 0; i--) { in mbedtls_mpi_cmp_abs()
898 if (X->p[i - 1] != 0) { in mbedtls_mpi_cmp_abs()
903 for (j = Y->n; j > 0; j--) { in mbedtls_mpi_cmp_abs()
904 if (Y->p[j - 1] != 0) { in mbedtls_mpi_cmp_abs()
916 return -1; in mbedtls_mpi_cmp_abs()
919 for (; i > 0; i--) { in mbedtls_mpi_cmp_abs()
920 if (X->p[i - 1] > Y->p[i - 1]) { in mbedtls_mpi_cmp_abs()
923 if (X->p[i - 1] < Y->p[i - 1]) { in mbedtls_mpi_cmp_abs()
924 return -1; in mbedtls_mpi_cmp_abs()
938 for (i = X->n; i > 0; i--) { in mbedtls_mpi_cmp_mpi()
939 if (X->p[i - 1] != 0) { in mbedtls_mpi_cmp_mpi()
944 for (j = Y->n; j > 0; j--) { in mbedtls_mpi_cmp_mpi()
945 if (Y->p[j - 1] != 0) { in mbedtls_mpi_cmp_mpi()
955 return X->s; in mbedtls_mpi_cmp_mpi()
958 return -Y->s; in mbedtls_mpi_cmp_mpi()
961 if (X->s > 0 && Y->s < 0) { in mbedtls_mpi_cmp_mpi()
964 if (Y->s > 0 && X->s < 0) { in mbedtls_mpi_cmp_mpi()
965 return -1; in mbedtls_mpi_cmp_mpi()
968 for (; i > 0; i--) { in mbedtls_mpi_cmp_mpi()
969 if (X->p[i - 1] > Y->p[i - 1]) { in mbedtls_mpi_cmp_mpi()
970 return X->s; in mbedtls_mpi_cmp_mpi()
972 if (X->p[i - 1] < Y->p[i - 1]) { in mbedtls_mpi_cmp_mpi()
973 return -X->s; in mbedtls_mpi_cmp_mpi()
989 Y.s = TO_SIGN(z); in mbedtls_mpi_cmp_int()
1017 X->s = 1; in mbedtls_mpi_add_abs()
1019 for (j = B->n; j > 0; j--) { in mbedtls_mpi_add_abs()
1020 if (B->p[j - 1] != 0) { in mbedtls_mpi_add_abs()
1025 /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0 in mbedtls_mpi_add_abs()
1033 /* j is the number of non-zero limbs of B. Add those to X. */ in mbedtls_mpi_add_abs()
1035 p = X->p; in mbedtls_mpi_add_abs()
1037 c = mbedtls_mpi_core_add(p, p, B->p, j); in mbedtls_mpi_add_abs()
1044 if (j >= X->n) { in mbedtls_mpi_add_abs()
1046 p = X->p + j; in mbedtls_mpi_add_abs()
1058 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1066 for (n = B->n; n > 0; n--) { in mbedtls_mpi_sub_abs()
1067 if (B->p[n - 1] != 0) { in mbedtls_mpi_sub_abs()
1071 if (n > A->n) { in mbedtls_mpi_sub_abs()
1077 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n)); in mbedtls_mpi_sub_abs()
1082 if (A->n > n && A != X) { in mbedtls_mpi_sub_abs()
1083 memcpy(X->p + n, A->p + n, (A->n - n) * ciL); in mbedtls_mpi_sub_abs()
1085 if (X->n > A->n) { in mbedtls_mpi_sub_abs()
1086 memset(X->p + A->n, 0, (X->n - A->n) * ciL); in mbedtls_mpi_sub_abs()
1089 carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n); in mbedtls_mpi_sub_abs()
1092 carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n); in mbedtls_mpi_sub_abs()
1102 X->s = 1; in mbedtls_mpi_sub_abs()
1109 * Calculate A + B * flip_B where flip_B is 1 or -1.
1115 int ret, s; in add_sub_mpi() local
1117 s = A->s; in add_sub_mpi()
1118 if (A->s * B->s * flip_B < 0) { in add_sub_mpi()
1125 X->s = cmp == 0 ? 1 : s; in add_sub_mpi()
1129 X->s = -s; in add_sub_mpi()
1133 X->s = s; in add_sub_mpi()
1150 * Signed subtraction: X = A - B
1154 return add_sub_mpi(X, A, B, -1); in mbedtls_mpi_sub_mpi()
1166 B.s = TO_SIGN(b); in mbedtls_mpi_add_int()
1174 * Signed subtraction: X = A - b
1182 B.s = TO_SIGN(b); in mbedtls_mpi_sub_int()
1209 for (i = A->n; i > 0; i--) { in mbedtls_mpi_mul_mpi()
1210 if (A->p[i - 1] != 0) { in mbedtls_mpi_mul_mpi()
1218 for (j = B->n; j > 0; j--) { in mbedtls_mpi_mul_mpi()
1219 if (B->p[j - 1] != 0) { in mbedtls_mpi_mul_mpi()
1230 mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j); in mbedtls_mpi_mul_mpi()
1233 * but does not eliminate side channels leaking the zero-ness. We do in mbedtls_mpi_mul_mpi()
1235 * not fully support an MPI object with a value of 0 and s == -1. */ in mbedtls_mpi_mul_mpi()
1237 X->s = 1; in mbedtls_mpi_mul_mpi()
1239 X->s = A->s * B->s; in mbedtls_mpi_mul_mpi()
1254 size_t n = A->n; in mbedtls_mpi_mul_int()
1255 while (n > 0 && A->p[n - 1] == 0) { in mbedtls_mpi_mul_int()
1256 --n; in mbedtls_mpi_mul_int()
1264 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */ in mbedtls_mpi_mul_int()
1267 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same in mbedtls_mpi_mul_int()
1275 * Note that calculating A*b as 0 + A*b doesn't work as-is because in mbedtls_mpi_mul_int()
1279 mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1); in mbedtls_mpi_mul_int()
1286 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1298 const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1; in mbedtls_int_div_int()
1301 size_t s; in mbedtls_int_div_int()
1319 if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) { in mbedtls_int_div_int()
1320 quotient = ((mbedtls_t_udbl) 1 << biL) - 1; in mbedtls_int_div_int()
1324 *r = (mbedtls_mpi_uint) (dividend - (quotient * d)); in mbedtls_int_div_int()
1331 * Algorithm D, Section 4.3.1 - The Art of Computer Programming in mbedtls_int_div_int()
1332 * Vol. 2 - Seminumerical Algorithms, Knuth in mbedtls_int_div_int()
1338 s = mbedtls_mpi_core_clz(d); in mbedtls_int_div_int()
1339 d = d << s; in mbedtls_int_div_int()
1341 u1 = u1 << s; in mbedtls_int_div_int()
1342 u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1)); in mbedtls_int_div_int()
1343 u0 = u0 << s; in mbedtls_int_div_int()
1355 r0 = u1 - d1 * q1; in mbedtls_int_div_int()
1358 q1 -= 1; in mbedtls_int_div_int()
1366 rAX = (u1 * radix) + (u0_msw - q1 * d); in mbedtls_int_div_int()
1368 r0 = rAX - q0 * d1; in mbedtls_int_div_int()
1371 q0 -= 1; in mbedtls_int_div_int()
1380 *r = (rAX * radix + u0_lsw - q0 * d) >> s; in mbedtls_int_div_int()
1407 * Avoid dynamic memory allocations for constant-size T2. in mbedtls_mpi_div_mpi()
1410 * so nobody increase the size of the MPI and we're safe to use an on-stack in mbedtls_mpi_div_mpi()
1413 T2.s = 1; in mbedtls_mpi_div_mpi()
1429 X.s = Y.s = 1; in mbedtls_mpi_div_mpi()
1431 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2)); in mbedtls_mpi_div_mpi()
1433 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2)); in mbedtls_mpi_div_mpi()
1436 if (k < biL - 1) { in mbedtls_mpi_div_mpi()
1437 k = biL - 1 - k; in mbedtls_mpi_div_mpi()
1444 n = X.n - 1; in mbedtls_mpi_div_mpi()
1445 t = Y.n - 1; in mbedtls_mpi_div_mpi()
1446 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t))); in mbedtls_mpi_div_mpi()
1449 Z.p[n - t]++; in mbedtls_mpi_div_mpi()
1452 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t))); in mbedtls_mpi_div_mpi()
1454 for (i = n; i > t; i--) { in mbedtls_mpi_div_mpi()
1456 Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u; in mbedtls_mpi_div_mpi()
1458 Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1], in mbedtls_mpi_div_mpi()
1462 T2.p[0] = (i < 2) ? 0 : X.p[i - 2]; in mbedtls_mpi_div_mpi()
1463 T2.p[1] = (i < 1) ? 0 : X.p[i - 1]; in mbedtls_mpi_div_mpi()
1466 Z.p[i - t - 1]++; in mbedtls_mpi_div_mpi()
1468 Z.p[i - t - 1]--; in mbedtls_mpi_div_mpi()
1471 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1]; in mbedtls_mpi_div_mpi()
1473 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1])); in mbedtls_mpi_div_mpi()
1476 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1])); in mbedtls_mpi_div_mpi()
1477 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); in mbedtls_mpi_div_mpi()
1482 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); in mbedtls_mpi_div_mpi()
1484 Z.p[i - t - 1]--; in mbedtls_mpi_div_mpi()
1490 Q->s = A->s * B->s; in mbedtls_mpi_div_mpi()
1495 X.s = A->s; in mbedtls_mpi_div_mpi()
1499 R->s = 1; in mbedtls_mpi_div_mpi()
1523 B.s = TO_SIGN(b); in mbedtls_mpi_div_int()
1575 if (b == 1 || A->n == 0) { in mbedtls_mpi_mod_int()
1581 *r = A->p[0] & 1; in mbedtls_mpi_mod_int()
1588 for (i = A->n, y = 0; i > 0; i--) { in mbedtls_mpi_mod_int()
1589 x = A->p[i - 1]; in mbedtls_mpi_mod_int()
1592 y -= z * b; in mbedtls_mpi_mod_int()
1597 y -= z * b; in mbedtls_mpi_mod_int()
1604 if (A->s < 0 && y != 0) { in mbedtls_mpi_mod_int()
1605 y = b - y; in mbedtls_mpi_mod_int()
1619 if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) { in mbedtls_mpi_exp_mod()
1635 if (E->n == 0) { in mbedtls_mpi_exp_mod()
1643 size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n); in mbedtls_mpi_exp_mod()
1653 * If 1st call, pre-compute R^2 mod N in mbedtls_mpi_exp_mod()
1655 if (prec_RR == NULL || prec_RR->p == NULL) { in mbedtls_mpi_exp_mod()
1662 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n)); in mbedtls_mpi_exp_mod()
1675 X->s = 1; in mbedtls_mpi_exp_mod()
1681 * - The core functions will not touch the limbs of X above N->n. The in mbedtls_mpi_exp_mod()
1684 * - Also, X must have at least as many limbs as N for the calls to the in mbedtls_mpi_exp_mod()
1690 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n)); in mbedtls_mpi_exp_mod()
1696 mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p); in mbedtls_mpi_exp_mod()
1697 mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T); in mbedtls_mpi_exp_mod()
1698 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()
1699 mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T); in mbedtls_mpi_exp_mod()
1705 if (A->s == -1 && (E->p[0] & 1) != 0) { in mbedtls_mpi_exp_mod()
1706 mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n); in mbedtls_mpi_exp_mod()
1707 X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1); in mbedtls_mpi_exp_mod()
1716 if (prec_RR == NULL || prec_RR->p == NULL) { in mbedtls_mpi_exp_mod()
1753 TA.s = TB.s = 1; in mbedtls_mpi_gcd()
1757 * - Sequences of multiplications or divisions by 2 are grouped into a in mbedtls_mpi_gcd()
1759 * - The procedure in HAC assumes that 0 < TB <= TA. in mbedtls_mpi_gcd()
1760 * - The condition TB <= TA is not actually necessary for correctness. in mbedtls_mpi_gcd()
1765 * - If TA = 0, the loop goes through 0 iterations and the result is in mbedtls_mpi_gcd()
1767 * - The case TB = 0 was short-circuited above. in mbedtls_mpi_gcd()
1771 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1 in mbedtls_mpi_gcd()
1772 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1 in mbedtls_mpi_gcd()
1782 * At each iteration, either the right-shift by 1 is made on a nonzero in mbedtls_mpi_gcd()
1784 * by at least 1, or the right-shift by 1 is made on zero and then in mbedtls_mpi_gcd()
1785 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted in mbedtls_mpi_gcd()
1786 * since in that case TB is calculated from TB-TA with the condition TB>TA). in mbedtls_mpi_gcd()
1793 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd, in mbedtls_mpi_gcd()
1794 * TA-TB is even so the division by 2 has an integer result. in mbedtls_mpi_gcd()
1796 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2 in mbedtls_mpi_gcd()
1797 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also in mbedtls_mpi_gcd()
1812 * - If there was at least one loop iteration, then one of TA or TB is odd, in mbedtls_mpi_gcd()
1815 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B. in mbedtls_mpi_gcd()
1848 ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng); in mbedtls_mpi_fill_random()
1870 int ret = mbedtls_mpi_resize_clear(X, N->n); in mbedtls_mpi_random()
1875 return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng); in mbedtls_mpi_random()
1879 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2000 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2010 if ((X->p[0] & 1) == 0) { in mpi_check_small_factors()
2030 * Miller-Rabin pseudo-primality test (HAC 4.24)
2037 size_t i, j, k, s; in mpi_miller_rabin() local
2045 * W = |X| - 1 in mpi_miller_rabin()
2049 s = mbedtls_mpi_lsb(&W); in mpi_miller_rabin()
2051 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s)); in mpi_miller_rabin()
2055 * pick a random A, 1 < A < |X| - 1 in mpi_miller_rabin()
2059 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng)); in mpi_miller_rabin()
2064 A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1; in mpi_miller_rabin()
2086 while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) { in mpi_miller_rabin()
2101 * not prime if A != |X| - 1 or A == 1 in mpi_miller_rabin()
2119 * Pseudo-primality test: small factors, then Miller-Rabin
2128 XX.s = 1; in mbedtls_mpi_is_prime_ext()
2129 XX.n = X->n; in mbedtls_mpi_is_prime_ext()
2130 XX.p = X->p; in mbedtls_mpi_is_prime_ext()
2155 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2186 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 in mbedtls_mpi_gen_prime()
2193 * 2^-100 error probability, number of rounds computed based on HAC, in mbedtls_mpi_gen_prime()
2204 … /* 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()
2205 if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) { in mbedtls_mpi_gen_prime()
2211 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits)); in mbedtls_mpi_gen_prime()
2213 X->p[0] |= 1; in mbedtls_mpi_gen_prime()
2228 X->p[0] |= 2; in mbedtls_mpi_gen_prime()
2237 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ in mbedtls_mpi_gen_prime()
2244 * before doing Miller-Rabin on any of them in mbedtls_mpi_gen_prime()
2260 * Next candidates. We want to preserve Y = (X-1) / 2 and in mbedtls_mpi_gen_prime()