2 * Copyright 2018-2020 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 "crypto/bn.h"
14 #include "crypto/security_bits.h"
15 #include "rsa_local.h"
17 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
18 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
19 #define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
22 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
23 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
27 * rsa Object used to store primes p & q.
28 * p1, p2 The returned auxiliary primes for p. If NULL they are not returned.
29 * Xpout An optionally returned random number used during generation of p.
30 * Xp An optional passed in value (that is random number used during
32 * Xp1, Xp2 Optionally passed in randomly generated numbers from which
33 * auxiliary primes p1 & p2 are calculated. If NULL these values
34 * are generated internally.
35 * q1, q2 The returned auxiliary primes for q. If NULL they are not returned.
36 * Xqout An optionally returned random number used during generation of q.
37 * Xq An optional passed in value (that is random number used during
39 * Xq1, Xq2 Optionally passed in randomly generated numbers from which
40 * auxiliary primes q1 & q2 are calculated. If NULL these values
41 * are generated internally.
42 * nbits The key size in bits (The size of the modulus n).
43 * e The public exponent.
44 * ctx A BN_CTX object.
45 * cb An optional BIGNUM callback.
46 * Returns: 1 if successful, or 0 otherwise.
48 * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
49 * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
50 * (Required for CAVS testing).
52 int rsa_fips186_4_gen_prob_primes(RSA
*rsa
, BIGNUM
*p1
, BIGNUM
*p2
,
53 BIGNUM
*Xpout
, const BIGNUM
*Xp
,
54 const BIGNUM
*Xp1
, const BIGNUM
*Xp2
,
55 BIGNUM
*q1
, BIGNUM
*q2
, BIGNUM
*Xqout
,
56 const BIGNUM
*Xq
, const BIGNUM
*Xq1
,
57 const BIGNUM
*Xq2
, int nbits
,
58 const BIGNUM
*e
, BN_CTX
*ctx
, BN_GENCB
*cb
)
61 BIGNUM
*Xpo
= NULL
, *Xqo
= NULL
, *tmp
= NULL
;
63 /* (Step 1) Check key length
64 * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
65 * Signature Generation and Key Agree/Transport.
67 if (nbits
< RSA_FIPS1864_MIN_KEYGEN_KEYSIZE
) {
68 RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES
, RSA_R_INVALID_KEY_LENGTH
);
72 if (!rsa_check_public_exponent(e
)) {
73 RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES
,
74 RSA_R_PUB_EXPONENT_OUT_OF_RANGE
);
78 /* (Step 3) Determine strength and check rand generator strength is ok -
79 * this step is redundant because the generator always returns a higher
80 * strength than is required.
84 tmp
= BN_CTX_get(ctx
);
85 Xpo
= (Xpout
!= NULL
) ? Xpout
: BN_CTX_get(ctx
);
86 Xqo
= (Xqout
!= NULL
) ? Xqout
: BN_CTX_get(ctx
);
87 if (tmp
== NULL
|| Xpo
== NULL
|| Xqo
== NULL
)
91 rsa
->p
= BN_secure_new();
93 rsa
->q
= BN_secure_new();
94 if (rsa
->p
== NULL
|| rsa
->q
== NULL
)
97 /* (Step 4) Generate p, Xp */
98 if (!bn_rsa_fips186_4_gen_prob_primes(rsa
->p
, Xpo
, p1
, p2
, Xp
, Xp1
, Xp2
,
102 /* (Step 5) Generate q, Xq*/
103 if (!bn_rsa_fips186_4_gen_prob_primes(rsa
->q
, Xqo
, q1
, q2
, Xq
, Xq1
,
104 Xq2
, nbits
, e
, ctx
, cb
))
107 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
108 ok
= rsa_check_pminusq_diff(tmp
, Xpo
, Xqo
, nbits
);
114 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
115 ok
= rsa_check_pminusq_diff(tmp
, rsa
->p
, rsa
->q
, nbits
);
120 break; /* successfully finished */
125 /* Zeroize any internally generated values that are not returned */
137 * Validates the RSA key size based on the target strength.
138 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
141 * nbits The key size in bits.
142 * strength The target strength in bits. -1 means the target
143 * strength is unknown.
144 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
146 int rsa_sp800_56b_validate_strength(int nbits
, int strength
)
148 int s
= (int)ifc_ffc_compute_security_bits(nbits
);
150 if (s
< RSA_FIPS1864_MIN_KEYGEN_STRENGTH
151 || s
> RSA_FIPS1864_MAX_KEYGEN_STRENGTH
) {
152 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH
, RSA_R_INVALID_MODULUS
);
155 if (strength
!= -1 && s
!= strength
) {
156 RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH
, RSA_R_INVALID_STRENGTH
);
164 * Using p & q, calculate other required parameters such as n, d.
165 * as well as the CRT parameters dP, dQ, qInv.
168 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
169 * 6.3.1.3 rsakpg1 - crt (Step 5)
173 * nbits The key size.
174 * e The public exponent.
175 * ctx A BN_CTX object.
177 * There is a small chance that the generated d will be too small.
178 * Returns: -1 = error,
179 * 0 = d is too small,
182 int rsa_sp800_56b_derive_params_from_pq(RSA
*rsa
, int nbits
,
183 const BIGNUM
*e
, BN_CTX
*ctx
)
186 BIGNUM
*p1
, *q1
, *lcm
, *p1q1
, *gcd
;
189 p1
= BN_CTX_get(ctx
);
190 q1
= BN_CTX_get(ctx
);
191 lcm
= BN_CTX_get(ctx
);
192 p1q1
= BN_CTX_get(ctx
);
193 gcd
= BN_CTX_get(ctx
);
197 /* LCM((p-1, q-1)) */
198 if (rsa_get_lcm(ctx
, rsa
->p
, rsa
->q
, lcm
, gcd
, p1
, q1
, p1q1
) != 1)
207 BN_clear_free(rsa
->d
);
208 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
209 rsa
->d
= BN_secure_new();
210 if (rsa
->d
== NULL
|| BN_mod_inverse(rsa
->d
, e
, lcm
, ctx
) == NULL
)
213 /* (Step 3) return an error if d is too small */
214 if (BN_num_bits(rsa
->d
) <= (nbits
>> 1)) {
219 /* (Step 4) n = pq */
222 if (rsa
->n
== NULL
|| !BN_mul(rsa
->n
, rsa
->p
, rsa
->q
, ctx
))
225 /* (Step 5a) dP = d mod (p-1) */
226 if (rsa
->dmp1
== NULL
)
227 rsa
->dmp1
= BN_new();
228 if (rsa
->dmp1
== NULL
|| !BN_mod(rsa
->dmp1
, rsa
->d
, p1
, ctx
))
231 /* (Step 5b) dQ = d mod (q-1) */
232 if (rsa
->dmq1
== NULL
)
233 rsa
->dmq1
= BN_secure_new();
234 if (rsa
->dmq1
== NULL
|| !BN_mod(rsa
->dmq1
, rsa
->d
, q1
, ctx
))
237 /* (Step 5c) qInv = (inverse of q) mod p */
239 rsa
->iqmp
= BN_secure_new();
240 if (rsa
->iqmp
== NULL
241 || BN_mod_inverse(rsa
->iqmp
, rsa
->q
, rsa
->p
, ctx
) == NULL
)
272 * Generate a SP800-56B RSA key.
274 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
275 * 6.3.1.1 rsakpg1 - basic
276 * 6.3.1.3 rsakpg1 - crt
278 * See also FIPS 186-4 Section B.3.6
279 * "Generation of Probable Primes with Conditions Based on Auxiliary
283 * rsa The rsa object.
284 * nbits The intended key size in bits.
285 * efixed The public exponent. If NULL a default of 65537 is used.
286 * cb An optional BIGNUM callback.
287 * Returns: 1 if successfully generated otherwise it returns 0.
289 int rsa_sp800_56b_generate_key(RSA
*rsa
, int nbits
, const BIGNUM
*efixed
,
297 /* (Steps 1a-1b) : Currently ignores the strength check */
298 if (!rsa_sp800_56b_validate_strength(nbits
, -1))
301 ctx
= BN_CTX_new_ex(rsa
->libctx
);
305 /* Set default if e is not passed in */
306 if (efixed
== NULL
) {
308 if (e
== NULL
|| !BN_set_word(e
, 65537))
311 e
= (BIGNUM
*)efixed
;
313 /* (Step 1c) fixed exponent is checked later . */
316 /* (Step 2) Generate prime factors */
317 if (!rsa_fips186_4_gen_prob_primes(rsa
, NULL
, NULL
, NULL
, NULL
, NULL
,
318 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
319 NULL
, nbits
, e
, ctx
, cb
))
321 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
322 ok
= rsa_sp800_56b_derive_params_from_pq(rsa
, nbits
, e
, ctx
);
327 /* Gets here if computed d is too small - so try again */
330 /* (Step 6) Do pairwise test - optional validity test has been omitted */
331 ret
= rsa_sp800_56b_pairwise_test(rsa
, ctx
);
340 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
341 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
343 * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
345 int rsa_sp800_56b_pairwise_test(RSA
*rsa
, BN_CTX
*ctx
)
351 tmp
= BN_CTX_get(ctx
);
356 ret
= (BN_set_word(k
, 2)
357 && BN_mod_exp(tmp
, k
, rsa
->e
, rsa
->n
, ctx
)
358 && BN_mod_exp(tmp
, tmp
, rsa
->d
, rsa
->n
, ctx
)
359 && BN_cmp(k
, tmp
) == 0);
361 RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST
, RSA_R_PAIRWISE_TEST_FAILURE
);