Bignum: Improve primality test for FIPS primes
The FIPS 186-4 RSA key generation prescribes lower failure probability
in primality testing and this makes key generation slower. We enable the
caller to decide between compliance/security and performance.
This python script calculates the base two logarithm of the formulas in
HAC Fact 4.48 and was used to determine the breakpoints and number of
rounds:
def mrpkt_log_2(k, t):
if t <= k/9.0:
return 3*math.log(k,2)/2+t-math.log(t,2)/2+4-2*math.sqrt(t*k)
elif t <= k/4.0:
c1 = math.log(7.0*k/20,2)-5*t
c2 = math.log(1/7.0,2)+15*math.log(k,2)/4.0-k/2.0-2*t
c3 = math.log(12*k,2)-k/4.0-3*t
return max(c1, c2, c3)
else:
return math.log(1/7.0)+15*math.log(k,2)/4.0-k/2.0-2*t
diff --git a/library/bignum.c b/library/bignum.c
index 51aa0b4..c9919fb 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -2056,7 +2056,7 @@
/*
* Miller-Rabin pseudo-primality test (HAC 4.24)
*/
-static int mpi_miller_rabin( const mbedtls_mpi *X,
+static int mpi_miller_rabin( const mbedtls_mpi *X, int flags,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
@@ -2077,12 +2077,27 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
i = mbedtls_mpi_bitlen( X );
- /*
- * HAC, table 4.4
- */
- n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
- ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
- ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
+
+ if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
+ {
+ /*
+ * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
+ */
+ n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
+ ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
+ ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
+ }
+ else
+ {
+ /*
+ * 2^-100 error probability, number of rounds computed based on HAC,
+ * fact 4.48
+ */
+ n = ( ( i >= 1450 ) ? 4 : ( i >= 1150 ) ? 5 :
+ ( i >= 1000 ) ? 6 : ( i >= 850 ) ? 7 :
+ ( i >= 750 ) ? 8 : ( i >= 500 ) ? 13 :
+ ( i >= 250 ) ? 28 : ( i >= 150 ) ? 40 : 51 );
+ }
for( i = 0; i < n; i++ )
{
@@ -2160,7 +2175,7 @@
/*
* Pseudo-primality test: small factors, then Miller-Rabin
*/
-int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
+int mpi_is_prime_internal( const mbedtls_mpi *X, int flags,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
@@ -2186,15 +2201,25 @@
return( ret );
}
- return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
+ return( mpi_miller_rabin( &XX, flags, f_rng, p_rng ) );
+}
+
+/*
+ * Pseudo-primality test, error probability 2^-80
+ */
+int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ return mpi_is_prime_internal( X, 0, f_rng, p_rng );
}
/*
* Prime number generation
*
- * If flags 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.
+ * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
+ * be either 1024 bits or 1536 bits long, and flags must contain
+ * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
*/
int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
int (*f_rng)(void *, unsigned char *, size_t),
@@ -2231,7 +2256,7 @@
if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
{
- ret = mbedtls_mpi_is_prime( X, f_rng, p_rng );
+ ret = mpi_is_prime_internal( X, flags, f_rng, p_rng );
if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
goto cleanup;
@@ -2264,8 +2289,10 @@
*/
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 )
+ ( ret = mpi_miller_rabin( X, flags, f_rng, p_rng ) )
+ == 0 &&
+ ( ret = mpi_miller_rabin( &Y, flags, f_rng, p_rng ) )
+ == 0 )
goto cleanup;
if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )