Merge pull request #6941 from gabor-mezei-arm/6375_quasi-reduction_function
Add function to fix quasi-reduction
diff --git a/library/bignum_mod_raw.c b/library/bignum_mod_raw.c
index 826dd07..bf0cb25 100644
--- a/library/bignum_mod_raw.c
+++ b/library/bignum_mod_raw.c
@@ -33,6 +33,8 @@
#include "bignum_mod.h"
#include "constant_time_internal.h"
+#include "bignum_mod_raw_invasive.h"
+
void mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint *X,
const mbedtls_mpi_uint *A,
const mbedtls_mpi_mod_modulus *N,
@@ -118,6 +120,19 @@
(void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c);
}
+#if defined(MBEDTLS_TEST_HOOKS)
+
+MBEDTLS_STATIC_TESTABLE
+void mbedtls_mpi_mod_raw_fix_quasi_reduction(mbedtls_mpi_uint *X,
+ const mbedtls_mpi_mod_modulus *N)
+{
+ mbedtls_mpi_uint c = mbedtls_mpi_core_sub(X, X, N->p, N->limbs);
+
+ (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c);
+}
+
+#endif /* MBEDTLS_TEST_HOOKS */
+
void mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint *X,
const mbedtls_mpi_uint *A,
const mbedtls_mpi_uint *B,
diff --git a/library/bignum_mod_raw_invasive.h b/library/bignum_mod_raw_invasive.h
new file mode 100644
index 0000000..ead8394
--- /dev/null
+++ b/library/bignum_mod_raw_invasive.h
@@ -0,0 +1,46 @@
+/**
+ * \file bignum_mod_raw_invasive.h
+ *
+ * \brief Function declarations for invasive functions of Low-level
+ * modular bignum.
+ */
+/**
+ * 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.
+ */
+
+#ifndef MBEDTLS_BIGNUM_MOD_RAW_INVASIVE_H
+#define MBEDTLS_BIGNUM_MOD_RAW_INVASIVE_H
+
+#include "common.h"
+#include "mbedtls/bignum.h"
+#include "bignum_mod.h"
+
+#if defined(MBEDTLS_TEST_HOOKS)
+
+/** Convert the result of a quasi-reduction to its canonical representative.
+ *
+ * \param[in,out] X The address of the MPI to be converted. Must have the
+ * same number of limbs as \p N. The input value must
+ * be in range 0 <= X < 2N.
+ * \param[in] N The address of the modulus.
+ */
+MBEDTLS_STATIC_TESTABLE
+void mbedtls_mpi_mod_raw_fix_quasi_reduction(mbedtls_mpi_uint *X,
+ const mbedtls_mpi_mod_modulus *N);
+
+#endif /* MBEDTLS_TEST_HOOKS */
+
+#endif /* MBEDTLS_BIGNUM_MOD_RAW_INVASIVE_H */
diff --git a/scripts/mbedtls_dev/bignum_mod_raw.py b/scripts/mbedtls_dev/bignum_mod_raw.py
index f9d9899..d197b54 100644
--- a/scripts/mbedtls_dev/bignum_mod_raw.py
+++ b/scripts/mbedtls_dev/bignum_mod_raw.py
@@ -51,6 +51,37 @@
result = (self.int_a - self.int_b) % self.int_n
return [self.format_result(result)]
+class BignumModRawFixQuasiReduction(bignum_common.ModOperationCommon,
+ BignumModRawTarget):
+ """Test cases for ecp quasi_reduction()."""
+ symbol = "-"
+ test_function = "mpi_mod_raw_fix_quasi_reduction"
+ test_name = "fix_quasi_reduction"
+ input_style = "fixed"
+ arity = 1
+
+ # Extend the default values with n < x < 2n
+ input_values = bignum_common.ModOperationCommon.input_values + [
+ "73",
+
+ # First number generated by random.getrandbits(1024) - seed(3,2)
+ "ea7b5bf55eb561a4216363698b529b4a97b750923ceb3ffd",
+
+ # First number generated by random.getrandbits(1024) - seed(1,2)
+ ("cd447e35b8b6d8fe442e3d437204e52db2221a58008a05a6c4647159c324c985"
+ "9b810e766ec9d28663ca828dd5f4b3b2e4b06ce60741c7a87ce42c8218072e8c"
+ "35bf992dc9e9c616612e7696a6cecc1b78e510617311d8a3c2ce6f447ed4d57b"
+ "1e2feb89414c343c1027c4d1c386bbc4cd613e30d8f16adf91b7584a2265b1f5")
+ ] # type: List[str]
+
+ def result(self) -> List[str]:
+ result = self.int_a % self.int_n
+ return [self.format_result(result)]
+
+ @property
+ def is_valid(self) -> bool:
+ return bool(self.int_a < 2 * self.int_n)
+
class BignumModRawMul(bignum_common.ModOperationCommon,
BignumModRawTarget):
"""Test cases for bignum mpi_mod_raw_mul()."""
diff --git a/tests/suites/test_suite_bignum_mod_raw.function b/tests/suites/test_suite_bignum_mod_raw.function
index 9310b0e..24ecba3 100644
--- a/tests/suites/test_suite_bignum_mod_raw.function
+++ b/tests/suites/test_suite_bignum_mod_raw.function
@@ -6,6 +6,8 @@
#include "constant_time_internal.h"
#include "test/constant_flow.h"
+#include "bignum_mod_raw_invasive.h"
+
/* END_HEADER */
/* BEGIN_DEPENDENCIES
@@ -338,6 +340,56 @@
}
/* END_CASE */
+/* BEGIN_CASE depends_on:MBEDTLS_TEST_HOOKS */
+void mpi_mod_raw_fix_quasi_reduction(char *input_N,
+ char *input_X,
+ char *result)
+{
+ mbedtls_mpi_uint *X = NULL;
+ mbedtls_mpi_uint *N = NULL;
+ mbedtls_mpi_uint *res = NULL;
+ mbedtls_mpi_uint *tmp = NULL;
+ size_t limbs_X;
+ size_t limbs_N;
+ size_t limbs_res;
+
+ mbedtls_mpi_mod_modulus m;
+ mbedtls_mpi_mod_modulus_init(&m);
+
+ TEST_EQUAL(mbedtls_test_read_mpi_core(&X, &limbs_X, input_X), 0);
+ TEST_EQUAL(mbedtls_test_read_mpi_core(&N, &limbs_N, input_N), 0);
+ TEST_EQUAL(mbedtls_test_read_mpi_core(&res, &limbs_res, result), 0);
+
+ size_t limbs = limbs_N;
+ size_t bytes = limbs * sizeof(mbedtls_mpi_uint);
+
+ TEST_EQUAL(limbs_X, limbs);
+ TEST_EQUAL(limbs_res, limbs);
+
+ ASSERT_ALLOC(tmp, limbs);
+ memcpy(tmp, X, bytes);
+
+ /* Check that 0 <= X < 2N */
+ mbedtls_mpi_uint c = mbedtls_mpi_core_sub(tmp, X, N, limbs);
+ TEST_ASSERT(c || mbedtls_mpi_core_lt_ct(tmp, N, limbs));
+
+ TEST_EQUAL(mbedtls_mpi_mod_modulus_setup(
+ &m, N, limbs,
+ MBEDTLS_MPI_MOD_REP_MONTGOMERY), 0);
+
+ mbedtls_mpi_mod_raw_fix_quasi_reduction(X, &m);
+ ASSERT_COMPARE(X, bytes, res, bytes);
+
+exit:
+ mbedtls_free(X);
+ mbedtls_free(res);
+ mbedtls_free(tmp);
+
+ mbedtls_mpi_mod_modulus_free(&m);
+ mbedtls_free(N);
+}
+/* END_CASE */
+
/* BEGIN_CASE */
void mpi_mod_raw_mul(char *input_A,
char *input_B,
diff --git a/tests/suites/test_suite_ecp.data b/tests/suites/test_suite_ecp.data
index 9311200..9a13793 100644
--- a/tests/suites/test_suite_ecp.data
+++ b/tests/suites/test_suite_ecp.data
@@ -1038,4 +1038,3 @@
ECP check order for CURVE448
depends_on:MBEDTLS_ECP_DP_CURVE448_ENABLED
ecp_check_order:MBEDTLS_ECP_DP_CURVE448:"3fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3"
-