2 * Copyright 2018-2024 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
5 * Licensed under the Apache License 2.0 (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
11 #include <openssl/err.h>
12 #include <openssl/bn.h>
13 #include <openssl/core.h>
14 #include <openssl/evp.h>
15 #include <openssl/rand.h>
16 #include "crypto/bn.h"
17 #include "crypto/security_bits.h"
18 #include "rsa_local.h"
20 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
21 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
24 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
25 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
29 * rsa Object used to store primes p & q.
30 * test Object used for CAVS testing only.that contains..
31 * p1, p2 The returned auxiliary primes for p.
32 * If NULL they are not returned.
33 * Xp An optional passed in value (that is random number used during
35 * Xp1, Xp2 Optionally passed in randomly generated numbers from which
36 * auxiliary primes p1 & p2 are calculated. If NULL these values
37 * are generated internally.
38 * q1, q2 The returned auxiliary primes for q.
39 * If NULL they are not returned.
40 * Xq An optional passed in value (that is random number used during
42 * Xq1, Xq2 Optionally passed in randomly generated numbers from which
43 * auxiliary primes q1 & q2 are calculated. If NULL these values
44 * are generated internally.
45 * nbits The key size in bits (The size of the modulus n).
46 * e The public exponent.
47 * ctx A BN_CTX object.
48 * cb An optional BIGNUM callback.
49 * Returns: 1 if successful, or 0 otherwise.
51 * p1, p2, q1, q2 are returned if they are not NULL.
52 * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
53 * (Required for CAVS testing).
55 int ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test,
56 int nbits, const BIGNUM *e, BN_CTX *ctx,
60 /* Temp allocated BIGNUMS */
61 BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
62 /* Intermediate BIGNUMS that can be returned for testing */
63 BIGNUM *p1 = NULL, *p2 = NULL;
64 BIGNUM *q1 = NULL, *q2 = NULL;
65 /* Intermediate BIGNUMS that can be input for testing */
66 BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL;
67 BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL;
69 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
84 /* (Step 1) Check key length
85 * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
86 * Signature Generation and Key Agree/Transport.
88 if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
89 ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
93 if (!ossl_rsa_check_public_exponent(e)) {
94 ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
98 /* (Step 3) Determine strength and check rand generator strength is ok -
99 * this step is redundant because the generator always returns a higher
100 * strength than is required.
104 tmp = BN_CTX_get(ctx);
105 Xpo = BN_CTX_get(ctx);
106 Xqo = BN_CTX_get(ctx);
107 if (tmp == NULL || Xpo == NULL || Xqo == NULL)
109 BN_set_flags(Xpo, BN_FLG_CONSTTIME);
110 BN_set_flags(Xqo, BN_FLG_CONSTTIME);
113 rsa->p = BN_secure_new();
115 rsa->q = BN_secure_new();
116 if (rsa->p == NULL || rsa->q == NULL)
118 BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
119 BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
121 /* (Step 4) Generate p, Xp */
122 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
126 /* (Step 5) Generate q, Xq*/
127 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
128 Xq2, nbits, e, ctx, cb))
131 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
132 ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
138 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
139 ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
144 break; /* successfully finished */
149 /* Zeroize any internally generated values that are not returned */
154 BN_clear_free(rsa->p);
156 BN_clear_free(rsa->q);
165 * Validates the RSA key size based on the target strength.
166 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
169 * nbits The key size in bits.
170 * strength The target strength in bits. -1 means the target
171 * strength is unknown.
172 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
174 int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength)
176 int s = (int)ossl_ifc_ffc_compute_security_bits(nbits);
179 if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH) {
180 ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS);
184 if (strength != -1 && s != strength) {
185 ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH);
192 * Validate that the random bit generator is of sufficient strength to generate
193 * a key of the specified length.
195 static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits)
201 * This should become mainstream once similar tests are added to the other
202 * key generations and once there is a way to disable these checks.
204 if (EVP_RAND_get_strength(rng) < ossl_ifc_ffc_compute_security_bits(nbits)) {
205 ERR_raise(ERR_LIB_RSA,
206 RSA_R_RANDOMNESS_SOURCE_STRENGTH_INSUFFICIENT);
215 * Using p & q, calculate other required parameters such as n, d.
216 * as well as the CRT parameters dP, dQ, qInv.
219 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
220 * 6.3.1.3 rsakpg1 - crt (Step 5)
224 * nbits The key size.
225 * e The public exponent.
226 * ctx A BN_CTX object.
228 * There is a small chance that the generated d will be too small.
229 * Returns: -1 = error,
230 * 0 = d is too small,
233 * SP800-56b key generation always passes a non NULL value for e.
234 * For other purposes, if e is NULL then it is assumed that e, n and d are
235 * already set in the RSA key and do not need to be recalculated.
237 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
238 const BIGNUM *e, BN_CTX *ctx)
241 BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
243 p1 = BN_CTX_get(ctx);
244 q1 = BN_CTX_get(ctx);
245 lcm = BN_CTX_get(ctx);
246 p1q1 = BN_CTX_get(ctx);
247 gcd = BN_CTX_get(ctx);
251 BN_set_flags(p1, BN_FLG_CONSTTIME);
252 BN_set_flags(q1, BN_FLG_CONSTTIME);
253 BN_set_flags(lcm, BN_FLG_CONSTTIME);
254 BN_set_flags(p1q1, BN_FLG_CONSTTIME);
255 BN_set_flags(gcd, BN_FLG_CONSTTIME);
257 /* LCM((p-1, q-1)) */
258 if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
262 * if e is provided as a parameter, don't recompute e, d or n
271 BN_clear_free(rsa->d);
272 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
273 rsa->d = BN_secure_new();
276 BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
277 if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
280 /* (Step 3) return an error if d is too small */
281 if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
286 /* (Step 4) n = pq */
289 if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
293 /* (Step 5a) dP = d mod (p-1) */
294 if (rsa->dmp1 == NULL)
295 rsa->dmp1 = BN_secure_new();
296 if (rsa->dmp1 == NULL)
298 BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
299 if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
302 /* (Step 5b) dQ = d mod (q-1) */
303 if (rsa->dmq1 == NULL)
304 rsa->dmq1 = BN_secure_new();
305 if (rsa->dmq1 == NULL)
307 BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
308 if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
311 /* (Step 5c) qInv = (inverse of q) mod p */
313 rsa->iqmp = BN_secure_new();
314 if (rsa->iqmp == NULL)
316 BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
317 if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
348 * Generate a SP800-56B RSA key.
350 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
351 * 6.3.1.1 rsakpg1 - basic
352 * 6.3.1.3 rsakpg1 - crt
354 * See also FIPS 186-4 Section B.3.6
355 * "Generation of Probable Primes with Conditions Based on Auxiliary
359 * rsa The rsa object.
360 * nbits The intended key size in bits.
361 * efixed The public exponent. If NULL a default of 65537 is used.
362 * cb An optional BIGNUM callback.
363 * Returns: 1 if successfully generated otherwise it returns 0.
365 int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
372 RSA_ACVP_TEST *info = NULL;
375 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
376 info = rsa->acvp_test;
379 /* (Steps 1a-1b) : Currently ignores the strength check */
380 if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1))
383 /* Check that the RNG is capable of generating a key this large */
384 if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits))
387 ctx = BN_CTX_new_ex(rsa->libctx);
391 /* Set default if e is not passed in */
392 if (efixed == NULL) {
394 if (e == NULL || !BN_set_word(e, 65537))
397 e = (BIGNUM *)efixed;
399 /* (Step 1c) fixed exponent is checked later .*/
402 /* (Step 2) Generate prime factors */
403 if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb))
406 /* p>q check and skipping in case of acvp test */
407 if (info == NULL && BN_cmp(rsa->p, rsa->q) < 0) {
413 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
414 ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
419 /* Gets here if computed d is too small - so try again */
422 /* (Step 6) Do pairwise test - optional validity test has been omitted */
423 ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx);
432 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
433 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
435 * Returns 1 if the RSA key passes the pairwise test or 0 if it fails.
437 int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
443 tmp = BN_CTX_get(ctx);
447 BN_set_flags(k, BN_FLG_CONSTTIME);
449 ret = (BN_set_word(k, 2)
450 && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
451 && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
452 && BN_cmp(k, tmp) == 0);
454 ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE);