Lines Matching full:x
56 int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X, in mbedtls_mpi_lt_mpi_ct() argument
62 if (X->n != Y->n) { in mbedtls_mpi_lt_mpi_ct()
70 X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1); in mbedtls_mpi_lt_mpi_ct()
75 * That is if X is negative (X_is_negative == 1), then X < Y is true and it in mbedtls_mpi_lt_mpi_ct()
76 * is false if X is positive (X_is_negative == 0). in mbedtls_mpi_lt_mpi_ct()
82 * Assuming signs are the same, compare X and Y. We switch the comparison 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()
105 * Conditionally assign X = Y, without leaking information
107 * (Leaking information about the respective sizes of X and Y is ok however.)
117 int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X, in mbedtls_mpi_safe_cond_assign() argument
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()
143 * Conditionally swap X and Y, without leaking information
146 * different memory access patterns when X and Y are used afterwards.
148 int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X, in mbedtls_mpi_safe_cond_swap() argument
155 if (X == Y) { in mbedtls_mpi_safe_cond_swap()
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()
168 mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap); in mbedtls_mpi_safe_cond_swap()
180 void mbedtls_mpi_init(mbedtls_mpi *X) in mbedtls_mpi_init() argument
182 X->s = 1; in mbedtls_mpi_init()
183 X->n = 0; in mbedtls_mpi_init()
184 X->p = NULL; in mbedtls_mpi_init()
190 void mbedtls_mpi_free(mbedtls_mpi *X) in mbedtls_mpi_free() argument
192 if (X == NULL) { in mbedtls_mpi_free()
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()
208 int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs) in mbedtls_mpi_grow() argument
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()
239 int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs) in mbedtls_mpi_shrink() argument
249 if (X->n <= nblimbs) { in mbedtls_mpi_shrink()
250 return mbedtls_mpi_grow(X, 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()
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) in mbedtls_mpi_resize_clear() argument
286 mbedtls_mpi_free(X); in mbedtls_mpi_resize_clear()
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()
293 mbedtls_mpi_free(X); in mbedtls_mpi_resize_clear()
294 return mbedtls_mpi_grow(X, limbs); in mbedtls_mpi_resize_clear()
299 * Copy the contents of Y into X.
303 * Ensure that X does not shrink. This is not guaranteed by the public API,
306 int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y) in mbedtls_mpi_copy() argument
311 if (X == Y) { 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()
330 X->s = Y->s; in mbedtls_mpi_copy()
332 if (X->n < i) { in mbedtls_mpi_copy()
333 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 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()
346 * Swap the contents of X and Y
348 void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y) in mbedtls_mpi_swap() argument
352 memcpy(&T, X, sizeof(mbedtls_mpi)); in mbedtls_mpi_swap()
353 memcpy(X, Y, sizeof(mbedtls_mpi)); in mbedtls_mpi_swap()
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) argument
376 int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z) in mbedtls_mpi_lset() argument
380 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1)); in mbedtls_mpi_lset()
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()
394 int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos) in mbedtls_mpi_get_bit() argument
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()
406 int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val) in mbedtls_mpi_set_bit() argument
416 if (X->n * biL <= pos) { in mbedtls_mpi_set_bit()
421 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1)); 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()
435 size_t mbedtls_mpi_lsb(const mbedtls_mpi *X) in mbedtls_mpi_lsb() argument
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()
472 size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X) in mbedtls_mpi_bitlen() argument
474 return mbedtls_mpi_core_bitlen(X->p, X->n); in mbedtls_mpi_bitlen()
480 size_t mbedtls_mpi_size(const mbedtls_mpi *X) in mbedtls_mpi_size() argument
482 return (mbedtls_mpi_bitlen(X) + 7) >> 3; in mbedtls_mpi_size()
512 int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s) in mbedtls_mpi_read_string() argument
527 mbedtls_mpi_free(X); in mbedtls_mpi_read_string()
545 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n)); in mbedtls_mpi_read_string()
546 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); in mbedtls_mpi_read_string()
550 X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2); in mbedtls_mpi_read_string()
553 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); in mbedtls_mpi_read_string()
557 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix)); in mbedtls_mpi_read_string()
558 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d)); in mbedtls_mpi_read_string()
562 if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) { in mbedtls_mpi_read_string()
563 X->s = -1; in mbedtls_mpi_read_string()
576 static int mpi_write_hlp(mbedtls_mpi *X, int radix, in mpi_write_hlp() argument
589 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix)); in mpi_write_hlp()
590 MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix)); in mpi_write_hlp()
601 } while (mbedtls_mpi_cmp_int(X, 0) != 0); in mpi_write_hlp()
614 int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix, in mbedtls_mpi_write_string() argument
626 n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */ in mbedtls_mpi_write_string()
653 if (X->s == -1) { in mbedtls_mpi_write_string()
662 for (i = X->n, k = 0; i > 0; i--) { in mbedtls_mpi_write_string()
664 c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF; in mbedtls_mpi_write_string()
676 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X)); in mbedtls_mpi_write_string()
697 * Read X from an opened file
699 int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin) in mbedtls_mpi_read_file() argument
738 return mbedtls_mpi_read_string(X, radix, p + 1); in mbedtls_mpi_read_file()
742 * Write X into an opened file (or stdout if fout == NULL)
744 int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout) in mbedtls_mpi_write_file() argument
760 MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n)); in mbedtls_mpi_write_file()
787 * Import X from unsigned binary data, little endian
792 int mbedtls_mpi_read_binary_le(mbedtls_mpi *X, in mbedtls_mpi_read_binary_le() argument
799 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); in mbedtls_mpi_read_binary_le()
801 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen)); in mbedtls_mpi_read_binary_le()
814 * Import X from unsigned binary data, big endian
819 int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen) in mbedtls_mpi_read_binary() argument
825 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); in mbedtls_mpi_read_binary()
827 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen)); in mbedtls_mpi_read_binary()
840 * Export X into unsigned binary data, little endian
842 int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X, in mbedtls_mpi_write_binary_le() argument
845 return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen); in mbedtls_mpi_write_binary_le()
849 * Export X into unsigned binary data, big endian
851 int mbedtls_mpi_write_binary(const mbedtls_mpi *X, in mbedtls_mpi_write_binary() argument
854 return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen); in mbedtls_mpi_write_binary()
858 * Left-shift: X <<= count
860 int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count) in mbedtls_mpi_shift_l() argument
865 i = mbedtls_mpi_bitlen(X) + count; in mbedtls_mpi_shift_l()
867 if (X->n * biL < i) { in mbedtls_mpi_shift_l()
868 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(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
882 int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count) in mbedtls_mpi_shift_r() argument
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()
893 int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y) in mbedtls_mpi_cmp_abs() argument
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()
909 /* If i == j == 0, i.e. abs(X) == abs(Y), 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()
934 int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y) in mbedtls_mpi_cmp_mpi() argument
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()
955 return X->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()
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()
983 int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z) in mbedtls_mpi_cmp_int() argument
993 return mbedtls_mpi_cmp_mpi(X, &Y); in mbedtls_mpi_cmp_int()
997 * Unsigned addition: X = |A| + |B| (HAC 14.7)
999 int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_add_abs() argument
1006 if (X == B) { in mbedtls_mpi_add_abs()
1007 const mbedtls_mpi *T = A; A = X; B = T; in mbedtls_mpi_add_abs()
1010 if (X != A) { in mbedtls_mpi_add_abs()
1011 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); in mbedtls_mpi_add_abs()
1015 * X must always be positive as a result of unsigned additions. in mbedtls_mpi_add_abs()
1017 X->s = 1; in mbedtls_mpi_add_abs()
1025 /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0 in mbedtls_mpi_add_abs()
1031 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j)); 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()
1044 if (j >= X->n) { in mbedtls_mpi_add_abs()
1045 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1)); 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)
1060 int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_sub_abs() argument
1077 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n)); in mbedtls_mpi_sub_abs()
1079 /* Set the high limbs of X to match A. Don't touch the lower limbs in mbedtls_mpi_sub_abs()
1080 * because X might be aliased to B, and we must not overwrite the 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()
1091 /* Propagate the carry through the rest of X. */ 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()
1101 /* X should always be positive as a result of unsigned subtractions. */ in mbedtls_mpi_sub_abs()
1102 X->s = 1; in mbedtls_mpi_sub_abs()
1111 static int add_sub_mpi(mbedtls_mpi *X, in add_sub_mpi() argument
1121 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B)); in add_sub_mpi()
1125 X->s = cmp == 0 ? 1 : s; in add_sub_mpi()
1127 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A)); in add_sub_mpi()
1129 X->s = -s; in add_sub_mpi()
1132 MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B)); in add_sub_mpi()
1133 X->s = s; in add_sub_mpi()
1142 * Signed addition: X = A + B
1144 int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_add_mpi() argument
1146 return add_sub_mpi(X, A, B, 1); in mbedtls_mpi_add_mpi()
1150 * Signed subtraction: X = A - B
1152 int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_sub_mpi() argument
1154 return add_sub_mpi(X, A, B, -1); in mbedtls_mpi_sub_mpi()
1158 * Signed addition: X = A + b
1160 int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) in mbedtls_mpi_add_int() argument
1170 return mbedtls_mpi_add_mpi(X, A, &B); in mbedtls_mpi_add_int()
1174 * Signed subtraction: X = A - b
1176 int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) in mbedtls_mpi_sub_int() argument
1186 return mbedtls_mpi_sub_mpi(X, A, &B); in mbedtls_mpi_sub_int()
1190 * Baseline multiplication: X = A * B (HAC 14.12)
1192 int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) in mbedtls_mpi_mul_mpi() argument
1202 if (X == A) { in mbedtls_mpi_mul_mpi()
1205 if (X == B) { in mbedtls_mpi_mul_mpi()
1227 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j)); in mbedtls_mpi_mul_mpi()
1228 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); in mbedtls_mpi_mul_mpi()
1230 mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j); 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()
1250 * Baseline multiplication: X = A * b
1252 int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b) in mbedtls_mpi_mul_int() argument
1261 return mbedtls_mpi_lset(X, 0); in mbedtls_mpi_mul_int()
1276 * A,X can be the same. */ in mbedtls_mpi_mul_int()
1277 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1)); in mbedtls_mpi_mul_int()
1278 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); in mbedtls_mpi_mul_int()
1279 mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1); in mbedtls_mpi_mul_int()
1397 mbedtls_mpi X, Y, Z, T1, T2; in mbedtls_mpi_div_mpi() local
1404 mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z); in mbedtls_mpi_div_mpi()
1427 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A)); in mbedtls_mpi_div_mpi()
1429 X.s = Y.s = 1; in mbedtls_mpi_div_mpi()
1438 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k)); in mbedtls_mpi_div_mpi()
1444 n = X.n - 1; in mbedtls_mpi_div_mpi()
1448 while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) { in mbedtls_mpi_div_mpi()
1450 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y)); in mbedtls_mpi_div_mpi()
1455 if (X.p[i] >= Y.p[t]) { 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()
1464 T2.p[2] = X.p[i]; in mbedtls_mpi_div_mpi()
1478 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1)); in mbedtls_mpi_div_mpi()
1480 if (mbedtls_mpi_cmp_int(&X, 0) < 0) { in mbedtls_mpi_div_mpi()
1483 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1)); in mbedtls_mpi_div_mpi()
1494 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k)); in mbedtls_mpi_div_mpi()
1495 X.s = A->s; in mbedtls_mpi_div_mpi()
1496 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X)); in mbedtls_mpi_div_mpi()
1505 mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z); in mbedtls_mpi_div_mpi()
1562 mbedtls_mpi_uint x, y, z; in mbedtls_mpi_mod_int() local
1589 x = A->p[i - 1]; in mbedtls_mpi_mod_int()
1590 y = (y << biH) | (x >> biH); in mbedtls_mpi_mod_int()
1594 x <<= biH; in mbedtls_mpi_mod_int()
1595 y = (y << biH) | (x >> biH); in mbedtls_mpi_mod_int()
1613 int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A, in mbedtls_mpi_exp_mod() argument
1636 ret = mbedtls_mpi_lset(X, 1); in mbedtls_mpi_exp_mod()
1667 * To preserve constness we need to make a copy of A. Using X for this to in mbedtls_mpi_exp_mod()
1670 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); in mbedtls_mpi_exp_mod()
1675 X->s = 1; in mbedtls_mpi_exp_mod()
1678 * Make sure that X is in a form that is safe for consumption by 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()
1687 if (mbedtls_mpi_cmp_mpi(X, N) >= 0) { in mbedtls_mpi_exp_mod()
1688 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N)); in mbedtls_mpi_exp_mod()
1690 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n)); 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()
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()
1709 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X)); in mbedtls_mpi_exp_mod()
1830 * Fill X with size bytes of random.
1835 int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size, in mbedtls_mpi_fill_random() argument
1843 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); in mbedtls_mpi_fill_random()
1848 ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng); in mbedtls_mpi_fill_random()
1854 int mbedtls_mpi_random(mbedtls_mpi *X, in mbedtls_mpi_random() argument
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)
1881 int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N) in mbedtls_mpi_inv_mod() argument
1955 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1)); in mbedtls_mpi_inv_mod()
1995 * Small divisors test (X must be positive)
2003 static int mpi_check_small_factors(const mbedtls_mpi *X) in mpi_check_small_factors() argument
2010 if ((X->p[0] & 1) == 0) { in mpi_check_small_factors()
2015 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p)); in mpi_check_small_factors()
2017 if (mbedtls_mpi_cmp_int(X, p) == 0) { in mpi_check_small_factors()
2032 static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds, in mpi_miller_rabin() argument
2045 * W = |X| - 1 in mpi_miller_rabin()
2048 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1)); 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()
2076 * A = A^R mod |X| in mpi_miller_rabin()
2078 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR)); in mpi_miller_rabin()
2088 * A = A * A mod |X| in mpi_miller_rabin()
2091 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X)); in mpi_miller_rabin()
2101 * not prime if A != |X| - 1 or A == 1 in mpi_miller_rabin()
2121 int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds, in mbedtls_mpi_is_prime_ext() argument
2129 XX.n = X->n; in mbedtls_mpi_is_prime_ext()
2130 XX.p = X->p; in mbedtls_mpi_is_prime_ext()
2159 int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags, in mbedtls_mpi_gen_prime() argument
2203 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng)); 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()
2216 ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng); in mbedtls_mpi_gen_prime()
2223 * A necessary condition for Y and X = 2Y + 1 to be prime in mbedtls_mpi_gen_prime()
2224 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). in mbedtls_mpi_gen_prime()
2225 * Make sure it is satisfied, while keeping X = 3 mod 4 in mbedtls_mpi_gen_prime()
2228 X->p[0] |= 2; in mbedtls_mpi_gen_prime()
2230 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3)); in mbedtls_mpi_gen_prime()
2232 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8)); in mbedtls_mpi_gen_prime()
2234 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4)); in mbedtls_mpi_gen_prime()
2237 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ in mbedtls_mpi_gen_prime()
2238 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X)); in mbedtls_mpi_gen_prime()
2243 * First, check small factors for X and Y in mbedtls_mpi_gen_prime()
2246 if ((ret = mpi_check_small_factors(X)) == 0 && in mbedtls_mpi_gen_prime()
2248 (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng)) in mbedtls_mpi_gen_prime()
2260 * Next candidates. We want to preserve Y = (X-1) / 2 and in mbedtls_mpi_gen_prime()
2261 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) in mbedtls_mpi_gen_prime()
2262 * so up Y by 6 and X by 12. in mbedtls_mpi_gen_prime()
2264 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12)); in mbedtls_mpi_gen_prime()
2296 mbedtls_mpi A, E, N, X, Y, U, V; in mbedtls_mpi_self_test() local
2298 mbedtls_mpi_init(&A); mbedtls_mpi_init(&E); mbedtls_mpi_init(&N); mbedtls_mpi_init(&X); in mbedtls_mpi_self_test()
2318 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N)); in mbedtls_mpi_self_test()
2333 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { in mbedtls_mpi_self_test()
2346 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N)); in mbedtls_mpi_self_test()
2360 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 || in mbedtls_mpi_self_test()
2374 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL)); in mbedtls_mpi_self_test()
2385 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { in mbedtls_mpi_self_test()
2398 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N)); in mbedtls_mpi_self_test()
2409 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { in mbedtls_mpi_self_test()
2427 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0])); in mbedtls_mpi_self_test()
2430 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y)); in mbedtls_mpi_self_test()
2449 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret); in mbedtls_mpi_self_test()
2452 mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X); in mbedtls_mpi_self_test()