Merge pull request #6230 from tom-cosgrove-arm/issue-6223-core-add
Bignum: extract core_add from the prototype
diff --git a/library/bignum.c b/library/bignum.c
index 58cd2f7..d33f07c 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -867,8 +867,7 @@
int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t i, j;
- mbedtls_mpi_uint *o, *p, c, tmp;
+ size_t j;
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( A != NULL );
MPI_VALIDATE_RET( B != NULL );
@@ -882,7 +881,7 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
/*
- * X should always be positive as a result of unsigned additions.
+ * X must always be positive as a result of unsigned additions.
*/
X->s = 1;
@@ -892,27 +891,25 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
- o = B->p; p = X->p; c = 0;
+ /* j is the number of non-zero limbs of B. Add those to X. */
- /*
- * tmp is used because it might happen that p == o
- */
- for( i = 0; i < j; i++, o++, p++ )
- {
- tmp= *o;
- *p += c; c = ( *p < c );
- *p += tmp; c += ( *p < tmp );
- }
+ mbedtls_mpi_uint *p = X->p;
+
+ mbedtls_mpi_uint c = mbedtls_mpi_core_add( p, p, B->p, j );
+
+ p += j;
+
+ /* Now propagate any carry */
while( c != 0 )
{
- if( i >= X->n )
+ if( j >= X->n )
{
- MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
- p = X->p + i;
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j + 1 ) );
+ p = X->p + j;
}
- *p += c; c = ( *p < c ); i++; p++;
+ *p += c; c = ( *p < c ); j++; p++;
}
cleanup:
diff --git a/library/bignum_core.c b/library/bignum_core.c
index 963af5b..b401fa3 100644
--- a/library/bignum_core.c
+++ b/library/bignum_core.c
@@ -316,8 +316,6 @@
return( 0 );
}
-
-
void mbedtls_mpi_core_shift_r( mbedtls_mpi_uint *X, size_t limbs,
size_t count )
{
@@ -360,7 +358,24 @@
}
}
+mbedtls_mpi_uint mbedtls_mpi_core_add( mbedtls_mpi_uint *X,
+ const mbedtls_mpi_uint *A,
+ const mbedtls_mpi_uint *B,
+ size_t limbs )
+{
+ mbedtls_mpi_uint c = 0;
+ for( size_t i = 0; i < limbs; i++ )
+ {
+ mbedtls_mpi_uint t = c + A[i];
+ c = ( t < A[i] );
+ t += B[i];
+ c += ( t < B[i] );
+ X[i] = t;
+ }
+
+ return( c );
+}
mbedtls_mpi_uint mbedtls_mpi_core_add_if( mbedtls_mpi_uint *X,
const mbedtls_mpi_uint *A,
diff --git a/library/bignum_core.h b/library/bignum_core.h
index 503bc1d..9a5b89f 100644
--- a/library/bignum_core.h
+++ b/library/bignum_core.h
@@ -278,6 +278,28 @@
size_t count );
/**
+ * \brief Add two fixed-size large unsigned integers, returning the carry.
+ *
+ * Calculates `A + B` where `A` and `B` have the same size.
+ *
+ * This function operates modulo `2^(biL*limbs)` and returns the carry
+ * (1 if there was a wraparound, and 0 otherwise).
+ *
+ * \p X may be aliased to \p A or \p B.
+ *
+ * \param[out] X The result of the addition.
+ * \param[in] A Little-endian presentation of the left operand.
+ * \param[in] B Little-endian presentation of the right operand.
+ * \param limbs Number of limbs of \p X, \p A and \p B.
+ *
+ * \return 1 if `A + B >= 2^(biL*limbs)`, 0 otherwise.
+ */
+mbedtls_mpi_uint mbedtls_mpi_core_add( mbedtls_mpi_uint *X,
+ const mbedtls_mpi_uint *A,
+ const mbedtls_mpi_uint *B,
+ size_t limbs );
+
+/**
* \brief Conditional addition of two fixed-size large unsigned integers,
* returning the carry.
*
diff --git a/scripts/mbedtls_dev/bignum_core.py b/scripts/mbedtls_dev/bignum_core.py
index e46364b..0d238e7 100644
--- a/scripts/mbedtls_dev/bignum_core.py
+++ b/scripts/mbedtls_dev/bignum_core.py
@@ -144,12 +144,12 @@
yield cls(a_value, b_value, 32).create_test_case()
yield cls(a_value, b_value, 64).create_test_case()
-class BignumCoreAddIf(BignumCoreOperationArchSplit):
- """Test cases for bignum core add if."""
+class BignumCoreAddAndAddIf(BignumCoreOperationArchSplit):
+ """Test cases for bignum core add and add-if."""
count = 0
symbol = "+"
- test_function = "mpi_core_add_if"
- test_name = "mbedtls_mpi_core_add_if"
+ test_function = "mpi_core_add_and_add_if"
+ test_name = "mpi_core_add_and_add_if"
def result(self) -> List[str]:
result = self.int_a + self.int_b
diff --git a/tests/suites/test_suite_bignum_core.function b/tests/suites/test_suite_bignum_core.function
index 74ee27a..57c2f37 100644
--- a/tests/suites/test_suite_bignum_core.function
+++ b/tests/suites/test_suite_bignum_core.function
@@ -5,6 +5,154 @@
#include "constant_time_internal.h"
#include "test/constant_flow.h"
+/** Verifies mbedtls_mpi_core_add().
+ *
+ * \param[in] A Little-endian presentation of the left operand.
+ * \param[in] B Little-endian presentation of the right operand.
+ * \param limbs Number of limbs in each MPI (\p A, \p B, \p S and \p X).
+ * \param[in] S Little-endian presentation of the expected sum.
+ * \param carry Expected carry from the addition.
+ * \param[in,out] X Temporary storage to be used for results.
+ *
+ * \return 1 if mbedtls_mpi_core_add() passes this test, otherwise 0.
+ */
+static int mpi_core_verify_add( mbedtls_mpi_uint *A,
+ mbedtls_mpi_uint *B,
+ size_t limbs,
+ mbedtls_mpi_uint *S,
+ int carry,
+ mbedtls_mpi_uint *X )
+{
+ int ret = 0;
+
+ size_t bytes = limbs * sizeof( *A );
+
+ /* The test cases have A <= B to avoid repetition, so we test A + B then,
+ * if A != B, B + A. If A == B, we can test when A and B are aliased */
+
+ /* A + B */
+
+ /* A + B => correct result and carry */
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, A, B, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+
+ /* A + B; alias output and first operand => correct result and carry */
+ memcpy( X, A, bytes );
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, X, B, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+
+ /* A + B; alias output and second operand => correct result and carry */
+ memcpy( X, B, bytes );
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, A, X, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+
+ if ( memcmp( A, B, bytes ) == 0 )
+ {
+ /* A == B, so test where A and B are aliased */
+
+ /* A + A => correct result and carry */
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, A, A, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+
+ /* A + A, output aliased to both operands => correct result and carry */
+ memcpy( X, A, bytes );
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, X, X, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+ }
+ else
+ {
+ /* A != B, so test B + A */
+
+ /* B + A => correct result and carry */
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, B, A, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+
+ /* B + A; alias output and first operand => correct result and carry */
+ memcpy( X, B, bytes );
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, X, A, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+
+ /* B + A; alias output and second operand => correct result and carry */
+ memcpy( X, A, bytes );
+ TEST_EQUAL( carry, mbedtls_mpi_core_add( X, B, X, limbs ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+ }
+
+ ret = 1;
+
+exit:
+ return ret;
+}
+
+/** Verifies mbedtls_mpi_core_add_if().
+ *
+ * \param[in] A Little-endian presentation of the left operand.
+ * \param[in] B Little-endian presentation of the right operand.
+ * \param limbs Number of limbs in each MPI (\p A, \p B, \p S and \p X).
+ * \param[in] S Little-endian presentation of the expected sum.
+ * \param carry Expected carry from the addition.
+ * \param[in,out] X Temporary storage to be used for results.
+ *
+ * \return 1 if mbedtls_mpi_core_add_if() passes this test, otherwise 0.
+ */
+static int mpi_core_verify_add_if( mbedtls_mpi_uint *A,
+ mbedtls_mpi_uint *B,
+ size_t limbs,
+ mbedtls_mpi_uint *S,
+ int carry,
+ mbedtls_mpi_uint *X )
+{
+ int ret = 0;
+
+ size_t bytes = limbs * sizeof( *A );
+
+ /* The test cases have A <= B to avoid repetition, so we test A + B then,
+ * if A != B, B + A. If A == B, we can test when A and B are aliased */
+
+ /* A + B */
+
+ /* cond = 0 => X unchanged, no carry */
+ memcpy( X, A, bytes );
+ TEST_EQUAL( 0, mbedtls_mpi_core_add_if( X, B, limbs, 0 ) );
+ ASSERT_COMPARE( X, bytes, A, bytes );
+
+ /* cond = 1 => correct result and carry */
+ TEST_EQUAL( carry, mbedtls_mpi_core_add_if( X, B, limbs, 1 ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+
+ if ( memcmp( A, B, bytes ) == 0 )
+ {
+ /* A == B, so test where A and B are aliased */
+
+ /* cond = 0 => X unchanged, no carry */
+ memcpy( X, B, bytes );
+ TEST_EQUAL( 0, mbedtls_mpi_core_add_if( X, X, limbs, 0 ) );
+ ASSERT_COMPARE( X, bytes, B, bytes );
+
+ /* cond = 1 => correct result and carry */
+ TEST_EQUAL( carry, mbedtls_mpi_core_add_if( X, X, limbs, 1 ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+ }
+ else
+ {
+ /* A != B, so test B + A */
+
+ /* cond = 0 => d unchanged, no carry */
+ memcpy( X, B, bytes );
+ TEST_EQUAL( 0, mbedtls_mpi_core_add_if( X, A, limbs, 0 ) );
+ ASSERT_COMPARE( X, bytes, B, bytes );
+
+ /* cond = 1 => correct result and carry */
+ TEST_EQUAL( carry, mbedtls_mpi_core_add_if( X, A, limbs, 1 ) );
+ ASSERT_COMPARE( X, bytes, S, bytes );
+ }
+
+ ret = 1;
+
+exit:
+ return ret;
+}
+
/* END_HEADER */
/* BEGIN_DEPENDENCIES
@@ -359,70 +507,28 @@
/* END_CASE */
/* BEGIN_CASE */
-void mpi_core_add_if( char * input_A, char * input_B,
- char * input_S, int carry )
+void mpi_core_add_and_add_if( char * input_A, char * input_B,
+ char * input_S, int carry )
{
mbedtls_mpi_uint *A = NULL; /* first value to add */
- size_t A_limbs;
mbedtls_mpi_uint *B = NULL; /* second value to add */
- size_t B_limbs;
mbedtls_mpi_uint *S = NULL; /* expected result */
- size_t S_limbs;
mbedtls_mpi_uint *X = NULL; /* destination - the in/out first operand */
- size_t X_limbs;
+ size_t A_limbs, B_limbs, S_limbs;
TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &A, &A_limbs, input_A ) );
TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &B, &B_limbs, input_B ) );
TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &S, &S_limbs, input_S ) );
- X_limbs = S_limbs;
- ASSERT_ALLOC( X, X_limbs );
- /* add_if expects all operands to be the same length */
+ /* add and add_if expect all operands to be the same length */
TEST_EQUAL( A_limbs, B_limbs );
TEST_EQUAL( A_limbs, S_limbs );
+
size_t limbs = A_limbs;
- size_t bytes = limbs * sizeof( *A );
+ ASSERT_ALLOC( X, limbs );
- /* The test cases have A <= B to avoid repetition, so we test A + B then,
- * if A != B, B + A. If A == B, we can test when A and B are aliased */
-
- /* A + B */
-
- /* cond = 0 => X unchanged, no carry */
- memcpy( X, A, bytes );
- TEST_EQUAL( 0, mbedtls_mpi_core_add_if( X, B, limbs, 0 ) );
- ASSERT_COMPARE( X, bytes, A, bytes );
-
- /* cond = 1 => correct result and carry */
- TEST_EQUAL( carry, mbedtls_mpi_core_add_if( X, B, limbs, 1 ) );
- ASSERT_COMPARE( X, bytes, S, bytes );
-
- if ( memcmp( A, B, bytes ) == 0 )
- {
- /* A == B, so test where A and B are aliased */
-
- /* cond = 0 => X unchanged, no carry */
- memcpy( X, B, bytes );
- TEST_EQUAL( 0, mbedtls_mpi_core_add_if( X, X, limbs, 0 ) );
- ASSERT_COMPARE( X, bytes, B, bytes );
-
- /* cond = 1 => correct result and carry */
- TEST_EQUAL( carry, mbedtls_mpi_core_add_if( X, X, limbs, 1 ) );
- ASSERT_COMPARE( X, bytes, S, bytes );
- }
- else
- {
- /* A != B, so test B + A */
-
- /* cond = 0 => d unchanged, no carry */
- memcpy( X, B, bytes );
- TEST_EQUAL( 0, mbedtls_mpi_core_add_if( X, A, limbs, 0 ) );
- ASSERT_COMPARE( X, bytes, B, bytes );
-
- /* cond = 1 => correct result and carry */
- TEST_EQUAL( carry, mbedtls_mpi_core_add_if( X, A, limbs, 1 ) );
- ASSERT_COMPARE( X, bytes, S, bytes );
- }
+ TEST_ASSERT( mpi_core_verify_add( A, B, limbs, S, carry, X ) );
+ TEST_ASSERT( mpi_core_verify_add_if( A, B, limbs, S, carry, X ) );
exit:
mbedtls_free( A );