Merge pull request #6971 from gabor-mezei-arm/6026_Secp192r1_fast_reduction
Extract Secp192r1 fast reduction from the prototype
diff --git a/library/ecp_curves.c b/library/ecp_curves.c
index 7987c3f..2a97b8c 100644
--- a/library/ecp_curves.c
+++ b/library/ecp_curves.c
@@ -4570,6 +4570,8 @@
/* Forward declarations */
#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
static int ecp_mod_p192(mbedtls_mpi *);
+MBEDTLS_STATIC_TESTABLE
+int mbedtls_ecp_mod_p192_raw(mbedtls_mpi_uint *Np, size_t Nn);
#endif
#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
static int ecp_mod_p224(mbedtls_mpi *);
@@ -4884,10 +4886,12 @@
}
#define WIDTH 8 / sizeof(mbedtls_mpi_uint)
-#define A(i) N->p + (i) * WIDTH
-#define ADD(i) add64(p, A(i), &c)
+#define A(i) Np + (i) * WIDTH
+#define ADD(i) add64(p, A(i), &c)
#define NEXT p += WIDTH; carry64(p, &c)
#define LAST p += WIDTH; *p = c; while (++p < end) *p = 0
+#define RESET last_carry[0] = c; c = 0; p = Np
+#define ADD_LAST add64(p, last_carry, &c)
/*
* Fast quasi-reduction modulo p192 (FIPS 186-3 D.2.1)
@@ -4895,28 +4899,51 @@
static int ecp_mod_p192(mbedtls_mpi *N)
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- mbedtls_mpi_uint c = 0;
- mbedtls_mpi_uint *p, *end;
-
- /* Make sure we have enough blocks so that A(5) is legal */
- MBEDTLS_MPI_CHK(mbedtls_mpi_grow(N, 6 * WIDTH));
-
- p = N->p;
- end = p + N->n;
-
- ADD(3); ADD(5); NEXT; // A0 += A3 + A5
- ADD(3); ADD(4); ADD(5); NEXT; // A1 += A3 + A4 + A5
- ADD(4); ADD(5); LAST; // A2 += A4 + A5
+ size_t expected_width = 2 * ((192 + biL - 1) / biL);
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(N, expected_width));
+ ret = mbedtls_ecp_mod_p192_raw(N->p, expected_width);
cleanup:
return ret;
}
+MBEDTLS_STATIC_TESTABLE
+int mbedtls_ecp_mod_p192_raw(mbedtls_mpi_uint *Np, size_t Nn)
+{
+ mbedtls_mpi_uint c = 0, last_carry[WIDTH] = { 0 };
+ mbedtls_mpi_uint *p, *end;
+
+ if (Nn != 2*((192 + biL - 1)/biL)) {
+ return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
+ }
+
+ p = Np;
+ end = p + Nn;
+
+ ADD(3); ADD(5); NEXT; // A0 += A3 + A5
+ ADD(3); ADD(4); ADD(5); NEXT; // A1 += A3 + A4 + A5
+ ADD(4); ADD(5); // A2 += A4 + A5
+
+ RESET;
+
+ /* Use the reduction for the carry as well:
+ * 2^192 * last_carry = 2^64 * last_carry + last_carry mod P192
+ */
+ ADD_LAST; NEXT; // A0 += last_carry
+ ADD_LAST; NEXT; // A1 += last_carry
+
+ LAST; // A2 += carry
+
+ return 0;
+}
+
#undef WIDTH
#undef A
#undef ADD
#undef NEXT
#undef LAST
+#undef RESET
+#undef ADD_LAST
#endif /* MBEDTLS_ECP_DP_SECP192R1_ENABLED */
#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \
diff --git a/library/ecp_invasive.h b/library/ecp_invasive.h
index 18815be..3ee238e 100644
--- a/library/ecp_invasive.h
+++ b/library/ecp_invasive.h
@@ -76,6 +76,25 @@
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
+#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
+
+/** Fast quasi-reduction modulo p192 (FIPS 186-3 D.2.1)
+ *
+ * This operation expects a 384 bit MPI and the result of the reduction
+ * is a 192 bit MPI.
+ *
+ * \param[in,out] Np The address of the MPI to be converted.
+ * Must have twice as many limbs as the modulus.
+ * Upon return this holds the reduced value. The bitlength
+ * of the reduced value is the same as that of the modulus
+ * (192 bits).
+ * \param[in] Nn The length of \p Np in limbs.
+ */
+MBEDTLS_STATIC_TESTABLE
+int mbedtls_ecp_mod_p192_raw(mbedtls_mpi_uint *Np, size_t Nn);
+
+#endif /* MBEDTLS_ECP_DP_SECP192R1_ENABLED */
+
#endif /* MBEDTLS_TEST_HOOKS && MBEDTLS_ECP_C */
#endif /* MBEDTLS_ECP_INVASIVE_H */
diff --git a/scripts/make_generated_files.bat b/scripts/make_generated_files.bat
index e9d9275..9cf34f6 100644
--- a/scripts/make_generated_files.bat
+++ b/scripts/make_generated_files.bat
@@ -11,4 +11,5 @@
perl scripts\generate_visualc_files.pl || exit /b 1
python scripts\generate_psa_constants.py || exit /b 1
python tests\scripts\generate_bignum_tests.py || exit /b 1
+python tests\scripts\generate_ecp_tests.py || exit /b 1
python tests\scripts\generate_psa_tests.py || exit /b 1
diff --git a/scripts/mbedtls_dev/ecp.py b/scripts/mbedtls_dev/ecp.py
new file mode 100644
index 0000000..93cd212
--- /dev/null
+++ b/scripts/mbedtls_dev/ecp.py
@@ -0,0 +1,77 @@
+"""Framework classes for generation of ecp test cases."""
+# 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.
+
+from typing import List
+
+from . import test_data_generation
+from . import bignum_common
+
+class EcpTarget(test_data_generation.BaseTarget):
+ #pylint: disable=abstract-method, too-few-public-methods
+ """Target for ecp test case generation."""
+ target_basename = 'test_suite_ecp.generated'
+
+class EcpP192R1Raw(bignum_common.ModOperationCommon,
+ EcpTarget):
+ """Test cases for ecp quasi_reduction()."""
+ symbol = "-"
+ test_function = "ecp_mod_p192_raw"
+ test_name = "ecp_mod_p192_raw"
+ input_style = "fixed"
+ arity = 1
+
+ moduli = ["fffffffffffffffffffffffffffffffeffffffffffffffff"] # type: List[str]
+
+ input_values = [
+ "0", "1",
+
+ # Modulus - 1
+ "fffffffffffffffffffffffffffffffefffffffffffffffe",
+
+ # First 8 number generated by random.getrandbits(384) - seed(2,2)
+ ("cf1822ffbc6887782b491044d5e341245c6e433715ba2bdd"
+ "177219d30e7a269fd95bafc8f2a4d27bdcf4bb99f4bea973"),
+ ("ffed9235288bc781ae66267594c9c9500925e4749b575bd1"
+ "3653f8dd9b1f282e4067c3584ee207f8da94e3e8ab73738f"),
+ ("ef8acd128b4f2fc15f3f57ebf30b94fa82523e86feac7eb7"
+ "dc38f519b91751dacdbd47d364be8049a372db8f6e405d93"),
+ ("e8624fab5186ee32ee8d7ee9770348a05d300cb90706a045"
+ "defc044a09325626e6b58de744ab6cce80877b6f71e1f6d2"),
+ ("2d3d854e061b90303b08c6e33c7295782d6c797f8f7d9b78"
+ "2a1be9cd8697bbd0e2520e33e44c50556c71c4a66148a86f"),
+ ("fec3f6b32e8d4b8a8f54f8ceacaab39e83844b40ffa9b9f1"
+ "5c14bc4a829e07b0829a48d422fe99a22c70501e533c9135"),
+ ("97eeab64ca2ce6bc5d3fd983c34c769fe89204e2e8168561"
+ "867e5e15bc01bfce6a27e0dfcbf8754472154e76e4c11ab2"),
+ ("bd143fa9b714210c665d7435c1066932f4767f26294365b2"
+ "721dea3bf63f23d0dbe53fcafb2147df5ca495fa5a91c89b"),
+
+ # Next 2 number generated by random.getrandbits(192)
+ "47733e847d718d733ff98ff387c56473a7a83ee0761ebfd2",
+ "cbd4d3e2d4dec9ef83f0be4e80371eb97f81375eecc1cb63"
+ ]
+
+ @property
+ def arg_a(self) -> str:
+ return super().format_arg('{:x}'.format(self.int_a)).zfill(2 * self.hex_digits)
+
+ def result(self) -> List[str]:
+ result = self.int_a % self.int_n
+ return [self.format_result(result)]
+
+ @property
+ def is_valid(self) -> bool:
+ return True
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index 4a7de82..4549a7a 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -32,6 +32,18 @@
execute_process(
COMMAND
${MBEDTLS_PYTHON_EXECUTABLE}
+ ${CMAKE_CURRENT_SOURCE_DIR}/../tests/scripts/generate_ecp_tests.py
+ --list-for-cmake
+ WORKING_DIRECTORY
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+ OUTPUT_VARIABLE
+ base_ecp_generated_data_files)
+string(REGEX REPLACE "[^;]*/" ""
+ base_ecp_generated_data_files "${base_ecp_generated_data_files}")
+
+execute_process(
+ COMMAND
+ ${MBEDTLS_PYTHON_EXECUTABLE}
${CMAKE_CURRENT_SOURCE_DIR}/../tests/scripts/generate_psa_tests.py
--list-for-cmake
WORKING_DIRECTORY
@@ -44,14 +56,18 @@
# Derive generated file paths in the build directory. The generated data
# files go into the suites/ subdirectory.
set(base_generated_data_files
- ${base_bignum_generated_data_files} ${base_psa_generated_data_files})
+ ${base_bignum_generated_data_files} ${base_ecp_generated_data_files} ${base_psa_generated_data_files})
string(REGEX REPLACE "([^;]+)" "suites/\\1"
all_generated_data_files "${base_generated_data_files}")
set(bignum_generated_data_files "")
+set(ecp_generated_data_files "")
set(psa_generated_data_files "")
foreach(file ${base_bignum_generated_data_files})
list(APPEND bignum_generated_data_files ${CMAKE_CURRENT_BINARY_DIR}/suites/${file})
endforeach()
+foreach(file ${base_ecp_generated_data_files})
+ list(APPEND ecp_generated_data_files ${CMAKE_CURRENT_BINARY_DIR}/suites/${file})
+endforeach()
foreach(file ${base_psa_generated_data_files})
list(APPEND psa_generated_data_files ${CMAKE_CURRENT_BINARY_DIR}/suites/${file})
endforeach()
@@ -77,6 +93,22 @@
)
add_custom_command(
OUTPUT
+ ${ecp_generated_data_files}
+ WORKING_DIRECTORY
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+ COMMAND
+ ${MBEDTLS_PYTHON_EXECUTABLE}
+ ${CMAKE_CURRENT_SOURCE_DIR}/../tests/scripts/generate_ecp_tests.py
+ --directory ${CMAKE_CURRENT_BINARY_DIR}/suites
+ DEPENDS
+ ${CMAKE_CURRENT_SOURCE_DIR}/../tests/scripts/generate_ecp_tests.py
+ ${CMAKE_CURRENT_SOURCE_DIR}/../scripts/mbedtls_dev/bignum_common.py
+ ${CMAKE_CURRENT_SOURCE_DIR}/../scripts/mbedtls_dev/ecp.py
+ ${CMAKE_CURRENT_SOURCE_DIR}/../scripts/mbedtls_dev/test_case.py
+ ${CMAKE_CURRENT_SOURCE_DIR}/../scripts/mbedtls_dev/test_data_generation.py
+ )
+ add_custom_command(
+ OUTPUT
${psa_generated_data_files}
WORKING_DIRECTORY
${CMAKE_CURRENT_SOURCE_DIR}/..
@@ -107,6 +139,7 @@
# With this line, only 4 sub-makefiles include the above command, that reduces
# the risk of a race.
add_custom_target(test_suite_bignum_generated_data DEPENDS ${bignum_generated_data_files})
+add_custom_target(test_suite_ecp_generated_data DEPENDS ${ecp_generated_data_files})
add_custom_target(test_suite_psa_generated_data DEPENDS ${psa_generated_data_files})
# If SKIP_TEST_SUITES is not defined with -D, get it from the environment.
if((NOT DEFINED SKIP_TEST_SUITES) AND (DEFINED ENV{SKIP_TEST_SUITES}))
@@ -129,6 +162,7 @@
# Get the test names of the tests with generated .data files
# from the generated_data_files list in parent scope.
set(bignum_generated_data_names "")
+ set(ecp_generated_data_names "")
set(psa_generated_data_names "")
foreach(generated_data_file ${bignum_generated_data_files})
# Get the plain filename
@@ -139,6 +173,15 @@
string(SUBSTRING ${generated_data_name} 11 -1 generated_data_name)
list(APPEND bignum_generated_data_names ${generated_data_name})
endforeach()
+ foreach(generated_data_file ${ecp_generated_data_files})
+ # Get the plain filename
+ get_filename_component(generated_data_name ${generated_data_file} NAME)
+ # Remove the ".data" extension
+ get_name_without_last_ext(generated_data_name ${generated_data_name})
+ # Remove leading "test_suite_"
+ string(SUBSTRING ${generated_data_name} 11 -1 generated_data_name)
+ list(APPEND ecp_generated_data_names ${generated_data_name})
+ endforeach()
foreach(generated_data_file ${psa_generated_data_files})
# Get the plain filename
get_filename_component(generated_data_name ${generated_data_file} NAME)
@@ -153,6 +196,10 @@
set(data_file
${CMAKE_CURRENT_BINARY_DIR}/suites/test_suite_${data_name}.data)
set(dependency test_suite_bignum_generated_data)
+ elseif(";${ecp_generated_data_names};" MATCHES ";${data_name};")
+ set(data_file
+ ${CMAKE_CURRENT_BINARY_DIR}/suites/test_suite_${data_name}.data)
+ set(dependency test_suite_ecp_generated_data)
elseif(";${psa_generated_data_names};" MATCHES ";${data_name};")
set(data_file
${CMAKE_CURRENT_BINARY_DIR}/suites/test_suite_${data_name}.data)
@@ -160,7 +207,7 @@
else()
set(data_file
${CMAKE_CURRENT_SOURCE_DIR}/suites/test_suite_${data_name}.data)
- set(dependency test_suite_bignum_generated_data test_suite_psa_generated_data)
+ set(dependency test_suite_bignum_generated_data test_suite_ecp_generated_data test_suite_psa_generated_data)
endif()
add_custom_command(
diff --git a/tests/Makefile b/tests/Makefile
index 312607e..c9283c9 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -73,6 +73,13 @@
ifeq ($(GENERATED_BIGNUM_DATA_FILES),FAILED)
$(error "$(PYTHON) scripts/generate_bignum_tests.py --list" failed)
endif
+GENERATED_ECP_DATA_FILES := $(patsubst tests/%,%,$(shell \
+ $(PYTHON) scripts/generate_ecp_tests.py --list || \
+ echo FAILED \
+))
+ifeq ($(GENERATED_ECP_DATA_FILES),FAILED)
+$(error "$(PYTHON) scripts/generate_ecp_tests.py --list" failed)
+endif
GENERATED_PSA_DATA_FILES := $(patsubst tests/%,%,$(shell \
$(PYTHON) scripts/generate_psa_tests.py --list || \
echo FAILED \
@@ -80,7 +87,7 @@
ifeq ($(GENERATED_PSA_DATA_FILES),FAILED)
$(error "$(PYTHON) scripts/generate_psa_tests.py --list" failed)
endif
-GENERATED_FILES := $(GENERATED_PSA_DATA_FILES) $(GENERATED_BIGNUM_DATA_FILES)
+GENERATED_FILES := $(GENERATED_PSA_DATA_FILES) $(GENERATED_ECP_DATA_FILES) $(GENERATED_BIGNUM_DATA_FILES)
generated_files: $(GENERATED_FILES)
# generate_bignum_tests.py and generate_psa_tests.py spend more time analyzing
@@ -89,7 +96,7 @@
# It's rare not to want all the outputs. So always generate all of its outputs.
# Use an intermediate phony dependency so that parallel builds don't run
# a separate instance of the recipe for each output file.
-.SECONDARY: generated_bignum_test_data generated_psa_test_data
+.SECONDARY: generated_bignum_test_data generated_ecp_test_data generated_psa_test_data
$(GENERATED_BIGNUM_DATA_FILES): generated_bignum_test_data
generated_bignum_test_data: scripts/generate_bignum_tests.py
generated_bignum_test_data: ../scripts/mbedtls_dev/bignum_common.py
@@ -102,6 +109,16 @@
echo " Gen $(GENERATED_BIGNUM_DATA_FILES)"
$(PYTHON) scripts/generate_bignum_tests.py
+$(GENERATED_ECP_DATA_FILES): generated_ecp_test_data
+generated_ecp_test_data: scripts/generate_ecp_tests.py
+generated_ecp_test_data: ../scripts/mbedtls_dev/bignum_common.py
+generated_ecp_test_data: ../scripts/mbedtls_dev/ecp.py
+generated_ecp_test_data: ../scripts/mbedtls_dev/test_case.py
+generated_ecp_test_data: ../scripts/mbedtls_dev/test_data_generation.py
+generated_ecp_test_data:
+ echo " Gen $(GENERATED_ECP_DATA_FILES)"
+ $(PYTHON) scripts/generate_ecp_tests.py
+
$(GENERATED_PSA_DATA_FILES): generated_psa_test_data
generated_psa_test_data: scripts/generate_psa_tests.py
generated_psa_test_data: ../scripts/mbedtls_dev/crypto_knowledge.py
diff --git a/tests/scripts/check-generated-files.sh b/tests/scripts/check-generated-files.sh
index 2bb9fea..4d6f930 100755
--- a/tests/scripts/check-generated-files.sh
+++ b/tests/scripts/check-generated-files.sh
@@ -137,4 +137,5 @@
check scripts/generate_visualc_files.pl visualc/VS2013
check scripts/generate_psa_constants.py programs/psa/psa_constant_names_generated.c
check tests/scripts/generate_bignum_tests.py $(tests/scripts/generate_bignum_tests.py --list)
+check tests/scripts/generate_ecp_tests.py $(tests/scripts/generate_ecp_tests.py --list)
check tests/scripts/generate_psa_tests.py $(tests/scripts/generate_psa_tests.py --list)
diff --git a/tests/scripts/generate_ecp_tests.py b/tests/scripts/generate_ecp_tests.py
new file mode 100755
index 0000000..abbfda5
--- /dev/null
+++ b/tests/scripts/generate_ecp_tests.py
@@ -0,0 +1,34 @@
+#!/usr/bin/env python3
+"""Generate test data for ecp functions.
+
+The command line usage, class structure and available methods are the same
+as in generate_bignum_tests.py.
+"""
+
+# 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.
+
+import sys
+
+import scripts_path # pylint: disable=unused-import
+from mbedtls_dev import test_data_generation
+# Import modules containing additional test classes
+# Test function classes in these modules will be registered by
+# the framework
+from mbedtls_dev import ecp # pylint: disable=unused-import
+
+if __name__ == '__main__':
+ # Use the section of the docstring relevant to the CLI as description
+ test_data_generation.main(sys.argv[1:], "\n".join(__doc__.splitlines()[:4]))
diff --git a/tests/suites/test_suite_ecp.function b/tests/suites/test_suite_ecp.function
index c8a0a82..b9d2b5e 100644
--- a/tests/suites/test_suite_ecp.function
+++ b/tests/suites/test_suite_ecp.function
@@ -3,6 +3,8 @@
#include "mbedtls/ecdsa.h"
#include "mbedtls/ecdh.h"
+#include "bignum_core.h"
+#include "bignum_mod_raw_invasive.h"
#include "ecp_invasive.h"
#if defined(MBEDTLS_TEST_HOOKS) && \
@@ -1299,3 +1301,46 @@
mbedtls_mpi_free(&expected_n);
}
/* END_CASE */
+
+/* BEGIN_CASE depends_on:MBEDTLS_TEST_HOOKS */
+void ecp_mod_p192_raw(char *input_N,
+ char *input_X,
+ char *result)
+{
+ mbedtls_mpi_uint *X = NULL;
+ mbedtls_mpi_uint *N = NULL;
+ mbedtls_mpi_uint *res = 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, 2 * limbs);
+ TEST_EQUAL(limbs_res, limbs);
+
+ TEST_EQUAL(mbedtls_mpi_mod_modulus_setup(
+ &m, N, limbs,
+ MBEDTLS_MPI_MOD_REP_MONTGOMERY), 0);
+
+ TEST_EQUAL(mbedtls_ecp_mod_p192_raw(X, limbs_X), 0);
+ TEST_LE_U(mbedtls_mpi_core_bitlen(X, limbs_X), 192);
+ mbedtls_mpi_mod_raw_fix_quasi_reduction(X, &m);
+ ASSERT_COMPARE(X, bytes, res, bytes);
+
+exit:
+ mbedtls_free(X);
+ mbedtls_free(res);
+
+ mbedtls_mpi_mod_modulus_free(&m);
+ mbedtls_free(N);
+}
+/* END_CASE */