Merge pull request #6776 from gabor-mezei-arm/6222_bignum_mod_mul

Bignum: Implement fixed width modular multiplication

5 files changed, 223 insertions, 0 deletions

diff --git a/library/bignum_mod.c b/library/bignum_mod.c
index c9efb33..bd67241 100644
--- a/library/bignum_mod.c
+++ b/library/bignum_mod.c
@@ -176,6 +176,28 @@ exit:
 
 /* BEGIN MERGE SLOT 2 */
 
+int mbedtls_mpi_mod_mul( mbedtls_mpi_mod_residue *X,
+                         const mbedtls_mpi_mod_residue *A,
+                         const mbedtls_mpi_mod_residue *B,
+                         const mbedtls_mpi_mod_modulus *N )
+{
+    if( N->limbs == 0 )
+        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+
+    if( X->limbs != N->limbs || A->limbs != N->limbs || B->limbs != N->limbs )
+        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+
+    mbedtls_mpi_uint *T = mbedtls_calloc( N->limbs * 2 + 1, ciL );
+    if( T == NULL )
+        return MBEDTLS_ERR_MPI_ALLOC_FAILED;
+
+    mbedtls_mpi_mod_raw_mul( X->p, A->p, B->p, N, T );
+
+    mbedtls_free( T );
+
+    return( 0 );
+}
+
 /* END MERGE SLOT 2 */
 
 /* BEGIN MERGE SLOT 3 */
diff --git a/library/bignum_mod.h b/library/bignum_mod.h
index 2ee219f..1b1e920 100644
--- a/library/bignum_mod.h
+++ b/library/bignum_mod.h
@@ -230,6 +230,40 @@ void mbedtls_mpi_mod_modulus_free( mbedtls_mpi_mod_modulus *m );
 
 /* BEGIN MERGE SLOT 2 */
 
+/** \brief  Multiply two residues, returning the residue modulo the specified
+ *          modulus.
+ *
+ * \note Currently handles the case when `N->int_rep` is
+ * MBEDTLS_MPI_MOD_REP_MONTGOMERY.
+ *
+ * The size of the operation is determined by \p N. \p A, \p B and \p X must
+ * all be associated with the modulus \p N and must all have the same number
+ * of limbs as \p N.
+ *
+ * \p X may be aliased to \p A or \p B, or even both, but may not overlap
+ * either otherwise. They may not alias \p N (since they must be in canonical
+ * form, they cannot == \p N).
+ *
+ * \param[out] X        The address of the result MPI. Must have the same
+ *                      number of limbs as \p N.
+ *                      On successful completion, \p X contains the result of
+ *                      the multiplication `A * B * R^-1` mod N where
+ *                      `R = 2^(biL * N->limbs)`.
+ * \param[in]  A        The address of the first MPI.
+ * \param[in]  B        The address of the second MPI.
+ * \param[in]  N        The address of the modulus. Used to perform a modulo
+ *                      operation on the result of the multiplication.
+ *
+ * \return      \c 0 if successful.
+ * \return      #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if all the parameters do not
+ *              have the same number of limbs or \p N is invalid.
+ * \return      #MBEDTLS_ERR_MPI_ALLOC_FAILED on memory-allocation failure.
+ */
+int mbedtls_mpi_mod_mul( mbedtls_mpi_mod_residue *X,
+                         const mbedtls_mpi_mod_residue *A,
+                         const mbedtls_mpi_mod_residue *B,
+                         const mbedtls_mpi_mod_modulus *N );
+
 /* END MERGE SLOT 2 */
 
 /* BEGIN MERGE SLOT 3 */
diff --git a/scripts/mbedtls_dev/bignum_mod.py b/scripts/mbedtls_dev/bignum_mod.py
index 25afe30..a83e136 100644
--- a/scripts/mbedtls_dev/bignum_mod.py
+++ b/scripts/mbedtls_dev/bignum_mod.py
@@ -31,6 +31,26 @@ class BignumModTarget(test_data_generation.BaseTarget):
 
 # BEGIN MERGE SLOT 2
 
+class BignumModMul(bignum_common.ModOperationCommon,
+                   BignumModTarget):
+    # pylint:disable=duplicate-code
+    """Test cases for bignum mpi_mod_mul()."""
+    symbol = "*"
+    test_function = "mpi_mod_mul"
+    test_name = "mbedtls_mpi_mod_mul"
+    input_style = "arch_split"
+    arity = 2
+
+    def arguments(self) -> List[str]:
+        return [self.format_result(self.to_montgomery(self.int_a)),
+                self.format_result(self.to_montgomery(self.int_b)),
+                bignum_common.quote_str(self.arg_n)
+               ] + self.result()
+
+    def result(self) -> List[str]:
+        result = (self.int_a * self.int_b) % self.int_n
+        return [self.format_result(self.to_montgomery(result))]
+
 # END MERGE SLOT 2
 
 # BEGIN MERGE SLOT 3
diff --git a/tests/suites/test_suite_bignum_mod.function b/tests/suites/test_suite_bignum_mod.function
index 79f5134..8ab8ccf 100644
--- a/tests/suites/test_suite_bignum_mod.function
+++ b/tests/suites/test_suite_bignum_mod.function
@@ -2,6 +2,7 @@
 #include "mbedtls/bignum.h"
 #include "mbedtls/entropy.h"
 #include "bignum_mod.h"
+#include "bignum_mod_raw.h"
 #include "constant_time_internal.h"
 #include "test/constant_flow.h"
 
@@ -102,6 +103,145 @@ exit:
 
 /* BEGIN MERGE SLOT 2 */
 
+/* BEGIN_CASE */
+void mpi_mod_mul( char * input_A,
+                  char * input_B,
+                  char * input_N,
+                  char * result )
+{
+    mbedtls_mpi_uint *X = NULL;
+
+    mbedtls_mpi_mod_residue rA = { NULL, 0 };
+    mbedtls_mpi_mod_residue rB = { NULL, 0 };
+    mbedtls_mpi_mod_residue rR = { NULL, 0 };
+    mbedtls_mpi_mod_residue rX = { NULL, 0 };
+
+    mbedtls_mpi_mod_modulus m;
+    mbedtls_mpi_mod_modulus_init( &m );
+
+    TEST_EQUAL( test_read_modulus( &m, MBEDTLS_MPI_MOD_REP_MONTGOMERY, input_N ),
+                0 );
+
+    TEST_EQUAL( test_read_residue( &rA, &m, input_A, 0 ), 0 );
+    TEST_EQUAL( test_read_residue( &rB, &m, input_B, 0 ), 0 );
+    TEST_EQUAL( test_read_residue( &rR, &m, result,  0 ), 0 );
+
+    const size_t limbs = m.limbs;
+    const size_t bytes = limbs * sizeof( mbedtls_mpi_uint );
+
+    TEST_EQUAL( rA.limbs, limbs );
+    TEST_EQUAL( rB.limbs, limbs );
+    TEST_EQUAL( rR.limbs, limbs );
+
+    ASSERT_ALLOC( X, limbs );
+
+    TEST_EQUAL( mbedtls_mpi_mod_residue_setup( &rX, &m, X, limbs ), 0 );
+
+    TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rA, &rB, &m ), 0 );
+    ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+
+    /* alias X to A */
+    memcpy( rX.p, rA.p, bytes );
+    TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rX, &rB, &m ), 0 );
+    ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+
+    /* alias X to B */
+    memcpy( rX.p, rB.p, bytes );
+    TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rA, &rX, &m ), 0);
+    ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+
+    /* A == B: alias A and B */
+    if( memcmp( rA.p, rB.p, bytes ) == 0 )
+    {
+        TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rA, &rA, &m ), 0 );
+        ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+
+        /* X, A, B all aliased together */
+        memcpy( rX.p, rA.p, bytes );
+        TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rX, &rX, &m ), 0 );
+        ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+    }
+
+    /* A != B: test B * A */
+    else
+    {
+        TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rB, &rA, &m ), 0 );
+        ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+
+        /* B * A: alias X to A */
+        memcpy( rX.p, rA.p, bytes );
+        TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rB, &rX, &m ), 0 );
+        ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+
+        /* B + A: alias X to B */
+        memcpy( rX.p, rB.p, bytes );
+        TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rX, &rA, &m ), 0 );
+        ASSERT_COMPARE( rX.p, bytes, rR.p, bytes );
+    }
+
+exit:
+    mbedtls_free( rA.p );
+    mbedtls_free( rB.p );
+    mbedtls_free( rR.p );
+    mbedtls_free( X );
+    mbedtls_free( (mbedtls_mpi_uint *) m.p );
+
+    mbedtls_mpi_mod_modulus_free( &m );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
+void mpi_mod_mul_neg( char * input_A,
+                      char * input_B,
+                      char * input_N,
+                      char * result,
+                      int exp_ret )
+{
+    mbedtls_mpi_uint *X = NULL;
+
+    mbedtls_mpi_mod_residue rA = { NULL, 0 };
+    mbedtls_mpi_mod_residue rB = { NULL, 0 };
+    mbedtls_mpi_mod_residue rR = { NULL, 0 };
+    mbedtls_mpi_mod_residue rX = { NULL, 0 };
+
+    mbedtls_mpi_mod_modulus m;
+    mbedtls_mpi_mod_modulus_init( &m );
+
+    mbedtls_mpi_mod_modulus fake_m;
+    mbedtls_mpi_mod_modulus_init( &fake_m );
+
+    TEST_EQUAL( test_read_modulus( &m, MBEDTLS_MPI_MOD_REP_MONTGOMERY, input_N ),
+                0 );
+
+    TEST_EQUAL( test_read_residue( &rA, &m, input_A, 1 ), 0 );
+    TEST_EQUAL( test_read_residue( &rB, &m, input_B, 1 ), 0 );
+    TEST_EQUAL( test_read_residue( &rR, &m, result,  1 ), 0 );
+
+    const size_t limbs = m.limbs;
+
+    ASSERT_ALLOC( X, limbs );
+
+    TEST_EQUAL( mbedtls_mpi_mod_residue_setup( &rX, &m, X, limbs ), 0 );
+    rX.limbs = rR.limbs;
+
+    TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rA, &rB, &m ), exp_ret );
+
+    /* Check when m is not initialized */
+    TEST_EQUAL( mbedtls_mpi_mod_mul( &rX, &rA, &rB, &fake_m ),
+                MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+
+exit:
+    mbedtls_free( rA.p );
+    mbedtls_free( rB.p );
+    mbedtls_free( rR.p );
+    mbedtls_free( X );
+    mbedtls_free( (mbedtls_mpi_uint *) m.p );
+
+    mbedtls_mpi_mod_modulus_free( &m );
+    mbedtls_mpi_mod_modulus_free( &fake_m );
+}
+/* END_CASE */
+
 /* END MERGE SLOT 2 */
 
 /* BEGIN MERGE SLOT 3 */
diff --git a/tests/suites/test_suite_bignum_mod.misc.data b/tests/suites/test_suite_bignum_mod.misc.data
index 6240e21..e369211 100644
--- a/tests/suites/test_suite_bignum_mod.misc.data
+++ b/tests/suites/test_suite_bignum_mod.misc.data
@@ -12,7 +12,14 @@ mpi_mod_setup:MBEDTLS_MPI_MOD_REP_MONTGOMERY:0
 # END MERGE SLOT 1
 
 # BEGIN MERGE SLOT 2
+Test mpi_mod_mul #1 N->limbs != A->limbs
+mpi_mod_mul_neg:"1":"00000000000000000000000000000000":"f0000000000000000000000000000000":"0":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
 
+Test mpi_mod_mul #2 N->limbs != B->limbs
+mpi_mod_mul_neg:"1234567890abcdef1234567890abcdef":"0":"f0000000000000000000000000000000":"0":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+Test mpi_mod_mul #3 N->limbs != X->limbs
+mpi_mod_mul_neg:"1234567890abcdef1234567890abcdef":"00000000000000000000000000000000":"f0000000000000000000000000000000":"0":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
 # END MERGE SLOT 2
 
 # BEGIN MERGE SLOT 3