Merge pull request #7591 from minosgalanakis/ecp/6028_xtract_fast_reduction_curve25519
[Bignum] Implement fast reduction curve25519
diff --git a/library/ecp_curves.c b/library/ecp_curves.c
index 85c889f..57ce39a 100644
--- a/library/ecp_curves.c
+++ b/library/ecp_curves.c
@@ -4605,6 +4605,8 @@
/* Additional forward declarations */
#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
static int ecp_mod_p255(mbedtls_mpi *);
+MBEDTLS_STATIC_TESTABLE
+int mbedtls_ecp_mod_p255_raw(mbedtls_mpi_uint *X, size_t X_limbs);
#endif
#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
static int ecp_mod_p448(mbedtls_mpi *);
@@ -5418,27 +5420,57 @@
*/
static int ecp_mod_p255(mbedtls_mpi *N)
{
- mbedtls_mpi_uint Mp[P255_WIDTH];
+ int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+ size_t expected_width = 2 * P255_WIDTH;
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(N, expected_width));
+ ret = mbedtls_ecp_mod_p255_raw(N->p, expected_width);
+cleanup:
+ return ret;
+}
- /* Helper references for top part of N */
- mbedtls_mpi_uint * const NT_p = N->p + P255_WIDTH;
- const size_t NT_n = N->n - P255_WIDTH;
- if (N->n <= P255_WIDTH) {
- return 0;
- }
- if (NT_n > P255_WIDTH) {
+MBEDTLS_STATIC_TESTABLE
+int mbedtls_ecp_mod_p255_raw(mbedtls_mpi_uint *X, size_t X_Limbs)
+{
+
+ if (X_Limbs != 2 * P255_WIDTH) {
return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
}
- /* Split N as N + 2^256 M */
- memcpy(Mp, NT_p, sizeof(mbedtls_mpi_uint) * NT_n);
- memset(NT_p, 0, sizeof(mbedtls_mpi_uint) * NT_n);
+ mbedtls_mpi_uint *carry = mbedtls_calloc(P255_WIDTH, ciL);
+ if (carry == NULL) {
+ return MBEDTLS_ERR_ECP_ALLOC_FAILED;
+ }
- /* N = A0 + 38 * A1 */
- mbedtls_mpi_core_mla(N->p, P255_WIDTH + 1,
- Mp, NT_n,
- 38);
+ /* Step 1: Reduction to P255_WIDTH limbs */
+ if (X_Limbs > P255_WIDTH) {
+ /* Helper references for top part of X */
+ mbedtls_mpi_uint * const A1 = X + P255_WIDTH;
+ const size_t A1_limbs = X_Limbs - P255_WIDTH;
+ /* X = A0 + 38 * A1, capture carry out */
+ *carry = mbedtls_mpi_core_mla(X, P255_WIDTH, A1, A1_limbs, 38);
+ /* Clear top part */
+ memset(A1, 0, sizeof(mbedtls_mpi_uint) * A1_limbs);
+ }
+
+ /* Step 2: Reduce to <2p
+ * Split as A0 + 2^255*c, with c a scalar, and compute A0 + 19*c */
+ *carry <<= 1;
+ *carry += (X[P255_WIDTH - 1] >> (biL - 1));
+ *carry *= 19;
+
+ /* Clear top bit */
+ X[P255_WIDTH - 1] <<= 1; X[P255_WIDTH - 1] >>= 1;
+ /* Since the top bit for X has been cleared 0 + 0 + Carry
+ * will not overflow.
+ *
+ * Furthermore for 2p = 2^256-38. When a carry propagation on the highest
+ * limb occurs, X > 2^255 and all the remaining bits on the limb are zero.
+ * - If X < 2^255 ==> X < 2p
+ * - If X > 2^255 ==> X < 2^256 - 2^255 < 2p */
+ (void) mbedtls_mpi_core_add(X, X, carry, P255_WIDTH);
+
+ mbedtls_free(carry);
return 0;
}
#endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
diff --git a/library/ecp_invasive.h b/library/ecp_invasive.h
index b730d95..587b173 100644
--- a/library/ecp_invasive.h
+++ b/library/ecp_invasive.h
@@ -241,6 +241,27 @@
#endif /* MBEDTLS_ECP_DP_SECP256K1_ENABLED */
+#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
+
+/** Fast quasi-reduction modulo p255 = 2^255 - 19
+ *
+ * \param[in,out] X The address of the MPI to be converted.
+ * Must have exact limb size that stores a 510-bit MPI
+ * (double the bitlength of the modulus).
+ * Upon return holds the reduced value which is
+ * in range `0 <= X < 2 * N` (where N is the modulus).
+ * \param[in] X_limbs The length of \p X in limbs.
+ *
+ * \return \c 0 on success.
+ * \return #MBEDTLS_ERR_ECP_BAD_INPUT_DATA if \p X does not have
+ * twice as many limbs as the modulus.
+ * \return #MBEDTLS_ERR_ECP_ALLOC_FAILED if memory allocation failed.
+ */
+MBEDTLS_STATIC_TESTABLE
+int mbedtls_ecp_mod_p255_raw(mbedtls_mpi_uint *X, size_t X_limbs);
+
+#endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
+
#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
MBEDTLS_STATIC_TESTABLE
diff --git a/scripts/mbedtls_dev/ecp.py b/scripts/mbedtls_dev/ecp.py
index c9fb5e5..02db438 100644
--- a/scripts/mbedtls_dev/ecp.py
+++ b/scripts/mbedtls_dev/ecp.py
@@ -97,7 +97,7 @@
def is_valid(self) -> bool:
return True
- def arguments(self):
+ def arguments(self)-> List[str]:
args = super().arguments()
return ["MBEDTLS_ECP_DP_SECP192R1"] + args
@@ -174,7 +174,7 @@
def is_valid(self) -> bool:
return True
- def arguments(self):
+ def arguments(self)-> List[str]:
args = super().arguments()
return ["MBEDTLS_ECP_DP_SECP224R1"] + args
@@ -258,7 +258,7 @@
def is_valid(self) -> bool:
return True
- def arguments(self):
+ def arguments(self)-> List[str]:
args = super().arguments()
return ["MBEDTLS_ECP_DP_SECP256R1"] + args
@@ -380,7 +380,7 @@
def is_valid(self) -> bool:
return True
- def arguments(self):
+ def arguments(self)-> List[str]:
args = super().arguments()
return ["MBEDTLS_ECP_DP_SECP384R1"] + args
@@ -485,7 +485,7 @@
def is_valid(self) -> bool:
return True
- def arguments(self):
+ def arguments(self)-> List[str]:
args = super().arguments()
return ["MBEDTLS_ECP_DP_SECP521R1"] + args
@@ -711,6 +711,75 @@
return ["MBEDTLS_ECP_DP_SECP256K1"] + args
+class EcpP255Raw(bignum_common.ModOperationCommon,
+ EcpTarget):
+ """Test cases for ECP 25519 fast reduction."""
+ symbol = "-"
+ test_function = "ecp_mod_p_generic_raw"
+ test_name = "mbedtls_ecp_mod_p255_raw"
+ input_style = "fixed"
+ arity = 1
+ dependencies = ["MBEDTLS_ECP_DP_CURVE25519_ENABLED"]
+
+ moduli = [("7fffffffffffffffffffffffffffffffffffffffffffffffff"
+ "ffffffffffffed")] # type: List[str]
+
+ input_values = [
+ "0", "1",
+
+ # Modulus - 1
+ ("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec"),
+
+ # Modulus + 1
+ ("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee"),
+
+ # 2^255 - 1
+ ("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"),
+
+ # Maximum canonical P255 multiplication result
+ ("3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec"
+ "0000000000000000000000000000000000000000000000000000000000000190"),
+
+ # First 8 number generated by random.getrandbits(510) - seed(2,2)
+ ("1019f0d64ee207f8da94e3e8ab73738fcf1822ffbc6887782b491044d5e34124"
+ "5c6e433715ba2bdd177219d30e7a269fd95bafc8f2a4d27bdcf4bb99f4bea973"),
+ ("20948fa1feac7eb7dc38f519b91751dacdbd47d364be8049a372db8f6e405d93"
+ "ffed9235288bc781ae66267594c9c9500925e4749b575bd13653f8dd9b1f282e"),
+ ("3a1893ea5186ee32ee8d7ee9770348a05d300cb90706a045defc044a09325626"
+ "e6b58de744ab6cce80877b6f71e1f6d2ef8acd128b4f2fc15f3f57ebf30b94fa"),
+ ("20a6923522fe99a22c70501e533c91352d3d854e061b90303b08c6e33c729578"
+ "2d6c797f8f7d9b782a1be9cd8697bbd0e2520e33e44c50556c71c4a66148a86f"),
+ ("3a248138e8168561867e5e15bc01bfce6a27e0dfcbf8754472154e76e4c11ab2"
+ "fec3f6b32e8d4b8a8f54f8ceacaab39e83844b40ffa9b9f15c14bc4a829e07b0"),
+ ("2f450feab714210c665d7435c1066932f4767f26294365b2721dea3bf63f23d0"
+ "dbe53fcafb2147df5ca495fa5a91c89b97eeab64ca2ce6bc5d3fd983c34c769f"),
+ ("1d199effe202849da9643a295a9ac6decbd4d3e2d4dec9ef83f0be4e80371eb9"
+ "7f81375eecc1cb6347733e847d718d733ff98ff387c56473a7a83ee0761ebfd2"),
+ ("3423c6ec531d6460f0caeef038c89b38a8acb5137c9260dc74e088a9b9492f25"
+ "8ebdbfe3eb9ac688b9d39cca91551e8259cc60b17604e4b4e73695c3e652c71a"),
+
+ # Next 2 number generated by random.getrandbits(255)
+ ("62f1243644a4a8f69dc8db48e86ec9c6e06f291b2a838af8d5c44a4eb3172062"),
+ ("6a606e54b4c9e755cc9c3adcf515a8234da4daeb4f3f87777ad1f45ae9500ec9"),
+ ]
+
+ @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
+
+ def arguments(self)-> List[str]:
+ args = super().arguments()
+ return ["MBEDTLS_ECP_DP_CURVE25519"] + args
+
+
class EcpP448Raw(bignum_common.ModOperationCommon,
EcpTarget):
"""Test cases for ECP P448 fast reduction."""
diff --git a/tests/suites/test_suite_ecp.function b/tests/suites/test_suite_ecp.function
index 49d6e6a..bd0fcf2 100644
--- a/tests/suites/test_suite_ecp.function
+++ b/tests/suites/test_suite_ecp.function
@@ -1350,6 +1350,13 @@
curve_func = &mbedtls_ecp_mod_p256k1_raw;
break;
#endif
+#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
+ case MBEDTLS_ECP_DP_CURVE25519:
+ limbs = 2 * limbs_N;
+ curve_bits = 255;
+ curve_func = &mbedtls_ecp_mod_p255_raw;
+ break;
+#endif
default:
mbedtls_test_fail("Unsupported curve_id", __LINE__, __FILE__);
goto exit;