Generate primes according to FIPS 186-4
The specification requires that numbers are the raw entropy (except for odd/
even) and at least 2^(nbits-0.5). If not, new random bits need to be used for
the next number. Similarly, if the number is not prime new random bits need to
be used.
diff --git a/library/bignum.c b/library/bignum.c
index 47bf1ef..f58af78 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -2194,12 +2194,23 @@
/*
* Prime number generation
+ *
+ * If dh_flag is 0 and nbits is at least 1024, then the procedure
+ * follows the RSA probably-prime generation method of FIPS 186-4.
+ * NB. FIPS 186-4 only allows the specific bit lengths of 1024 and 1536.
*/
int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
- int ret;
+#ifdef MBEDTLS_HAVE_INT64
+// ceil(2^63.5)
+#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
+#else
+// ceil(2^31.5)
+#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
+#endif
+ int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
size_t k, n;
mbedtls_mpi_uint r;
mbedtls_mpi Y;
@@ -2211,69 +2222,66 @@
n = BITS_TO_LIMBS( nbits );
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
-
- k = mbedtls_mpi_bitlen( X );
- if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits + 1 ) );
-
- mbedtls_mpi_set_bit( X, nbits-1, 1 );
-
- X->p[0] |= 1;
-
- if( dh_flag == 0 )
+ while( 1 )
{
- while( ( ret = mbedtls_mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
+ MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
+ /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
+ if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
+
+ k = n * biL;
+ if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
+ X->p[0] |= 1;
+
+ if( dh_flag == 0 )
{
+ ret = mbedtls_mpi_is_prime( X, f_rng, p_rng );
+
if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
goto cleanup;
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 2 ) );
}
- }
- else
- {
- /*
- * 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
- */
-
- X->p[0] |= 2;
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
- if( r == 0 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
- else if( r == 1 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
-
- /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
- MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
-
- while( 1 )
+ else
{
/*
- * First, check small factors for X and Y
- * before doing Miller-Rabin on any of them
+ * 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
*/
- 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 )
+
+ X->p[0] |= 2;
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
+ if( r == 0 )
+ MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
+ else if( r == 1 )
+ MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
+
+ /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
+
+ while( 1 )
{
- break;
+ /*
+ * 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 )
+ goto cleanup;
+
+ if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
+ goto cleanup;
+
+ /*
+ * 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.
+ */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
}
-
- if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
- goto cleanup;
-
- /*
- * 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.
- */
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
}
}