xref: /openssl/crypto/rsa/rsa_sp800_56b_gen.c (revision fb323b27)
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 #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  */
ossl_rsa_fips186_4_gen_prob_primes(RSA * rsa,RSA_ACVP_TEST * test,int nbits,const BIGNUM * e,BN_CTX * ctx,BN_GENCB * cb)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 {
59     int ret = 0, ok;
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;
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     if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
89         ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
90         return 0;
91     }
92 
93     if (!ossl_rsa_check_public_exponent(e)) {
94         ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
95         return 0;
96     }
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     BN_CTX_start(ctx);
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)
108         goto err;
109     BN_set_flags(Xpo, BN_FLG_CONSTTIME);
110     BN_set_flags(Xqo, BN_FLG_CONSTTIME);
111 
112     if (rsa->p == NULL)
113         rsa->p = BN_secure_new();
114     if (rsa->q == NULL)
115         rsa->q = BN_secure_new();
116     if (rsa->p == NULL || rsa->q == NULL)
117         goto err;
118     BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
119     BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
120 
121     /* (Step 4) Generate p, Xp */
122     if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
123                                                nbits, e, ctx, cb))
124         goto err;
125     for (;;) {
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))
129             goto err;
130 
131         /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
132         ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
133         if (ok < 0)
134             goto err;
135         if (ok == 0)
136             continue;
137 
138         /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
139         ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
140         if (ok < 0)
141             goto err;
142         if (ok == 0)
143             continue;
144         break; /* successfully finished */
145     }
146     rsa->dirty_cnt++;
147     ret = 1;
148 err:
149     /* Zeroize any internally generated values that are not returned */
150     BN_clear(Xpo);
151     BN_clear(Xqo);
152     BN_clear(tmp);
153     if (ret != 1) {
154         BN_clear_free(rsa->p);
155         rsa->p = NULL;
156         BN_clear_free(rsa->q);
157         rsa->q = NULL;
158     }
159 
160     BN_CTX_end(ctx);
161     return ret;
162 }
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  */
ossl_rsa_sp800_56b_validate_strength(int nbits,int strength)174 int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength)
175 {
176     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     if (strength != -1 && s != strength) {
185         ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH);
186         return 0;
187     }
188     return 1;
189 }
190 
191 /*
192  * Validate that the random bit generator is of sufficient strength to generate
193  * a key of the specified length.
194  */
rsa_validate_rng_strength(EVP_RAND_CTX * rng,int nbits)195 static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits)
196 {
197     if (rng == NULL)
198         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     return 1;
211 }
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  */
ossl_rsa_sp800_56b_derive_params_from_pq(RSA * rsa,int nbits,const BIGNUM * e,BN_CTX * ctx)237 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
238                                              const BIGNUM *e, BN_CTX *ctx)
239 {
240     int ret = -1;
241     BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
242     BN_CTX_start(ctx);
243     p1 = BN_CTX_get(ctx);
244     q1 = BN_CTX_get(ctx);
245     lcm = BN_CTX_get(ctx);
246     p1q1 = BN_CTX_get(ctx);
247     gcd = BN_CTX_get(ctx);
248     if (gcd == NULL)
249         goto err;
250 
251     BN_set_flags(p1, BN_FLG_CONSTTIME);
252     BN_set_flags(q1, BN_FLG_CONSTTIME);
253     BN_set_flags(lcm, BN_FLG_CONSTTIME);
254     BN_set_flags(p1q1, BN_FLG_CONSTTIME);
255     BN_set_flags(gcd, BN_FLG_CONSTTIME);
256 
257     /* LCM((p-1, q-1)) */
258     if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
259         goto err;
260 
261     /*
262      * if e is provided as a parameter, don't recompute e, d or n
263      */
264     if (e != NULL) {
265         /* copy e */
266         BN_free(rsa->e);
267         rsa->e = BN_dup(e);
268         if (rsa->e == NULL)
269             goto err;
270 
271         BN_clear_free(rsa->d);
272         /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
273         rsa->d = BN_secure_new();
274         if (rsa->d == NULL)
275             goto err;
276         BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
277         if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
278             goto err;
279 
280         /* (Step 3) return an error if d is too small */
281         if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
282             ret = 0;
283             goto err;
284         }
285 
286         /* (Step 4) n = pq */
287         if (rsa->n == NULL)
288             rsa->n = BN_new();
289         if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
290             goto err;
291     }
292 
293     /* (Step 5a) dP = d mod (p-1) */
294     if (rsa->dmp1 == NULL)
295         rsa->dmp1 = BN_secure_new();
296     if (rsa->dmp1 == NULL)
297         goto err;
298     BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
299     if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
300         goto err;
301 
302     /* (Step 5b) dQ = d mod (q-1) */
303     if (rsa->dmq1 == NULL)
304         rsa->dmq1 = BN_secure_new();
305     if (rsa->dmq1 == NULL)
306         goto err;
307     BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
308     if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
309         goto err;
310 
311     /* (Step 5c) qInv = (inverse of q) mod p */
312     BN_free(rsa->iqmp);
313     rsa->iqmp = BN_secure_new();
314     if (rsa->iqmp == NULL)
315         goto err;
316     BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
317     if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
318         goto err;
319 
320     rsa->dirty_cnt++;
321     ret = 1;
322 err:
323     if (ret != 1) {
324         BN_free(rsa->e);
325         rsa->e = NULL;
326         BN_free(rsa->d);
327         rsa->d = NULL;
328         BN_free(rsa->n);
329         rsa->n = NULL;
330         BN_free(rsa->iqmp);
331         rsa->iqmp = NULL;
332         BN_free(rsa->dmq1);
333         rsa->dmq1 = NULL;
334         BN_free(rsa->dmp1);
335         rsa->dmp1 = NULL;
336     }
337     BN_clear(p1);
338     BN_clear(q1);
339     BN_clear(lcm);
340     BN_clear(p1q1);
341     BN_clear(gcd);
342 
343     BN_CTX_end(ctx);
344     return ret;
345 }
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  */
ossl_rsa_sp800_56b_generate_key(RSA * rsa,int nbits,const BIGNUM * efixed,BN_GENCB * cb)365 int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
366                                     BN_GENCB *cb)
367 {
368     int ret = 0;
369     int ok;
370     BN_CTX *ctx = NULL;
371     BIGNUM *e = NULL;
372     RSA_ACVP_TEST *info = NULL;
373     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     if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1))
381         return 0;
382 
383     /* Check that the RNG is capable of generating a key this large */
384    if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits))
385         return 0;
386 
387     ctx = BN_CTX_new_ex(rsa->libctx);
388     if (ctx == NULL)
389         return 0;
390 
391     /* Set default if e is not passed in */
392     if (efixed == NULL) {
393         e = BN_new();
394         if (e == NULL || !BN_set_word(e, 65537))
395             goto err;
396     } else {
397         e = (BIGNUM *)efixed;
398     }
399     /* (Step 1c) fixed exponent is checked later .*/
400 
401     for (;;) {
402         /* (Step 2) Generate prime factors */
403         if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb))
404             goto err;
405 
406         /* p>q check and skipping in case of acvp test */
407         if (info == NULL && BN_cmp(rsa->p, rsa->q) < 0) {
408             tmp = rsa->p;
409             rsa->p = rsa->q;
410             rsa->q = tmp;
411         }
412 
413         /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
414         ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
415         if (ok < 0)
416             goto err;
417         if (ok > 0)
418             break;
419         /* Gets here if computed d is too small - so try again */
420     }
421 
422     /* (Step 6) Do pairwise test - optional validity test has been omitted */
423     ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx);
424 err:
425     if (efixed == NULL)
426         BN_free(e);
427     BN_CTX_free(ctx);
428     return ret;
429 }
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  */
ossl_rsa_sp800_56b_pairwise_test(RSA * rsa,BN_CTX * ctx)437 int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
438 {
439     int ret = 0;
440     BIGNUM *k, *tmp;
441 
442     BN_CTX_start(ctx);
443     tmp = BN_CTX_get(ctx);
444     k = BN_CTX_get(ctx);
445     if (k == NULL)
446         goto err;
447     BN_set_flags(k, BN_FLG_CONSTTIME);
448 
449     ret = (BN_set_word(k, 2)
450            && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
451            && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
452            && BN_cmp(k, tmp) == 0);
453     if (ret == 0)
454         ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE);
455 err:
456     BN_CTX_end(ctx);
457     return ret;
458 }
459