summaryrefslogtreecommitdiffstats
path: root/thirdparty/mbedtls/library/bignum.c
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/mbedtls/library/bignum.c')
-rw-r--r--thirdparty/mbedtls/library/bignum.c1349
1 files changed, 313 insertions, 1036 deletions
diff --git a/thirdparty/mbedtls/library/bignum.c b/thirdparty/mbedtls/library/bignum.c
index fadd9e9cc2..c45fd5bf24 100644
--- a/thirdparty/mbedtls/library/bignum.c
+++ b/thirdparty/mbedtls/library/bignum.c
@@ -26,48 +26,159 @@
#if defined(MBEDTLS_BIGNUM_C)
#include "mbedtls/bignum.h"
-#include "mbedtls/bn_mul.h"
+#include "bignum_core.h"
+#include "bn_mul.h"
#include "mbedtls/platform_util.h"
#include "mbedtls/error.h"
#include "constant_time_internal.h"
-#include "bignum_internal.h"
#include <limits.h>
#include <string.h>
#include "mbedtls/platform.h"
-#define MPI_VALIDATE_RET(cond) \
- MBEDTLS_INTERNAL_VALIDATE_RET(cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA)
-#define MPI_VALIDATE(cond) \
- MBEDTLS_INTERNAL_VALIDATE(cond)
-#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
-#define biL (ciL << 3) /* bits in limb */
-#define biH (ciL << 2) /* half limb size */
-#define MPI_SIZE_T_MAX ((size_t) -1) /* SIZE_T_MAX is not standard */
+/*
+ * Conditionally select an MPI sign in constant time.
+ * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid
+ * values.)
+ */
+static inline signed short mbedtls_ct_mpi_sign_if(mbedtls_ct_condition_t cond,
+ signed short sign1, signed short sign2)
+{
+ return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1;
+}
/*
- * Convert between bits/chars and number of limbs
- * Divide first in order to avoid potential overflows
+ * Compare signed values in constant time
*/
-#define BITS_TO_LIMBS(i) ((i) / biL + ((i) % biL != 0))
-#define CHARS_TO_LIMBS(i) ((i) / ciL + ((i) % ciL != 0))
+int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X,
+ const mbedtls_mpi *Y,
+ unsigned *ret)
+{
+ mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result;
-/* Implementation that should never be optimized out by the compiler */
-static void mbedtls_mpi_zeroize(mbedtls_mpi_uint *v, size_t n)
+ if (X->n != Y->n) {
+ return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+ }
+
+ /*
+ * Set N_is_negative to MBEDTLS_CT_FALSE if N >= 0, MBEDTLS_CT_TRUE if N < 0.
+ * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
+ */
+ X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1);
+ Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1);
+
+ /*
+ * If the signs are different, then the positive operand is the bigger.
+ * That is if X is negative (X_is_negative == 1), then X < Y is true and it
+ * is false if X is positive (X_is_negative == 0).
+ */
+ different_sign = mbedtls_ct_bool_ne(X_is_negative, Y_is_negative); // true if different sign
+ result = mbedtls_ct_bool_and(different_sign, X_is_negative);
+
+ /*
+ * Assuming signs are the same, compare X and Y. We switch the comparison
+ * order if they are negative so that we get the right result, regardles of
+ * sign.
+ */
+
+ /* This array is used to conditionally swap the pointers in const time */
+ void * const p[2] = { X->p, Y->p };
+ size_t i = mbedtls_ct_size_if_else_0(X_is_negative, 1);
+ mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n);
+
+ /*
+ * Store in result iff the signs are the same (i.e., iff different_sign == false). If
+ * the signs differ, result has already been set, so we don't change it.
+ */
+ result = mbedtls_ct_bool_or(result,
+ mbedtls_ct_bool_and(mbedtls_ct_bool_not(different_sign), lt));
+
+ *ret = mbedtls_ct_uint_if_else_0(result, 1);
+
+ return 0;
+}
+
+/*
+ * Conditionally assign X = Y, without leaking information
+ * about whether the assignment was made or not.
+ * (Leaking information about the respective sizes of X and Y is ok however.)
+ */
+#if defined(_MSC_VER) && defined(MBEDTLS_PLATFORM_IS_WINDOWS_ON_ARM64) && \
+ (_MSC_FULL_VER < 193131103)
+/*
+ * MSVC miscompiles this function if it's inlined prior to Visual Studio 2022 version 17.1. See:
+ * https://developercommunity.visualstudio.com/t/c-compiler-miscompiles-part-of-mbedtls-library-on/1646989
+ */
+__declspec(noinline)
+#endif
+int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X,
+ const mbedtls_mpi *Y,
+ unsigned char assign)
{
- mbedtls_platform_zeroize(v, ciL * n);
+ int ret = 0;
+
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
+
+ {
+ mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign);
+
+ X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s);
+
+ mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign);
+
+ mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign);
+ for (size_t i = Y->n; i < X->n; i++) {
+ X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]);
+ }
+ }
+
+cleanup:
+ return ret;
}
/*
+ * Conditionally swap X and Y, without leaking information
+ * about whether the swap was made or not.
+ * Here it is not ok to simply swap the pointers, which would lead to
+ * different memory access patterns when X and Y are used afterwards.
+ */
+int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X,
+ mbedtls_mpi *Y,
+ unsigned char swap)
+{
+ int ret = 0;
+ int s;
+
+ if (X == Y) {
+ return 0;
+ }
+
+ mbedtls_ct_condition_t do_swap = mbedtls_ct_bool(swap);
+
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n));
+
+ s = X->s;
+ X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s);
+ Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s);
+
+ mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap);
+
+cleanup:
+ return ret;
+}
+
+/* Implementation that should never be optimized out by the compiler */
+#define mbedtls_mpi_zeroize_and_free(v, n) mbedtls_zeroize_and_free(v, ciL * (n))
+
+/*
* Initialize one MPI
*/
void mbedtls_mpi_init(mbedtls_mpi *X)
{
- MPI_VALIDATE(X != NULL);
-
X->s = 1;
X->n = 0;
X->p = NULL;
@@ -83,8 +194,7 @@ void mbedtls_mpi_free(mbedtls_mpi *X)
}
if (X->p != NULL) {
- mbedtls_mpi_zeroize(X->p, X->n);
- mbedtls_free(X->p);
+ mbedtls_mpi_zeroize_and_free(X->p, X->n);
}
X->s = 1;
@@ -98,7 +208,6 @@ void mbedtls_mpi_free(mbedtls_mpi *X)
int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
{
mbedtls_mpi_uint *p;
- MPI_VALIDATE_RET(X != NULL);
if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
return MBEDTLS_ERR_MPI_ALLOC_FAILED;
@@ -111,11 +220,12 @@ int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
if (X->p != NULL) {
memcpy(p, X->p, X->n * ciL);
- mbedtls_mpi_zeroize(X->p, X->n);
- mbedtls_free(X->p);
+ mbedtls_mpi_zeroize_and_free(X->p, X->n);
}
- X->n = nblimbs;
+ /* nblimbs fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
+ * fits, and we've checked that nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
+ X->n = (unsigned short) nblimbs;
X->p = p;
}
@@ -130,7 +240,6 @@ int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
{
mbedtls_mpi_uint *p;
size_t i;
- MPI_VALIDATE_RET(X != NULL);
if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
return MBEDTLS_ERR_MPI_ALLOC_FAILED;
@@ -159,11 +268,12 @@ int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
if (X->p != NULL) {
memcpy(p, X->p, i * ciL);
- mbedtls_mpi_zeroize(X->p, X->n);
- mbedtls_free(X->p);
+ mbedtls_mpi_zeroize_and_free(X->p, X->n);
}
- X->n = i;
+ /* i fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
+ * fits, and we've checked that i <= nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
+ X->n = (unsigned short) i;
X->p = p;
return 0;
@@ -191,15 +301,12 @@ static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
* This function is not constant-time. Leading zeros in Y may be removed.
*
* Ensure that X does not shrink. This is not guaranteed by the public API,
- * but some code in the bignum module relies on this property, for example
- * in mbedtls_mpi_exp_mod().
+ * but some code in the bignum module might still rely on this property.
*/
int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
{
int ret = 0;
size_t i;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(Y != NULL);
if (X == Y) {
return 0;
@@ -241,8 +348,6 @@ cleanup:
void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y)
{
mbedtls_mpi T;
- MPI_VALIDATE(X != NULL);
- MPI_VALIDATE(Y != NULL);
memcpy(&T, X, sizeof(mbedtls_mpi));
memcpy(X, Y, sizeof(mbedtls_mpi));
@@ -261,19 +366,22 @@ static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
}
+/* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
+ * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
+#define TO_SIGN(x) ((mbedtls_mpi_sint) (((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1)
+
/*
* Set value from integer
*/
int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- MPI_VALIDATE_RET(X != NULL);
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1));
memset(X->p, 0, X->n * ciL);
X->p[0] = mpi_sint_abs(z);
- X->s = (z < 0) ? -1 : 1;
+ X->s = TO_SIGN(z);
cleanup:
@@ -285,8 +393,6 @@ cleanup:
*/
int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
{
- MPI_VALIDATE_RET(X != NULL);
-
if (X->n * biL <= pos) {
return 0;
}
@@ -294,10 +400,6 @@ int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
return (X->p[pos / biL] >> (pos % biL)) & 0x01;
}
-/* Get a specific byte, without range checks. */
-#define GET_BYTE(X, i) \
- (((X)->p[(i) / ciL] >> (((i) % ciL) * 8)) & 0xff)
-
/*
* Set a bit to a specific value of 0 or 1
*/
@@ -306,7 +408,6 @@ int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
int ret = 0;
size_t off = pos / biL;
size_t idx = pos % biL;
- MPI_VALIDATE_RET(X != NULL);
if (val != 0 && val != 1) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
@@ -333,59 +434,44 @@ cleanup:
*/
size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
{
- size_t i, j, count = 0;
- MBEDTLS_INTERNAL_VALIDATE_RET(X != NULL, 0);
+ size_t i;
+#if defined(__has_builtin)
+#if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz)
+ #define mbedtls_mpi_uint_ctz __builtin_ctz
+#elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl)
+ #define mbedtls_mpi_uint_ctz __builtin_ctzl
+#elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll)
+ #define mbedtls_mpi_uint_ctz __builtin_ctzll
+#endif
+#endif
+
+#if defined(mbedtls_mpi_uint_ctz)
for (i = 0; i < X->n; i++) {
- for (j = 0; j < biL; j++, count++) {
+ if (X->p[i] != 0) {
+ return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
+ }
+ }
+#else
+ size_t count = 0;
+ for (i = 0; i < X->n; i++) {
+ for (size_t j = 0; j < biL; j++, count++) {
if (((X->p[i] >> j) & 1) != 0) {
return count;
}
}
}
+#endif
return 0;
}
/*
- * Count leading zero bits in a given integer
- */
-static size_t mbedtls_clz(const mbedtls_mpi_uint x)
-{
- size_t j;
- mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
-
- for (j = 0; j < biL; j++) {
- if (x & mask) {
- break;
- }
-
- mask >>= 1;
- }
-
- return j;
-}
-
-/*
* Return the number of bits
*/
size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
{
- size_t i, j;
-
- if (X->n == 0) {
- return 0;
- }
-
- for (i = X->n - 1; i > 0; i--) {
- if (X->p[i] != 0) {
- break;
- }
- }
-
- j = biL - mbedtls_clz(X->p[i]);
-
- return (i * biL) + j;
+ return mbedtls_mpi_core_bitlen(X->p, X->n);
}
/*
@@ -430,8 +516,6 @@ int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
int sign = 1;
mbedtls_mpi_uint d;
mbedtls_mpi T;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(s != NULL);
if (radix < 2 || radix > 16) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
@@ -452,7 +536,7 @@ int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
slen = strlen(s);
if (radix == 16) {
- if (slen > MPI_SIZE_T_MAX >> 2) {
+ if (slen > SIZE_MAX >> 2) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
}
@@ -534,9 +618,6 @@ int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix,
size_t n;
char *p;
mbedtls_mpi T;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(olen != NULL);
- MPI_VALIDATE_RET(buflen == 0 || buf != NULL);
if (radix < 2 || radix > 16) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
@@ -602,7 +683,7 @@ int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix,
}
*p++ = '\0';
- *olen = p - buf;
+ *olen = (size_t) (p - buf);
cleanup:
@@ -626,9 +707,6 @@ int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin)
*/
char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(fin != NULL);
-
if (radix < 2 || radix > 16) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
}
@@ -672,7 +750,6 @@ int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE
* newline characters and '\0'
*/
char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
- MPI_VALIDATE_RET(X != NULL);
if (radix < 2 || radix > 16) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
@@ -706,111 +783,22 @@ cleanup:
}
#endif /* MBEDTLS_FS_IO */
-
-/* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
- * into the storage form used by mbedtls_mpi. */
-
-static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c(mbedtls_mpi_uint x)
-{
- uint8_t i;
- unsigned char *x_ptr;
- mbedtls_mpi_uint tmp = 0;
-
- for (i = 0, x_ptr = (unsigned char *) &x; i < ciL; i++, x_ptr++) {
- tmp <<= CHAR_BIT;
- tmp |= (mbedtls_mpi_uint) *x_ptr;
- }
-
- return tmp;
-}
-
-static mbedtls_mpi_uint mpi_uint_bigendian_to_host(mbedtls_mpi_uint x)
-{
-#if defined(__BYTE_ORDER__)
-
-/* Nothing to do on bigendian systems. */
-#if (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
- return x;
-#endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
-
-#if (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
-
-/* For GCC and Clang, have builtins for byte swapping. */
-#if defined(__GNUC__) && defined(__GNUC_PREREQ)
-#if __GNUC_PREREQ(4, 3)
-#define have_bswap
-#endif
-#endif
-
-#if defined(__clang__) && defined(__has_builtin)
-#if __has_builtin(__builtin_bswap32) && \
- __has_builtin(__builtin_bswap64)
-#define have_bswap
-#endif
-#endif
-
-#if defined(have_bswap)
- /* The compiler is hopefully able to statically evaluate this! */
- switch (sizeof(mbedtls_mpi_uint)) {
- case 4:
- return __builtin_bswap32(x);
- case 8:
- return __builtin_bswap64(x);
- }
-#endif
-#endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */
-#endif /* __BYTE_ORDER__ */
-
- /* Fall back to C-based reordering if we don't know the byte order
- * or we couldn't use a compiler-specific builtin. */
- return mpi_uint_bigendian_to_host_c(x);
-}
-
-static void mpi_bigendian_to_host(mbedtls_mpi_uint * const p, size_t limbs)
-{
- mbedtls_mpi_uint *cur_limb_left;
- mbedtls_mpi_uint *cur_limb_right;
- if (limbs == 0) {
- return;
- }
-
- /*
- * Traverse limbs and
- * - adapt byte-order in each limb
- * - swap the limbs themselves.
- * For that, simultaneously traverse the limbs from left to right
- * and from right to left, as long as the left index is not bigger
- * than the right index (it's not a problem if limbs is odd and the
- * indices coincide in the last iteration).
- */
- for (cur_limb_left = p, cur_limb_right = p + (limbs - 1);
- cur_limb_left <= cur_limb_right;
- cur_limb_left++, cur_limb_right--) {
- mbedtls_mpi_uint tmp;
- /* Note that if cur_limb_left == cur_limb_right,
- * this code effectively swaps the bytes only once. */
- tmp = mpi_uint_bigendian_to_host(*cur_limb_left);
- *cur_limb_left = mpi_uint_bigendian_to_host(*cur_limb_right);
- *cur_limb_right = tmp;
- }
-}
-
/*
* Import X from unsigned binary data, little endian
+ *
+ * This function is guaranteed to return an MPI with exactly the necessary
+ * number of limbs (in particular, it does not skip 0s in the input).
*/
int mbedtls_mpi_read_binary_le(mbedtls_mpi *X,
const unsigned char *buf, size_t buflen)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t i;
- size_t const limbs = CHARS_TO_LIMBS(buflen);
+ const size_t limbs = CHARS_TO_LIMBS(buflen);
/* Ensure that target MPI has exactly the necessary number of limbs */
MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
- for (i = 0; i < buflen; i++) {
- X->p[i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3);
- }
+ MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen));
cleanup:
@@ -824,28 +812,19 @@ cleanup:
/*
* Import X from unsigned binary data, big endian
+ *
+ * This function is guaranteed to return an MPI with exactly the necessary
+ * number of limbs (in particular, it does not skip 0s in the input).
*/
int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t const limbs = CHARS_TO_LIMBS(buflen);
- size_t const overhead = (limbs * ciL) - buflen;
- unsigned char *Xp;
-
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(buflen == 0 || buf != NULL);
+ const size_t limbs = CHARS_TO_LIMBS(buflen);
/* Ensure that target MPI has exactly the necessary number of limbs */
MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
- /* Avoid calling `memcpy` with NULL source or destination argument,
- * even if buflen is 0. */
- if (buflen != 0) {
- Xp = (unsigned char *) X->p;
- memcpy(Xp + overhead, buf, buflen);
-
- mpi_bigendian_to_host(X->p, limbs);
- }
+ MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
cleanup:
@@ -863,34 +842,7 @@ cleanup:
int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X,
unsigned char *buf, size_t buflen)
{
- size_t stored_bytes = X->n * ciL;
- size_t bytes_to_copy;
- size_t i;
-
- if (stored_bytes < buflen) {
- bytes_to_copy = stored_bytes;
- } else {
- bytes_to_copy = buflen;
-
- /* The output buffer is smaller than the allocated size of X.
- * However X may fit if its leading bytes are zero. */
- for (i = bytes_to_copy; i < stored_bytes; i++) {
- if (GET_BYTE(X, i) != 0) {
- return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
- }
- }
- }
-
- for (i = 0; i < bytes_to_copy; i++) {
- buf[i] = GET_BYTE(X, i);
- }
-
- if (stored_bytes < buflen) {
- /* Write trailing 0 bytes */
- memset(buf + stored_bytes, 0, buflen - stored_bytes);
- }
-
- return 0;
+ return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen);
}
/*
@@ -899,42 +851,7 @@ int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X,
int mbedtls_mpi_write_binary(const mbedtls_mpi *X,
unsigned char *buf, size_t buflen)
{
- size_t stored_bytes;
- size_t bytes_to_copy;
- unsigned char *p;
- size_t i;
-
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(buflen == 0 || buf != NULL);
-
- stored_bytes = X->n * ciL;
-
- if (stored_bytes < buflen) {
- /* There is enough space in the output buffer. Write initial
- * null bytes and record the position at which to start
- * writing the significant bytes. In this case, the execution
- * trace of this function does not depend on the value of the
- * number. */
- bytes_to_copy = stored_bytes;
- p = buf + buflen - stored_bytes;
- memset(buf, 0, buflen - stored_bytes);
- } else {
- /* The output buffer is smaller than the allocated size of X.
- * However X may fit if its leading bytes are zero. */
- bytes_to_copy = buflen;
- p = buf;
- for (i = bytes_to_copy; i < stored_bytes; i++) {
- if (GET_BYTE(X, i) != 0) {
- return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
- }
- }
- }
-
- for (i = 0; i < bytes_to_copy; i++) {
- p[bytes_to_copy - i - 1] = GET_BYTE(X, i);
- }
-
- return 0;
+ return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
}
/*
@@ -943,12 +860,7 @@ int mbedtls_mpi_write_binary(const mbedtls_mpi *X,
int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t i, v0, t1;
- mbedtls_mpi_uint r0 = 0, r1;
- MPI_VALIDATE_RET(X != NULL);
-
- v0 = count / (biL);
- t1 = count & (biL - 1);
+ size_t i;
i = mbedtls_mpi_bitlen(X) + count;
@@ -958,31 +870,7 @@ int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
ret = 0;
- /*
- * shift by count / limb_size
- */
- if (v0 > 0) {
- for (i = X->n; i > v0; i--) {
- X->p[i - 1] = X->p[i - v0 - 1];
- }
-
- for (; i > 0; i--) {
- X->p[i - 1] = 0;
- }
- }
-
- /*
- * shift by count % limb_size
- */
- if (t1 > 0) {
- for (i = v0; i < X->n; i++) {
- r1 = X->p[i] >> (biL - t1);
- X->p[i] <<= t1;
- X->p[i] |= r0;
- r0 = r1;
- }
- }
-
+ mbedtls_mpi_core_shift_l(X->p, X->n, count);
cleanup:
return ret;
@@ -993,42 +881,9 @@ cleanup:
*/
int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
{
- size_t i, v0, v1;
- mbedtls_mpi_uint r0 = 0, r1;
- MPI_VALIDATE_RET(X != NULL);
-
- v0 = count / biL;
- v1 = count & (biL - 1);
-
- if (v0 > X->n || (v0 == X->n && v1 > 0)) {
- return mbedtls_mpi_lset(X, 0);
+ if (X->n != 0) {
+ mbedtls_mpi_core_shift_r(X->p, X->n, count);
}
-
- /*
- * shift by count / limb_size
- */
- if (v0 > 0) {
- for (i = 0; i < X->n - v0; i++) {
- X->p[i] = X->p[i + v0];
- }
-
- for (; i < X->n; i++) {
- X->p[i] = 0;
- }
- }
-
- /*
- * shift by count % limb_size
- */
- if (v1 > 0) {
- for (i = X->n; i > 0; i--) {
- r1 = X->p[i - 1] << (biL - v1);
- X->p[i - 1] >>= v1;
- X->p[i - 1] |= r0;
- r0 = r1;
- }
- }
-
return 0;
}
@@ -1038,8 +893,6 @@ int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
{
size_t i, j;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(Y != NULL);
for (i = X->n; i > 0; i--) {
if (X->p[i - 1] != 0) {
@@ -1053,9 +906,8 @@ int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
}
}
- if (i == 0 && j == 0) {
- return 0;
- }
+ /* If i == j == 0, i.e. abs(X) == abs(Y),
+ * we end up returning 0 at the end of the function. */
if (i > j) {
return 1;
@@ -1082,8 +934,6 @@ int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
{
size_t i, j;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(Y != NULL);
for (i = X->n; i > 0; i--) {
if (X->p[i - 1] != 0) {
@@ -1134,10 +984,9 @@ int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
{
mbedtls_mpi Y;
mbedtls_mpi_uint p[1];
- MPI_VALIDATE_RET(X != NULL);
*p = mpi_sint_abs(z);
- Y.s = (z < 0) ? -1 : 1;
+ Y.s = TO_SIGN(z);
Y.n = 1;
Y.p = p;
@@ -1150,11 +999,9 @@ int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t i, j;
- mbedtls_mpi_uint *o, *p, c, tmp;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
+ size_t j;
+ mbedtls_mpi_uint *p;
+ mbedtls_mpi_uint c;
if (X == B) {
const mbedtls_mpi *T = A; A = X; B = T;
@@ -1165,7 +1012,7 @@ int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
}
/*
- * X should always be positive as a result of unsigned additions.
+ * X must always be positive as a result of unsigned additions.
*/
X->s = 1;
@@ -1183,24 +1030,23 @@ int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j));
- o = B->p; p = X->p; c = 0;
+ /* j is the number of non-zero limbs of B. Add those to X. */
- /*
- * tmp is used because it might happen that p == o
- */
- for (i = 0; i < j; i++, o++, p++) {
- tmp = *o;
- *p += c; c = (*p < c);
- *p += tmp; c += (*p < tmp);
- }
+ p = X->p;
+
+ c = mbedtls_mpi_core_add(p, p, B->p, j);
+
+ p += j;
+
+ /* Now propagate any carry */
while (c != 0) {
- if (i >= X->n) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + 1));
- p = X->p + i;
+ if (j >= X->n) {
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
+ p = X->p + j;
}
- *p += c; c = (*p < c); i++; p++;
+ *p += c; c = (*p < c); j++; p++;
}
cleanup:
@@ -1208,39 +1054,6 @@ cleanup:
return ret;
}
-/**
- * Helper for mbedtls_mpi subtraction.
- *
- * Calculate l - r where l and r have the same size.
- * This function operates modulo (2^ciL)^n and returns the carry
- * (1 if there was a wraparound, i.e. if `l < r`, and 0 otherwise).
- *
- * d may be aliased to l or r.
- *
- * \param n Number of limbs of \p d, \p l and \p r.
- * \param[out] d The result of the subtraction.
- * \param[in] l The left operand.
- * \param[in] r The right operand.
- *
- * \return 1 if `l < r`.
- * 0 if `l >= r`.
- */
-static mbedtls_mpi_uint mpi_sub_hlp(size_t n,
- mbedtls_mpi_uint *d,
- const mbedtls_mpi_uint *l,
- const mbedtls_mpi_uint *r)
-{
- size_t i;
- mbedtls_mpi_uint c = 0, t, z;
-
- for (i = 0; i < n; i++) {
- z = (l[i] < c); t = l[i] - c;
- c = (t < r[i]) + z; d[i] = t - r[i];
- }
-
- return c;
-}
-
/*
* Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
*/
@@ -1249,9 +1062,6 @@ int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
size_t n;
mbedtls_mpi_uint carry;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
for (n = B->n; n > 0; n--) {
if (B->p[n - 1] != 0) {
@@ -1276,19 +1086,16 @@ int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
memset(X->p + A->n, 0, (X->n - A->n) * ciL);
}
- carry = mpi_sub_hlp(n, X->p, A->p, B->p);
+ carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
if (carry != 0) {
- /* Propagate the carry to the first nonzero limb of X. */
- for (; n < X->n && X->p[n] == 0; n++) {
- --X->p[n];
- }
- /* If we ran out of space for the carry, it means that the result
- * is negative. */
- if (n == X->n) {
+ /* Propagate the carry through the rest of X. */
+ carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n);
+
+ /* If we have further carry/borrow, the result is negative. */
+ if (carry != 0) {
ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
goto cleanup;
}
- --X->p[n];
}
/* X should always be positive as a result of unsigned subtractions. */
@@ -1306,9 +1113,6 @@ static int add_sub_mpi(mbedtls_mpi *X,
int flip_B)
{
int ret, s;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
s = A->s;
if (A->s * B->s * flip_B < 0) {
@@ -1357,11 +1161,9 @@ int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b
{
mbedtls_mpi B;
mbedtls_mpi_uint p[1];
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
p[0] = mpi_sint_abs(b);
- B.s = (b < 0) ? -1 : 1;
+ B.s = TO_SIGN(b);
B.n = 1;
B.p = p;
@@ -1375,98 +1177,15 @@ int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b
{
mbedtls_mpi B;
mbedtls_mpi_uint p[1];
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
p[0] = mpi_sint_abs(b);
- B.s = (b < 0) ? -1 : 1;
+ B.s = TO_SIGN(b);
B.n = 1;
B.p = p;
return mbedtls_mpi_sub_mpi(X, A, &B);
}
-/** Helper for mbedtls_mpi multiplication.
- *
- * Add \p b * \p s to \p d.
- *
- * \param i The number of limbs of \p s.
- * \param[in] s A bignum to multiply, of size \p i.
- * It may overlap with \p d, but only if
- * \p d <= \p s.
- * Its leading limb must not be \c 0.
- * \param[in,out] d The bignum to add to.
- * It must be sufficiently large to store the
- * result of the multiplication. This means
- * \p i + 1 limbs if \p d[\p i - 1] started as 0 and \p b
- * is not known a priori.
- * \param b A scalar to multiply.
- */
-static
-#if defined(__APPLE__) && defined(__arm__)
-/*
- * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
- * appears to need this to prevent bad ARM code generation at -O3.
- */
-__attribute__((noinline))
-#endif
-void mpi_mul_hlp(size_t i,
- const mbedtls_mpi_uint *s,
- mbedtls_mpi_uint *d,
- mbedtls_mpi_uint b)
-{
- mbedtls_mpi_uint c = 0, t = 0;
- (void) t; /* Unused in some architectures */
-
-#if defined(MULADDC_HUIT)
- for (; i >= 8; i -= 8) {
- MULADDC_INIT
- MULADDC_HUIT
- MULADDC_STOP
- }
-
- for (; i > 0; i--) {
- MULADDC_INIT
- MULADDC_CORE
- MULADDC_STOP
- }
-#else /* MULADDC_HUIT */
- for (; i >= 16; i -= 16) {
- MULADDC_INIT
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
-
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
- MULADDC_STOP
- }
-
- for (; i >= 8; i -= 8) {
- MULADDC_INIT
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
-
- MULADDC_CORE MULADDC_CORE
- MULADDC_CORE MULADDC_CORE
- MULADDC_STOP
- }
-
- for (; i > 0; i--) {
- MULADDC_INIT
- MULADDC_CORE
- MULADDC_STOP
- }
-#endif /* MULADDC_HUIT */
-
- while (c != 0) {
- *d += c; c = (*d < c); d++;
- }
-}
-
/*
* Baseline multiplication: X = A * B (HAC 14.12)
*/
@@ -1476,11 +1195,9 @@ int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
size_t i, j;
mbedtls_mpi TA, TB;
int result_is_zero = 0;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
- mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB);
+ mbedtls_mpi_init(&TA);
+ mbedtls_mpi_init(&TB);
if (X == A) {
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
@@ -1510,9 +1227,7 @@ int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
- for (; j > 0; j--) {
- mpi_mul_hlp(i, A->p, X->p + j - 1, B->p[j - 1]);
- }
+ mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j);
/* If the result is 0, we don't shortcut the operation, which reduces
* but does not eliminate side channels leaking the zero-ness. We do
@@ -1536,22 +1251,17 @@ cleanup:
*/
int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
{
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
-
- /* mpi_mul_hlp can't deal with a leading 0. */
size_t n = A->n;
while (n > 0 && A->p[n - 1] == 0) {
--n;
}
- /* The general method below doesn't work if n==0 or b==0. By chance
- * calculating the result is trivial in those cases. */
+ /* The general method below doesn't work if b==0. */
if (b == 0 || n == 0) {
return mbedtls_mpi_lset(X, 0);
}
- /* Calculate A*b as A + A*(b-1) to take advantage of mpi_mul_hlp */
+ /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
/* In general, A * b requires 1 limb more than b. If
* A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
@@ -1560,10 +1270,13 @@ int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b
* making the call to grow() unconditional causes slightly fewer
* calls to calloc() in ECP code, presumably because it reuses the
* same mpi for a while and this way the mpi is more likely to directly
- * grow to its final size. */
+ * grow to its final size.
+ *
+ * Note that calculating A*b as 0 + A*b doesn't work as-is because
+ * A,X can be the same. */
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1));
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
- mpi_mul_hlp(n, A->p, X->p, b - 1);
+ mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
cleanup:
return ret;
@@ -1622,7 +1335,7 @@ static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1,
/*
* Normalize the divisor, d, and dividend, u0, u1
*/
- s = mbedtls_clz(d);
+ s = mbedtls_mpi_core_clz(d);
d = d << s;
u1 = u1 << s;
@@ -1683,8 +1396,6 @@ int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
size_t i, n, t, k;
mbedtls_mpi X, Y, Z, T1, T2;
mbedtls_mpi_uint TP2[3];
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
if (mbedtls_mpi_cmp_int(B, 0) == 0) {
return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
@@ -1807,10 +1518,9 @@ int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R,
{
mbedtls_mpi B;
mbedtls_mpi_uint p[1];
- MPI_VALIDATE_RET(A != NULL);
p[0] = mpi_sint_abs(b);
- B.s = (b < 0) ? -1 : 1;
+ B.s = TO_SIGN(b);
B.n = 1;
B.p = p;
@@ -1823,9 +1533,6 @@ int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R,
int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- MPI_VALIDATE_RET(R != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
if (mbedtls_mpi_cmp_int(B, 0) < 0) {
return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
@@ -1853,8 +1560,6 @@ int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_s
{
size_t i;
mbedtls_mpi_uint x, y, z;
- MPI_VALIDATE_RET(r != NULL);
- MPI_VALIDATE_RET(A != NULL);
if (b == 0) {
return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
@@ -1905,152 +1610,11 @@ int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_s
return 0;
}
-/*
- * Fast Montgomery initialization (thanks to Tom St Denis)
- */
-mbedtls_mpi_uint mbedtls_mpi_montmul_init(const mbedtls_mpi_uint *N)
-{
- mbedtls_mpi_uint x = N[0];
-
- x += ((N[0] + 2) & 4) << 1;
-
- for (unsigned int i = biL; i >= 8; i /= 2) {
- x *= (2 - (N[0] * x));
- }
-
- return ~x + 1;
-}
-
-void mbedtls_mpi_montmul(mbedtls_mpi *A,
- const mbedtls_mpi *B,
- const mbedtls_mpi *N,
- mbedtls_mpi_uint mm,
- const mbedtls_mpi *T)
-{
- size_t i, n, m;
- mbedtls_mpi_uint u0, u1, *d;
-
- memset(T->p, 0, T->n * ciL);
-
- d = T->p;
- n = N->n;
- m = (B->n < n) ? B->n : n;
-
- for (i = 0; i < n; i++) {
- /*
- * T = (T + u0*B + u1*N) / 2^biL
- */
- u0 = A->p[i];
- u1 = (d[0] + u0 * B->p[0]) * mm;
-
- mpi_mul_hlp(m, B->p, d, u0);
- mpi_mul_hlp(n, N->p, d, u1);
-
- *d++ = u0; d[n + 1] = 0;
- }
-
- /* At this point, d is either the desired result or the desired result
- * plus N. We now potentially subtract N, avoiding leaking whether the
- * subtraction is performed through side channels. */
-
- /* Copy the n least significant limbs of d to A, so that
- * A = d if d < N (recall that N has n limbs). */
- memcpy(A->p, d, n * ciL);
- /* If d >= N then we want to set A to d - N. To prevent timing attacks,
- * do the calculation without using conditional tests. */
- /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
- d[n] += 1;
- d[n] -= mpi_sub_hlp(n, d, d, N->p);
- /* If d0 < N then d < (2^biL)^n
- * so d[n] == 0 and we want to keep A as it is.
- * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
- * so d[n] == 1 and we want to set A to the result of the subtraction
- * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
- * This exactly corresponds to a conditional assignment. */
- mbedtls_ct_mpi_uint_cond_assign(n, A->p, d, (unsigned char) d[n]);
-}
-
-/*
- * Montgomery reduction: A = A * R^-1 mod N
- *
- * See mbedtls_mpi_montmul() regarding constraints and guarantees on the
- * parameters.
- */
-static void mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N,
- mbedtls_mpi_uint mm, const mbedtls_mpi *T)
-{
- mbedtls_mpi_uint z = 1;
- mbedtls_mpi U;
-
- U.n = U.s = (int) z;
- U.p = &z;
-
- mbedtls_mpi_montmul(A, &U, N, mm, T);
-}
-
-/**
- * Select an MPI from a table without leaking the index.
- *
- * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
- * reads the entire table in order to avoid leaking the value of idx to an
- * attacker able to observe memory access patterns.
- *
- * \param[out] R Where to write the selected MPI.
- * \param[in] T The table to read from.
- * \param[in] T_size The number of elements in the table.
- * \param[in] idx The index of the element to select;
- * this must satisfy 0 <= idx < T_size.
- *
- * \return \c 0 on success, or a negative error code.
- */
-static int mpi_select(mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx)
-{
- int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
-
- for (size_t i = 0; i < T_size; i++) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(R, &T[i],
- (unsigned char) mbedtls_ct_size_bool_eq(i,
- idx)));
- }
-
-cleanup:
- return ret;
-}
-
-int mbedtls_mpi_get_mont_r2_unsafe(mbedtls_mpi *X,
- const mbedtls_mpi *N)
-{
- int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, N->n * 2 * biL));
- MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
- MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(X, N->n));
-
-cleanup:
- return ret;
-}
-
-/*
- * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
- */
int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A,
const mbedtls_mpi *E, const mbedtls_mpi *N,
mbedtls_mpi *prec_RR)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t window_bitsize;
- size_t i, j, nblimbs;
- size_t bufsize, nbits;
- size_t exponent_bits_in_window = 0;
- mbedtls_mpi_uint ei, mm, state;
- mbedtls_mpi RR, T, W[(size_t) 1 << MBEDTLS_MPI_WINDOW_SIZE], WW, Apos;
- int neg;
-
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(E != NULL);
- MPI_VALIDATE_RET(N != NULL);
if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
@@ -2066,259 +1630,88 @@ int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A,
}
/*
- * Init temps and window size
+ * Ensure that the exponent that we are passing to the core is not NULL.
*/
- mm = mbedtls_mpi_montmul_init(N->p);
- mbedtls_mpi_init(&RR); mbedtls_mpi_init(&T);
- mbedtls_mpi_init(&Apos);
- mbedtls_mpi_init(&WW);
- memset(W, 0, sizeof(W));
-
- i = mbedtls_mpi_bitlen(E);
-
- window_bitsize = (i > 671) ? 6 : (i > 239) ? 5 :
- (i > 79) ? 4 : (i > 23) ? 3 : 1;
-
-#if (MBEDTLS_MPI_WINDOW_SIZE < 6)
- if (window_bitsize > MBEDTLS_MPI_WINDOW_SIZE) {
- window_bitsize = MBEDTLS_MPI_WINDOW_SIZE;
+ if (E->n == 0) {
+ ret = mbedtls_mpi_lset(X, 1);
+ return ret;
}
-#endif
-
- const size_t w_table_used_size = (size_t) 1 << window_bitsize;
-
- /*
- * This function is not constant-trace: its memory accesses depend on the
- * exponent value. To defend against timing attacks, callers (such as RSA
- * and DHM) should use exponent blinding. However this is not enough if the
- * adversary can find the exponent in a single trace, so this function
- * takes extra precautions against adversaries who can observe memory
- * access patterns.
- *
- * This function performs a series of multiplications by table elements and
- * squarings, and we want the prevent the adversary from finding out which
- * table element was used, and from distinguishing between multiplications
- * and squarings. Firstly, when multiplying by an element of the window
- * W[i], we do a constant-trace table lookup to obfuscate i. This leaves
- * squarings as having a different memory access patterns from other
- * multiplications. So secondly, we put the accumulator in the table as
- * well, and also do a constant-trace table lookup to multiply by the
- * accumulator which is W[x_index].
- *
- * This way, all multiplications take the form of a lookup-and-multiply.
- * The number of lookup-and-multiply operations inside each iteration of
- * the main loop still depends on the bits of the exponent, but since the
- * other operations in the loop don't have an easily recognizable memory
- * trace, an adversary is unlikely to be able to observe the exact
- * patterns.
- *
- * An adversary may still be able to recover the exponent if they can
- * observe both memory accesses and branches. However, branch prediction
- * exploitation typically requires many traces of execution over the same
- * data, which is defeated by randomized blinding.
- */
- const size_t x_index = 0;
- mbedtls_mpi_init(&W[x_index]);
-
- j = N->n + 1;
- /* All W[i] including the accumulator must have at least N->n limbs for
- * the mbedtls_mpi_montmul() and mpi_montred() calls later. Here we ensure
- * that W[1] and the accumulator W[x_index] are large enough. later we'll
- * grow other W[i] to the same length. They must not be shrunk midway
- * through this function!
- */
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[x_index], j));
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], j));
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T, j * 2));
/*
- * Compensate for negative A (and correct at the end)
+ * Allocate working memory for mbedtls_mpi_core_exp_mod()
*/
- neg = (A->s == -1);
- if (neg) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Apos, A));
- Apos.s = 1;
- A = &Apos;
+ size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n);
+ mbedtls_mpi_uint *T = (mbedtls_mpi_uint *) mbedtls_calloc(T_limbs, sizeof(mbedtls_mpi_uint));
+ if (T == NULL) {
+ return MBEDTLS_ERR_MPI_ALLOC_FAILED;
}
+ mbedtls_mpi RR;
+ mbedtls_mpi_init(&RR);
+
/*
* If 1st call, pre-compute R^2 mod N
*/
if (prec_RR == NULL || prec_RR->p == NULL) {
- mbedtls_mpi_get_mont_r2_unsafe(&RR, N);
+ MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N));
if (prec_RR != NULL) {
- memcpy(prec_RR, &RR, sizeof(mbedtls_mpi));
+ *prec_RR = RR;
}
} else {
- memcpy(&RR, prec_RR, sizeof(mbedtls_mpi));
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n));
+ RR = *prec_RR;
}
/*
- * W[1] = A * R^2 * R^-1 mod N = A * R mod N
+ * To preserve constness we need to make a copy of A. Using X for this to
+ * save memory.
*/
- if (mbedtls_mpi_cmp_mpi(A, N) >= 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&W[1], A, N));
- /* This should be a no-op because W[1] is already that large before
- * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
- * in mbedtls_mpi_montmul() below, so let's make sure. */
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], N->n + 1));
- } else {
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[1], A));
- }
-
- /* Note that this is safe because W[1] always has at least N->n limbs
- * (it grew above and was preserved by mbedtls_mpi_copy()). */
- mbedtls_mpi_montmul(&W[1], &RR, N, mm, &T);
+ MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
/*
- * W[x_index] = R^2 * R^-1 mod N = R mod N
+ * Compensate for negative A (and correct at the end).
*/
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[x_index], &RR));
- mpi_montred(&W[x_index], N, mm, &T);
-
-
- if (window_bitsize > 1) {
- /*
- * W[i] = W[1] ^ i
- *
- * The first bit of the sliding window is always 1 and therefore we
- * only need to store the second half of the table.
- *
- * (There are two special elements in the table: W[0] for the
- * accumulator/result and W[1] for A in Montgomery form. Both of these
- * are already set at this point.)
- */
- j = w_table_used_size / 2;
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[j], N->n + 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[j], &W[1]));
-
- for (i = 0; i < window_bitsize - 1; i++) {
- mbedtls_mpi_montmul(&W[j], &W[j], N, mm, &T);
- }
-
- /*
- * W[i] = W[i - 1] * W[1]
- */
- for (i = j + 1; i < w_table_used_size; i++) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[i], N->n + 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[i], &W[i - 1]));
-
- mbedtls_mpi_montmul(&W[i], &W[1], N, mm, &T);
- }
- }
-
- nblimbs = E->n;
- bufsize = 0;
- nbits = 0;
- state = 0;
-
- while (1) {
- if (bufsize == 0) {
- if (nblimbs == 0) {
- break;
- }
-
- nblimbs--;
-
- bufsize = sizeof(mbedtls_mpi_uint) << 3;
- }
-
- bufsize--;
-
- ei = (E->p[nblimbs] >> bufsize) & 1;
-
- /*
- * skip leading 0s
- */
- if (ei == 0 && state == 0) {
- continue;
- }
-
- if (ei == 0 && state == 1) {
- /*
- * out of window, square W[x_index]
- */
- MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
- mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
- continue;
- }
-
- /*
- * add ei to current window
- */
- state = 2;
-
- nbits++;
- exponent_bits_in_window |= (ei << (window_bitsize - nbits));
-
- if (nbits == window_bitsize) {
- /*
- * W[x_index] = W[x_index]^window_bitsize R^-1 mod N
- */
- for (i = 0; i < window_bitsize; i++) {
- MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
- x_index));
- mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
- }
-
- /*
- * W[x_index] = W[x_index] * W[exponent_bits_in_window] R^-1 mod N
- */
- MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
- exponent_bits_in_window));
- mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
-
- state--;
- nbits = 0;
- exponent_bits_in_window = 0;
- }
- }
+ X->s = 1;
/*
- * process the remaining bits
+ * Make sure that X is in a form that is safe for consumption by
+ * the core functions.
+ *
+ * - The core functions will not touch the limbs of X above N->n. The
+ * result will be correct if those limbs are 0, which the mod call
+ * ensures.
+ * - Also, X must have at least as many limbs as N for the calls to the
+ * core functions.
*/
- for (i = 0; i < nbits; i++) {
- MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
- mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
-
- exponent_bits_in_window <<= 1;
-
- if ((exponent_bits_in_window & ((size_t) 1 << window_bitsize)) != 0) {
- MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, 1));
- mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
- }
+ if (mbedtls_mpi_cmp_mpi(X, N) >= 0) {
+ MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
}
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n));
/*
- * W[x_index] = A^E * R * R^-1 mod N = A^E mod N
+ * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod().
*/
- mpi_montred(&W[x_index], N, mm, &T);
-
- if (neg && E->n != 0 && (E->p[0] & 1) != 0) {
- W[x_index].s = -1;
- MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&W[x_index], N, &W[x_index]));
+ {
+ mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p);
+ mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T);
+ mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
+ mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T);
}
/*
- * Load the result in the output variable.
+ * Correct for negative A.
*/
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &W[x_index]));
-
-cleanup:
+ if (A->s == -1 && (E->p[0] & 1) != 0) {
+ mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n);
+ X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1);
- /* The first bit of the sliding window is always 1 and therefore the first
- * half of the table was unused. */
- for (i = w_table_used_size/2; i < w_table_used_size; i++) {
- mbedtls_mpi_free(&W[i]);
+ MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X));
}
- mbedtls_mpi_free(&W[x_index]);
- mbedtls_mpi_free(&W[1]);
- mbedtls_mpi_free(&T);
- mbedtls_mpi_free(&Apos);
- mbedtls_mpi_free(&WW);
+cleanup:
+
+ mbedtls_mpi_zeroize_and_free(T, T_limbs);
if (prec_RR == NULL || prec_RR->p == NULL) {
mbedtls_mpi_free(&RR);
@@ -2336,10 +1729,6 @@ int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
size_t lz, lzt;
mbedtls_mpi TA, TB;
- MPI_VALIDATE_RET(G != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
-
mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB);
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A));
@@ -2437,50 +1826,18 @@ cleanup:
return ret;
}
-/* Fill X with n_bytes random bytes.
- * X must already have room for those bytes.
- * The ordering of the bytes returned from the RNG is suitable for
- * deterministic ECDSA (see RFC 6979 §3.3 and mbedtls_mpi_random()).
- * The size and sign of X are unchanged.
- * n_bytes must not be 0.
- */
-static int mpi_fill_random_internal(
- mbedtls_mpi *X, size_t n_bytes,
- int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
-{
- int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- const size_t limbs = CHARS_TO_LIMBS(n_bytes);
- const size_t overhead = (limbs * ciL) - n_bytes;
-
- if (X->n < limbs) {
- return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
- }
-
- memset(X->p, 0, overhead);
- memset((unsigned char *) X->p + limbs * ciL, 0, (X->n - limbs) * ciL);
- MBEDTLS_MPI_CHK(f_rng(p_rng, (unsigned char *) X->p + overhead, n_bytes));
- mpi_bigendian_to_host(X->p, limbs);
-
-cleanup:
- return ret;
-}
-
/*
* Fill X with size bytes of random.
- *
- * Use a temporary bytes representation to make sure the result is the same
- * regardless of the platform endianness (useful when f_rng is actually
- * deterministic, eg for tests).
+ * The bytes returned from the RNG are used in a specific order which
+ * is suitable for deterministic ECDSA (see the specification of
+ * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()).
*/
int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t const limbs = CHARS_TO_LIMBS(size);
-
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(f_rng != NULL);
+ const size_t limbs = CHARS_TO_LIMBS(size);
/* Ensure that target MPI has exactly the necessary number of limbs */
MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
@@ -2488,7 +1845,7 @@ int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size,
return 0;
}
- ret = mpi_fill_random_internal(X, size, f_rng, p_rng);
+ ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng);
cleanup:
return ret;
@@ -2500,13 +1857,6 @@ int mbedtls_mpi_random(mbedtls_mpi *X,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng)
{
- int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
- int count;
- unsigned lt_lower = 1, lt_upper = 0;
- size_t n_bits = mbedtls_mpi_bitlen(N);
- size_t n_bytes = (n_bits + 7) / 8;
- mbedtls_mpi lower_bound;
-
if (min < 0) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
}
@@ -2514,58 +1864,15 @@ int mbedtls_mpi_random(mbedtls_mpi *X,
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
}
- /*
- * When min == 0, each try has at worst a probability 1/2 of failing
- * (the msb has a probability 1/2 of being 0, and then the result will
- * be < N), so after 30 tries failure probability is a most 2**(-30).
- *
- * When N is just below a power of 2, as is the case when generating
- * a random scalar on most elliptic curves, 1 try is enough with
- * overwhelming probability. When N is just above a power of 2,
- * as when generating a random scalar on secp224k1, each try has
- * a probability of failing that is almost 1/2.
- *
- * The probabilities are almost the same if min is nonzero but negligible
- * compared to N. This is always the case when N is crypto-sized, but
- * it's convenient to support small N for testing purposes. When N
- * is small, use a higher repeat count, otherwise the probability of
- * failure is macroscopic.
- */
- count = (n_bytes > 4 ? 30 : 250);
-
- mbedtls_mpi_init(&lower_bound);
-
/* Ensure that target MPI has exactly the same number of limbs
* as the upper bound, even if the upper bound has leading zeros.
- * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
- MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, N->n));
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&lower_bound, N->n));
- MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&lower_bound, min));
-
- /*
- * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
- * when f_rng is a suitably parametrized instance of HMAC_DRBG:
- * - use the same byte ordering;
- * - keep the leftmost n_bits bits of the generated octet string;
- * - try until result is in the desired range.
- * This also avoids any bias, which is especially important for ECDSA.
- */
- do {
- MBEDTLS_MPI_CHK(mpi_fill_random_internal(X, n_bytes, f_rng, p_rng));
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, 8 * n_bytes - n_bits));
-
- if (--count == 0) {
- ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
- goto cleanup;
- }
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_lt_mpi_ct(X, &lower_bound, &lt_lower));
- MBEDTLS_MPI_CHK(mbedtls_mpi_lt_mpi_ct(X, N, &lt_upper));
- } while (lt_lower != 0 || lt_upper == 0);
+ * This is necessary for mbedtls_mpi_core_random. */
+ int ret = mbedtls_mpi_resize_clear(X, N->n);
+ if (ret != 0) {
+ return ret;
+ }
-cleanup:
- mbedtls_mpi_free(&lower_bound);
- return ret;
+ return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng);
}
/*
@@ -2575,9 +1882,6 @@ int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(N != NULL);
if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
@@ -2661,29 +1965,30 @@ cleanup:
#if defined(MBEDTLS_GENPRIME)
-static const int small_prime[] =
-{
- 3, 5, 7, 11, 13, 17, 19, 23,
- 29, 31, 37, 41, 43, 47, 53, 59,
- 61, 67, 71, 73, 79, 83, 89, 97,
- 101, 103, 107, 109, 113, 127, 131, 137,
- 139, 149, 151, 157, 163, 167, 173, 179,
- 181, 191, 193, 197, 199, 211, 223, 227,
- 229, 233, 239, 241, 251, 257, 263, 269,
- 271, 277, 281, 283, 293, 307, 311, 313,
- 317, 331, 337, 347, 349, 353, 359, 367,
- 373, 379, 383, 389, 397, 401, 409, 419,
- 421, 431, 433, 439, 443, 449, 457, 461,
- 463, 467, 479, 487, 491, 499, 503, 509,
- 521, 523, 541, 547, 557, 563, 569, 571,
- 577, 587, 593, 599, 601, 607, 613, 617,
- 619, 631, 641, 643, 647, 653, 659, 661,
- 673, 677, 683, 691, 701, 709, 719, 727,
- 733, 739, 743, 751, 757, 761, 769, 773,
- 787, 797, 809, 811, 821, 823, 827, 829,
- 839, 853, 857, 859, 863, 877, 881, 883,
- 887, 907, 911, 919, 929, 937, 941, 947,
- 953, 967, 971, 977, 983, 991, 997, -103
+/* Gaps between primes, starting at 3. https://oeis.org/A001223 */
+static const unsigned char small_prime_gaps[] = {
+ 2, 2, 4, 2, 4, 2, 4, 6,
+ 2, 6, 4, 2, 4, 6, 6, 2,
+ 6, 4, 2, 6, 4, 6, 8, 4,
+ 2, 4, 2, 4, 14, 4, 6, 2,
+ 10, 2, 6, 6, 4, 6, 6, 2,
+ 10, 2, 4, 2, 12, 12, 4, 2,
+ 4, 6, 2, 10, 6, 6, 6, 2,
+ 6, 4, 2, 10, 14, 4, 2, 4,
+ 14, 6, 10, 2, 4, 6, 8, 6,
+ 6, 4, 6, 8, 4, 8, 10, 2,
+ 10, 2, 6, 4, 6, 8, 4, 2,
+ 4, 12, 8, 4, 8, 4, 6, 12,
+ 2, 18, 6, 10, 6, 6, 2, 6,
+ 10, 6, 6, 2, 6, 6, 4, 2,
+ 12, 10, 2, 4, 6, 6, 2, 12,
+ 4, 6, 8, 10, 8, 10, 8, 6,
+ 6, 4, 8, 6, 4, 8, 4, 14,
+ 10, 12, 2, 10, 2, 4, 2, 10,
+ 14, 4, 2, 4, 14, 4, 2, 4,
+ 20, 4, 8, 10, 8, 4, 6, 6,
+ 14, 4, 6, 6, 8, 6, /*reaches 997*/
+ 0 /* the last entry is effectively unused */
};
/*
@@ -2700,20 +2005,20 @@ static int mpi_check_small_factors(const mbedtls_mpi *X)
int ret = 0;
size_t i;
mbedtls_mpi_uint r;
+ unsigned p = 3; /* The first odd prime */
if ((X->p[0] & 1) == 0) {
return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
}
- for (i = 0; small_prime[i] > 0; i++) {
- if (mbedtls_mpi_cmp_int(X, small_prime[i]) <= 0) {
- return 1;
- }
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, small_prime[i]));
-
+ for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) {
+ MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p));
if (r == 0) {
- return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
+ if (mbedtls_mpi_cmp_int(X, p) == 0) {
+ return 1;
+ } else {
+ return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
+ }
}
}
@@ -2732,9 +2037,6 @@ static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds,
size_t i, j, k, s;
mbedtls_mpi W, R, T, A, RR;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(f_rng != NULL);
-
mbedtls_mpi_init(&W); mbedtls_mpi_init(&R);
mbedtls_mpi_init(&T); mbedtls_mpi_init(&A);
mbedtls_mpi_init(&RR);
@@ -2822,8 +2124,6 @@ int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds,
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
mbedtls_mpi XX;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(f_rng != NULL);
XX.s = 1;
XX.n = X->n;
@@ -2849,26 +2149,6 @@ int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds,
return mpi_miller_rabin(&XX, rounds, f_rng, p_rng);
}
-#if !defined(MBEDTLS_DEPRECATED_REMOVED)
-/*
- * Pseudo-primality test, error probability 2^-80
- */
-int mbedtls_mpi_is_prime(const mbedtls_mpi *X,
- int (*f_rng)(void *, unsigned char *, size_t),
- void *p_rng)
-{
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(f_rng != NULL);
-
- /*
- * In the past our key generation aimed for an error rate of at most
- * 2^-80. Since this function is deprecated, aim for the same certainty
- * here as well.
- */
- return mbedtls_mpi_is_prime_ext(X, 40, f_rng, p_rng);
-}
-#endif
-
/*
* Prime number generation
*
@@ -2893,9 +2173,6 @@ int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags,
mbedtls_mpi_uint r;
mbedtls_mpi Y;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(f_rng != NULL);
-
if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
}