df15b8ce87af8666fc7afb647565328992313ec1
[openssl.git] / crypto / rsa / rsa_sp800_56b_gen.c
1 /*
2  * Copyright 2018-2020 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 "crypto/bn.h"
15 #include "crypto/security_bits.h"
16 #include "rsa_local.h"
17
18 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
19 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
20 #define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
21
22 /*
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
25  * Primes".
26  *
27  * Params:
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
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  *       Xqout An optionally returned random number used during generation of q.
41  *       Xq An optional passed in value (that is random number used during
42  *          generation of q).
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.
51  * Notes:
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).
55  */
56 int rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test, int nbits,
57                                   const BIGNUM *e, BN_CTX *ctx, 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 *Xpout = NULL, *Xqout = NULL;
67     BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL;
68     BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL;
69
70 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
71     if (test != NULL) {
72         Xp1 = test->Xp1;
73         Xp2 = test->Xp2;
74         Xq1 = test->Xq1;
75         Xq2 = test->Xq2;
76         Xp = test->Xp;
77         Xq = test->Xq;
78         p1 = test->p1;
79         p2 = test->p2;
80         q1 = test->q1;
81         q2 = test->q2;
82     }
83 #endif
84
85     /* (Step 1) Check key length
86      * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
87      * Signature Generation and Key Agree/Transport.
88      */
89     if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
90         RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES, RSA_R_KEY_SIZE_TOO_SMALL);
91         return 0;
92     }
93
94     if (!rsa_check_public_exponent(e)) {
95         RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES,
96                RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
97         return 0;
98     }
99
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.
103      */
104
105     BN_CTX_start(ctx);
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)
110         goto err;
111     BN_set_flags(Xpo, BN_FLG_CONSTTIME);
112     BN_set_flags(Xqo, BN_FLG_CONSTTIME);
113
114     if (rsa->p == NULL)
115         rsa->p = BN_secure_new();
116     if (rsa->q == NULL)
117         rsa->q = BN_secure_new();
118     if (rsa->p == NULL || rsa->q == NULL)
119         goto err;
120     BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
121     BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
122
123     /* (Step 4) Generate p, Xp */
124     if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
125                                           nbits, e, ctx, cb))
126         goto err;
127     for(;;) {
128         /* (Step 5) Generate q, Xq*/
129         if (!bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
130                                               Xq2, nbits, e, ctx, cb))
131             goto err;
132
133         /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
134         ok = rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
135         if (ok < 0)
136             goto err;
137         if (ok == 0)
138             continue;
139
140         /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
141         ok = rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
142         if (ok < 0)
143             goto err;
144         if (ok == 0)
145             continue;
146         break; /* successfully finished */
147     }
148     rsa->dirty_cnt++;
149     ret = 1;
150 err:
151     /* Zeroize any internally generated values that are not returned */
152     if (Xpo != Xpout)
153         BN_clear(Xpo);
154     if (Xqo != Xqout)
155         BN_clear(Xqo);
156     BN_clear(tmp);
157
158     BN_CTX_end(ctx);
159     return ret;
160 }
161
162 /*
163  * Validates the RSA key size based on the target strength.
164  * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
165  *
166  * Params:
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.
171  */
172 int rsa_sp800_56b_validate_strength(int nbits, int strength)
173 {
174     int s = (int)ifc_ffc_compute_security_bits(nbits);
175 #ifdef FIPS_MODULE
176     if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH
177             || s > RSA_FIPS1864_MAX_KEYGEN_STRENGTH) {
178         RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_MODULUS);
179         return 0;
180     }
181 #endif
182     if (strength != -1 && s != strength) {
183         RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_STRENGTH);
184         return 0;
185     }
186     return 1;
187 }
188
189 /*
190  *
191  * Using p & q, calculate other required parameters such as n, d.
192  * as well as the CRT parameters dP, dQ, qInv.
193  *
194  * See SP800-56Br1
195  *   6.3.1.1 rsakpg1 - basic (Steps 3-4)
196  *   6.3.1.3 rsakpg1 - crt   (Step 5)
197  *
198  * Params:
199  *     rsa An rsa object.
200  *     nbits The key size.
201  *     e The public exponent.
202  *     ctx A BN_CTX object.
203  * Notes:
204  *   There is a small chance that the generated d will be too small.
205  * Returns: -1 = error,
206  *           0 = d is too small,
207  *           1 = success.
208  */
209 int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
210                                         const BIGNUM *e, BN_CTX *ctx)
211 {
212     int ret = -1;
213     BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
214
215     BN_CTX_start(ctx);
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);
221     if (gcd == NULL)
222         goto err;
223
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);
229
230     /* LCM((p-1, q-1)) */
231     if (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
232         goto err;
233
234     /* copy e */
235     BN_free(rsa->e);
236     rsa->e = BN_dup(e);
237     if (rsa->e == NULL)
238         goto err;
239
240     BN_clear_free(rsa->d);
241     /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
242     rsa->d = BN_secure_new();
243     if (rsa->d == NULL)
244         goto err;
245     BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
246     if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
247         goto err;
248
249     /* (Step 3) return an error if d is too small */
250     if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
251         ret = 0;
252         goto err;
253     }
254
255     /* (Step 4) n = pq */
256     if (rsa->n == NULL)
257         rsa->n = BN_new();
258     if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
259         goto err;
260
261     /* (Step 5a) dP = d mod (p-1) */
262     if (rsa->dmp1 == NULL)
263         rsa->dmp1 = BN_secure_new();
264     if (rsa->dmp1 == NULL)
265             goto err;
266     BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
267     if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
268         goto err;
269
270     /* (Step 5b) dQ = d mod (q-1) */
271     if (rsa->dmq1 == NULL)
272         rsa->dmq1 = BN_secure_new();
273     if (rsa->dmq1 == NULL)
274             goto err;
275     BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
276     if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
277         goto err;
278
279     /* (Step 5c) qInv = (inverse of q) mod p */
280     BN_free(rsa->iqmp);
281     rsa->iqmp = BN_secure_new();
282     if (rsa->iqmp == NULL)
283             goto err;
284     BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
285     if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
286         goto err;
287
288     rsa->dirty_cnt++;
289     ret = 1;
290 err:
291     if (ret != 1) {
292         BN_free(rsa->e);
293         rsa->e = NULL;
294         BN_free(rsa->d);
295         rsa->d = NULL;
296         BN_free(rsa->n);
297         rsa->n = NULL;
298         BN_free(rsa->iqmp);
299         rsa->iqmp = NULL;
300         BN_free(rsa->dmq1);
301         rsa->dmq1 = NULL;
302         BN_free(rsa->dmp1);
303         rsa->dmp1 = NULL;
304     }
305     BN_clear(p1);
306     BN_clear(q1);
307     BN_clear(lcm);
308     BN_clear(p1q1);
309     BN_clear(gcd);
310
311     BN_CTX_end(ctx);
312     return ret;
313 }
314
315 /*
316  * Generate a SP800-56B RSA key.
317  *
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
321  *
322  * See also FIPS 186-4 Section B.3.6
323  * "Generation of Probable Primes with Conditions Based on Auxiliary
324  * Probable Primes."
325  *
326  * Params:
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.
332  */
333 int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
334                                BN_GENCB *cb)
335 {
336     int ret = 0;
337     int ok;
338     BN_CTX *ctx = NULL;
339     BIGNUM *e = NULL;
340     RSA_ACVP_TEST *info = NULL;
341
342 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
343     info = rsa->acvp_test;
344 #endif
345
346     /* (Steps 1a-1b) : Currently ignores the strength check */
347     if (!rsa_sp800_56b_validate_strength(nbits, -1))
348         return 0;
349
350     ctx = BN_CTX_new_ex(rsa->libctx);
351     if (ctx == NULL)
352         return 0;
353
354     /* Set default if e is not passed in */
355     if (efixed == NULL) {
356         e = BN_new();
357         if (e == NULL || !BN_set_word(e, 65537))
358             goto err;
359     } else {
360         e = (BIGNUM *)efixed;
361     }
362     /* (Step 1c) fixed exponent is checked later .*/
363
364     for (;;) {
365         /* (Step 2) Generate prime factors */
366         if (!rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx,
367                                            cb))
368             goto err;
369         /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
370         ok = rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
371         if (ok < 0)
372             goto err;
373         if (ok > 0)
374             break;
375         /* Gets here if computed d is too small - so try again */
376     }
377
378     /* (Step 6) Do pairwise test - optional validity test has been omitted */
379     ret = rsa_sp800_56b_pairwise_test(rsa, ctx);
380 err:
381     if (efixed == NULL)
382         BN_free(e);
383     BN_CTX_free(ctx);
384     return ret;
385 }
386
387 /*
388  * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
389  * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
390  *
391  * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
392  */
393 int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
394 {
395     int ret = 0;
396     BIGNUM *k, *tmp;
397
398     BN_CTX_start(ctx);
399     tmp = BN_CTX_get(ctx);
400     k = BN_CTX_get(ctx);
401     if (k == NULL)
402         goto err;
403     BN_set_flags(k, BN_FLG_CONSTTIME);
404
405     ret = (BN_set_word(k, 2)
406           && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
407           && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
408           && BN_cmp(k, tmp) == 0);
409     if (ret == 0)
410         RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST, RSA_R_PAIRWISE_TEST_FAILURE);
411 err:
412     BN_CTX_end(ctx);
413     return ret;
414 }