/* * Copyright 2018-2021 The OpenSSL Project Authors. All Rights Reserved. * Copyright (c) 2018-2019, Oracle and/or its affiliates. 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 * in the file LICENSE in the source distribution or at * https://www.openssl.org/source/license.html */ #include #include #include #include #include #include "crypto/bn.h" #include "crypto/security_bits.h" #include "rsa_local.h" #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112 /* * 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. * test Object used for CAVS testing only.that contains.. * 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 ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test, int nbits, const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb) { int ret = 0, ok; /* Temp allocated BIGNUMS */ BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL; /* Intermediate BIGNUMS that can be returned for testing */ BIGNUM *p1 = NULL, *p2 = NULL; BIGNUM *q1 = NULL, *q2 = NULL; /* Intermediate BIGNUMS that can be input for testing */ BIGNUM *Xpout = NULL, *Xqout = NULL; BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL; BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL; #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) if (test != NULL) { Xp1 = test->Xp1; Xp2 = test->Xp2; Xq1 = test->Xq1; Xq2 = test->Xq2; Xp = test->Xp; Xq = test->Xq; p1 = test->p1; p2 = test->p2; q1 = test->q1; q2 = test->q2; } #endif /* (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) { ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL); return 0; } if (!ossl_rsa_check_public_exponent(e)) { ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE); return 0; } /* (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; BN_set_flags(Xpo, BN_FLG_CONSTTIME); BN_set_flags(Xqo, BN_FLG_CONSTTIME); 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; BN_set_flags(rsa->p, BN_FLG_CONSTTIME); BN_set_flags(rsa->q, BN_FLG_CONSTTIME); /* (Step 4) Generate p, Xp */ if (!ossl_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 (!ossl_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 = ossl_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 = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits); if (ok < 0) goto err; if (ok == 0) continue; break; /* successfully finished */ } rsa->dirty_cnt++; 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 ossl_rsa_sp800_56b_validate_strength(int nbits, int strength) { int s = (int)ossl_ifc_ffc_compute_security_bits(nbits); #ifdef FIPS_MODULE if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH) { ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS); return 0; } #endif if (strength != -1 && s != strength) { ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH); return 0; } return 1; } /* * Validate that the random bit generator is of sufficient strength to generate * a key of the specified length. */ static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits) { if (rng == NULL) return 0; #ifdef FIPS_MODULE /* * This should become mainstream once similar tests are added to the other * key generations and once there is a way to disable these checks. */ if (EVP_RAND_get_strength(rng) < ossl_ifc_ffc_compute_security_bits(nbits)) { ERR_raise(ERR_LIB_RSA, RSA_R_RANDOMNESS_SOURCE_STRENGTH_INSUFFICIENT); return 0; } #endif 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 ossl_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; BN_set_flags(p1, BN_FLG_CONSTTIME); BN_set_flags(q1, BN_FLG_CONSTTIME); BN_set_flags(lcm, BN_FLG_CONSTTIME); BN_set_flags(p1q1, BN_FLG_CONSTTIME); BN_set_flags(gcd, BN_FLG_CONSTTIME); /* LCM((p-1, q-1)) */ if (ossl_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) goto err; BN_set_flags(rsa->d, BN_FLG_CONSTTIME); if (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_secure_new(); if (rsa->dmp1 == NULL) goto err; BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME); if (!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) goto err; BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME); if (!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) goto err; BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME); if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL) goto err; rsa->dirty_cnt++; 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 ossl_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; RSA_ACVP_TEST *info = NULL; #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) info = rsa->acvp_test; #endif /* (Steps 1a-1b) : Currently ignores the strength check */ if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1)) return 0; /* Check that the RNG is capable of generating a key this large */ if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits)) return 0; ctx = BN_CTX_new_ex(rsa->libctx); 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 (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb)) goto err; /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */ ok = ossl_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 = ossl_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 ossl_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; BN_set_flags(k, BN_FLG_CONSTTIME); 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) ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE); err: BN_CTX_end(ctx); return ret; }