d1673d5c9899d1986252b9a0b1534bcb54b64a08
[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 "crypto/bn.h"
14 #include "crypto/security_bits.h"
15 #include "rsa_local.h"
16
17 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
18 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
19 #define RSA_FIPS1864_MAX_KEYGEN_STRENGTH 256
20
21 /*
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
24  * Primes".
25  *
26  * Params:
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
31  *        generation of p).
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
38  *        generation of q).
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.
47  * Notes:
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).
51  */
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)
59 {
60     int ret = 0, ok;
61     BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
62
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.
66      */
67     if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
68         RSAerr(RSA_F_RSA_FIPS186_4_GEN_PROB_PRIMES, RSA_R_KEY_SIZE_TOO_SMALL);
69         return 0;
70     }
71
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);
75         return 0;
76     }
77
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.
81      */
82
83     BN_CTX_start(ctx);
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)
88         goto err;
89
90     if (rsa->p == NULL)
91         rsa->p = BN_secure_new();
92     if (rsa->q == NULL)
93         rsa->q = BN_secure_new();
94     if (rsa->p == NULL || rsa->q == NULL)
95         goto err;
96
97     /* (Step 4) Generate p, Xp */
98     if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
99                                           nbits, e, ctx, cb))
100         goto err;
101     for(;;) {
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))
105             goto err;
106
107         /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
108         ok = rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
109         if (ok < 0)
110             goto err;
111         if (ok == 0)
112             continue;
113
114         /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
115         ok = rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
116         if (ok < 0)
117             goto err;
118         if (ok == 0)
119             continue;
120         break; /* successfully finished */
121     }
122     rsa->dirty_cnt++;
123     ret = 1;
124 err:
125     /* Zeroize any internally generated values that are not returned */
126     if (Xpo != Xpout)
127         BN_clear(Xpo);
128     if (Xqo != Xqout)
129         BN_clear(Xqo);
130     BN_clear(tmp);
131
132     BN_CTX_end(ctx);
133     return ret;
134 }
135
136 /*
137  * Validates the RSA key size based on the target strength.
138  * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
139  *
140  * Params:
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.
145  */
146 int rsa_sp800_56b_validate_strength(int nbits, int strength)
147 {
148     int s = (int)ifc_ffc_compute_security_bits(nbits);
149 #ifdef FIPS_MODULE
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);
153         return 0;
154     }
155 #endif
156     if (strength != -1 && s != strength) {
157         RSAerr(RSA_F_RSA_SP800_56B_VALIDATE_STRENGTH, RSA_R_INVALID_STRENGTH);
158         return 0;
159     }
160     return 1;
161 }
162
163 /*
164  *
165  * Using p & q, calculate other required parameters such as n, d.
166  * as well as the CRT parameters dP, dQ, qInv.
167  *
168  * See SP800-56Br1
169  *   6.3.1.1 rsakpg1 - basic (Steps 3-4)
170  *   6.3.1.3 rsakpg1 - crt   (Step 5)
171  *
172  * Params:
173  *     rsa An rsa object.
174  *     nbits The key size.
175  *     e The public exponent.
176  *     ctx A BN_CTX object.
177  * Notes:
178  *   There is a small chance that the generated d will be too small.
179  * Returns: -1 = error,
180  *           0 = d is too small,
181  *           1 = success.
182  */
183 int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
184                                         const BIGNUM *e, BN_CTX *ctx)
185 {
186     int ret = -1;
187     BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
188
189     BN_CTX_start(ctx);
190     p1 = BN_CTX_get(ctx);
191     q1 = BN_CTX_get(ctx);
192     lcm = BN_CTX_get(ctx);
193     p1q1 = BN_CTX_get(ctx);
194     gcd = BN_CTX_get(ctx);
195     if (gcd == NULL)
196         goto err;
197
198     /* LCM((p-1, q-1)) */
199     if (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
200         goto err;
201
202     /* copy e */
203     BN_free(rsa->e);
204     rsa->e = BN_dup(e);
205     if (rsa->e == NULL)
206         goto err;
207
208     BN_clear_free(rsa->d);
209     /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
210     rsa->d = BN_secure_new();
211     if (rsa->d == NULL || BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
212         goto err;
213
214     /* (Step 3) return an error if d is too small */
215     if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
216         ret = 0;
217         goto err;
218     }
219
220     /* (Step 4) n = pq */
221     if (rsa->n == NULL)
222         rsa->n = BN_new();
223     if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
224         goto err;
225
226     /* (Step 5a) dP = d mod (p-1) */
227     if (rsa->dmp1 == NULL)
228         rsa->dmp1 = BN_new();
229     if (rsa->dmp1 == NULL || !BN_mod(rsa->dmp1, rsa->d, p1, ctx))
230         goto err;
231
232     /* (Step 5b) dQ = d mod (q-1) */
233     if (rsa->dmq1 == NULL)
234         rsa->dmq1 = BN_secure_new();
235     if (rsa->dmq1 == NULL || !BN_mod(rsa->dmq1, rsa->d, q1, ctx))
236         goto err;
237
238     /* (Step 5c) qInv = (inverse of q) mod p */
239     BN_free(rsa->iqmp);
240     rsa->iqmp = BN_secure_new();
241     if (rsa->iqmp == NULL
242             || BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
243         goto err;
244
245     rsa->dirty_cnt++;
246     ret = 1;
247 err:
248     if (ret != 1) {
249         BN_free(rsa->e);
250         rsa->e = NULL;
251         BN_free(rsa->d);
252         rsa->d = NULL;
253         BN_free(rsa->n);
254         rsa->n = NULL;
255         BN_free(rsa->iqmp);
256         rsa->iqmp = NULL;
257         BN_free(rsa->dmq1);
258         rsa->dmq1 = NULL;
259         BN_free(rsa->dmp1);
260         rsa->dmp1 = NULL;
261     }
262     BN_clear(p1);
263     BN_clear(q1);
264     BN_clear(lcm);
265     BN_clear(p1q1);
266     BN_clear(gcd);
267
268     BN_CTX_end(ctx);
269     return ret;
270 }
271
272 /*
273  * Generate a SP800-56B RSA key.
274  *
275  * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
276  *    6.3.1.1 rsakpg1 - basic
277  *    6.3.1.3 rsakpg1 - crt
278  *
279  * See also FIPS 186-4 Section B.3.6
280  * "Generation of Probable Primes with Conditions Based on Auxiliary
281  * Probable Primes."
282  *
283  * Params:
284  *     rsa The rsa object.
285  *     nbits The intended key size in bits.
286  *     efixed The public exponent. If NULL a default of 65537 is used.
287  *     cb An optional BIGNUM callback.
288  * Returns: 1 if successfully generated otherwise it returns 0.
289  */
290 int rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
291                                BN_GENCB *cb)
292 {
293     int ret = 0;
294     int ok;
295     BN_CTX *ctx = NULL;
296     BIGNUM *e = NULL;
297
298     /* (Steps 1a-1b) : Currently ignores the strength check */
299     if (!rsa_sp800_56b_validate_strength(nbits, -1))
300         return 0;
301
302     ctx = BN_CTX_new_ex(rsa->libctx);
303     if (ctx == NULL)
304         return 0;
305
306     /* Set default if e is not passed in */
307     if (efixed == NULL) {
308         e = BN_new();
309         if (e == NULL || !BN_set_word(e, 65537))
310             goto err;
311     } else {
312         e = (BIGNUM *)efixed;
313     }
314     /* (Step 1c) fixed exponent is checked later . */
315
316     for (;;) {
317         /* (Step 2) Generate prime factors */
318         if (!rsa_fips186_4_gen_prob_primes(rsa, NULL, NULL, NULL, NULL, NULL,
319                                            NULL, NULL, NULL, NULL, NULL, NULL,
320                                            NULL, nbits, e, ctx, cb))
321             goto err;
322         /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
323         ok = rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
324         if (ok < 0)
325             goto err;
326         if (ok > 0)
327             break;
328         /* Gets here if computed d is too small - so try again */
329     }
330
331     /* (Step 6) Do pairwise test - optional validity test has been omitted */
332     ret = rsa_sp800_56b_pairwise_test(rsa, ctx);
333 err:
334     if (efixed == NULL)
335         BN_free(e);
336     BN_CTX_free(ctx);
337     return ret;
338 }
339
340 /*
341  * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
342  * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
343  *
344  * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
345  */
346 int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
347 {
348     int ret = 0;
349     BIGNUM *k, *tmp;
350
351     BN_CTX_start(ctx);
352     tmp = BN_CTX_get(ctx);
353     k = BN_CTX_get(ctx);
354     if (k == NULL)
355         goto err;
356
357     ret = (BN_set_word(k, 2)
358           && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
359           && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
360           && BN_cmp(k, tmp) == 0);
361     if (ret == 0)
362         RSAerr(RSA_F_RSA_SP800_56B_PAIRWISE_TEST, RSA_R_PAIRWISE_TEST_FAILURE);
363 err:
364     BN_CTX_end(ctx);
365     return ret;
366 }