Merge pull request #6743 from minosgalanakis/bignum/implement_modular_negation
Bignum: Implement fixed width modular negation
diff --git a/library/bignum_mod_raw.c b/library/bignum_mod_raw.c
index 266d915..c98a1c1 100644
--- a/library/bignum_mod_raw.c
+++ b/library/bignum_mod_raw.c
@@ -213,6 +213,18 @@
mbedtls_free( T );
return( 0 );
}
+
+void mbedtls_mpi_mod_raw_neg( mbedtls_mpi_uint *X,
+ const mbedtls_mpi_uint *A,
+ const mbedtls_mpi_mod_modulus *m )
+{
+ mbedtls_mpi_core_sub( X, m->p, A, m->limbs );
+
+ /* If A=0 initially, then X=N now. Detect this by
+ * subtracting N and catching the carry. */
+ mbedtls_mpi_uint borrow = mbedtls_mpi_core_sub( X, X, m->p, m->limbs );
+ (void) mbedtls_mpi_core_add_if( X, m->p, m->limbs, (unsigned) borrow );
+}
/* END MERGE SLOT 7 */
/* BEGIN MERGE SLOT 8 */
diff --git a/library/bignum_mod_raw.h b/library/bignum_mod_raw.h
index 698119e..f9968ba 100644
--- a/library/bignum_mod_raw.h
+++ b/library/bignum_mod_raw.h
@@ -278,6 +278,23 @@
*/
int mbedtls_mpi_mod_raw_from_mont_rep( mbedtls_mpi_uint *X,
const mbedtls_mpi_mod_modulus *m );
+
+/** \brief Perform fixed width modular negation.
+ *
+ * The size of the operation is determined by \p m. \p A must have
+ * the same number of limbs as \p m.
+ *
+ * \p X may be aliased to \p A.
+ *
+ * \param[out] X The result of the modular negation.
+ * This must be initialized.
+ * \param[in] A Little-endian presentation of the input operand. This
+ * must be less than or equal to \p m.
+ * \param[in] m The modulus to use.
+ */
+void mbedtls_mpi_mod_raw_neg( mbedtls_mpi_uint *X,
+ const mbedtls_mpi_uint *A,
+ const mbedtls_mpi_mod_modulus *m);
/* END MERGE SLOT 7 */
/* BEGIN MERGE SLOT 8 */
diff --git a/scripts/mbedtls_dev/bignum_mod_raw.py b/scripts/mbedtls_dev/bignum_mod_raw.py
index 0486426..6fc4c91 100644
--- a/scripts/mbedtls_dev/bignum_mod_raw.py
+++ b/scripts/mbedtls_dev/bignum_mod_raw.py
@@ -137,7 +137,18 @@
result = self.from_montgomery(self.int_a)
return [self.format_result(result)]
+class BignumModRawModNegate(bignum_common.ModOperationCommon,
+ BignumModRawTarget):
+ """ Test cases for mpi_mod_raw_neg(). """
+ test_function = "mpi_mod_raw_neg"
+ test_name = "Modular negation: "
+ symbol = "-"
+ input_style = "arch_split"
+ arity = 1
+ def result(self) -> List[str]:
+ result = (self.int_n - self.int_a) % self.int_n
+ return [self.format_result(result)]
# END MERGE SLOT 7
# BEGIN MERGE SLOT 8
diff --git a/tests/suites/test_suite_bignum_mod_raw.function b/tests/suites/test_suite_bignum_mod_raw.function
index 5d23707..83e1f54 100644
--- a/tests/suites/test_suite_bignum_mod_raw.function
+++ b/tests/suites/test_suite_bignum_mod_raw.function
@@ -595,6 +595,60 @@
mbedtls_free( X );
}
/* END_CASE */
+
+/* BEGIN_CASE */
+void mpi_mod_raw_neg( char * input_N, char * input_A, char * input_X )
+{
+ mbedtls_mpi_uint *N = NULL;
+ mbedtls_mpi_uint *A = NULL;
+ mbedtls_mpi_uint *X = NULL;
+ mbedtls_mpi_uint *R = NULL;
+ mbedtls_mpi_uint *Z = NULL;
+ size_t n_limbs, a_limbs, x_limbs, bytes;
+
+ mbedtls_mpi_mod_modulus m;
+ mbedtls_mpi_mod_modulus_init( &m );
+
+ /* Read inputs */
+ TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &N, &n_limbs, input_N ) );
+ TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &A, &a_limbs, input_A ) );
+ TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &X, &x_limbs, input_X ) );
+
+ TEST_EQUAL( a_limbs, n_limbs );
+ TEST_EQUAL( x_limbs, n_limbs );
+ bytes = n_limbs * sizeof( mbedtls_mpi_uint );
+
+ ASSERT_ALLOC( R, n_limbs );
+ ASSERT_ALLOC( Z, n_limbs );
+
+ TEST_EQUAL( 0, mbedtls_mpi_mod_modulus_setup( &m, N, n_limbs,
+ MBEDTLS_MPI_MOD_REP_MONTGOMERY ) );
+
+ /* Neg( A == 0 ) => Zero result */
+ mbedtls_mpi_mod_raw_neg( R, Z, &m );
+ ASSERT_COMPARE( R, bytes, Z, bytes );
+
+ /* Neg( A == N ) => Zero result */
+ mbedtls_mpi_mod_raw_neg( R, N, &m );
+ ASSERT_COMPARE( R, bytes, Z, bytes );
+
+ /* Neg( A ) => Correct result */
+ mbedtls_mpi_mod_raw_neg( R, A, &m );
+ ASSERT_COMPARE( R, bytes, X, bytes );
+
+ /* Neg( A ): alias A to R => Correct result */
+ mbedtls_mpi_mod_raw_neg( A, A, &m );
+ ASSERT_COMPARE( A, bytes, X, bytes );
+exit:
+ mbedtls_mpi_mod_modulus_free( &m );
+ mbedtls_free( N );
+ mbedtls_free( A );
+ mbedtls_free( X );
+ mbedtls_free( R );
+ mbedtls_free( Z );
+}
+/* END_CASE */
+
/* END MERGE SLOT 7 */
/* BEGIN MERGE SLOT 8 */