/src/openssl/crypto/rsa/rsa_sp800_56b_gen.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 2018-2024 The OpenSSL Project Authors. All Rights Reserved. |
3 | | * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved. |
4 | | * |
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 |
9 | | */ |
10 | | |
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" |
19 | | |
20 | 0 | #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048 |
21 | | #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112 |
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. |
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 |
34 | | * generation of p). |
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 |
41 | | * generation of q). |
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. |
50 | | * Notes: |
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). |
54 | | */ |
55 | | int ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test, |
56 | | int nbits, const BIGNUM *e, BN_CTX *ctx, |
57 | | BN_GENCB *cb) |
58 | 0 | { |
59 | 0 | int ret = 0, ok; |
60 | | /* Temp allocated BIGNUMS */ |
61 | 0 | BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL; |
62 | | /* Intermediate BIGNUMS that can be returned for testing */ |
63 | 0 | BIGNUM *p1 = NULL, *p2 = NULL; |
64 | 0 | BIGNUM *q1 = NULL, *q2 = NULL; |
65 | | /* Intermediate BIGNUMS that can be input for testing */ |
66 | 0 | BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL; |
67 | 0 | BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL; |
68 | |
|
69 | | #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) |
70 | | if (test != NULL) { |
71 | | Xp1 = test->Xp1; |
72 | | Xp2 = test->Xp2; |
73 | | Xq1 = test->Xq1; |
74 | | Xq2 = test->Xq2; |
75 | | Xp = test->Xp; |
76 | | Xq = test->Xq; |
77 | | p1 = test->p1; |
78 | | p2 = test->p2; |
79 | | q1 = test->q1; |
80 | | q2 = test->q2; |
81 | | } |
82 | | #endif |
83 | | |
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. |
87 | | */ |
88 | 0 | if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) { |
89 | 0 | ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL); |
90 | 0 | return 0; |
91 | 0 | } |
92 | | |
93 | 0 | if (!ossl_rsa_check_public_exponent(e)) { |
94 | 0 | ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE); |
95 | 0 | return 0; |
96 | 0 | } |
97 | | |
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. |
101 | | */ |
102 | | |
103 | 0 | BN_CTX_start(ctx); |
104 | 0 | tmp = BN_CTX_get(ctx); |
105 | 0 | Xpo = BN_CTX_get(ctx); |
106 | 0 | Xqo = BN_CTX_get(ctx); |
107 | 0 | if (tmp == NULL || Xpo == NULL || Xqo == NULL) |
108 | 0 | goto err; |
109 | 0 | BN_set_flags(Xpo, BN_FLG_CONSTTIME); |
110 | 0 | BN_set_flags(Xqo, BN_FLG_CONSTTIME); |
111 | |
|
112 | 0 | if (rsa->p == NULL) |
113 | 0 | rsa->p = BN_secure_new(); |
114 | 0 | if (rsa->q == NULL) |
115 | 0 | rsa->q = BN_secure_new(); |
116 | 0 | if (rsa->p == NULL || rsa->q == NULL) |
117 | 0 | goto err; |
118 | 0 | BN_set_flags(rsa->p, BN_FLG_CONSTTIME); |
119 | 0 | BN_set_flags(rsa->q, BN_FLG_CONSTTIME); |
120 | | |
121 | | /* (Step 4) Generate p, Xp */ |
122 | 0 | if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2, |
123 | 0 | nbits, e, ctx, cb)) |
124 | 0 | goto err; |
125 | 0 | for (;;) { |
126 | | /* (Step 5) Generate q, Xq*/ |
127 | 0 | if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1, |
128 | 0 | Xq2, nbits, e, ctx, cb)) |
129 | 0 | goto err; |
130 | | |
131 | | /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */ |
132 | 0 | ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits); |
133 | 0 | if (ok < 0) |
134 | 0 | goto err; |
135 | 0 | if (ok == 0) |
136 | 0 | continue; |
137 | | |
138 | | /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */ |
139 | 0 | ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits); |
140 | 0 | if (ok < 0) |
141 | 0 | goto err; |
142 | 0 | if (ok == 0) |
143 | 0 | continue; |
144 | 0 | break; /* successfully finished */ |
145 | 0 | } |
146 | 0 | rsa->dirty_cnt++; |
147 | 0 | ret = 1; |
148 | 0 | err: |
149 | | /* Zeroize any internally generated values that are not returned */ |
150 | 0 | BN_clear(Xpo); |
151 | 0 | BN_clear(Xqo); |
152 | 0 | BN_clear(tmp); |
153 | 0 | if (ret != 1) { |
154 | 0 | BN_clear_free(rsa->p); |
155 | 0 | rsa->p = NULL; |
156 | 0 | BN_clear_free(rsa->q); |
157 | 0 | rsa->q = NULL; |
158 | 0 | } |
159 | |
|
160 | 0 | BN_CTX_end(ctx); |
161 | 0 | return ret; |
162 | 0 | } |
163 | | |
164 | | /* |
165 | | * Validates the RSA key size based on the target strength. |
166 | | * See SP800-56Br1 6.3.1.1 (Steps 1a-1b) |
167 | | * |
168 | | * Params: |
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. |
173 | | */ |
174 | | int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength) |
175 | 0 | { |
176 | 0 | int s = (int)ossl_ifc_ffc_compute_security_bits(nbits); |
177 | |
|
178 | | #ifdef FIPS_MODULE |
179 | | if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH) { |
180 | | ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS); |
181 | | return 0; |
182 | | } |
183 | | #endif |
184 | 0 | if (strength != -1 && s != strength) { |
185 | 0 | ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH); |
186 | 0 | return 0; |
187 | 0 | } |
188 | 0 | return 1; |
189 | 0 | } |
190 | | |
191 | | /* |
192 | | * Validate that the random bit generator is of sufficient strength to generate |
193 | | * a key of the specified length. |
194 | | */ |
195 | | static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits) |
196 | 0 | { |
197 | 0 | if (rng == NULL) |
198 | 0 | return 0; |
199 | | #ifdef FIPS_MODULE |
200 | | /* |
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. |
203 | | */ |
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); |
207 | | return 0; |
208 | | } |
209 | | #endif |
210 | 0 | return 1; |
211 | 0 | } |
212 | | |
213 | | /* |
214 | | * |
215 | | * Using p & q, calculate other required parameters such as n, d. |
216 | | * as well as the CRT parameters dP, dQ, qInv. |
217 | | * |
218 | | * See SP800-56Br1 |
219 | | * 6.3.1.1 rsakpg1 - basic (Steps 3-4) |
220 | | * 6.3.1.3 rsakpg1 - crt (Step 5) |
221 | | * |
222 | | * Params: |
223 | | * rsa An rsa object. |
224 | | * nbits The key size. |
225 | | * e The public exponent. |
226 | | * ctx A BN_CTX object. |
227 | | * Notes: |
228 | | * There is a small chance that the generated d will be too small. |
229 | | * Returns: -1 = error, |
230 | | * 0 = d is too small, |
231 | | * 1 = success. |
232 | | * |
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. |
236 | | */ |
237 | | int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits, |
238 | | const BIGNUM *e, BN_CTX *ctx) |
239 | 0 | { |
240 | 0 | int ret = -1; |
241 | 0 | BIGNUM *p1, *q1, *lcm, *p1q1, *gcd; |
242 | 0 | BN_CTX_start(ctx); |
243 | 0 | p1 = BN_CTX_get(ctx); |
244 | 0 | q1 = BN_CTX_get(ctx); |
245 | 0 | lcm = BN_CTX_get(ctx); |
246 | 0 | p1q1 = BN_CTX_get(ctx); |
247 | 0 | gcd = BN_CTX_get(ctx); |
248 | 0 | if (gcd == NULL) |
249 | 0 | goto err; |
250 | | |
251 | 0 | BN_set_flags(p1, BN_FLG_CONSTTIME); |
252 | 0 | BN_set_flags(q1, BN_FLG_CONSTTIME); |
253 | 0 | BN_set_flags(lcm, BN_FLG_CONSTTIME); |
254 | 0 | BN_set_flags(p1q1, BN_FLG_CONSTTIME); |
255 | 0 | BN_set_flags(gcd, BN_FLG_CONSTTIME); |
256 | | |
257 | | /* LCM((p-1, q-1)) */ |
258 | 0 | if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1) |
259 | 0 | goto err; |
260 | | |
261 | | /* |
262 | | * if e is provided as a parameter, don't recompute e, d or n |
263 | | */ |
264 | 0 | if (e != NULL) { |
265 | | /* copy e */ |
266 | 0 | BN_free(rsa->e); |
267 | 0 | rsa->e = BN_dup(e); |
268 | 0 | if (rsa->e == NULL) |
269 | 0 | goto err; |
270 | | |
271 | 0 | BN_clear_free(rsa->d); |
272 | | /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */ |
273 | 0 | rsa->d = BN_secure_new(); |
274 | 0 | if (rsa->d == NULL) |
275 | 0 | goto err; |
276 | 0 | BN_set_flags(rsa->d, BN_FLG_CONSTTIME); |
277 | 0 | if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL) |
278 | 0 | goto err; |
279 | | |
280 | | /* (Step 3) return an error if d is too small */ |
281 | 0 | if (BN_num_bits(rsa->d) <= (nbits >> 1)) { |
282 | 0 | ret = 0; |
283 | 0 | goto err; |
284 | 0 | } |
285 | | |
286 | | /* (Step 4) n = pq */ |
287 | 0 | if (rsa->n == NULL) |
288 | 0 | rsa->n = BN_new(); |
289 | 0 | if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx)) |
290 | 0 | goto err; |
291 | 0 | } |
292 | | |
293 | | /* (Step 5a) dP = d mod (p-1) */ |
294 | 0 | if (rsa->dmp1 == NULL) |
295 | 0 | rsa->dmp1 = BN_secure_new(); |
296 | 0 | if (rsa->dmp1 == NULL) |
297 | 0 | goto err; |
298 | 0 | BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME); |
299 | 0 | if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx)) |
300 | 0 | goto err; |
301 | | |
302 | | /* (Step 5b) dQ = d mod (q-1) */ |
303 | 0 | if (rsa->dmq1 == NULL) |
304 | 0 | rsa->dmq1 = BN_secure_new(); |
305 | 0 | if (rsa->dmq1 == NULL) |
306 | 0 | goto err; |
307 | 0 | BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME); |
308 | 0 | if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx)) |
309 | 0 | goto err; |
310 | | |
311 | | /* (Step 5c) qInv = (inverse of q) mod p */ |
312 | 0 | BN_free(rsa->iqmp); |
313 | 0 | rsa->iqmp = BN_secure_new(); |
314 | 0 | if (rsa->iqmp == NULL) |
315 | 0 | goto err; |
316 | 0 | BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME); |
317 | 0 | if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL) |
318 | 0 | goto err; |
319 | | |
320 | 0 | rsa->dirty_cnt++; |
321 | 0 | ret = 1; |
322 | 0 | err: |
323 | 0 | if (ret != 1) { |
324 | 0 | BN_free(rsa->e); |
325 | 0 | rsa->e = NULL; |
326 | 0 | BN_free(rsa->d); |
327 | 0 | rsa->d = NULL; |
328 | 0 | BN_free(rsa->n); |
329 | 0 | rsa->n = NULL; |
330 | 0 | BN_free(rsa->iqmp); |
331 | 0 | rsa->iqmp = NULL; |
332 | 0 | BN_free(rsa->dmq1); |
333 | 0 | rsa->dmq1 = NULL; |
334 | 0 | BN_free(rsa->dmp1); |
335 | 0 | rsa->dmp1 = NULL; |
336 | 0 | } |
337 | 0 | BN_clear(p1); |
338 | 0 | BN_clear(q1); |
339 | 0 | BN_clear(lcm); |
340 | 0 | BN_clear(p1q1); |
341 | 0 | BN_clear(gcd); |
342 | |
|
343 | 0 | BN_CTX_end(ctx); |
344 | 0 | return ret; |
345 | 0 | } |
346 | | |
347 | | /* |
348 | | * Generate a SP800-56B RSA key. |
349 | | * |
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 |
353 | | * |
354 | | * See also FIPS 186-4 Section B.3.6 |
355 | | * "Generation of Probable Primes with Conditions Based on Auxiliary |
356 | | * Probable Primes." |
357 | | * |
358 | | * Params: |
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. |
364 | | */ |
365 | | int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed, |
366 | | BN_GENCB *cb) |
367 | 0 | { |
368 | 0 | int ret = 0; |
369 | 0 | int ok; |
370 | 0 | BN_CTX *ctx = NULL; |
371 | 0 | BIGNUM *e = NULL; |
372 | 0 | RSA_ACVP_TEST *info = NULL; |
373 | 0 | BIGNUM *tmp; |
374 | |
|
375 | | #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS) |
376 | | info = rsa->acvp_test; |
377 | | #endif |
378 | | |
379 | | /* (Steps 1a-1b) : Currently ignores the strength check */ |
380 | 0 | if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1)) |
381 | 0 | return 0; |
382 | | |
383 | | /* Check that the RNG is capable of generating a key this large */ |
384 | 0 | if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits)) |
385 | 0 | return 0; |
386 | | |
387 | 0 | ctx = BN_CTX_new_ex(rsa->libctx); |
388 | 0 | if (ctx == NULL) |
389 | 0 | return 0; |
390 | | |
391 | | /* Set default if e is not passed in */ |
392 | 0 | if (efixed == NULL) { |
393 | 0 | e = BN_new(); |
394 | 0 | if (e == NULL || !BN_set_word(e, 65537)) |
395 | 0 | goto err; |
396 | 0 | } else { |
397 | 0 | e = (BIGNUM *)efixed; |
398 | 0 | } |
399 | | /* (Step 1c) fixed exponent is checked later .*/ |
400 | | |
401 | 0 | for (;;) { |
402 | | /* (Step 2) Generate prime factors */ |
403 | 0 | if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb)) |
404 | 0 | goto err; |
405 | | |
406 | | /* p>q check and skipping in case of acvp test */ |
407 | 0 | if (info == NULL && BN_cmp(rsa->p, rsa->q) < 0) { |
408 | 0 | tmp = rsa->p; |
409 | 0 | rsa->p = rsa->q; |
410 | 0 | rsa->q = tmp; |
411 | 0 | } |
412 | | |
413 | | /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */ |
414 | 0 | ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx); |
415 | 0 | if (ok < 0) |
416 | 0 | goto err; |
417 | 0 | if (ok > 0) |
418 | 0 | break; |
419 | | /* Gets here if computed d is too small - so try again */ |
420 | 0 | } |
421 | | |
422 | | /* (Step 6) Do pairwise test - optional validity test has been omitted */ |
423 | 0 | ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx); |
424 | 0 | err: |
425 | 0 | if (efixed == NULL) |
426 | 0 | BN_free(e); |
427 | 0 | BN_CTX_free(ctx); |
428 | 0 | return ret; |
429 | 0 | } |
430 | | |
431 | | /* |
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. |
434 | | * |
435 | | * Returns 1 if the RSA key passes the pairwise test or 0 if it fails. |
436 | | */ |
437 | | int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx) |
438 | 0 | { |
439 | 0 | int ret = 0; |
440 | 0 | BIGNUM *k, *tmp; |
441 | |
|
442 | 0 | BN_CTX_start(ctx); |
443 | 0 | tmp = BN_CTX_get(ctx); |
444 | 0 | k = BN_CTX_get(ctx); |
445 | 0 | if (k == NULL) |
446 | 0 | goto err; |
447 | 0 | BN_set_flags(k, BN_FLG_CONSTTIME); |
448 | |
|
449 | 0 | ret = (BN_set_word(k, 2) |
450 | 0 | && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx) |
451 | 0 | && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx) |
452 | 0 | && BN_cmp(k, tmp) == 0); |
453 | 0 | if (ret == 0) |
454 | 0 | ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE); |
455 | 0 | err: |
456 | 0 | BN_CTX_end(ctx); |
457 | 0 | return ret; |
458 | 0 | } |