2 * Copyright 2018-2021 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 "crypto/bn.h"
15 #include "crypto/security_bits.h"
16 #include "rsa_local.h"
18 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
19 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
20 #define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
23 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
24 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
28 * rsa Object used to store primes p & q.
29 * test Object used for CAVS testing only.that contains..
30 * p1, p2 The returned auxiliary primes for p.
31 * If NULL they are not returned.
32 * Xpout An optionally returned random number used during generation of p.
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 * Xqout An optionally returned random number used during generation of q.
41 * Xq An optional passed in value (that is random number used during
43 * Xq1, Xq2 Optionally passed in randomly generated numbers from which
44 * auxiliary primes q1 & q2 are calculated. If NULL these values
45 * are generated internally.
46 * nbits The key size in bits (The size of the modulus n).
47 * e The public exponent.
48 * ctx A BN_CTX object.
49 * cb An optional BIGNUM callback.
50 * Returns: 1 if successful, or 0 otherwise.
52 * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
53 * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
54 * (Required for CAVS testing).
56 int ossl_rsa_fips186_4_gen_prob_primes(RSA
*rsa
, RSA_ACVP_TEST
*test
,
57 int nbits
, const BIGNUM
*e
, BN_CTX
*ctx
,
61 /* Temp allocated BIGNUMS */
62 BIGNUM
*Xpo
= NULL
, *Xqo
= NULL
, *tmp
= NULL
;
63 /* Intermediate BIGNUMS that can be returned for testing */
64 BIGNUM
*p1
= NULL
, *p2
= NULL
;
65 BIGNUM
*q1
= NULL
, *q2
= NULL
;
66 /* Intermediate BIGNUMS that can be input for testing */
67 BIGNUM
*Xpout
= NULL
, *Xqout
= NULL
;
68 BIGNUM
*Xp
= NULL
, *Xp1
= NULL
, *Xp2
= NULL
;
69 BIGNUM
*Xq
= NULL
, *Xq1
= NULL
, *Xq2
= NULL
;
71 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
86 /* (Step 1) Check key length
87 * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
88 * Signature Generation and Key Agree/Transport.
90 if (nbits
< RSA_FIPS1864_MIN_KEYGEN_KEYSIZE
) {
91 ERR_raise(ERR_LIB_RSA
, RSA_R_KEY_SIZE_TOO_SMALL
);
95 if (!ossl_rsa_check_public_exponent(e
)) {
96 ERR_raise(ERR_LIB_RSA
, RSA_R_PUB_EXPONENT_OUT_OF_RANGE
);
100 /* (Step 3) Determine strength and check rand generator strength is ok -
101 * this step is redundant because the generator always returns a higher
102 * strength than is required.
106 tmp
= BN_CTX_get(ctx
);
107 Xpo
= (Xpout
!= NULL
) ? Xpout
: BN_CTX_get(ctx
);
108 Xqo
= (Xqout
!= NULL
) ? Xqout
: BN_CTX_get(ctx
);
109 if (tmp
== NULL
|| Xpo
== NULL
|| Xqo
== NULL
)
111 BN_set_flags(Xpo
, BN_FLG_CONSTTIME
);
112 BN_set_flags(Xqo
, BN_FLG_CONSTTIME
);
115 rsa
->p
= BN_secure_new();
117 rsa
->q
= BN_secure_new();
118 if (rsa
->p
== NULL
|| rsa
->q
== NULL
)
120 BN_set_flags(rsa
->p
, BN_FLG_CONSTTIME
);
121 BN_set_flags(rsa
->q
, BN_FLG_CONSTTIME
);
123 /* (Step 4) Generate p, Xp */
124 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa
->p
, Xpo
, p1
, p2
, Xp
, Xp1
, Xp2
,
128 /* (Step 5) Generate q, Xq*/
129 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa
->q
, Xqo
, q1
, q2
, Xq
, Xq1
,
130 Xq2
, nbits
, e
, ctx
, cb
))
133 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
134 ok
= ossl_rsa_check_pminusq_diff(tmp
, Xpo
, Xqo
, nbits
);
140 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
141 ok
= ossl_rsa_check_pminusq_diff(tmp
, rsa
->p
, rsa
->q
, nbits
);
146 break; /* successfully finished */
151 /* Zeroize any internally generated values that are not returned */
163 * Validates the RSA key size based on the target strength.
164 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
167 * nbits The key size in bits.
168 * strength The target strength in bits. -1 means the target
169 * strength is unknown.
170 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
172 int ossl_rsa_sp800_56b_validate_strength(int nbits
, int strength
)
174 int s
= (int)ifc_ffc_compute_security_bits(nbits
);
176 if (s
< RSA_FIPS1864_MIN_KEYGEN_STRENGTH
177 || s
> RSA_FIPS1864_MAX_KEYGEN_STRENGTH
) {
178 ERR_raise(ERR_LIB_RSA
, RSA_R_INVALID_MODULUS
);
182 if (strength
!= -1 && s
!= strength
) {
183 ERR_raise(ERR_LIB_RSA
, RSA_R_INVALID_STRENGTH
);
191 * Using p & q, calculate other required parameters such as n, d.
192 * as well as the CRT parameters dP, dQ, qInv.
195 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
196 * 6.3.1.3 rsakpg1 - crt (Step 5)
200 * nbits The key size.
201 * e The public exponent.
202 * ctx A BN_CTX object.
204 * There is a small chance that the generated d will be too small.
205 * Returns: -1 = error,
206 * 0 = d is too small,
209 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA
*rsa
, int nbits
,
210 const BIGNUM
*e
, BN_CTX
*ctx
)
213 BIGNUM
*p1
, *q1
, *lcm
, *p1q1
, *gcd
;
216 p1
= BN_CTX_get(ctx
);
217 q1
= BN_CTX_get(ctx
);
218 lcm
= BN_CTX_get(ctx
);
219 p1q1
= BN_CTX_get(ctx
);
220 gcd
= BN_CTX_get(ctx
);
224 BN_set_flags(p1
, BN_FLG_CONSTTIME
);
225 BN_set_flags(q1
, BN_FLG_CONSTTIME
);
226 BN_set_flags(lcm
, BN_FLG_CONSTTIME
);
227 BN_set_flags(p1q1
, BN_FLG_CONSTTIME
);
228 BN_set_flags(gcd
, BN_FLG_CONSTTIME
);
230 /* LCM((p-1, q-1)) */
231 if (ossl_rsa_get_lcm(ctx
, rsa
->p
, rsa
->q
, lcm
, gcd
, p1
, q1
, p1q1
) != 1)
240 BN_clear_free(rsa
->d
);
241 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
242 rsa
->d
= BN_secure_new();
245 BN_set_flags(rsa
->d
, BN_FLG_CONSTTIME
);
246 if (BN_mod_inverse(rsa
->d
, e
, lcm
, ctx
) == NULL
)
249 /* (Step 3) return an error if d is too small */
250 if (BN_num_bits(rsa
->d
) <= (nbits
>> 1)) {
255 /* (Step 4) n = pq */
258 if (rsa
->n
== NULL
|| !BN_mul(rsa
->n
, rsa
->p
, rsa
->q
, ctx
))
261 /* (Step 5a) dP = d mod (p-1) */
262 if (rsa
->dmp1
== NULL
)
263 rsa
->dmp1
= BN_secure_new();
264 if (rsa
->dmp1
== NULL
)
266 BN_set_flags(rsa
->dmp1
, BN_FLG_CONSTTIME
);
267 if (!BN_mod(rsa
->dmp1
, rsa
->d
, p1
, ctx
))
270 /* (Step 5b) dQ = d mod (q-1) */
271 if (rsa
->dmq1
== NULL
)
272 rsa
->dmq1
= BN_secure_new();
273 if (rsa
->dmq1
== NULL
)
275 BN_set_flags(rsa
->dmq1
, BN_FLG_CONSTTIME
);
276 if (!BN_mod(rsa
->dmq1
, rsa
->d
, q1
, ctx
))
279 /* (Step 5c) qInv = (inverse of q) mod p */
281 rsa
->iqmp
= BN_secure_new();
282 if (rsa
->iqmp
== NULL
)
284 BN_set_flags(rsa
->iqmp
, BN_FLG_CONSTTIME
);
285 if (BN_mod_inverse(rsa
->iqmp
, rsa
->q
, rsa
->p
, ctx
) == NULL
)
316 * Generate a SP800-56B RSA key.
318 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
319 * 6.3.1.1 rsakpg1 - basic
320 * 6.3.1.3 rsakpg1 - crt
322 * See also FIPS 186-4 Section B.3.6
323 * "Generation of Probable Primes with Conditions Based on Auxiliary
327 * rsa The rsa object.
328 * nbits The intended key size in bits.
329 * efixed The public exponent. If NULL a default of 65537 is used.
330 * cb An optional BIGNUM callback.
331 * Returns: 1 if successfully generated otherwise it returns 0.
333 int ossl_rsa_sp800_56b_generate_key(RSA
*rsa
, int nbits
, const BIGNUM
*efixed
,
340 RSA_ACVP_TEST
*info
= NULL
;
342 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
343 info
= rsa
->acvp_test
;
346 /* (Steps 1a-1b) : Currently ignores the strength check */
347 if (!ossl_rsa_sp800_56b_validate_strength(nbits
, -1))
350 ctx
= BN_CTX_new_ex(rsa
->libctx
);
354 /* Set default if e is not passed in */
355 if (efixed
== NULL
) {
357 if (e
== NULL
|| !BN_set_word(e
, 65537))
360 e
= (BIGNUM
*)efixed
;
362 /* (Step 1c) fixed exponent is checked later .*/
365 /* (Step 2) Generate prime factors */
366 if (!ossl_rsa_fips186_4_gen_prob_primes(rsa
, info
, nbits
, e
, ctx
, cb
))
368 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
369 ok
= ossl_rsa_sp800_56b_derive_params_from_pq(rsa
, nbits
, e
, ctx
);
374 /* Gets here if computed d is too small - so try again */
377 /* (Step 6) Do pairwise test - optional validity test has been omitted */
378 ret
= ossl_rsa_sp800_56b_pairwise_test(rsa
, ctx
);
387 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
388 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
390 * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
392 int ossl_rsa_sp800_56b_pairwise_test(RSA
*rsa
, BN_CTX
*ctx
)
398 tmp
= BN_CTX_get(ctx
);
402 BN_set_flags(k
, BN_FLG_CONSTTIME
);
404 ret
= (BN_set_word(k
, 2)
405 && BN_mod_exp(tmp
, k
, rsa
->e
, rsa
->n
, ctx
)
406 && BN_mod_exp(tmp
, tmp
, rsa
->d
, rsa
->n
, ctx
)
407 && BN_cmp(k
, tmp
) == 0);
409 ERR_raise(ERR_LIB_RSA
, RSA_R_PAIRWISE_TEST_FAILURE
);