From 5f9b3c2e220ca6d0eaff32324a973ef67933a844 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Tom=C3=A1=C5=A1=20Mr=C3=A1z?= Date: Tue, 22 Mar 2016 17:12:55 +0100 Subject: rsa: Add FIPS 186-4 compliant RSA probable prime key generator. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * cipher/primegen.c (_gcry_fips186_4_prime_check): New. * cipher/rsa.c (generate_fips): New. (rsa_generate): Use new function in fips mode or with test-parms. * tests/keygen.c (check_rsa_keys): Add test using e=65539. -- Signed-off-by: Tomáš Mráz Tomáš's patch war originally for libgcrypt 1.6.3 and has been ported to master (1.7) by wk. Further changes: - ChangeLog entries. - Some re-indentation - Use an extra test case instead of changing an existing one. Signed-off-by: Werner Koch --- cipher/primegen.c | 21 ++++ cipher/rsa.c | 298 +++++++++++++++++++++++++++++++++++++++++++++++++++++- src/g10lib.h | 3 + tests/keygen.c | 22 ++++ 4 files changed, 341 insertions(+), 3 deletions(-) diff --git a/cipher/primegen.c b/cipher/primegen.c index 3ed432bf..cccda84e 100644 --- a/cipher/primegen.c +++ b/cipher/primegen.c @@ -1182,6 +1182,27 @@ _gcry_prime_check (gcry_mpi_t x, unsigned int flags) return GPG_ERR_NO_PRIME; } + +/* Check whether the number X is prime according to FIPS 186-4 table C.2. */ +gcry_err_code_t +_gcry_fips186_4_prime_check (gcry_mpi_t x, unsigned int bits) +{ + gcry_err_code_t ec = GPG_ERR_NO_ERROR; + + switch (mpi_cmp_ui (x, 2)) + { + case 0: return ec; /* 2 is a prime */ + case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes. */ + } + + /* We use 5 or 4 rounds as specified in table C.2 */ + if (! check_prime (x, mpi_const (MPI_C_TWO), bits > 1024 ? 4 : 5, NULL, NULL)) + ec = GPG_ERR_NO_PRIME; + + return ec; +} + + /* Find a generator for PRIME where the factorization of (prime-1) is in the NULL terminated array FACTORS. Return the generator as a newly allocated MPI in R_G. If START_G is not NULL, use this as s diff --git a/cipher/rsa.c b/cipher/rsa.c index 787b14a1..cb3c464a 100644 --- a/cipher/rsa.c +++ b/cipher/rsa.c @@ -356,6 +356,286 @@ generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, } +/**************** + * Generate a key pair with a key of size NBITS. + * USE_E = 0 let Libcgrypt decide what exponent to use. + * = 1 request the use of a "secure" exponent; this is required by some + * specification to be 65537. + * > 2 Use this public exponent. If the given exponent + * is not odd one is internally added to it. + * TESTPARMS: If set, do not generate but test whether the p,q is probably prime + * Returns key with zeroes to not break code calling this function. + * TRANSIENT_KEY: If true, generate the primes using the standard RNG. + * Returns: 2 structures filled with all needed values + */ +static gpg_err_code_t +generate_fips (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, + gcry_sexp_t testparms, int transient_key) +{ + gcry_mpi_t p, q; /* the two primes */ + gcry_mpi_t d; /* the private key */ + gcry_mpi_t u; + gcry_mpi_t p1, q1; + gcry_mpi_t n; /* the public key */ + gcry_mpi_t e; /* the exponent */ + gcry_mpi_t g; + gcry_mpi_t minp; + gcry_mpi_t diff, mindiff; + gcry_random_level_t random_level; + unsigned int pbits = nbits/2; + unsigned int i; + int pqswitch; + gpg_err_code_t ec = GPG_ERR_NO_PRIME; + + if (nbits < 1024 || (nbits & 0x1FF)) + return GPG_ERR_INV_VALUE; + if (_gcry_enforced_fips_mode() && nbits != 2048 && nbits != 3072) + return GPG_ERR_INV_VALUE; + + /* The random quality depends on the transient_key flag. */ + random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM; + + if (testparms) + { + /* Parameters to derive the key are given. */ + /* Note that we explicitly need to setup the values of tbl + because some compilers (e.g. OpenWatcom, IRIX) don't allow to + initialize a structure with automatic variables. */ + struct { const char *name; gcry_mpi_t *value; } tbl[] = { + { "e" }, + { "p" }, + { "q" }, + { NULL } + }; + int idx; + gcry_sexp_t oneparm; + + tbl[0].value = &e; + tbl[1].value = &p; + tbl[2].value = &q; + + for (idx=0; tbl[idx].name; idx++) + { + oneparm = sexp_find_token (testparms, tbl[idx].name, 0); + if (oneparm) + { + *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG); + sexp_release (oneparm); + } + } + for (idx=0; tbl[idx].name; idx++) + if (!*tbl[idx].value) + break; + if (tbl[idx].name) + { + /* At least one parameter is missing. */ + for (idx=0; tbl[idx].name; idx++) + _gcry_mpi_release (*tbl[idx].value); + return GPG_ERR_MISSING_VALUE; + } + } + else + { + if (use_e < 65537) + use_e = 65537; /* This is the smallest value allowed by FIPS */ + + e = mpi_alloc ((32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB); + + use_e |= 1; /* make sure this is odd */ + mpi_set_ui (e, use_e); + + p = mpi_snew (pbits); + q = mpi_snew (pbits); + } + + n = mpi_new (nbits); + d = mpi_snew (nbits); + u = mpi_snew (nbits); + + /* prepare approximate minimum p and q */ + minp = mpi_new (pbits); + mpi_set_ui (minp, 0xB504F334); + mpi_lshift (minp, minp, pbits - 32); + + /* prepare minimum p and q difference */ + diff = mpi_new (pbits); + mindiff = mpi_new (pbits - 99); + mpi_set_ui (mindiff, 1); + mpi_lshift (mindiff, mindiff, pbits - 100); + + p1 = mpi_snew (pbits); + q1 = mpi_snew (pbits); + g = mpi_snew (pbits); + + retry: + /* generate p and q */ + for (i = 0; i < 5 * pbits; i++) + { + ploop: + if (!testparms) + { + _gcry_mpi_randomize (p, pbits, random_level); + } + if (mpi_cmp (p, minp) < 0) + { + if (testparms) + goto err; + goto ploop; + } + + mpi_sub_ui (p1, p, 1); + if (mpi_gcd (g, p1, e)) + { + if (_gcry_fips186_4_prime_check (p, pbits) != GPG_ERR_NO_ERROR) + { + /* not a prime */ + if (testparms) + goto err; + } + else + break; + } + else if (testparms) + goto err; + } + if (i >= 5 * pbits) + goto err; + + for (i = 0; i < 5 * pbits; i++) + { + qloop: + if (!testparms) + { + _gcry_mpi_randomize (q, pbits, random_level); + } + if (mpi_cmp (q, minp) < 0) + { + if (testparms) + goto err; + goto qloop; + } + if (mpi_cmp (p, q) > 0) + { + pqswitch = 1; + mpi_sub (diff, p, q); + } + else + { + pqswitch = 0; + mpi_sub (diff, q, p); + } + if (mpi_cmp (diff, mindiff) < 0) + { + if (testparms) + goto err; + goto qloop; + } + + mpi_sub_ui (q1, q, 1); + if (mpi_gcd (g, q1, e)) + { + if (_gcry_fips186_4_prime_check (q, pbits) != GPG_ERR_NO_ERROR) + { + /* not a prime */ + if (testparms) + goto err; + } + else + break; + } + else if (testparms) + goto err; + } + if (i >= 5 * pbits) + goto err; + + if (testparms) + { + mpi_clear (p); + mpi_clear (q); + } + else + { + gcry_mpi_t f; + + if (pqswitch) + { + gcry_mpi_t tmp; + + tmp = p; + p = q; + q = tmp; + } + + f = mpi_snew (nbits); + + /* calculate the modulus */ + mpi_mul (n, p, q); + + /* calculate the secret key d = e^1 mod phi */ + mpi_gcd (g, p1, q1); + mpi_fdiv_q (f, p1, g); + mpi_mul (f, f, q1); + + mpi_invm (d, e, f); + + _gcry_mpi_release (f); + + if (mpi_get_nbits (d) < pbits) + goto retry; + + /* calculate the inverse of p and q (used for chinese remainder theorem)*/ + mpi_invm (u, p, q ); + } + + ec = 0; + + if (DBG_CIPHER) + { + log_mpidump(" p= ", p ); + log_mpidump(" q= ", q ); + log_mpidump(" n= ", n ); + log_mpidump(" e= ", e ); + log_mpidump(" d= ", d ); + log_mpidump(" u= ", u ); + } + + err: + + _gcry_mpi_release (p1); + _gcry_mpi_release (q1); + _gcry_mpi_release (g); + _gcry_mpi_release (minp); + _gcry_mpi_release (mindiff); + _gcry_mpi_release (diff); + + sk->n = n; + sk->e = e; + sk->p = p; + sk->q = q; + sk->d = d; + sk->u = u; + + /* Now we can test our keys. */ + if (ec || (!testparms && test_keys (sk, nbits - 64))) + { + _gcry_mpi_release (sk->n); sk->n = NULL; + _gcry_mpi_release (sk->e); sk->e = NULL; + _gcry_mpi_release (sk->p); sk->p = NULL; + _gcry_mpi_release (sk->q); sk->q = NULL; + _gcry_mpi_release (sk->d); sk->d = NULL; + _gcry_mpi_release (sk->u); sk->u = NULL; + if (!ec) + { + fips_signal_error ("self-test after key generation failed"); + return GPG_ERR_SELFTEST_FAILED; + } + } + + return ec; +} + + /* Helper for generate_x931. */ static gcry_mpi_t gen_x931_parm_xp (unsigned int nbits) @@ -816,7 +1096,7 @@ rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey) } } - if (deriveparms || (flags & PUBKEY_FLAG_USE_X931) || fips_mode ()) + if (deriveparms || (flags & PUBKEY_FLAG_USE_X931)) { int swapped; ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped); @@ -836,9 +1116,21 @@ rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey) sexp_release (l1); } } + deriveparms = (genparms? sexp_find_token (genparms, "test-parms", 0) + /**/ : NULL); + /* Generate. */ - ec = generate_std (&sk, nbits, evalue, - !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); + if (deriveparms || fips_mode()) + { + ec = generate_fips (&sk, nbits, evalue, deriveparms, + !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); + } + else + { + ec = generate_std (&sk, nbits, evalue, + !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); + } + sexp_release (deriveparms); } if (!ec) diff --git a/src/g10lib.h b/src/g10lib.h index 1070d9e9..170ffa16 100644 --- a/src/g10lib.h +++ b/src/g10lib.h @@ -263,6 +263,9 @@ gpg_err_code_t _gcry_generate_fips186_3_prime int *r_counter, void **r_seed, size_t *r_seedlen, int *r_hashalgo); +gpg_err_code_t _gcry_fips186_4_prime_check (const gcry_mpi_t x, + unsigned int bits); + /* Replacements of missing functions (missing-string.c). */ #ifndef HAVE_STPCPY diff --git a/tests/keygen.c b/tests/keygen.c index dcb59e48..4bcea20d 100644 --- a/tests/keygen.c +++ b/tests/keygen.c @@ -235,6 +235,28 @@ check_rsa_keys (void) gcry_sexp_release (key); + if (verbose) + show ("creating 1024 bit RSA key with e=65539\n"); + rc = gcry_sexp_new (&keyparm, + "(genkey\n" + " (rsa\n" + " (nbits 4:1024)\n" + " (rsa-use-e 5:65539)\n" + " ))", 0, 1); + if (rc) + die ("error creating S-expression: %s\n", gpg_strerror (rc)); + rc = gcry_pk_genkey (&key, keyparm); + gcry_sexp_release (keyparm); + if (rc && !in_fips_mode) + fail ("error generating RSA key: %s\n", gpg_strerror (rc)); + else if (!rc && in_fips_mode) + fail ("generating RSA key must not work!"); + + if (!rc) + check_generated_rsa_key (key, 65539); + gcry_sexp_release (key); + + if (verbose) show ("creating 512 bit RSA key with e=257\n"); rc = gcry_sexp_new (&keyparm, -- cgit v1.2.1