]>
Commit | Line | Data |
---|---|---|
8240d5fa | 1 | /* |
8020d79b | 2 | * Copyright 2018-2021 The OpenSSL Project Authors. All Rights Reserved. |
8240d5fa SL |
3 | * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved. |
4 | * | |
a6ed19dc | 5 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
8240d5fa SL |
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 | |
9 | */ | |
10 | ||
11 | #include <openssl/err.h> | |
12 | #include <openssl/bn.h> | |
4f2271d5 | 13 | #include <openssl/core.h> |
476798f2 P |
14 | #include <openssl/evp.h> |
15 | #include <openssl/rand.h> | |
25f2138b | 16 | #include "crypto/bn.h" |
55f02cb6 | 17 | #include "crypto/security_bits.h" |
706457b7 | 18 | #include "rsa_local.h" |
8240d5fa SL |
19 | |
20 | #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048 | |
21 | #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112 | |
8240d5fa SL |
22 | |
23 | /* | |
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 | |
26 | * Primes". | |
27 | * | |
28 | * Params: | |
29 | * rsa Object used to store primes p & q. | |
4f2271d5 SL |
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 | * Xpout An optionally returned random number used during generation of p. | |
34 | * Xp An optional passed in value (that is random number used during | |
35 | * generation of p). | |
36 | * Xp1, Xp2 Optionally passed in randomly generated numbers from which | |
37 | * auxiliary primes p1 & p2 are calculated. If NULL these values | |
38 | * are generated internally. | |
39 | * q1, q2 The returned auxiliary primes for q. | |
40 | * If NULL they are not returned. | |
41 | * Xqout An optionally returned random number used during generation of q. | |
42 | * Xq An optional passed in value (that is random number used during | |
43 | * generation of q). | |
44 | * Xq1, Xq2 Optionally passed in randomly generated numbers from which | |
45 | * auxiliary primes q1 & q2 are calculated. If NULL these values | |
46 | * are generated internally. | |
8240d5fa SL |
47 | * nbits The key size in bits (The size of the modulus n). |
48 | * e The public exponent. | |
49 | * ctx A BN_CTX object. | |
50 | * cb An optional BIGNUM callback. | |
51 | * Returns: 1 if successful, or 0 otherwise. | |
52 | * Notes: | |
53 | * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL. | |
54 | * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in. | |
55 | * (Required for CAVS testing). | |
56 | */ | |
23b2fc0b P |
57 | int ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test, |
58 | int nbits, const BIGNUM *e, BN_CTX *ctx, | |
59 | BN_GENCB *cb) | |
8240d5fa SL |
60 | { |
61 | int ret = 0, ok; | |
4f2271d5 | 62 | /* Temp allocated BIGNUMS */ |
8240d5fa | 63 | BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL; |
4f2271d5 SL |
64 | /* Intermediate BIGNUMS that can be returned for testing */ |
65 | BIGNUM *p1 = NULL, *p2 = NULL; | |
66 | BIGNUM *q1 = NULL, *q2 = NULL; | |
67 | /* Intermediate BIGNUMS that can be input for testing */ | |
68 | BIGNUM *Xpout = NULL, *Xqout = NULL; | |
69 | BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL; | |
70 | BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL; | |
71 | ||
72 | #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) | |
73 | if (test != NULL) { | |
74 | Xp1 = test->Xp1; | |
75 | Xp2 = test->Xp2; | |
76 | Xq1 = test->Xq1; | |
77 | Xq2 = test->Xq2; | |
78 | Xp = test->Xp; | |
79 | Xq = test->Xq; | |
80 | p1 = test->p1; | |
81 | p2 = test->p2; | |
82 | q1 = test->q1; | |
83 | q2 = test->q2; | |
84 | } | |
85 | #endif | |
8240d5fa SL |
86 | |
87 | /* (Step 1) Check key length | |
88 | * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA | |
89 | * Signature Generation and Key Agree/Transport. | |
90 | */ | |
91 | if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) { | |
9311d0c4 | 92 | ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL); |
8240d5fa SL |
93 | return 0; |
94 | } | |
95 | ||
23b2fc0b | 96 | if (!ossl_rsa_check_public_exponent(e)) { |
9311d0c4 | 97 | ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE); |
952abb15 | 98 | return 0; |
8240d5fa SL |
99 | } |
100 | ||
101 | /* (Step 3) Determine strength and check rand generator strength is ok - | |
102 | * this step is redundant because the generator always returns a higher | |
103 | * strength than is required. | |
104 | */ | |
105 | ||
106 | BN_CTX_start(ctx); | |
107 | tmp = BN_CTX_get(ctx); | |
108 | Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx); | |
109 | Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx); | |
110 | if (tmp == NULL || Xpo == NULL || Xqo == NULL) | |
111 | goto err; | |
d4bf0d57 NT |
112 | BN_set_flags(Xpo, BN_FLG_CONSTTIME); |
113 | BN_set_flags(Xqo, BN_FLG_CONSTTIME); | |
8240d5fa SL |
114 | |
115 | if (rsa->p == NULL) | |
116 | rsa->p = BN_secure_new(); | |
117 | if (rsa->q == NULL) | |
118 | rsa->q = BN_secure_new(); | |
119 | if (rsa->p == NULL || rsa->q == NULL) | |
120 | goto err; | |
d4bf0d57 NT |
121 | BN_set_flags(rsa->p, BN_FLG_CONSTTIME); |
122 | BN_set_flags(rsa->q, BN_FLG_CONSTTIME); | |
8240d5fa SL |
123 | |
124 | /* (Step 4) Generate p, Xp */ | |
94553e85 SL |
125 | if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2, |
126 | nbits, e, ctx, cb)) | |
8240d5fa | 127 | goto err; |
1287dabd | 128 | for (;;) { |
8240d5fa | 129 | /* (Step 5) Generate q, Xq*/ |
94553e85 SL |
130 | if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1, |
131 | Xq2, nbits, e, ctx, cb)) | |
8240d5fa SL |
132 | goto err; |
133 | ||
134 | /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */ | |
23b2fc0b | 135 | ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits); |
8240d5fa SL |
136 | if (ok < 0) |
137 | goto err; | |
138 | if (ok == 0) | |
139 | continue; | |
140 | ||
141 | /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */ | |
23b2fc0b | 142 | ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits); |
8240d5fa SL |
143 | if (ok < 0) |
144 | goto err; | |
145 | if (ok == 0) | |
146 | continue; | |
147 | break; /* successfully finished */ | |
148 | } | |
29be6023 | 149 | rsa->dirty_cnt++; |
8240d5fa SL |
150 | ret = 1; |
151 | err: | |
152 | /* Zeroize any internally generated values that are not returned */ | |
153 | if (Xpo != Xpout) | |
154 | BN_clear(Xpo); | |
155 | if (Xqo != Xqout) | |
156 | BN_clear(Xqo); | |
157 | BN_clear(tmp); | |
158 | ||
159 | BN_CTX_end(ctx); | |
160 | return ret; | |
161 | } | |
162 | ||
163 | /* | |
164 | * Validates the RSA key size based on the target strength. | |
165 | * See SP800-56Br1 6.3.1.1 (Steps 1a-1b) | |
166 | * | |
167 | * Params: | |
168 | * nbits The key size in bits. | |
169 | * strength The target strength in bits. -1 means the target | |
170 | * strength is unknown. | |
171 | * Returns: 1 if the key size matches the target strength, or 0 otherwise. | |
172 | */ | |
23b2fc0b | 173 | int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength) |
8240d5fa | 174 | { |
9500c823 SL |
175 | int s = (int)ossl_ifc_ffc_compute_security_bits(nbits); |
176 | ||
8bf37709 | 177 | #ifdef FIPS_MODULE |
0c05fda4 | 178 | if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH) { |
9311d0c4 | 179 | ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS); |
8240d5fa SL |
180 | return 0; |
181 | } | |
8bf37709 | 182 | #endif |
8240d5fa | 183 | if (strength != -1 && s != strength) { |
9311d0c4 | 184 | ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH); |
8240d5fa SL |
185 | return 0; |
186 | } | |
187 | return 1; | |
188 | } | |
189 | ||
476798f2 P |
190 | /* |
191 | * Validate that the random bit generator is of sufficient strength to generate | |
192 | * a key of the specified length. | |
193 | */ | |
194 | static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits) | |
195 | { | |
196 | if (rng == NULL) | |
197 | return 0; | |
64360304 P |
198 | #ifdef FIPS_MODULE |
199 | /* | |
200 | * This should become mainstream once similar tests are added to the other | |
201 | * key generations and once there is a way to disable these checks. | |
202 | */ | |
ed576acd | 203 | if (EVP_RAND_get_strength(rng) < ossl_ifc_ffc_compute_security_bits(nbits)) { |
476798f2 P |
204 | ERR_raise(ERR_LIB_RSA, |
205 | RSA_R_RANDOMNESS_SOURCE_STRENGTH_INSUFFICIENT); | |
206 | return 0; | |
207 | } | |
64360304 | 208 | #endif |
476798f2 P |
209 | return 1; |
210 | } | |
211 | ||
8240d5fa SL |
212 | /* |
213 | * | |
214 | * Using p & q, calculate other required parameters such as n, d. | |
215 | * as well as the CRT parameters dP, dQ, qInv. | |
216 | * | |
217 | * See SP800-56Br1 | |
218 | * 6.3.1.1 rsakpg1 - basic (Steps 3-4) | |
219 | * 6.3.1.3 rsakpg1 - crt (Step 5) | |
220 | * | |
221 | * Params: | |
222 | * rsa An rsa object. | |
223 | * nbits The key size. | |
224 | * e The public exponent. | |
225 | * ctx A BN_CTX object. | |
226 | * Notes: | |
227 | * There is a small chance that the generated d will be too small. | |
228 | * Returns: -1 = error, | |
229 | * 0 = d is too small, | |
230 | * 1 = success. | |
231 | */ | |
23b2fc0b P |
232 | int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits, |
233 | const BIGNUM *e, BN_CTX *ctx) | |
8240d5fa SL |
234 | { |
235 | int ret = -1; | |
236 | BIGNUM *p1, *q1, *lcm, *p1q1, *gcd; | |
237 | ||
238 | BN_CTX_start(ctx); | |
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); | |
244 | if (gcd == NULL) | |
245 | goto err; | |
246 | ||
d4bf0d57 NT |
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); | |
252 | ||
8240d5fa | 253 | /* LCM((p-1, q-1)) */ |
23b2fc0b | 254 | if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1) |
8240d5fa SL |
255 | goto err; |
256 | ||
257 | /* copy e */ | |
258 | BN_free(rsa->e); | |
259 | rsa->e = BN_dup(e); | |
260 | if (rsa->e == NULL) | |
261 | goto err; | |
262 | ||
263 | BN_clear_free(rsa->d); | |
264 | /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */ | |
265 | rsa->d = BN_secure_new(); | |
d4bf0d57 NT |
266 | if (rsa->d == NULL) |
267 | goto err; | |
268 | BN_set_flags(rsa->d, BN_FLG_CONSTTIME); | |
269 | if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL) | |
8240d5fa SL |
270 | goto err; |
271 | ||
272 | /* (Step 3) return an error if d is too small */ | |
273 | if (BN_num_bits(rsa->d) <= (nbits >> 1)) { | |
274 | ret = 0; | |
275 | goto err; | |
276 | } | |
277 | ||
278 | /* (Step 4) n = pq */ | |
279 | if (rsa->n == NULL) | |
280 | rsa->n = BN_new(); | |
281 | if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx)) | |
282 | goto err; | |
283 | ||
284 | /* (Step 5a) dP = d mod (p-1) */ | |
285 | if (rsa->dmp1 == NULL) | |
d4bf0d57 NT |
286 | rsa->dmp1 = BN_secure_new(); |
287 | if (rsa->dmp1 == NULL) | |
555fea85 | 288 | goto err; |
d4bf0d57 NT |
289 | BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME); |
290 | if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx)) | |
8240d5fa SL |
291 | goto err; |
292 | ||
293 | /* (Step 5b) dQ = d mod (q-1) */ | |
294 | if (rsa->dmq1 == NULL) | |
295 | rsa->dmq1 = BN_secure_new(); | |
d4bf0d57 | 296 | if (rsa->dmq1 == NULL) |
555fea85 | 297 | goto err; |
d4bf0d57 NT |
298 | BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME); |
299 | if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx)) | |
8240d5fa SL |
300 | goto err; |
301 | ||
302 | /* (Step 5c) qInv = (inverse of q) mod p */ | |
303 | BN_free(rsa->iqmp); | |
304 | rsa->iqmp = BN_secure_new(); | |
d4bf0d57 | 305 | if (rsa->iqmp == NULL) |
555fea85 | 306 | goto err; |
d4bf0d57 NT |
307 | BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME); |
308 | if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL) | |
8240d5fa SL |
309 | goto err; |
310 | ||
29be6023 | 311 | rsa->dirty_cnt++; |
8240d5fa SL |
312 | ret = 1; |
313 | err: | |
314 | if (ret != 1) { | |
315 | BN_free(rsa->e); | |
316 | rsa->e = NULL; | |
317 | BN_free(rsa->d); | |
318 | rsa->d = NULL; | |
319 | BN_free(rsa->n); | |
320 | rsa->n = NULL; | |
321 | BN_free(rsa->iqmp); | |
322 | rsa->iqmp = NULL; | |
323 | BN_free(rsa->dmq1); | |
324 | rsa->dmq1 = NULL; | |
325 | BN_free(rsa->dmp1); | |
326 | rsa->dmp1 = NULL; | |
327 | } | |
328 | BN_clear(p1); | |
329 | BN_clear(q1); | |
330 | BN_clear(lcm); | |
331 | BN_clear(p1q1); | |
332 | BN_clear(gcd); | |
333 | ||
334 | BN_CTX_end(ctx); | |
335 | return ret; | |
336 | } | |
337 | ||
338 | /* | |
339 | * Generate a SP800-56B RSA key. | |
340 | * | |
341 | * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent" | |
342 | * 6.3.1.1 rsakpg1 - basic | |
343 | * 6.3.1.3 rsakpg1 - crt | |
344 | * | |
345 | * See also FIPS 186-4 Section B.3.6 | |
346 | * "Generation of Probable Primes with Conditions Based on Auxiliary | |
347 | * Probable Primes." | |
348 | * | |
349 | * Params: | |
350 | * rsa The rsa object. | |
351 | * nbits The intended key size in bits. | |
352 | * efixed The public exponent. If NULL a default of 65537 is used. | |
353 | * cb An optional BIGNUM callback. | |
354 | * Returns: 1 if successfully generated otherwise it returns 0. | |
355 | */ | |
23b2fc0b P |
356 | int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed, |
357 | BN_GENCB *cb) | |
8240d5fa SL |
358 | { |
359 | int ret = 0; | |
360 | int ok; | |
361 | BN_CTX *ctx = NULL; | |
362 | BIGNUM *e = NULL; | |
4f2271d5 SL |
363 | RSA_ACVP_TEST *info = NULL; |
364 | ||
365 | #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) | |
366 | info = rsa->acvp_test; | |
367 | #endif | |
8240d5fa SL |
368 | |
369 | /* (Steps 1a-1b) : Currently ignores the strength check */ | |
23b2fc0b | 370 | if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1)) |
8240d5fa SL |
371 | return 0; |
372 | ||
476798f2 P |
373 | /* Check that the RNG is capable of generating a key this large */ |
374 | if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits)) | |
375 | return 0; | |
376 | ||
afb638f1 | 377 | ctx = BN_CTX_new_ex(rsa->libctx); |
8240d5fa SL |
378 | if (ctx == NULL) |
379 | return 0; | |
380 | ||
381 | /* Set default if e is not passed in */ | |
382 | if (efixed == NULL) { | |
383 | e = BN_new(); | |
384 | if (e == NULL || !BN_set_word(e, 65537)) | |
385 | goto err; | |
386 | } else { | |
387 | e = (BIGNUM *)efixed; | |
388 | } | |
4f2271d5 | 389 | /* (Step 1c) fixed exponent is checked later .*/ |
8240d5fa SL |
390 | |
391 | for (;;) { | |
392 | /* (Step 2) Generate prime factors */ | |
23b2fc0b | 393 | if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb)) |
8240d5fa SL |
394 | goto err; |
395 | /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */ | |
23b2fc0b | 396 | ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx); |
8240d5fa SL |
397 | if (ok < 0) |
398 | goto err; | |
399 | if (ok > 0) | |
400 | break; | |
401 | /* Gets here if computed d is too small - so try again */ | |
402 | } | |
403 | ||
404 | /* (Step 6) Do pairwise test - optional validity test has been omitted */ | |
23b2fc0b | 405 | ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx); |
8240d5fa SL |
406 | err: |
407 | if (efixed == NULL) | |
408 | BN_free(e); | |
409 | BN_CTX_free(ctx); | |
410 | return ret; | |
411 | } | |
412 | ||
413 | /* | |
414 | * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by | |
415 | * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1. | |
416 | * | |
417 | * Returns 1 if the RSA key passes the pairwise test or 0 it it fails. | |
418 | */ | |
23b2fc0b | 419 | int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx) |
8240d5fa SL |
420 | { |
421 | int ret = 0; | |
422 | BIGNUM *k, *tmp; | |
423 | ||
424 | BN_CTX_start(ctx); | |
425 | tmp = BN_CTX_get(ctx); | |
426 | k = BN_CTX_get(ctx); | |
427 | if (k == NULL) | |
428 | goto err; | |
d4bf0d57 | 429 | BN_set_flags(k, BN_FLG_CONSTTIME); |
8240d5fa SL |
430 | |
431 | ret = (BN_set_word(k, 2) | |
555fea85 P |
432 | && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx) |
433 | && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx) | |
434 | && BN_cmp(k, tmp) == 0); | |
8240d5fa | 435 | if (ret == 0) |
9311d0c4 | 436 | ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE); |
8240d5fa SL |
437 | err: |
438 | BN_CTX_end(ctx); | |
439 | return ret; | |
440 | } |