New constant-flow function mbedtls_mpi_core_uint_le_mpi
Compare a single-limb MPI with a multi-limb MPI. This is rather ad hoc, but
will be useful for mbedtls_mpi_core_random.
Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
diff --git a/library/bignum_core.c b/library/bignum_core.c
index 6635351..08158fa 100644
--- a/library/bignum_core.c
+++ b/library/bignum_core.c
@@ -154,6 +154,27 @@
}
}
+/* Whether min <= A, in constant time.
+ * A_limbs must be at least 1. */
+unsigned mbedtls_mpi_core_uint_le_mpi( mbedtls_mpi_uint min,
+ const mbedtls_mpi_uint *A,
+ size_t A_limbs )
+{
+ /* min <= least significant limb? */
+ unsigned min_le_lsl = 1 ^ mbedtls_ct_mpi_uint_lt( A[0], min );
+
+ /* most significant limbs (excluding 1) are all zero? */
+ mbedtls_mpi_uint msll_mask = 0;
+ for( size_t i = 1; i < A_limbs; i++ )
+ msll_mask |= A[i];
+ /* The most significant limbs of A are not all zero iff msll_mask != 0. */
+ unsigned msll_nonzero = mbedtls_ct_mpi_uint_mask( msll_mask ) & 1;
+
+ /* min <= A iff the lowest limb of A is >= min or the other limbs
+ * are not all zero. */
+ return( min_le_lsl | msll_nonzero );
+}
+
void mbedtls_mpi_core_cond_assign( mbedtls_mpi_uint *X,
const mbedtls_mpi_uint *A,
size_t limbs,
diff --git a/library/bignum_core.h b/library/bignum_core.h
index 24559c6..120fa18 100644
--- a/library/bignum_core.h
+++ b/library/bignum_core.h
@@ -129,6 +129,22 @@
void mbedtls_mpi_core_bigendian_to_host( mbedtls_mpi_uint *A,
size_t A_limbs );
+/** \brief Compare a machine integer with an MPI.
+ *
+ * This function operates in constant time with respect
+ * to the values of \p min and \p A.
+ *
+ * \param min A machine integer.
+ * \param[in] A An MPI.
+ * \param A_limbs The number of limbs of \p A.
+ * This must be at least 1.
+ *
+ * \return 1 if \p min is less than or equal to \p A, otherwise 0.
+ */
+unsigned mbedtls_mpi_core_uint_le_mpi( mbedtls_mpi_uint min,
+ const mbedtls_mpi_uint *A,
+ size_t A_limbs );
+
/**
* \brief Perform a safe conditional copy of an MPI which doesn't reveal
* whether assignment was done or not.
diff --git a/tests/suites/test_suite_bignum_core.function b/tests/suites/test_suite_bignum_core.function
index 078239f..d842c49 100644
--- a/tests/suites/test_suite_bignum_core.function
+++ b/tests/suites/test_suite_bignum_core.function
@@ -345,6 +345,56 @@
/* END_CASE */
/* BEGIN_CASE */
+void mpi_core_uint_le_mpi( char *input_A )
+{
+ mbedtls_mpi_uint *A = NULL;
+ size_t A_limbs = 0;
+
+ TEST_EQUAL( mbedtls_test_read_mpi_core( &A, &A_limbs, input_A ), 0 );
+
+ int is_large = 0; /* nonzero limbs beyond the lowest-order one? */
+ for( size_t i = 1; i < A_limbs; i++ )
+ {
+ if( A[i] != 0 )
+ {
+ is_large = 1;
+ break;
+ }
+ }
+
+ TEST_CF_SECRET( A, A_limbs * sizeof( *A ) );
+
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( 0, A, A_limbs ), 1 );
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( A[0], A, A_limbs ), 1 );
+
+ if( is_large )
+ {
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( A[0] + 1,
+ A, A_limbs ), 1 );
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( (mbedtls_mpi_uint)( -1 ) >> 1,
+ A, A_limbs ), 1 );
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( (mbedtls_mpi_uint)( -1 ),
+ A, A_limbs ), 1 );
+ }
+ else
+ {
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( A[0] + 1,
+ A, A_limbs ),
+ A[0] + 1 <= A[0] );
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( (mbedtls_mpi_uint)( -1 ) >> 1,
+ A, A_limbs ),
+ (mbedtls_mpi_uint)( -1 ) >> 1 <= A[0] );
+ TEST_EQUAL( mbedtls_mpi_core_uint_le_mpi( (mbedtls_mpi_uint)( -1 ),
+ A, A_limbs ),
+ (mbedtls_mpi_uint)( -1 ) <= A[0] );
+ }
+
+exit:
+ mbedtls_free( A );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
void mpi_core_cond_assign( char * input_X,
char * input_Y,
int input_bytes )
diff --git a/tests/suites/test_suite_bignum_core.misc.data b/tests/suites/test_suite_bignum_core.misc.data
index 62480e4..81a767a 100644
--- a/tests/suites/test_suite_bignum_core.misc.data
+++ b/tests/suites/test_suite_bignum_core.misc.data
@@ -242,6 +242,69 @@
mbedtls_mpi_core_lt_ct: x>y (alternating limbs)
mpi_core_lt_ct:"FF1111111111111111":"11FFFFFFFFFFFFFFFF":0
+Test mbedtls_mpi_core_uint_le_mpi: 0 (1 limb)
+mpi_core_uint_le_mpi:"00"
+
+Test mbedtls_mpi_core_uint_le_mpi: 0 (>=2 limbs)
+mpi_core_uint_le_mpi:"000000000000000000"
+
+Test mbedtls_mpi_core_uint_le_mpi: 1 (1 limb)
+mpi_core_uint_le_mpi:"01"
+
+Test mbedtls_mpi_core_uint_le_mpi: 1 (>=2 limbs)
+mpi_core_uint_le_mpi:"000000000000000001"
+
+Test mbedtls_mpi_core_uint_le_mpi: 42 (1 limb)
+mpi_core_uint_le_mpi:"2a"
+
+Test mbedtls_mpi_core_uint_le_mpi: 42 (>=2 limbs)
+mpi_core_uint_le_mpi:"000000000000000042"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^31-1
+mpi_core_uint_le_mpi:"7fffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^31-1 with leading zero limb
+mpi_core_uint_le_mpi:"00000000007fffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^32-1
+mpi_core_uint_le_mpi:"ffffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^32-1 with leading zero limb
+mpi_core_uint_le_mpi:"0000000000ffffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^32
+mpi_core_uint_le_mpi:"10000000"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^32 with leading zero limb
+mpi_core_uint_le_mpi:"000000000010000000"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^32+1
+mpi_core_uint_le_mpi:"10000001"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^32+1 with leading zero limb
+mpi_core_uint_le_mpi:"000000000010000001"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^63-1
+mpi_core_uint_le_mpi:"7fffffffffffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^63-1 with leading zero limb
+mpi_core_uint_le_mpi:"007fffffffffffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^64-1
+mpi_core_uint_le_mpi:"ffffffffffffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^64-1 with leading zero limb
+mpi_core_uint_le_mpi:"00ffffffffffffffff"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^64
+mpi_core_uint_le_mpi:"010000000000000000"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^64+1
+mpi_core_uint_le_mpi:"010000000000000001"
+
+Test mbedtls_mpi_core_uint_le_mpi: 2^64+2
+mpi_core_uint_le_mpi:"010000000000000002"
+
mbedtls_mpi_core_cond_assign: 1 limb
mpi_core_cond_assign:"FFFFFFFF":"11111111":4