Merged Prime generation improvements
diff --git a/include/polarssl/bignum.h b/include/polarssl/bignum.h
index 9bed027..b63a242 100644
--- a/include/polarssl/bignum.h
+++ b/include/polarssl/bignum.h
@@ -58,7 +58,7 @@
#define POLARSSL_ERR_MPI_NOT_ACCEPTABLE -0x000E /**< The input arguments are not acceptable. */
#define POLARSSL_ERR_MPI_MALLOC_FAILED -0x0010 /**< Memory allocation failed. */
-#define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
+#define MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
/*
* Maximum size MPIs are allowed to grow to in number of limbs.
diff --git a/library/bignum.c b/library/bignum.c
index 2a97a59..4de2e9a 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1797,40 +1797,27 @@
};
/*
- * Miller-Rabin primality test (HAC 4.24)
+ * Small divisors test (X must be positive)
+ *
+ * Return values:
+ * 0: no small factor (possible prime, more tests needed)
+ * 1: certain prime
+ * POLARSSL_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
+ * other negative: error
*/
-int mpi_is_prime( mpi *X,
- int (*f_rng)(void *, unsigned char *, size_t),
- void *p_rng )
+static int mpi_check_small_factors( const mpi *X )
{
- int ret, xs;
- size_t i, j, n, s;
- mpi W, R, T, A, RR;
+ int ret = 0;
+ size_t i;
+ t_uint r;
- if( mpi_cmp_int( X, 0 ) == 0 ||
- mpi_cmp_int( X, 1 ) == 0 )
- return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
-
- if( mpi_cmp_int( X, 2 ) == 0 )
- return( 0 );
-
- mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
- mpi_init( &RR );
-
- xs = X->s; X->s = 1;
-
- /*
- * test trivial factors first
- */
if( ( X->p[0] & 1 ) == 0 )
return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
for( i = 0; small_prime[i] > 0; i++ )
{
- t_uint r;
-
if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
- return( 0 );
+ return( 1 );
MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
@@ -1838,6 +1825,24 @@
return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
}
+cleanup:
+ return( ret );
+}
+
+/*
+ * Miller-Rabin pseudo-primality test (HAC 4.24)
+ */
+static int mpi_miller_rabin( const mpi *X,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ int ret;
+ size_t i, j, n, s;
+ mpi W, R, T, A, RR;
+
+ mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
+ mpi_init( &RR );
+
/*
* W = |X| - 1
* R = W >> lsb( W )
@@ -1905,9 +1910,6 @@
}
cleanup:
-
- X->s = xs;
-
mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
mpi_free( &RR );
@@ -1915,6 +1917,34 @@
}
/*
+ * Pseudo-primality test: small factors, then Miller-Rabin
+ */
+int mpi_is_prime( mpi *X,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ int ret;
+ const mpi XX = { 1, X->n, X->p }; /* Abs(X) */
+
+ if( mpi_cmp_int( &XX, 0 ) == 0 ||
+ mpi_cmp_int( &XX, 1 ) == 0 )
+ return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
+
+ if( mpi_cmp_int( &XX, 2 ) == 0 )
+ return( 0 );
+
+ if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
+ {
+ if( ret == 1 )
+ return( 0 );
+
+ return( ret );
+ }
+
+ return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
+}
+
+/*
* Prime number generation
*/
int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
@@ -1923,6 +1953,7 @@
{
int ret;
size_t k, n;
+ t_uint r;
mpi Y;
if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS )
@@ -1952,26 +1983,45 @@
}
else
{
- MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
+ /*
+ * An necessary condition for Y and X = 2Y + 1 to be prime
+ * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
+ * Make sure it is satisfied, while keeping X = 3 mod 4
+ */
+ MPI_CHK( mpi_mod_int( &r, X, 3 ) );
+ if( r == 0 )
+ MPI_CHK( mpi_add_int( X, X, 8 ) );
+ else if( r == 1 )
+ MPI_CHK( mpi_add_int( X, X, 4 ) );
+
+ /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
+ MPI_CHK( mpi_copy( &Y, X ) );
MPI_CHK( mpi_shift_r( &Y, 1 ) );
while( 1 )
{
- if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
+ /*
+ * First, check small factors for X and Y
+ * before doing Miller-Rabin on any of them
+ */
+ if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
+ ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
+ ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
+ ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
{
- if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
- break;
-
- if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
- goto cleanup;
+ break;
}
if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
goto cleanup;
- MPI_CHK( mpi_add_int( &Y, X, 1 ) );
- MPI_CHK( mpi_add_int( X, X, 2 ) );
- MPI_CHK( mpi_shift_r( &Y, 1 ) );
+ /*
+ * Next candidates. We want to preserve Y = (X-1) / 2 and
+ * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
+ * so up Y by 6 and X by 12.
+ */
+ MPI_CHK( mpi_add_int( X, X, 12 ) );
+ MPI_CHK( mpi_add_int( &Y, &Y, 6 ) );
}
}
diff --git a/programs/pkey/dh_genprime.c b/programs/pkey/dh_genprime.c
index 2089fb6..f51465a 100644
--- a/programs/pkey/dh_genprime.c
+++ b/programs/pkey/dh_genprime.c
@@ -74,6 +74,8 @@
printf( " predefined DHM parameters from dhm.h instead!\n\n" );
printf( "============================================================\n\n" );
+ printf( " ! Generating large primes may take minutes!\n" );
+
printf( "\n . Seeding the random number generator..." );
fflush( stdout );
diff --git a/tests/suites/test_suite_mpi.data b/tests/suites/test_suite_mpi.data
index 924f364..859a38e 100644
--- a/tests/suites/test_suite_mpi.data
+++ b/tests/suites/test_suite_mpi.data
@@ -504,11 +504,19 @@
depends_on:POLARSSL_GENPRIME
mpi_is_prime:10:"47":0
-Test mpi_is_prime #1
+Test mpi_is_prime #1a
+depends_on:POLARSSL_GENPRIME
+mpi_is_prime:10:"83726728883146151979668243326097049289208482987685965276439157162337476477581":POLARSSL_ERR_MPI_NOT_ACCEPTABLE
+
+Test mpi_is_prime #1b
+depends_on:POLARSSL_GENPRIME
+mpi_is_prime:10:"81248637410584921454869308488899267096530643632730258201256092582281263244641":POLARSSL_ERR_MPI_NOT_ACCEPTABLE
+
+Test mpi_is_prime #2a
depends_on:POLARSSL_GENPRIME
mpi_is_prime:10:"827131507221654563937832686696200995595835694437983658840870036586124168186967796809117749047430768825822857042432722828096779098498192459819306321073968735177531164565305635281198148032612029767584644305912099":0
-Test mpi_is_prime #2
+Test mpi_is_prime #2b
depends_on:POLARSSL_GENPRIME
mpi_is_prime:10:"827131507221654563937832686696200995595835694437983658840870036586124168186967796809117749047430768825822857042432722828096779098498192459819306321073968735177531164565305635281198148032612029767584644305912001":POLARSSL_ERR_MPI_NOT_ACCEPTABLE