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/include/mbedtls/bignum.h b/include/mbedtls/bignum.h
index cd0cba8..0ee32dd 100644
--- a/include/mbedtls/bignum.h
+++ b/include/mbedtls/bignum.h
@@ -726,7 +726,8 @@
int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N );
/**
- * \brief Miller-Rabin primality test
+ * \brief Miller-Rabin primality test with error probability of
+ * 2<sup>-80</sup>
*
* \param X MPI to check
* \param f_rng RNG function
@@ -747,7 +748,8 @@
* mbedtls_mpi_gen_prime().
*/
typedef enum {
- MBEDTLS_MPI_GEN_PRIME_FLAG_DH = 0x0001, /**< (X-1)/2 is prime too */
+ MBEDTLS_MPI_GEN_PRIME_FLAG_DH = 0x0001, /**< (X-1)/2 is prime too */
+ MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR = 0x0002, /**< lower error rate from 2<sup>-80</sup> to 2<sup>-128</sup> */
} mbedtls_mpi_gen_prime_flag_t;
/**