Import mbedtls-3.6.0
Imports Mbed TLS 3.6.0 from https://github.com/Mbed-TLS/mbedtls.git
tags mbedtls-3.6.0, v3.6.0
Files that are not needed are removed:
cd lib/libmbedtls
rm -rf mbedtls
cp -R path/to/mbedtls-3.6.0/mbedtls .
cd mbedtls
rm CMakeLists.txt DartConfiguration.tcl Makefile
rm .gitignore .travis.yml .pylintrc .globalrc .mypy.ini BRANCHES.md
rm include/.gitignore include/CMakeLists.txt library/.gitignore
rm library/CMakeLists.txt library/Makefile
rm -r cmake
rm -rf .git .github doxygen configs programs scripts tests visualc
rm -rf 3rdparty ChangeLog.d docs pkgconfig .gitmodules .readthedocs.yaml
rm library/mps_*
cd ..
git add mbedtls
This time we leave library/psa_* present to enable TLS 1.3 features.
This is a complete overwrite of previous code so earlier changes in the
previous branch import/mbedtls-3.4.0 will be added on top of this commit.
Signed-off-by: Tom Van Eyck <tom.vaneyck@kuleuven.be>
Acked-by: Jens Wiklander <jens.wiklander@linaro.org>
diff --git a/lib/libmbedtls/mbedtls/library/bignum.c b/lib/libmbedtls/mbedtls/library/bignum.c
index b6733b7..c45fd5b 100644
--- a/lib/libmbedtls/mbedtls/library/bignum.c
+++ b/lib/libmbedtls/mbedtls/library/bignum.c
@@ -2,19 +2,7 @@
* Multi-precision integer library
*
* Copyright The Mbed TLS Contributors
- * SPDX-License-Identifier: Apache-2.0
- *
- * Licensed under the Apache License, Version 2.0 (the "License"); you may
- * not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
- * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
+ * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
*/
/*
@@ -49,45 +37,151 @@
#include "mbedtls/platform.h"
-#include <mempool.h>
-#include <util.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 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;
+}
-void *mbedtls_mpi_mempool;
+/*
+ * Compare signed values in constant time
+ */
+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;
+
+ 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)
+{
+ 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 */
-static void mbedtls_mpi_zeroize(mbedtls_mpi_uint *v, size_t n)
-{
- mbedtls_platform_zeroize(v, ciL * n);
-}
+#define mbedtls_mpi_zeroize_and_free(v, n) mbedtls_zeroize_and_free(v, ciL * (n))
/*
* Initialize one MPI
*/
-static void mpi_init(mbedtls_mpi *X, short use_mempool)
-{
- MPI_VALIDATE(X != NULL);
-
- X->s = 1;
- X->use_mempool = use_mempool;
- X->n = 0;
- X->p = NULL;
-}
-
void mbedtls_mpi_init(mbedtls_mpi *X)
{
- mpi_init(X, 0 /*use_mempool*/);
-}
-
-void mbedtls_mpi_init_mempool(mbedtls_mpi *X)
-{
- mpi_init(X, !!mbedtls_mpi_mempool /*use_mempool*/);
+ X->s = 1;
+ X->n = 0;
+ X->p = NULL;
}
/*
@@ -100,11 +194,7 @@
}
if (X->p != NULL) {
- mbedtls_mpi_zeroize(X->p, X->n);
- if(X->use_mempool)
- mempool_free(mbedtls_mpi_mempool, X->p);
- else
- mbedtls_free(X->p);
+ mbedtls_mpi_zeroize_and_free(X->p, X->n);
}
X->s = 1;
@@ -118,34 +208,24 @@
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;
}
if (X->n < nblimbs) {
- if(X->use_mempool) {
- p = mempool_alloc(mbedtls_mpi_mempool, nblimbs * ciL);
- if(p == NULL)
- return MBEDTLS_ERR_MPI_ALLOC_FAILED;
- memset(p, 0, nblimbs * ciL);
- } else {
- p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL);
- if (p == NULL)
- return MBEDTLS_ERR_MPI_ALLOC_FAILED;
+ if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL)) == NULL) {
+ return MBEDTLS_ERR_MPI_ALLOC_FAILED;
}
if (X->p != NULL) {
memcpy(p, X->p, X->n * ciL);
- mbedtls_mpi_zeroize(X->p, X->n);
- if (X->use_mempool)
- mempool_free(mbedtls_mpi_mempool, X->p);
- else
- 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;
}
@@ -160,7 +240,6 @@
{
mbedtls_mpi_uint *p;
size_t i;
- MPI_VALIDATE_RET(X != NULL);
if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
return MBEDTLS_ERR_MPI_ALLOC_FAILED;
@@ -183,26 +262,18 @@
i = nblimbs;
}
- if (X->use_mempool) {
- p = mempool_alloc(mbedtls_mpi_mempool, i * ciL);
- if (p == NULL)
- return MBEDTLS_ERR_MPI_ALLOC_FAILED;
- memset(p, 0, i * ciL);
- } else {
- if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL)
- return MBEDTLS_ERR_MPI_ALLOC_FAILED;
+ if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL) {
+ return MBEDTLS_ERR_MPI_ALLOC_FAILED;
}
if (X->p != NULL) {
memcpy(p, X->p, i * ciL);
- mbedtls_mpi_zeroize(X->p, X->n);
- if (X->use_mempool)
- mempool_free(mbedtls_mpi_mempool, X->p);
- else
- 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;
@@ -230,15 +301,12 @@
* 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;
@@ -280,8 +348,6 @@
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));
@@ -300,19 +366,22 @@
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:
@@ -324,8 +393,6 @@
*/
int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
{
- MPI_VALIDATE_RET(X != NULL);
-
if (X->n * biL <= pos) {
return 0;
}
@@ -341,7 +408,6 @@
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;
@@ -368,16 +434,34 @@
*/
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;
}
@@ -432,14 +516,12 @@
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;
}
- mbedtls_mpi_init_mempool(&T);
+ mbedtls_mpi_init(&T);
if (s[0] == 0) {
mbedtls_mpi_free(X);
@@ -454,7 +536,7 @@
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;
}
@@ -536,9 +618,6 @@
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;
@@ -569,7 +648,7 @@
}
p = buf;
- mbedtls_mpi_init_mempool(&T);
+ mbedtls_mpi_init(&T);
if (X->s == -1) {
*p++ = '-';
@@ -604,7 +683,7 @@
}
*p++ = '\0';
- *olen = p - buf;
+ *olen = (size_t) (p - buf);
cleanup:
@@ -628,9 +707,6 @@
*/
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;
}
@@ -674,7 +750,6 @@
* 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;
@@ -746,9 +821,6 @@
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
const size_t limbs = CHARS_TO_LIMBS(buflen);
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(buflen == 0 || buf != NULL);
-
/* Ensure that target MPI has exactly the necessary number of limbs */
MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
@@ -788,12 +860,7 @@
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;
@@ -803,31 +870,7 @@
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;
@@ -838,7 +881,6 @@
*/
int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
{
- MPI_VALIDATE_RET(X != NULL);
if (X->n != 0) {
mbedtls_mpi_core_shift_r(X->p, X->n, count);
}
@@ -851,8 +893,6 @@
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) {
@@ -866,9 +906,8 @@
}
}
- 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;
@@ -895,8 +934,6 @@
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) {
@@ -947,10 +984,9 @@
{
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;
@@ -964,9 +1000,8 @@
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
size_t j;
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(A != NULL);
- MPI_VALIDATE_RET(B != NULL);
+ mbedtls_mpi_uint *p;
+ mbedtls_mpi_uint c;
if (X == B) {
const mbedtls_mpi *T = A; A = X; B = T;
@@ -997,9 +1032,9 @@
/* j is the number of non-zero limbs of B. Add those to X. */
- mbedtls_mpi_uint *p = X->p;
+ p = X->p;
- mbedtls_mpi_uint c = mbedtls_mpi_core_add(p, p, B->p, j);
+ c = mbedtls_mpi_core_add(p, p, B->p, j);
p += j;
@@ -1027,9 +1062,6 @@
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) {
@@ -1081,9 +1113,6 @@
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) {
@@ -1132,11 +1161,9 @@
{
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;
@@ -1150,11 +1177,9 @@
{
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;
@@ -1170,11 +1195,9 @@
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_mempool(&TA); mbedtls_mpi_init_mempool(&TB);
+ mbedtls_mpi_init(&TA);
+ mbedtls_mpi_init(&TB);
if (X == A) {
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
@@ -1204,13 +1227,7 @@
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
- for (size_t k = 0; k < j; k++) {
- /* We know that there cannot be any carry-out since we're
- * iterating from bottom to top. */
- (void) mbedtls_mpi_core_mla(X->p + k, i + 1,
- A->p, i,
- B->p[k]);
- }
+ 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
@@ -1234,9 +1251,6 @@
*/
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);
-
size_t n = A->n;
while (n > 0 && A->p[n - 1] == 0) {
--n;
@@ -1382,15 +1396,13 @@
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;
}
- mbedtls_mpi_init_mempool(&X); mbedtls_mpi_init_mempool(&Y);
- mbedtls_mpi_init_mempool(&Z); mbedtls_mpi_init_mempool(&T1);
+ mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z);
+ mbedtls_mpi_init(&T1);
/*
* Avoid dynamic memory allocations for constant-size T2.
*
@@ -1506,10 +1518,9 @@
{
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;
@@ -1522,9 +1533,6 @@
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;
@@ -1552,8 +1560,6 @@
{
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;
@@ -1604,125 +1610,11 @@
return 0;
}
-static void mpi_montg_init(mbedtls_mpi_uint *mm, const mbedtls_mpi *N)
-{
- *mm = mbedtls_mpi_core_montmul_init(N->p);
-}
-
-void mbedtls_mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
-{
- mpi_montg_init( mm, N );
-}
-
-/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
- *
- * \param[in,out] A One of the numbers to multiply.
- * It must have at least as many limbs as N
- * (A->n >= N->n), and any limbs beyond n are ignored.
- * On successful completion, A contains the result of
- * the multiplication A * B * R^-1 mod N where
- * R = (2^ciL)^n.
- * \param[in] B One of the numbers to multiply.
- * It must be nonzero and must not have more limbs than N
- * (B->n <= N->n).
- * \param[in] N The modulus. \p N must be odd.
- * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
- * This is -N^-1 mod 2^ciL.
- * \param[in,out] T A bignum for temporary storage.
- * It must be at least twice the limb size of N plus 1
- * (T->n >= 2 * N->n + 1).
- * Its initial content is unused and
- * its final content is indeterminate.
- * It does not get reallocated.
- */
-static void mpi_montmul(mbedtls_mpi *A, const mbedtls_mpi *B,
- const mbedtls_mpi *N, mbedtls_mpi_uint mm,
- mbedtls_mpi *T)
-{
- mbedtls_mpi_core_montmul(A->p, A->p, B->p, B->n, N->p, N->n, mm, T->p);
-}
-
-void mbedtls_mpi_montmul(mbedtls_mpi *A, const mbedtls_mpi *B,
- const mbedtls_mpi *N, mbedtls_mpi_uint mm,
- mbedtls_mpi *T )
-{
- mpi_montmul( A, B, N, mm, T);
-}
-
-/*
- * Montgomery reduction: A = A * R^-1 mod N
- *
- * See mpi_montmul() regarding constraints and guarantees on the parameters.
- */
-static void mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N,
- mbedtls_mpi_uint mm, mbedtls_mpi *T)
-{
- mbedtls_mpi_uint z = 1;
- mbedtls_mpi U;
-
- U.n = U.s = (int) z;
- U.p = &z;
-
- mpi_montmul(A, &U, N, mm, T);
-}
-
-void mbedtls_mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N,
- mbedtls_mpi_uint mm, mbedtls_mpi *T)
-{
- mpi_montred(A, 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;
-}
-
-/*
- * 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, WW, Apos;
- mbedtls_mpi *W;
- const size_t array_size_W = 2 << MBEDTLS_MPI_WINDOW_SIZE;
- 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;
@@ -1738,268 +1630,88 @@
}
/*
- * Init temps and window size
+ * Ensure that the exponent that we are passing to the core is not NULL.
*/
- mpi_montg_init(&mm, N);
- mbedtls_mpi_init_mempool(&RR); mbedtls_mpi_init(&T);
- mbedtls_mpi_init_mempool(&Apos);
- mbedtls_mpi_init_mempool(&WW);
-
- 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;
-
- W = mempool_alloc(mbedtls_mpi_mempool,
- sizeof( mbedtls_mpi ) * array_size_W);
- if (W == NULL) {
- ret = MBEDTLS_ERR_MPI_ALLOC_FAILED;
- goto cleanup;
- }
- for (i = 0; i < array_size_W; i++)
- mbedtls_mpi_init_mempool(W + i);
- /*
- * 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 X in the table as
- * well, and also do a constant-trace table lookup to multiply by X.
- *
- * 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.
- *
- * To achieve this, we make a copy of X and we use the table entry in each
- * calculation from this point on.
- */
- const size_t x_index = 0;
- mbedtls_mpi_copy(&W[x_index], X);
-
- j = N->n + 1;
- /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
- * and mpi_montred() calls later. Here we ensure that W[1] and X are
- * large enough, and 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(&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_CHK(mbedtls_mpi_lset(&RR, 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&RR, N->n * 2 * biL));
- MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&RR, &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(&W[1], j));
-
- /*
- * W[1] = A * R^2 * R^-1 mod N = A * R mod N
- */
- 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 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()). */
- mpi_montmul(&W[1], &RR, N, mm, &T);
-
- /*
- * W[x_index] = R^2 * R^-1 mod N = R mod N
- */
- 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++) {
- 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]));
-
- 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));
- 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));
- 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));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
-
- state--;
- nbits = 0;
- exponent_bits_in_window = 0;
- }
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n));
+ RR = *prec_RR;
}
/*
- * process the remaining bits
+ * To preserve constness we need to make a copy of A. Using X for this to
+ * save memory.
*/
- for (i = 0; i < nbits; i++) {
- MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
+ MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
- exponent_bits_in_window <<= 1;
+ /*
+ * Compensate for negative A (and correct at the end).
+ */
+ X->s = 1;
- if ((exponent_bits_in_window & ((size_t) 1 << window_bitsize)) != 0) {
- MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, 1));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
- }
+ /*
+ * 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.
+ */
+ 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));
+
+ /*
+ * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod().
+ */
+ {
+ 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);
}
/*
- * W[x_index] = A^E * R * R^-1 mod N = A^E mod N
+ * Correct for negative A.
*/
- mpi_montred(&W[x_index], N, mm, &T);
+ 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);
- 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_CHK(mbedtls_mpi_add_mpi(X, N, X));
}
- /*
- * Load the result in the output variable.
- */
- mbedtls_mpi_copy(X, &W[x_index]);
-
cleanup:
- if (W)
- for (i = 0; i < array_size_W; i++)
- mbedtls_mpi_free(W + i);
- mempool_free(mbedtls_mpi_mempool , W);
-
- mbedtls_mpi_free(&T);
- mbedtls_mpi_free(&Apos);
- mbedtls_mpi_free(&WW);
+ mbedtls_mpi_zeroize_and_free(T, T_limbs);
if (prec_RR == NULL || prec_RR->p == NULL) {
mbedtls_mpi_free(&RR);
@@ -2017,11 +1729,7 @@
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_mempool(&TA); mbedtls_mpi_init_mempool(&TB);
+ mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB);
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A));
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B));
@@ -2131,9 +1839,6 @@
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
const size_t limbs = CHARS_TO_LIMBS(size);
- MPI_VALIDATE_RET(X != NULL);
- MPI_VALIDATE_RET(f_rng != NULL);
-
/* Ensure that target MPI has exactly the necessary number of limbs */
MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
if (size == 0) {
@@ -2177,19 +1882,14 @@
{
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;
}
- mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TU);
- mbedtls_mpi_init_mempool(&U1); mbedtls_mpi_init_mempool(&U2);
- mbedtls_mpi_init_mempool(&G); mbedtls_mpi_init_mempool(&TB);
- mbedtls_mpi_init_mempool(&TV); mbedtls_mpi_init_mempool(&V1);
- mbedtls_mpi_init_mempool(&V2);
+ mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TU); mbedtls_mpi_init(&U1); mbedtls_mpi_init(&U2);
+ mbedtls_mpi_init(&G); mbedtls_mpi_init(&TB); mbedtls_mpi_init(&TV);
+ mbedtls_mpi_init(&V1); mbedtls_mpi_init(&V2);
MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N));
@@ -2265,29 +1965,30 @@
#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 */
};
/*
@@ -2304,20 +2005,20 @@
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;
+ }
}
}
@@ -2336,12 +2037,9 @@
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_mempool(&W); mbedtls_mpi_init_mempool(&R);
- mbedtls_mpi_init_mempool(&T); mbedtls_mpi_init_mempool(&A);
- mbedtls_mpi_init_mempool(&RR);
+ mbedtls_mpi_init(&W); mbedtls_mpi_init(&R);
+ mbedtls_mpi_init(&T); mbedtls_mpi_init(&A);
+ mbedtls_mpi_init(&RR);
/*
* W = |X| - 1
@@ -2366,7 +2064,7 @@
A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1;
}
- if (count++ > 300) {
+ if (count++ > 30) {
ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
goto cleanup;
}
@@ -2426,8 +2124,6 @@
{
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;
@@ -2477,14 +2173,11 @@
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;
}
- mbedtls_mpi_init_mempool(&Y);
+ mbedtls_mpi_init(&Y);
n = BITS_TO_LIMBS(nbits);
@@ -2602,10 +2295,8 @@
int ret, i;
mbedtls_mpi A, E, N, X, Y, U, V;
- mbedtls_mpi_init_mempool(&A); mbedtls_mpi_init_mempool(&E);
- mbedtls_mpi_init_mempool(&N); mbedtls_mpi_init_mempool(&X);
- mbedtls_mpi_init_mempool(&Y); mbedtls_mpi_init_mempool(&U);
- mbedtls_mpi_init_mempool(&V);
+ mbedtls_mpi_init(&A); mbedtls_mpi_init(&E); mbedtls_mpi_init(&N); mbedtls_mpi_init(&X);
+ mbedtls_mpi_init(&Y); mbedtls_mpi_init(&U); mbedtls_mpi_init(&V);
MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16,
"EFE021C2645FD1DC586E69184AF4A31E" \