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