Bignum: Add tests for primality testing
Primality tests have to deal with different distribution when generating
primes and when validating primes.
These new tests are testing if mbedtls_mpi_is_prime() is working
properly in the latter setting.
The new tests involve pseudoprimes with maximum number of
non-witnesses. The non-witnesses were generated by printing them
from mpi_miller_rabin(). The pseudoprimes were generated by the
following function:
void gen_monier( mbedtls_mpi* res, int nbits )
{
mbedtls_mpi p_2x_plus_1, p_4x_plus_1, x, tmp;
mbedtls_mpi_init( &p_2x_plus_1 );
mbedtls_mpi_init( &p_4x_plus_1 );
mbedtls_mpi_init( &x ); mbedtls_mpi_init( &tmp );
do
{
mbedtls_mpi_gen_prime( &p_2x_plus_1, nbits >> 1, 0,
rnd_std_rand, NULL );
mbedtls_mpi_sub_int( &x, &p_2x_plus_1, 1 );
mbedtls_mpi_div_int( &x, &tmp, &x, 2 );
if( mbedtls_mpi_get_bit( &x, 0 ) == 0 )
continue;
mbedtls_mpi_mul_int( &p_4x_plus_1, &x, 4 );
mbedtls_mpi_add_int( &p_4x_plus_1, &p_4x_plus_1, 1 );
if( mbedtls_mpi_is_prime( &p_4x_plus_1, rnd_std_rand,
NULL ) == 0 )
break;
} while( 1 );
mbedtls_mpi_mul_mpi( res, &p_2x_plus_1, &p_4x_plus_1 );
}
diff --git a/tests/suites/test_suite_mpi.function b/tests/suites/test_suite_mpi.function
index e598f8d..c6548b1 100644
--- a/tests/suites/test_suite_mpi.function
+++ b/tests/suites/test_suite_mpi.function
@@ -1,5 +1,48 @@
/* BEGIN_HEADER */
#include "mbedtls/bignum.h"
+
+typedef struct mbedtls_test_mpi_random
+{
+ data_t *data;
+ size_t pos;
+ size_t chunk_len;
+} mbedtls_test_mpi_random;
+
+/*
+ * This function is called by the Miller-Rabin primality test each time it
+ * chooses a random witness. The witnesses (or non-witnesses as provided by the
+ * test) are stored in the data member of the state structure. Each number is in
+ * the format that mbedtls_mpi_read_string understands and is chunk_len long.
+ */
+int mbedtls_test_mpi_miller_rabin_determinizer( void* state,
+ unsigned char* buf,
+ size_t len )
+{
+ mbedtls_test_mpi_random *random = (mbedtls_test_mpi_random*) state;
+
+ if( random == NULL || random->data->x == NULL || buf == NULL )
+ return( -1 );
+
+ if( random->pos + random->chunk_len > random->data->len
+ || random->chunk_len > len )
+ {
+ return( -1 );
+ }
+
+ memset( buf, 0, len );
+
+ /* The witness is written to the end of the buffer, since the buffer is
+ * used as big endian, unsigned binary data in mbedtls_mpi_read_binary.
+ * Writing the witness to the start of the buffer would result in the
+ * buffer being 'witness 000...000', which would be treated as
+ * witness * 2^n for some n. */
+ memcpy( buf + len - random->chunk_len, &random->data->x[random->pos],
+ random->chunk_len );
+
+ random->pos += random->chunk_len;
+
+ return( 0 );
+}
/* END_HEADER */
/* BEGIN_DEPENDENCIES
@@ -809,6 +852,29 @@
/* END_CASE */
/* BEGIN_CASE depends_on:MBEDTLS_GENPRIME */
+void mbedtls_mpi_is_prime_det( data_t * input_X, data_t * witnesses,
+ int chunk_len, int div_result )
+{
+ mbedtls_mpi X;
+ int res;
+ mbedtls_test_mpi_random rand;
+
+ mbedtls_mpi_init( &X );
+ rand.data = witnesses;
+ rand.pos = 0;
+ rand.chunk_len = chunk_len;
+
+ TEST_ASSERT( mbedtls_mpi_read_binary( &X, input_X->x, input_X->len ) == 0 );
+ res = mbedtls_mpi_is_prime( &X, mbedtls_test_mpi_miller_rabin_determinizer,
+ &rand );
+ TEST_ASSERT( res == div_result );
+
+exit:
+ mbedtls_mpi_free( &X );
+}
+/* END_CASE */
+
+/* BEGIN_CASE depends_on:MBEDTLS_GENPRIME */
void mbedtls_mpi_gen_prime( int bits, int flags, int ref_ret )
{
mbedtls_mpi X;