Generate RSA keys according to FIPS 186-4
The specification requires that P and Q are not too close. The specification
also requires that you generate a P and stick with it, generating new Qs until
you have found a pair that works. In practice, it turns out that sometimes a
particular P results in it being very unlikely a Q can be found matching all
the constraints. So we keep the original behavior where a new P and Q are
generated every round.
diff --git a/library/rsa.c b/library/rsa.c
index 2f72d40..729e1f7 100644
--- a/library/rsa.c
+++ b/library/rsa.c
@@ -495,6 +495,9 @@
/*
* Generate an RSA keypair
+ *
+ * This generation method follows the RSA key pair generation procedure of
+ * FIPS 186-4 if 2^16 < exponent < 2^256 and nbits = 2048 or nbits = 3072.
*/
int mbedtls_rsa_gen_key( mbedtls_rsa_context *ctx,
int (*f_rng)(void *, unsigned char *, size_t),
@@ -516,8 +519,9 @@
/*
* find primes P and Q with Q < P so that:
- * 1. GCD( E, (P-1)*(Q-1) ) == 1
- * 2. E^-1 mod LCM(P-1, Q-1) > 2^( nbits / 2 )
+ * 1. |P-Q| > 2^( nbits / 2 - 100 )
+ * 2. GCD( E, (P-1)*(Q-1) ) == 1
+ * 3. E^-1 mod LCM(P-1, Q-1) > 2^( nbits / 2 )
*/
MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &ctx->E, exponent ) );
@@ -529,14 +533,13 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_gen_prime( &ctx->Q, nbits >> 1, 0,
f_rng, p_rng ) );
- if( mbedtls_mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 )
+ /* make sure the difference between p and q is not too small (FIPS 186-4 §B.3.3 step 5.4) */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &H, &ctx->P, &ctx->Q ) );
+ if( mbedtls_mpi_bitlen( &H ) <= ( ( nbits >= 200 ) ? ( ( nbits >> 1 ) - 99 ) : 0 ) )
continue;
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
- if( mbedtls_mpi_bitlen( &ctx->N ) != nbits )
- continue;
-
- if( mbedtls_mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 )
+ /* not required by any standards, but some users rely on the fact that P > Q */
+ if( H.s < 0 )
mbedtls_mpi_swap( &ctx->P, &ctx->Q );
/* Temporarily replace P,Q by P-1, Q-1 */
@@ -544,12 +547,12 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &ctx->Q, &ctx->Q, 1 ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &H, &ctx->P, &ctx->Q ) );
- /* check GCD( E, (P-1)*(Q-1) ) == 1 */
+ /* check GCD( E, (P-1)*(Q-1) ) == 1 (FIPS 186-4 §B.3.1 criterion 2(a)) */
MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, &ctx->E, &H ) );
if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
continue;
- /* compute smallest possible D = E^-1 mod LCM(P-1, Q-1) */
+ /* compute smallest possible D = E^-1 mod LCM(P-1, Q-1) (FIPS 186-4 §B.3.1 criterion 3(b)) */
MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, &ctx->P, &ctx->Q ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &L, NULL, &H, &G ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &ctx->D, &ctx->E, &L ) );
@@ -565,6 +568,8 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &ctx->P, &ctx->P, 1 ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &ctx->Q, &ctx->Q, 1 ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
+
ctx->len = mbedtls_mpi_size( &ctx->N );
#if !defined(MBEDTLS_RSA_NO_CRT)
