summaryrefslogtreecommitdiffstats
path: root/crypto
diff options
context:
space:
mode:
Diffstat (limited to 'crypto')
-rw-r--r--crypto/bn/bn_prime.c271
-rw-r--r--crypto/bn/bn_rsa_fips186_4.c346
-rw-r--r--crypto/bn/build.info3
-rw-r--r--crypto/include/internal/bn_int.h27
-rw-r--r--crypto/rsa/build.info3
-rw-r--r--crypto/rsa/rsa_chk.c14
-rw-r--r--crypto/rsa/rsa_gen.c9
-rw-r--r--crypto/rsa/rsa_lib.c2
-rw-r--r--crypto/rsa/rsa_locl.h38
-rw-r--r--crypto/rsa/rsa_sp800_56b_check.c386
-rw-r--r--crypto/rsa/rsa_sp800_56b_gen.c362
11 files changed, 1375 insertions, 86 deletions
diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index c4ab8693fc..7a87b97db3 100644
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -1,5 +1,5 @@
/*
- * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
*
* Licensed under the Apache License 2.0 (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
@@ -19,14 +19,49 @@
*/
#include "bn_prime.h"
-static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
- const BIGNUM *a1_odd, int k, BN_CTX *ctx,
- BN_MONT_CTX *mont);
static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods);
static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
const BIGNUM *add, const BIGNUM *rem,
BN_CTX *ctx);
+#if BN_BITS2 == 64
+# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
+#else
+# define BN_DEF(lo, hi) lo, hi
+#endif
+
+/*
+ * See SP800 89 5.3.3 (Step f)
+ * The product of the set of primes ranging from 3 to 751
+ * Generated using process in test/bn_internal_test.c test_bn_small_factors().
+ * This includes 751 (which is not currently included in SP 800-89).
+ */
+static const BN_ULONG small_prime_factors[] = {
+ BN_DEF(0x3ef4e3e1, 0xc4309333), BN_DEF(0xcd2d655f, 0x71161eb6),
+ BN_DEF(0x0bf94862, 0x95e2238c), BN_DEF(0x24f7912b, 0x3eb233d3),
+ BN_DEF(0xbf26c483, 0x6b55514b), BN_DEF(0x5a144871, 0x0a84d817),
+ BN_DEF(0x9b82210a, 0x77d12fee), BN_DEF(0x97f050b3, 0xdb5b93c2),
+ BN_DEF(0x4d6c026b, 0x4acad6b9), BN_DEF(0x54aec893, 0xeb7751f3),
+ BN_DEF(0x36bc85c4, 0xdba53368), BN_DEF(0x7f5ec78e, 0xd85a1b28),
+ BN_DEF(0x6b322244, 0x2eb072d8), BN_DEF(0x5e2b3aea, 0xbba51112),
+ BN_DEF(0x0e2486bf, 0x36ed1a6c), BN_DEF(0xec0c5727, 0x5f270460),
+ (BN_ULONG)0x000017b1
+};
+
+#define BN_SMALL_PRIME_FACTORS_TOP OSSL_NELEM(small_prime_factors)
+static const BIGNUM _bignum_small_prime_factors = {
+ (BN_ULONG *)small_prime_factors,
+ BN_SMALL_PRIME_FACTORS_TOP,
+ BN_SMALL_PRIME_FACTORS_TOP,
+ 0,
+ BN_FLG_STATIC_DATA
+};
+
+const BIGNUM *bn_get0_small_factors(void)
+{
+ return &_bignum_small_prime_factors;
+}
+
int BN_GENCB_call(BN_GENCB *cb, int a, int b)
{
/* No callback means continue */
@@ -148,127 +183,199 @@ int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
}
-int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
+/* See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. */
+int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx_passed,
int do_trial_division, BN_GENCB *cb)
{
- int i, j, ret = -1;
- int k;
+ int i, status, ret = -1;
BN_CTX *ctx = NULL;
- BIGNUM *A1, *A1_odd, *A3, *check; /* taken from ctx */
- BN_MONT_CTX *mont = NULL;
- /* Take care of the really small primes 2 & 3 */
- if (BN_is_word(a, 2) || BN_is_word(a, 3))
- return 1;
-
- /* Check odd and bigger than 1 */
- if (!BN_is_odd(a) || BN_cmp(a, BN_value_one()) <= 0)
+ /* w must be bigger than 1 */
+ if (BN_cmp(w, BN_value_one()) <= 0)
return 0;
- if (checks == BN_prime_checks)
- checks = BN_prime_checks_for_size(BN_num_bits(a));
+ /* w must be odd */
+ if (BN_is_odd(w)) {
+ /* Take care of the really small prime 3 */
+ if (BN_is_word(w, 3))
+ return 1;
+ } else {
+ /* 2 is the only even prime */
+ return BN_is_word(w, 2);
+ }
/* first look for small factors */
if (do_trial_division) {
for (i = 1; i < NUMPRIMES; i++) {
- BN_ULONG mod = BN_mod_word(a, primes[i]);
+ BN_ULONG mod = BN_mod_word(w, primes[i]);
if (mod == (BN_ULONG)-1)
- goto err;
+ return -1;
if (mod == 0)
- return BN_is_word(a, primes[i]);
+ return BN_is_word(w, primes[i]);
}
if (!BN_GENCB_call(cb, 1, -1))
- goto err;
+ return -1;
}
-
if (ctx_passed != NULL)
ctx = ctx_passed;
else if ((ctx = BN_CTX_new()) == NULL)
goto err;
- BN_CTX_start(ctx);
- A1 = BN_CTX_get(ctx);
- A3 = BN_CTX_get(ctx);
- A1_odd = BN_CTX_get(ctx);
- check = BN_CTX_get(ctx);
- if (check == NULL)
+ ret = bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status);
+ if (!ret)
goto err;
+ ret = (status == BN_PRIMETEST_PROBABLY_PRIME);
+err:
+ if (ctx_passed == NULL)
+ BN_CTX_free(ctx);
+ return ret;
+}
+
+/*
+ * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test.
+ * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero).
+ * The Step numbers listed in the code refer to the enhanced case.
+ *
+ * if enhanced is set, then status returns one of the following:
+ * BN_PRIMETEST_PROBABLY_PRIME
+ * BN_PRIMETEST_COMPOSITE_WITH_FACTOR
+ * BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME
+ * if enhanced is zero, then status returns either
+ * BN_PRIMETEST_PROBABLY_PRIME or
+ * BN_PRIMETEST_COMPOSITE
+ *
+ * returns 0 if there was an error, otherwise it returns 1.
+ */
+int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
+ BN_GENCB *cb, int enhanced, int *status)
+{
+ int i, j, a, ret = 0;
+ BIGNUM *g, *w1, *w3, *x, *m, *z, *b;
+ BN_MONT_CTX *mont = NULL;
- /* compute A1 := a - 1 */
- if (!BN_copy(A1, a) || !BN_sub_word(A1, 1))
+ /* w must be odd */
+ if (!BN_is_odd(w))
+ return 0;
+
+ BN_CTX_start(ctx);
+ g = BN_CTX_get(ctx);
+ w1 = BN_CTX_get(ctx);
+ w3 = BN_CTX_get(ctx);
+ x = BN_CTX_get(ctx);
+ m = BN_CTX_get(ctx);
+ z = BN_CTX_get(ctx);
+ b = BN_CTX_get(ctx);
+
+ if (!(b != NULL
+ /* w1 := w - 1 */
+ && BN_copy(w1, w)
+ && BN_sub_word(w1, 1)
+ /* w3 := w - 3 */
+ && BN_copy(w3, w)
+ && BN_sub_word(w3, 3)))
goto err;
- /* compute A3 := a - 3 */
- if (!BN_copy(A3, a) || !BN_sub_word(A3, 3))
+
+ /* check w is larger than 3, otherwise the random b will be too small */
+ if (BN_is_zero(w3) || BN_is_negative(w3))
goto err;
- /* write A1 as A1_odd * 2^k */
- k = 1;
- while (!BN_is_bit_set(A1, k))
- k++;
- if (!BN_rshift(A1_odd, A1, k))
+ /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */
+ a = 1;
+ while (!BN_is_bit_set(w1, a))
+ a++;
+ /* (Step 2) m = (w-1) / 2^a */
+ if (!BN_rshift(m, w1, a))
goto err;
/* Montgomery setup for computations mod a */
mont = BN_MONT_CTX_new();
- if (mont == NULL)
- goto err;
- if (!BN_MONT_CTX_set(mont, a, ctx))
+ if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))
goto err;
- for (i = 0; i < checks; i++) {
- /* 1 < check < a-1 */
- if (!BN_priv_rand_range(check, A3) || !BN_add_word(check, 2))
- goto err;
+ if (iterations == BN_prime_checks)
+ iterations = BN_prime_checks_for_size(BN_num_bits(w));
- j = witness(check, a, A1, A1_odd, k, ctx, mont);
- if (j == -1)
+ /* (Step 4) */
+ for (i = 0; i < iterations; ++i) {
+ /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */
+ if (!BN_priv_rand_range(b, w3) || !BN_add_word(b, 2)) /* 1 < b < w-1 */
goto err;
- if (j) {
- ret = 0;
+
+ if (enhanced) {
+ /* (Step 4.3) */
+ if (!BN_gcd(g, b, w, ctx))
+ goto err;
+ /* (Step 4.4) */
+ if (!BN_is_one(g)) {
+ *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
+ ret = 1;
+ goto err;
+ }
+ }
+ /* (Step 4.5) z = b^m mod w */
+ if (!BN_mod_exp_mont(z, b, m, w, ctx, mont))
goto err;
+ /* (Step 4.6) if (z = 1 or z = w-1) */
+ if (BN_is_one(z) || BN_cmp(z, w1) == 0)
+ goto outer_loop;
+ /* (Step 4.7) for j = 1 to a-1 */
+ for (j = 1; j < a ; ++j) {
+ /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */
+ if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
+ goto err;
+ /* (Step 4.7.3) */
+ if (BN_cmp(z, w1) == 0)
+ goto outer_loop;
+ /* (Step 4.7.4) */
+ if (BN_is_one(z))
+ goto composite;
}
if (!BN_GENCB_call(cb, 1, i))
goto err;
+ /* At this point z = b^((w-1)/2) mod w */
+ /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */
+ if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
+ goto err;
+ /* (Step 4.10) */
+ if (BN_is_one(z))
+ goto composite;
+ /* (Step 4.11) x = b^(w-1) mod w */
+ if (!BN_copy(x, z))
+ goto err;
+composite:
+ if (enhanced) {
+ /* (Step 4.1.2) g = GCD(x-1, w) */
+ if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx))
+ goto err;
+ /* (Steps 4.1.3 - 4.1.4) */
+ if (BN_is_one(g))
+ *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME;
+ else
+ *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
+ } else {
+ *status = BN_PRIMETEST_COMPOSITE;
+ }
+ ret = 1;
+ goto err;
+outer_loop: ;
+ /* (Step 4.1.5) */
}
+ /* (Step 5) */
+ *status = BN_PRIMETEST_PROBABLY_PRIME;
ret = 1;
- err:
- if (ctx != NULL) {
- BN_CTX_end(ctx);
- if (ctx_passed == NULL)
- BN_CTX_free(ctx);
- }
+err:
+ BN_clear(g);
+ BN_clear(w1);
+ BN_clear(w3);
+ BN_clear(x);
+ BN_clear(m);
+ BN_clear(z);
+ BN_clear(b);
+ BN_CTX_end(ctx);
BN_MONT_CTX_free(mont);
-
return ret;
}
-static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
- const BIGNUM *a1_odd, int k, BN_CTX *ctx,
- BN_MONT_CTX *mont)
-{
- if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
- return -1;
- if (BN_is_one(w))
- return 0; /* probably prime */
- if (BN_cmp(w, a1) == 0)
- return 0; /* w == -1 (mod a), 'a' is probably prime */
- while (--k) {
- if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
- return -1;
- if (BN_is_one(w))
- return 1; /* 'a' is composite, otherwise a previous 'w'
- * would have been == -1 (mod 'a') */
- if (BN_cmp(w, a1) == 0)
- return 0; /* w == -1 (mod a), 'a' is probably prime */
- }
- /*
- * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
- * it is neither -1 nor +1 -- so 'a' cannot be prime
- */
- bn_check_top(w);
- return 1;
-}
-
static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
{
int i;
diff --git a/crypto/bn/bn_rsa_fips186_4.c b/crypto/bn/bn_rsa_fips186_4.c
new file mode 100644
index 0000000000..261669d0d0
--- /dev/null
+++ b/crypto/bn/bn_rsa_fips186_4.c
@@ -0,0 +1,346 @@
+/*
+ * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
+ *
+ * Licensed under the OpenSSL license (the "License"). You may not use
+ * this file except in compliance with the License. You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+/*
+ * According to NIST SP800-131A "Transitioning the use of cryptographic
+ * algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
+ * allowed for signatures (Table 2) or key transport (Table 5). In the code
+ * below any attempt to generate 1024 bit RSA keys will result in an error (Note
+ * that digital signature verification can still use deprecated 1024 bit keys).
+ *
+ * Also see FIPS1402IG A.14
+ * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
+ * must be generated before the module generates the RSA primes p and q.
+ * Table B.1 in FIPS 186-4 specifies, for RSA modulus lengths of 2048 and
+ * 3072 bits only, the min/max total length of the auxiliary primes.
+ * When implementing the RSA signature generation algorithm
+ * with other approved RSA modulus sizes, the vendor shall use the limitations
+ * from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
+ * FIPS 186-4 whose length does not exceed that of the implementation's RSA
+ * modulus. In particular, when generating the primes for the 4096-bit RSA
+ * modulus the limitations stated for the 3072-bit modulus shall apply.
+ */
+#include <stdio.h>
+#include <openssl/bn.h>
+#include "bn_lcl.h"
+#include "internal/bn_int.h"
+
+/*
+ * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
+ *
+ * Params:
+ * nbits The key size in bits.
+ * Returns:
+ * The minimum size of the auxiliary primes or 0 if nbits is invalid.
+ */
+static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
+{
+ if (nbits >= 3072)
+ return 171;
+ if (nbits == 2048)
+ return 141;
+ return 0;
+}
+
+/*
+ * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
+ * len(q1) + len(q2) for p,q Probable Primes".
+ *
+ * Params:
+ * nbits The key size in bits.
+ * Returns:
+ * The maximum length or 0 if nbits is invalid.
+ */
+static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
+{
+ if (nbits >= 3072)
+ return 1518;
+ if (nbits == 2048)
+ return 1007;
+ return 0;
+}
+
+/*
+ * FIPS 186-4 Table C.3 for error probability of 2^-100
+ * Minimum number of Miller Rabin Rounds for p1, p2, q1 & q2.
+ *
+ * Params:
+ * aux_prime_bits The auxiliary prime size in bits.
+ * Returns:
+ * The minimum number of Miller Rabin Rounds for an auxiliary prime, or
+ * 0 if aux_prime_bits is invalid.
+ */
+static int bn_rsa_fips186_4_aux_prime_MR_min_checks(int aux_prime_bits)
+{
+ if (aux_prime_bits > 170)
+ return 27;
+ if (aux_prime_bits > 140)
+ return 32;
+ return 0; /* Error case */
+}
+
+/*
+ * FIPS 186-4 Table C.3 for error probability of 2^-100
+ * Minimum number of Miller Rabin Rounds for p, q.
+ *
+ * Params:
+ * nbits The key size in bits.
+ * Returns:
+ * The minimum number of Miller Rabin Rounds required,
+ * or 0 if nbits is invalid.
+ */
+int bn_rsa_fips186_4_prime_MR_min_checks(int nbits)
+{
+ if (nbits >= 3072) /* > 170 */
+ return 3;
+ if (nbits == 2048) /* > 140 */
+ return 4;
+ return 0; /* Error case */
+}
+
+/*
+ * Find the first odd integer that is a probable prime.
+ *
+ * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
+ *
+ * Params:
+ * Xp1 The passed in starting point to find a probably prime.
+ * p1 The returned probable prime (first odd integer >= Xp1)
+ * ctx A BN_CTX object.
+ * cb An optional BIGNUM callback.
+ * Returns: 1 on success otherwise it returns 0.
+ */
+static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
+ BIGNUM *p1, BN_CTX *ctx,
+ BN_GENCB *cb)
+{
+ int ret = 0;
+ int i = 0;
+ int checks = bn_rsa_fips186_4_aux_prime_MR_min_checks(BN_num_bits(Xp1));
+
+ if (checks == 0 || BN_copy(p1, Xp1) == NULL)
+ return 0;
+
+ /* Find the first odd number >= Xp1 that is probably prime */
+ for(;;) {
+ i++;
+ BN_GENCB_call(cb, 0, i);
+ /* MR test with trial division */
+ if (BN_is_prime_fasttest_ex(p1, checks, ctx, 1, cb))
+ break;
+ /* Get next odd number */
+ if (!BN_add_word(p1, 2))
+ goto err;
+ }
+ BN_GENCB_call(cb, 2, i);
+ ret = 1;
+err:
+ return ret;
+}
+
+/*
+ * Generate a probable prime (p or q).
+ *
+ * See FIPS 186-4 B.3.6 (Steps 4 & 5)
+ *
+ * Params:
+ * p The returned probable prime.
+ * Xpout An optionally returned random number used during generation of p.
+ * p1, p2 The returned auxiliary primes. If NULL they are not returned.
+ * Xp An optional passed in value (that is random number used during
+ * generation of p).
+ * Xp1, Xp2 Optional passed in values that are normally generated
+ * internally. Used to find p1, p2.
+ * nlen The bit length of the modulus (the key size).
+ * e The public exponent.
+ * ctx A BN_CTX object.
+ * cb An optional BIGNUM callback.
+ * Returns: 1 on success otherwise it returns 0.
+ */
+int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
+ BIGNUM *p1, BIGNUM *p2,
+ const BIGNUM *Xp, const BIGNUM *Xp1,
+ const BIGNUM *Xp2, int nlen,
+ const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
+{
+ int ret = 0;
+ BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
+ int bitlen;
+
+ if (p == NULL || Xpout == NULL)
+ return 0;
+
+ BN_CTX_start(ctx);
+
+ p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
+ p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
+ Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
+ Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
+ if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
+ goto err;
+
+ bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
+ if (bitlen == 0)
+ goto err;
+
+ /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
+ if (Xp1 == NULL) {
+ /* Set the top and bottom bits to make it odd and the correct size */
+ if (!BN_priv_rand(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
+ goto err;
+ }
+ /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
+ if (Xp2 == NULL) {
+ /* Set the top and bottom bits to make it odd and the correct size */
+ if (!BN_priv_rand(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
+ goto err;
+ }
+
+ /* (Steps 4.2/5.2) - find first auxiliary probable primes */
+ if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
+ || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
+ goto err;
+ /* (Table B.1) auxiliary prime Max length check */
+ if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
+ bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
+ goto err;
+ /* (Steps 4.3/5.3) - generate prime */
+ if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
+ goto err;
+ ret = 1;
+err:
+ /* Zeroize any internally generated values that are not returned */
+ if (p1 == NULL)
+ BN_clear(p1i);
+ if (p2 == NULL)
+ BN_clear(p2i);
+ if (Xp1 == NULL)
+ BN_clear(Xp1i);
+ if (Xp2 == NULL)
+ BN_clear(Xp2i);
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/*
+ * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
+ * prime numbers and the Chinese Remainder Theorem.
+ *
+ * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
+ * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
+ *
+ * Params:
+ * Y The returned prime factor (private_prime_factor) of the modulus n.
+ * X The returned random number used during generation of the prime factor.
+ * Xin An optional passed in value for X used for testing purposes.
+ * r1 An auxiliary prime.
+ * r2 An auxiliary prime.
+ * nlen The desired length of n (the RSA modulus).
+ * e The public exponent.
+ * ctx A BN_CTX object.
+ * cb An optional BIGNUM callback object.
+ * Returns: 1 on success otherwise it returns 0.
+ * Assumptions:
+ * Y, X, r1, r2, e are not NULL.
+ */
+int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
+ const BIGNUM *r1, const BIGNUM *r2, int nlen,
+ const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
+{
+ int ret = 0;
+ int i, imax;
+ int bits = nlen >> 1;
+ int checks = bn_rsa_fips186_4_prime_MR_min_checks(nlen);
+ BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
+
+ if (checks == 0)
+ return 0;
+ BN_CTX_start(ctx);
+
+ R = BN_CTX_get(ctx);
+ tmp = BN_CTX_get(ctx);
+ r1r2x2 = BN_CTX_get(ctx);
+ y1 = BN_CTX_get(ctx);
+ r1x2 = BN_CTX_get(ctx);
+ if (r1x2 == NULL)
+ goto err;
+
+ if (Xin != NULL && BN_copy(X, Xin) == NULL)
+ goto err;
+
+ if (!(BN_lshift1(r1x2, r1)
+ /* (Step 1) GCD(2r1, r2) = 1 */
+ && BN_gcd(tmp, r1x2, r2, ctx)
+ && BN_is_one(tmp)
+ /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
+ && BN_mod_inverse(R, r2, r1x2, ctx)
+ && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
+ && BN_mod_inverse(tmp, r1x2, r2, ctx)
+ && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
+ && BN_sub(R, R, tmp)
+ /* Calculate 2r1r2 */
+ && BN_mul(r1r2x2, r1x2, r2, ctx)))
+ goto err;
+ /* Make positive by adding the modulus */
+ if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
+ goto err;
+
+ imax = 5 * bits; /* max = 5/2 * nbits */
+ for (;;) {
+ if (Xin == NULL) {
+ /*
+ * (Step 3) Choose Random X such that
+ * sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1.
+ *
+ * For the lower bound:
+ * sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2)
+ * where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE...
+ * so largest number will have B5... as the top byte
+ * Setting the top 2 bits gives 0xC0.
+ */
+ if (!BN_priv_rand(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY))
+ goto end;
+ }
+ /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
+ if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
+ goto err;
+ /* (Step 5) */
+ i = 0;
+ for (;;) {
+ /* (Step 6) */
+ if (BN_num_bits(Y) > bits) {
+ if (Xin == NULL)
+ break; /* Randomly Generated X so Go back to Step 3 */
+ else
+ goto err; /* X is not random so it will always fail */
+ }
+ BN_GENCB_call(cb, 0, 2);
+
+ /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
+ if (BN_copy(y1, Y) == NULL
+ || !BN_sub_word(y1, 1)
+ || !BN_gcd(tmp, y1, e, ctx))
+ goto err;
+ if (BN_is_one(tmp)
+ && BN_is_prime_fasttest_ex(Y, checks, ctx, 1, cb))
+ goto end;
+ /* (Step 8-10) */
+ if (++i >= imax || !BN_add(Y, Y, r1r2x2))
+ goto err;
+ }
+ }
+end:
+ ret = 1;
+ BN_GENCB_call(cb, 3, 0);
+err:
+ BN_clear(y1);
+ BN_CTX_end(ctx);
+ return ret;
+}
diff --git a/crypto/bn/build.info b/crypto/bn/build.info
index a463eddabb..7e34ce41b3 100644
--- a/crypto/bn/build.info
+++ b/crypto/bn/build.info
@@ -5,7 +5,8 @@ SOURCE[../../libcrypto]=\
bn_kron.c bn_sqrt.c bn_gcd.c bn_prime.c bn_err.c bn_sqr.c \
{- $target{bn_asm_src} -} \
bn_recp.c bn_mont.c bn_mpi.c bn_exp2.c bn_gf2m.c bn_nist.c \
- bn_depr.c bn_const.c bn_x931p.c bn_intern.c bn_dh.c bn_srp.c
+ bn_depr.c bn_const.c bn_x931p.c bn_intern.c bn_dh.c bn_srp.c \
+ bn_rsa_fips186_4.c
INCLUDE[../../libcrypto]=../../crypto/include
INCLUDE[bn_exp.o]=..
diff --git a/crypto/include/internal/bn_int.h b/crypto/include/internal/bn_int.h
index 66e34ec5b8..514eaeeb90 100644
--- a/crypto/include/internal/bn_int.h
+++ b/crypto/include/internal/bn_int.h
@@ -87,4 +87,31 @@ int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n);
int bn_div_fixed_top(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
const BIGNUM *d, BN_CTX *ctx);
+#define BN_PRIMETEST_COMPOSITE 0
+#define BN_PRIMETEST_COMPOSITE_WITH_FACTOR 1
+#define BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME 2
+#define BN_PRIMETEST_PROBABLY_PRIME 3
+
+int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
+ BN_GENCB *cb, int enhanced, int *status);
+
+const BIGNUM *bn_get0_small_factors(void);
+
+int bn_rsa_fips186_4_prime_MR_min_checks(int nbits);
+
+int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
+ BIGNUM *p1, BIGNUM *p2,
+ const BIGNUM *Xp, const BIGNUM *Xp1,
+ const BIGNUM *Xp2, int nlen,
+ const BIGNUM *e, BN_CTX *ctx,
+ BN_GENCB *cb);
+
+int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
+ const BIGNUM *r1, const BIGNUM *r2, int nlen,
+ const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb);
+
+#ifdef __cplusplus
+}
+#endif
+
#endif
diff --git a/crypto/rsa/build.info b/crypto/rsa/build.info
index 87f924922f..70864170ed 100644
--- a/crypto/rsa/build.info
+++ b/crypto/rsa/build.info
@@ -3,4 +3,5 @@ SOURCE[../../libcrypto]=\
rsa_ossl.c rsa_gen.c rsa_lib.c rsa_sign.c rsa_saos.c rsa_err.c \
rsa_pk1.c rsa_ssl.c rsa_none.c rsa_oaep.c rsa_chk.c \
rsa_pss.c rsa_x931.c rsa_asn1.c rsa_depr.c rsa_ameth.c rsa_prn.c \
- rsa_pmeth.c rsa_crpt.c rsa_x931g.c rsa_meth.c rsa_mp.c
+ rsa_pmeth.c rsa_crpt.c rsa_x931g.c rsa_meth.c rsa_mp.c \
+ rsa_sp800_56b_gen.c rsa_sp800_56b_check.c
diff --git a/crypto/rsa/rsa_chk.c b/crypto/rsa/rsa_chk.c
index 805f998ff2..4f65dfa64b 100644
--- a/crypto/rsa/rsa_chk.c
+++ b/crypto/rsa/rsa_chk.c
@@ -16,8 +16,21 @@ int RSA_check_key(const RSA *key)
return RSA_check_key_ex(key, NULL);
}
+/*
+ * NOTE: Key validation requires separate checks to be able to be accessed
+ * individually. These should be visible from the PKEY API..
+ * See rsa_sp800_56b_check_public, rsa_sp800_56b_check_private and
+ * rsa_sp800_56b_check_keypair.
+ */
int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
{
+#ifdef FIPS_MODE
+ if (!(rsa_sp800_56b_check_public(key)
+ && rsa_sp800_56b_check_private(key)
+ && rsa_sp800_56b_check_keypair(key, NULL, -1, RSA_bits(key))
+ return 0;
+
+#else
BIGNUM *i, *j, *k, *l, *m;
BN_CTX *ctx;
int ret = 1, ex_primes = 0, idx;
@@ -225,4 +238,5 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
BN_free(m);
BN_CTX_free(ctx);
return ret;
+#endif /* FIPS_MODE */
}
diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c
index 1d38ec993a..4bfe3c3a96 100644
--- a/crypto/rsa/rsa_gen.c
+++ b/crypto/rsa/rsa_gen.c
@@ -41,6 +41,7 @@ int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
BIGNUM *e_value, BN_GENCB *cb)
{
+#ifndef FIPS_MODE
/* multi-prime is only supported with the builtin key generation */
if (rsa->meth->rsa_multi_prime_keygen != NULL) {
return rsa->meth->rsa_multi_prime_keygen(rsa, bits, primes,
@@ -57,13 +58,18 @@ int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
else
return 0;
}
-
+#endif /* FIPS_MODE */
return rsa_builtin_keygen(rsa, bits, primes, e_value, cb);
}
static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value,
BN_GENCB *cb)
{
+#ifdef FIPS_MODE
+ if (primes != 2)
+ return 0;
+ return rsa_sp800_56b_generate_key(rsa, bits, e_value, cb);
+#else
BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *prime;
int ok = -1, n = 0, bitsr[RSA_MAX_PRIME_NUM], bitse = 0;
int i = 0, quo = 0, rmd = 0, adj = 0, retries = 0;
@@ -391,4 +397,5 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value,
BN_CTX_end(ctx);
BN_CTX_free(ctx);
return ok;
+#endif /* FIPS_MODE */
}
diff --git a/crypto/rsa/rsa_lib.c b/crypto/rsa/rsa_lib.c
index 0848936b2d..f337a0df08 100644
--- a/crypto/rsa/rsa_lib.c
+++ b/crypto/rsa/rsa_lib.c
@@ -253,7 +253,7 @@ static uint32_t ilog_e(uint64_t v)
* \cdot(log_e(nBits \cdot log_e(2))^{2/3} - 4.69}{log_e(2)}
* The two cube roots are merged together here.
*/
-static uint16_t rsa_compute_security_bits(int n)
+uint16_t rsa_compute_security_bits(int n)
{
uint64_t x;
uint32_t lx;
diff --git a/crypto/rsa/rsa_locl.h b/crypto/rsa/rsa_locl.h
index 44a2a2df39..5dcd6eab7b 100644
--- a/crypto/rsa/rsa_locl.h
+++ b/crypto/rsa/rsa_locl.h
@@ -7,6 +7,9 @@
* https://www.openssl.org/source/license.html
*/
+#ifndef RSA_LOCAL_HEADER_H
+#define RSA_LOCAL_HEADER_H
+
#include <openssl/rsa.h>
#include "internal/refcount.h"
@@ -130,3 +133,38 @@ void rsa_multip_info_free(RSA_PRIME_INFO *pinfo);
RSA_PRIME_INFO *rsa_multip_info_new(void);
int rsa_multip_calc_product(RSA *rsa);
int rsa_multip_cap(int bits);
+
+uint16_t rsa_compute_security_bits(int n);
+
+int rsa_sp800_56b_validate_strength(int nbits, int strength);
+int rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
+ int nbits);
+int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
+ BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
+ BIGNUM *p1q1);
+
+int rsa_check_public_exponent(const BIGNUM *e);
+int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx);
+int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx);
+int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx);
+int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx);
+
+int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx);
+int rsa_sp800_56b_check_public(const RSA *rsa);
+int rsa_sp800_56b_check_private(const RSA *rsa);
+int rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed,
+ int strength, int nbits);
+int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
+ BN_GENCB *cb);
+
+int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
+ const BIGNUM *e, BN_CTX *ctx);
+int rsa_fips186_4_gen_prob_primes(RSA *rsa, BIGNUM *p1, BIGNUM *p2,
+ BIGNUM *Xpout, const BIGNUM *Xp,
+ const BIGNUM *Xp1, const BIGNUM *Xp2,
+ BIGNUM *q1, BIGNUM *q2, BIGNUM *Xqout,
+ const BIGNUM *Xq, const BIGNUM *Xq1,
+ const BIGNUM *Xq2, int nbits,
+ const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb);
+
+#endif /* RSA_LOCAL_HEADER_H */
diff --git a/crypto/rsa/rsa_sp800_56b_check.c b/crypto/rsa/rsa_sp800_56b_check.c
new file mode 100644
index 0000000000..10e264e591
--- /dev/null
+++ b/crypto/rsa/rsa_sp800_56b_check.c
@@ -0,0 +1,386 @@
+/*
+ * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
+ *
+ * Licensed under the OpenSSL license (the "License"). You may not use
+ * this file except in compliance with the License. You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <openssl/err.h>
+#include <openssl/bn.h>
+#include "internal/bn_int.h"
+#include "rsa_locl.h"
+
+/*
+ * Part of the RSA keypair test.
+ * Check the Chinese Remainder Theorem components are valid.
+ *
+ * See SP800-5bBr1
+ * 6.4.1.2.3: rsakpv1-crt Step 7
+ * 6.4.1.3.3: rsakpv2-crt Step 7
+ */
+int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx)
+{
+ int ret = 0;
+ BIGNUM *r = NULL, *p1 = NULL, *q1 = NULL;
+
+ /* check if only some of the crt components are set */
+ if (rsa->dmp1 == NULL || rsa->dmq1 == NULL || rsa->iqmp == NULL) {
+ if (rsa->dmp1 != NULL || rsa->dmq1 != NULL || rsa->iqmp != NULL)
+ return 0;
+ return 1; /* return ok if all components are NULL */
+ }
+
+ BN_CTX_start(ctx);
+ r = BN_CTX_get(ctx);
+ p1 = BN_CTX_get(ctx);
+ q1 = BN_CTX_get(ctx);
+ ret = (q1 != NULL)
+ /* p1 = p -1 */
+ && (BN_copy(p1, rsa->p) != NULL)
+ && BN_sub_word(p1, 1)
+ /* q1 = q - 1 */
+ && (BN_copy(q1, rsa->q) != NULL)
+ && BN_sub_word(q1, 1)
+ /* (a) 1 < dP < (p – 1). */
+ && (BN_cmp(rsa->dmp1, BN_value_one()) > 0)
+ && (BN_cmp(rsa->dmp1, p1) < 0)
+ /* (b) 1 < dQ < (q - 1). */
+ && (BN_cmp(rsa->dmq1, BN_value_one()) > 0)
+ && (BN_cmp(rsa->dmq1, q1) < 0)
+ /* (c) 1 < qInv < p */
+ && (BN_cmp(rsa->iqmp, BN_value_one()) > 0)
+ && (BN_cmp(rsa->iqmp, rsa->p) < 0)
+ /* (d) 1 = (dP . e) mod (p - 1)*/
+ && BN_mod_mul(r, rsa->dmp1, rsa->e, p1, ctx)
+ && BN_is_one(r)
+ /* (e) 1 = (dQ . e) mod (q - 1) */
+ && BN_mod_mul(r, rsa->dmq1, rsa->e, q1, ctx)
+ && BN_is_one(r)
+ /* (f) 1 = (qInv . q) mod p */
+ && BN_mod_mul(r, rsa->iqmp, rsa->q, rsa->p, ctx)
+ && BN_is_one(r);
+ BN_clear(p1);
+ BN_clear(q1);
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/*
+ * Part of the RSA keypair test.
+ * Check that (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2) - 1
+ *
+ * See SP800-5bBr1 6.4.1.2.1 Part 5 (c) & (g) - used for both p and q.
+ *
+ * (√2)(2^(nbits/2 - 1) = (√2/2)(2^(nbits/2))
+ * √2/2 = 0.707106781186547524400 = 0.B504F333F9DE6484597D8
+ * 0.B504F334 gives an approximation to 11 decimal places.
+ * The range is then from
+ * 0xB504F334_0000.......................000 to
+ * 0xFFFFFFFF_FFFF.......................FFF
+ */
+int rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx)
+{
+ int ret = 0;
+ BIGNUM *tmp, *low;
+
+ nbits >>= 1;
+
+ /* Upper bound check */
+ if (BN_num_bits(p) != nbits)
+ return 0;
+
+ BN_CTX_start(ctx);
+ tmp = BN_CTX_get(ctx);
+ low = BN_CTX_get(ctx);
+
+ /* set low = (√2)(2^(nbits/2 - 1) */
+ if (low == NULL || !BN_set_word(tmp, 0xB504F334))
+ goto err;
+
+ if (nbits >= 32) {
+ if (!BN_lshift(low, tmp, nbits - 32))
+ goto err;
+ } else if (!BN_rshift(low, tmp, 32 - nbits)) {
+ goto err;
+ }
+ if (BN_cmp(p, low) < 0)
+ goto err;
+ ret = 1;
+err:
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/*
+ * Part of the RSA keypair test.
+ * Check the prime factor (for either p or q)
+ * i.e: p is prime AND GCD(p - 1, e) = 1
+ *
+ * See SP800-5bBr1 6.4.1.2.3 Step 5 (a to d) & (e to h).
+ */
+int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx)
+{
+ int checks = bn_rsa_fips186_4_prime_MR_min_checks(nbits);
+ int ret = 0;
+ BIGNUM *p1 = NULL, *gcd = NULL;
+
+ /* (Steps 5 a-b) prime test */
+ if (BN_is_prime_fasttest_ex(p, checks, ctx, 1, NULL) != 1
+ /* (Step 5c) (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2 - 1) */
+ || rsa_check_prime_factor_range(p, nbits, ctx) != 1)
+ return 0;
+
+ BN_CTX_start(ctx);
+ p1 = BN_CTX_get(ctx);
+ gcd = BN_CTX_get(ctx);
+ ret = (gcd != NULL)
+ /* (Step 5d) GCD(p-1, e) = 1 */
+ && (BN_copy(p1, p) != NULL)
+ && BN_sub_word(p1, 1)
+ && BN_gcd(gcd, p1, e, ctx)
+ && BN_is_one(gcd);
+
+ BN_clear(p1);
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/*
+ * See SP800-56Br1 6.4.1.2.3 Part 6(a-b) Check the private exponent d
+ * satisfies:
+ * (Step 6a) 2^(nBit/2) < d < LCM(p–1, q–1).
+ * (Step 6b) 1 = (d*e) mod LCM(p–1, q–1)
+ */
+int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx)
+{
+ int ret;
+ BIGNUM *r, *p1, *q1, *lcm, *p1q1, *gcd;
+
+ /* (Step 6a) 2^(nbits/2) < d */
+ if (BN_num_bits(rsa->d) <= (nbits >> 1))
+ return 0;
+
+ BN_CTX_start(ctx);
+ r = BN_CTX_get(ctx);
+ p1 = BN_CTX_get(ctx);
+ q1 = BN_CTX_get(ctx);
+ lcm = BN_CTX_get(ctx);
+ p1q1 = BN_CTX_get(ctx);
+ gcd = BN_CTX_get(ctx);
+ ret = (gcd != NULL
+ /* LCM(p - 1, q - 1) */
+ && (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) == 1)
+ /* (Step 6a) d < LCM(p - 1, q - 1) */
+ && (BN_cmp(rsa->d, lcm) < 0)
+ /* (Step 6b) 1 = (e . d) mod LCM(p - 1, q - 1) */
+ && BN_mod_mul(r, rsa->e, rsa->d, lcm, ctx)
+ && BN_is_one(r));
+
+ BN_clear(p1);
+ BN_clear(q1);
+ BN_clear(lcm);
+ BN_clear(gcd);
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/* Check exponent is odd, and has a bitlen ranging from [17..256] */
+int rsa_check_public_exponent(const BIGNUM *e)
+{
+ int bitlen = BN_num_bits(e);
+
+ return (BN_is_odd(e) && bitlen > 16 && bitlen < 257);
+}
+
+/*
+ * SP800-56Br1 6.4.1.2.1 (Step 5i): |p - q| > 2^(nbits/2 - 100)
+ * i.e- numbits(p-q-1) > (nbits/2 -100)
+ */
+int rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
+ int nbits)
+{
+ int bitlen = (nbits >> 1) - 100;
+
+ if (!BN_sub(diff, p, q))
+ return -1;
+ BN_set_negative(diff, 0);
+
+ if (BN_is_zero(diff))
+ return 0;
+
+ if (!BN_sub_word(diff, 1))
+ return -1;
+ return (BN_num_bits(diff) > bitlen);
+}
+
+/* return LCM(p-1, q-1) */
+int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
+ BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
+ BIGNUM *p1q1)
+{
+ return BN_sub(p1, p, BN_value_one()) /* p-1 */
+ && BN_sub(q1, q, BN_value_one()) /* q-1 */
+ && BN_mul(p1q1, p1, q1, ctx) /* (p-1)(q-1) */
+ && BN_gcd(gcd, p1, q1, ctx)
+ && BN_div(lcm, NULL, p1q1, gcd, ctx); /* LCM((p-1, q-1)) */
+}
+
+/*
+ * SP800-56Br1 6.4.2.2 Partial Public Key Validation for RSA refers to
+ * SP800-89 5.3.3 (Explicit) Partial Public Key Validation for RSA
+ * caveat is that the modulus must be as specified in SP800-56Br1
+ */
+int rsa_sp800_56b_check_public(const RSA *rsa)
+{
+ int ret = 0, nbits, iterations, status;
+ BN_CTX *ctx = NULL;
+ BIGNUM *gcd = NULL;
+
+ if (rsa->n == NULL || rsa->e == NULL)
+ return 0;
+
+ /*
+ * (Step a): modulus must be 2048 or 3072 (caveat from SP800-56Br1)
+ * NOTE: changed to allow keys >= 2048
+ */
+ nbits = BN_num_bits(rsa->n);
+ if (!rsa_sp800_56b_validate_strength(nbits, -1)) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_KEY_LENGTH);
+ return 0;
+ }
+ if (!BN_is_odd(rsa->n)) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
+ return 0;
+ }
+
+ /* (Steps b-c): 2^16 < e < 2^256, n and e must be odd */
+ if (!rsa_check_public_exponent(rsa->e)) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC,
+ RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
+ return 0;
+ }
+
+ ctx = BN_CTX_new();
+ gcd = BN_new();
+ if (ctx == NULL || gcd == NULL)
+ goto err;
+
+ iterations = bn_rsa_fips186_4_prime_MR_min_checks(nbits);
+ /* (Steps d-f):
+ * The modulus is composite, but not a power of a prime.
+ * The modulus has no factors smaller than 752.
+ */
+ if (!BN_gcd(gcd, rsa->n, bn_get0_small_factors(), ctx) || !BN_is_one(gcd)) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
+ goto err;
+ }
+
+ ret = bn_miller_rabin_is_prime(rsa->n, iterations, ctx, NULL, 1, &status);
+ if (ret != 1 || status != BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
+ ret = 0;
+ goto err;
+ }
+
+ ret = 1;
+err:
+ BN_free(gcd);
+ BN_CTX_free(ctx);
+ return ret;
+}
+
+/*
+ * Perform validation of the RSA private key to check that 0 < D < N.
+ */
+int rsa_sp800_56b_check_private(const RSA *rsa)
+{
+ if (rsa->d == NULL || rsa->n == NULL)
+ return 0;
+ return BN_cmp(rsa->d, BN_value_one()) >= 0 && BN_cmp(rsa->d, rsa->n) < 0;
+}
+
+/*
+ * RSA key pair validation.
+ *
+ * SP800-56Br1.
+ * 6.4.1.2 "RSAKPV1 Family: RSA Key - Pair Validation with a Fixed Exponent"
+ * 6.4.1.3 "RSAKPV2 Family: RSA Key - Pair Validation with a Random Exponent"
+ *
+ * It uses:
+ * 6.4.1.2.3 "rsakpv1 - crt"
+ * 6.4.1.3.3 "rsakpv2 - crt"
+ */
+int rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed,
+ int strength, int nbits)
+{
+ int ret = 0;
+ BN_CTX *ctx = NULL;
+ BIGNUM *r = NULL;
+
+ if (rsa->p == NULL
+ || rsa->q == NULL
+ || rsa->e == NULL
+ || rsa->d == NULL
+ || rsa->n == NULL) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
+ return 0;
+ }
+ /* (Step 1): Check Ranges */
+ if (!rsa_sp800_56b_validate_strength(nbits, strength))
+ return 0;
+
+ /* If the exponent is known */
+ if (efixed != NULL) {
+ /* (2): Check fixed exponent matches public exponent. */
+ if (BN_cmp(efixed, rsa->e) != 0) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
+ return 0;
+ }
+ }
+ /* (Step 1.c): e is odd integer 65537 <= e < 2^256 */
+ if (!rsa_check_public_exponent(rsa->e)) {
+ /* exponent out of range */
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR,
+ RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
+ return 0;
+ }
+ /* (Step 3.b): check the modulus */
+ if (nbits != BN_num_bits(rsa->n)) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
+ return 0;
+ }
+
+ ctx = BN_CTX_new();
+ if (ctx == NULL)
+ return 0;
+
+ BN_CTX_start(ctx);
+ r = BN_CTX_get(ctx);
+ if (r == NULL || !BN_mul(r, rsa->p, rsa->q, ctx))
+ goto err;
+ /* (Step 4.c): Check n = pq */
+ if (BN_cmp(rsa->n, r) != 0) {
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_REQUEST);
+ goto err;
+ }
+
+ /* (Step 5): check prime factors p & q */
+ ret = rsa_check_prime_factor(rsa->p, rsa->e, nbits, ctx)
+ && rsa_check_prime_factor(rsa->q, rsa->e, nbits, ctx)
+ && (rsa_check_pminusq_diff(r, rsa->p, rsa->q, nbits) > 0)
+ /* (Step 6): Check the private exponent d */
+ && rsa_check_private_exponent(rsa, nbits, ctx)
+ /* 6.4.1.2.3 (Step 7): Check the CRT components */
+ && rsa_check_crt_components(rsa, ctx);
+ if (ret != 1)
+ RSAerr(RSA_F_RSA_SP800_56B_CHECK_KEYPAIR, RSA_R_INVALID_KEYPAIR);
+
+err:
+ BN_clear(r);
+ BN_CTX_end(ctx);
+ BN_CTX_free(ctx);
+ return ret;
+}
diff --git a/crypto/rsa/rsa_sp800_56b_gen.c b/crypto/rsa/rsa_sp800_56b_gen.c
new file mode 100644
index 0000000000..221136bd0c
--- /dev/null
+++ b/crypto/rsa/rsa_sp800_56b_gen.c
@@ -0,0 +1,362 @@
+/*
+ * Copyright 2018-2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
+ *
+ * Licensed under the OpenSSL license (the "License"). You may not use
+ * this file except in compliance with the License. You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <openssl/err.h>
+#include <openssl/bn.h>
+#include "internal/bn_int.h"
+#include "rsa_locl.h"
+
+#define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
+#define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
+#define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
+
+/*
+ * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
+ * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
+ * Primes".
+ *
+ * Params:
+ * rsa Object used to store primes p & q.
+ * p1, p2 The returned auxiliary primes for p. If NULL they are not returned.
+ * Xpout An optionally returned random number used during generation of p.
+ * Xp An optional passed in value (that is random number used during
+ * generation of p).
+ * Xp1, Xp2 Optionally passed in randomly generated numbers from which
+ * auxiliary primes p1 & p2 are calculated. If NULL these values
+ * are generated internally.
+ * q1, q2 The returned auxiliary primes for q. If NULL they are not returned.
+ * Xqout An optionally returned random number used during generation of q.
+ * Xq An optional passed in value (that is random number used during
+ * generation of q).
+ * Xq1, Xq2 Optionally passed in randomly generated numbers from which
+ * auxiliary primes q1 & q2 are calculated. If NULL these values
+ * are generated internally.
+ * nbits The key size in bits (The size of the modulus n).
+ * e The public exponent.
+ * ctx A BN_CTX object.
+ * cb An optional BIGNUM callback.
+ * Returns: 1 if successful, or 0 otherwise.
+ * Notes:
+ * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
+ * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
+ * (Required for CAVS testing).
+ */
+int rsa_fips186_4_gen_prob_primes(RSA *rsa, BIGNUM *p1, BIGNUM *p2,
+ BIGNUM *Xpout, const BIGNUM *Xp,
+ const BIGNUM *Xp1, const BIGNUM *Xp2,
+ BIGNUM *q1, BIGNUM *q2, BIGNUM *Xqout,
+ const BIGNUM *Xq, const BIGNUM *Xq1,
+ const BIGNUM *Xq2, int nbits,
+ const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
+{
+ int ret = 0, ok;
+ BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
+
+ /* (Step 1) Check key length
+ * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
+ * Signature Generation and Key Agree/Transport.
+ */
+ if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
+ RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES, RSA_R_INVALID_KEY_LENGTH);
+ return 0;
+ }
+
+ if (!rsa_check_public_exponent(e)) {
+ RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES,
+ RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
+ goto err;
+ }
+
+ /* (Step 3) Determine strength and check rand generator strength is ok -
+ * this step is redundant because the generator always returns a higher
+ * strength than is required.
+ */
+
+ BN_CTX_start(ctx);
+ tmp = BN_CTX_get(ctx);
+ Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx);
+ Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx);
+ if (tmp == NULL || Xpo == NULL || Xqo == NULL)
+ goto err;
+
+ if (rsa->p == NULL)
+ rsa->p = BN_secure_new();
+ if (rsa->q == NULL)
+ rsa->q = BN_secure_new();
+ if (rsa->p == NULL || rsa->q == NULL)
+ goto err;
+
+ /* (Step 4) Generate p, Xp */
+ if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
+ nbits, e, ctx, cb))
+ goto err;
+ for(;;) {
+ /* (Step 5) Generate q, Xq*/
+ if (!bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
+ Xq2, nbits, e, ctx, cb))
+ goto err;
+
+ /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
+ ok = rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
+ if (ok < 0)
+ goto err;
+ if (ok == 0)
+ continue;
+
+ /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
+ ok = rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
+ if (ok < 0)
+ goto err;
+ if (ok == 0)
+ continue;
+ break; /* successfully finished */
+ }
+ ret = 1;
+err:
+ /* Zeroize any internally generated values that are not returned */
+ if (Xpo != Xpout)
+ BN_clear(Xpo);
+ if (Xqo != Xqout)
+ BN_clear(Xqo);
+ BN_clear(tmp);
+
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/*
+ * Validates the RSA key size based on the target strength.
+ * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
+ *
+ * Params:
+ * nbits The key size in bits.
+ * strength The target strength in bits. -1 means the target
+ * strength is unknown.
+ * Returns: 1 if the key size matches the target strength, or 0 otherwise.
+ */
+int rsa_sp800_56b_validate_strength(int nbits, int strength)
+{
+ int s = (int)rsa_compute_security_bits(nbits);
+
+ if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH
+ || s > RSA_FIPS1864_MAX_KEYGEN_STRENGTH) {
+ RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_MODULUS);
+ return 0;
+ }
+ if (strength != -1 && s != strength) {
+ RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_STRENGTH);
+ return 0;
+ }
+ return 1;
+}
+
+/*
+ *
+ * Using p & q, calculate other required parameters such as n, d.
+ * as well as the CRT parameters dP, dQ, qInv.
+ *
+ * See SP800-56Br1
+ * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
+ * 6.3.1.3 rsakpg1 - crt (Step 5)
+ *
+ * Params:
+ * rsa An rsa object.
+ * nbits The key size.
+ * e The public exponent.
+ * ctx A BN_CTX object.
+ * Notes:
+ * There is a small chance that the generated d will be too small.
+ * Returns: -1 = error,
+ * 0 = d is too small,
+ * 1 = success.
+ */
+int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
+ const BIGNUM *e, BN_CTX *ctx)
+{
+ int ret = -1;
+ BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
+
+ BN_CTX_start(ctx);
+ p1 = BN_CTX_get(ctx);
+ q1 = BN_CTX_get(ctx);
+ lcm = BN_CTX_get(ctx);
+ p1q1 = BN_CTX_get(ctx);
+ gcd = BN_CTX_get(ctx);
+ if (gcd == NULL)
+ goto err;
+
+ /* LCM((p-1, q-1)) */
+ if (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
+ goto err;
+
+ /* copy e */
+ BN_free(rsa->e);
+ rsa->e = BN_dup(e);
+ if (rsa->e == NULL)
+ goto err;
+
+ BN_clear_free(rsa->d);
+ /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
+ rsa->d = BN_secure_new();
+ if (rsa->d == NULL || BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
+ goto err;
+
+ /* (Step 3) return an error if d is too small */
+ if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
+ ret = 0;
+ goto err;
+ }
+
+ /* (Step 4) n = pq */
+ if (rsa->n == NULL)
+ rsa->n = BN_new();
+ if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
+ goto err;
+
+ /* (Step 5a) dP = d mod (p-1) */
+ if (rsa->dmp1 == NULL)
+ rsa->dmp1 = BN_new();
+ if (rsa->dmp1 == NULL || !BN_mod(rsa->dmp1, rsa->d, p1, ctx))
+ goto err;
+
+ /* (Step 5b) dQ = d mod (q-1) */
+ if (rsa->dmq1 == NULL)
+ rsa->dmq1 = BN_secure_new();
+ if (rsa->dmq1 == NULL || !BN_mod(rsa->dmq1, rsa->d, q1, ctx))
+ goto err;
+
+ /* (Step 5c) qInv = (inverse of q) mod p */
+ BN_free(rsa->iqmp);
+ rsa->iqmp = BN_secure_new();
+ if (rsa->iqmp == NULL
+ || BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
+ goto err;
+
+ ret = 1;
+err:
+ if (ret != 1) {
+ BN_free(rsa->e);
+ rsa->e = NULL;
+ BN_free(rsa->d);
+ rsa->d = NULL;
+ BN_free(rsa->n);
+ rsa->n = NULL;
+ BN_free(rsa->iqmp);
+ rsa->iqmp = NULL;
+ BN_free(rsa->dmq1);
+ rsa->dmq1 = NULL;
+ BN_free(rsa->dmp1);
+ rsa->dmp1 = NULL;
+ }
+ BN_clear(p1);
+ BN_clear(q1);
+ BN_clear(lcm);
+ BN_clear(p1q1);
+ BN_clear(gcd);
+
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/*
+ * Generate a SP800-56B RSA key.
+ *
+ * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
+ * 6.3.1.1 rsakpg1 - basic
+ * 6.3.1.3 rsakpg1 - crt
+ *
+ * See also FIPS 186-4 Section B.3.6
+ * "Generation of Probable Primes with Conditions Based on Auxiliary
+ * Probable Primes."
+ *
+ * Params:
+ * rsa The rsa object.
+ * nbits The intended key size in bits.
+ * efixed The public exponent. If NULL a default of 65537 is used.
+ * cb An optional BIGNUM callback.
+ * Returns: 1 if successfully generated otherwise it returns 0.
+ */
+int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
+ BN_GENCB *cb)
+{
+ int ret = 0;
+ int ok;
+ BN_CTX *ctx = NULL;
+ BIGNUM *e = NULL;
+
+ /* (Steps 1a-1b) : Currently ignores the strength check */
+ if (!rsa_sp800_56b_validate_strength(nbits, -1))
+ return 0;
+
+ ctx = BN_CTX_new();
+ if (ctx == NULL)
+ return 0;
+
+ /* Set default if e is not passed in */
+ if (efixed == NULL) {
+ e = BN_new();
+ if (e == NULL || !BN_set_word(e, 65537))
+ goto err;
+ } else {
+ e = (BIGNUM *)efixed;
+ }
+ /* (Step 1c) fixed exponent is checked later . */
+
+ for (;;) {
+ /* (Step 2) Generate prime factors */
+ if (!rsa_fips186_4_gen_prob_primes(rsa, NULL, NULL, NULL, NULL, NULL,
+ NULL, NULL, NULL, NULL, NULL, NULL,
+ NULL, nbits, e, ctx, cb))
+ goto err;
+ /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
+ ok = rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
+ if (ok < 0)
+ goto err;
+ if (ok > 0)
+ break;
+ /* Gets here if computed d is too small - so try again */
+ }
+
+ /* (Step 6) Do pairwise test - optional validity test has been omitted */
+ ret = rsa_sp800_56b_pairwise_test(rsa, ctx);
+err:
+ if (efixed == NULL)
+ BN_free(e);
+ BN_CTX_free(ctx);
+ return ret;
+}
+
+/*
+ * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
+ * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
+ *
+ * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
+ */
+int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
+{
+ int ret = 0;
+ BIGNUM *k, *tmp;
+
+ BN_CTX_start(ctx);
+ tmp = BN_CTX_get(ctx);
+ k = BN_CTX_get(ctx);
+ if (k == NULL)
+ goto err;
+
+ ret = (BN_set_word(k, 2)
+ && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
+ && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
+ && BN_cmp(k, tmp) == 0);
+ if (ret == 0)
+ RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST, RSA_R_PAIRWISE_TEST_FAILURE);
+err:
+ BN_CTX_end(ctx);
+ return ret;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-08 13:59:06 +0100