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 */
161 * Validates the RSA key size based on the target strength.
162 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
165 * nbits The key size in bits.
166 * strength The target strength in bits. -1 means the target
167 * strength is unknown.
168 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
170 int ossl_rsa_sp800_56b_validate_strength(int nbits
, int strength
)
172 int s
= (int)ossl_ifc_ffc_compute_security_bits(nbits
);
175 if (s
< RSA_FIPS1864_MIN_KEYGEN_STRENGTH
) {
176 ERR_raise(ERR_LIB_RSA
, RSA_R_INVALID_MODULUS
);
180 if (strength
!= -1 && s
!= strength
) {
181 ERR_raise(ERR_LIB_RSA
, RSA_R_INVALID_STRENGTH
);
188 * Validate that the random bit generator is of sufficient strength to generate
189 * a key of the specified length.
191 static int rsa_validate_rng_strength(EVP_RAND_CTX
*rng
, int nbits
)
197 * This should become mainstream once similar tests are added to the other
198 * key generations and once there is a way to disable these checks.
200 if (EVP_RAND_get_strength(rng
) < ossl_ifc_ffc_compute_security_bits(nbits
)) {
201 ERR_raise(ERR_LIB_RSA
,
202 RSA_R_RANDOMNESS_SOURCE_STRENGTH_INSUFFICIENT
);
211 * Using p & q, calculate other required parameters such as n, d.
212 * as well as the CRT parameters dP, dQ, qInv.
215 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
216 * 6.3.1.3 rsakpg1 - crt (Step 5)
220 * nbits The key size.
221 * e The public exponent.
222 * ctx A BN_CTX object.
224 * There is a small chance that the generated d will be too small.
225 * Returns: -1 = error,
226 * 0 = d is too small,
229 * SP800-56b key generation always passes a non NULL value for e.
230 * For other purposes, if e is NULL then it is assumed that e, n and d are
231 * already set in the RSA key and do not need to be recalculated.
233 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA
*rsa
, int nbits
,
234 const BIGNUM
*e
, BN_CTX
*ctx
)
237 BIGNUM
*p1
, *q1
, *lcm
, *p1q1
, *gcd
;
239 p1
= BN_CTX_get(ctx
);
240 q1
= BN_CTX_get(ctx
);
241 lcm
= BN_CTX_get(ctx
);
242 p1q1
= BN_CTX_get(ctx
);
243 gcd
= BN_CTX_get(ctx
);
247 BN_set_flags(p1
, BN_FLG_CONSTTIME
);
248 BN_set_flags(q1
, BN_FLG_CONSTTIME
);
249 BN_set_flags(lcm
, BN_FLG_CONSTTIME
);
250 BN_set_flags(p1q1
, BN_FLG_CONSTTIME
);
251 BN_set_flags(gcd
, BN_FLG_CONSTTIME
);
253 /* LCM((p-1, q-1)) */
254 if (ossl_rsa_get_lcm(ctx
, rsa
->p
, rsa
->q
, lcm
, gcd
, p1
, q1
, p1q1
) != 1)
258 * if e is provided as a parameter, don't recompute e, d or n
267 BN_clear_free(rsa
->d
);
268 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
269 rsa
->d
= BN_secure_new();
272 BN_set_flags(rsa
->d
, BN_FLG_CONSTTIME
);
273 if (BN_mod_inverse(rsa
->d
, e
, lcm
, ctx
) == NULL
)
276 /* (Step 3) return an error if d is too small */
277 if (BN_num_bits(rsa
->d
) <= (nbits
>> 1)) {
282 /* (Step 4) n = pq */
285 if (rsa
->n
== NULL
|| !BN_mul(rsa
->n
, rsa
->p
, rsa
->q
, ctx
))
289 /* (Step 5a) dP = d mod (p-1) */
290 if (rsa
->dmp1
== NULL
)
291 rsa
->dmp1
= BN_secure_new();
292 if (rsa
->dmp1
== NULL
)
294 BN_set_flags(rsa
->dmp1
, BN_FLG_CONSTTIME
);
295 if (!BN_mod(rsa
->dmp1
, rsa
->d
, p1
, ctx
))
298 /* (Step 5b) dQ = d mod (q-1) */
299 if (rsa
->dmq1
== NULL
)
300 rsa
->dmq1
= BN_secure_new();
301 if (rsa
->dmq1
== NULL
)
303 BN_set_flags(rsa
->dmq1
, BN_FLG_CONSTTIME
);
304 if (!BN_mod(rsa
->dmq1
, rsa
->d
, q1
, ctx
))
307 /* (Step 5c) qInv = (inverse of q) mod p */
309 rsa
->iqmp
= BN_secure_new();
310 if (rsa
->iqmp
== NULL
)
312 BN_set_flags(rsa
->iqmp
, BN_FLG_CONSTTIME
);
313 if (BN_mod_inverse(rsa
->iqmp
, rsa
->q
, rsa
->p
, ctx
) == NULL
)
344 * Generate a SP800-56B RSA key.
346 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
347 * 6.3.1.1 rsakpg1 - basic
348 * 6.3.1.3 rsakpg1 - crt
350 * See also FIPS 186-4 Section B.3.6
351 * "Generation of Probable Primes with Conditions Based on Auxiliary
355 * rsa The rsa object.
356 * nbits The intended key size in bits.
357 * efixed The public exponent. If NULL a default of 65537 is used.
358 * cb An optional BIGNUM callback.
359 * Returns: 1 if successfully generated otherwise it returns 0.
361 int ossl_rsa_sp800_56b_generate_key(RSA
*rsa
, int nbits
, const BIGNUM
*efixed
,
368 RSA_ACVP_TEST
*info
= NULL
;
371 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
372 info
= rsa
->acvp_test
;
375 /* (Steps 1a-1b) : Currently ignores the strength check */
376 if (!ossl_rsa_sp800_56b_validate_strength(nbits
, -1))
379 /* Check that the RNG is capable of generating a key this large */
380 if (!rsa_validate_rng_strength(RAND_get0_private(rsa
->libctx
), nbits
))
383 ctx
= BN_CTX_new_ex(rsa
->libctx
);
387 /* Set default if e is not passed in */
388 if (efixed
== NULL
) {
390 if (e
== NULL
|| !BN_set_word(e
, 65537))
393 e
= (BIGNUM
*)efixed
;
395 /* (Step 1c) fixed exponent is checked later .*/
398 /* (Step 2) Generate prime factors */
399 if (!ossl_rsa_fips186_4_gen_prob_primes(rsa
, info
, nbits
, e
, ctx
, cb
))
402 /* p>q check and skipping in case of acvp test */
403 if (info
== NULL
&& BN_cmp(rsa
->p
, rsa
->q
) < 0) {
409 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
410 ok
= ossl_rsa_sp800_56b_derive_params_from_pq(rsa
, nbits
, e
, ctx
);
415 /* Gets here if computed d is too small - so try again */
418 /* (Step 6) Do pairwise test - optional validity test has been omitted */
419 ret
= ossl_rsa_sp800_56b_pairwise_test(rsa
, ctx
);
428 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
429 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
431 * Returns 1 if the RSA key passes the pairwise test or 0 if it fails.
433 int ossl_rsa_sp800_56b_pairwise_test(RSA
*rsa
, BN_CTX
*ctx
)
439 tmp
= BN_CTX_get(ctx
);
443 BN_set_flags(k
, BN_FLG_CONSTTIME
);
445 ret
= (BN_set_word(k
, 2)
446 && BN_mod_exp(tmp
, k
, rsa
->e
, rsa
->n
, ctx
)
447 && BN_mod_exp(tmp
, tmp
, rsa
->d
, rsa
->n
, ctx
)
448 && BN_cmp(k
, tmp
) == 0);
450 ERR_raise(ERR_LIB_RSA
, RSA_R_PAIRWISE_TEST_FAILURE
);