Add new, constant time mpi comparison
diff --git a/include/mbedtls/bignum.h b/include/mbedtls/bignum.h
index 1c86072..b57f2a1 100644
--- a/include/mbedtls/bignum.h
+++ b/include/mbedtls/bignum.h
@@ -560,6 +560,25 @@
int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y );
/**
+ * \brief Compare two MPIs in constant time.
+ *
+ * \param X The left-hand MPI. This must point to an initialized MPI
+ * with the same allocated length as Y.
+ * \param Y The right-hand MPI. This must point to an initialized MPI
+ * with the same allocated length as X.
+ * \param ret The result of the comparison:
+ * \c 1 if \p X is greater than \p Y.
+ * \c -1 if \p X is lesser than \p Y.
+ * \c 0 if \p X is equal to \p Y.
+ *
+ * \return 0 on success.
+ * \return MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the allocated length of
+ * the two input MPIs is not the same.
+ */
+int mbedtls_mpi_cmp_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
+ int *ret );
+
+/**
* \brief Compare an MPI with an integer.
*
* \param X The left-hand MPI. This must point to an initialized MPI.
diff --git a/library/bignum.c b/library/bignum.c
index 7a700bc..c54a1fe 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1071,6 +1071,96 @@
return( 0 );
}
+static int ct_lt_mpi_uint( const mbedtls_mpi_uint x, const mbedtls_mpi_uint y )
+{
+ mbedtls_mpi_uint ret;
+ mbedtls_mpi_uint cond;
+
+ /*
+ * Check if the most significant bits (MSB) of the operands are different.
+ */
+ cond = ( x ^ y );
+ /*
+ * If the MSB are the same then the difference x-y will be negative (and
+ * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
+ */
+ ret = ( x - y ) & ~cond;
+ /*
+ * If the MSB are different, then the operand with the MSB of 1 is the
+ * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
+ * the MSB of y is 0.)
+ */
+ ret |= y & cond;
+
+
+ ret = ret >> ( sizeof( mbedtls_mpi_uint ) * 8 - 1 );
+
+ return ret;
+}
+
+/*
+ * Compare signed values in constant time
+ */
+int mbedtls_mpi_cmp_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
+ int *ret )
+{
+ size_t i;
+ unsigned int cond, done;
+
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( Y != NULL );
+ MPI_VALIDATE_RET( ret != NULL );
+
+ if( X->n != Y->n )
+ return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+
+ /*
+ * if( X->s > 0 && Y->s < 0 )
+ * {
+ * *ret = 1;
+ * done = 1;
+ * }
+ * else if( Y->s > 0 && X->s < 0 )
+ * {
+ * *ret = -1;
+ * done = 1;
+ * }
+ */
+ unsigned int sign_X = X->s;
+ unsigned int sign_Y = Y->s;
+ cond = ( ( sign_X ^ sign_Y ) >> ( sizeof( unsigned int ) * 8 - 1 ) );
+ *ret = cond * X->s;
+ done = cond;
+
+ for( i = X->n; i > 0; i-- )
+ {
+ /*
+ * if( ( X->p[i - 1] > Y->p[i - 1] ) && !done )
+ * {
+ * done = 1;
+ * *ret = X->s;
+ * }
+ */
+ cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] );
+ *ret |= ( cond * ( 1 - done ) ) * X->s;
+ done |= cond * ( 1 - done );
+
+ /*
+ * if( ( X->p[i - 1] < Y->p[i - 1] ) && !done )
+ * {
+ * done = 1;
+ * *ret = -X->s;
+ * }
+ */
+ cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] );
+ *ret |= ( cond * ( 1 - done ) ) * -X->s;
+ done |= cond * ( 1 - done );
+
+ }
+
+ return( 0 );
+}
+
/*
* Compare signed values
*/