Update RSA keygen to use sp800-56b by default
[openssl.git] / crypto / rsa / rsa_gen.c
1 /*
2  * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 /*
11  * NB: these functions have been "upgraded", the deprecated versions (which
12  * are compatibility wrappers using these functions) are in rsa_depr.c. -
13  * Geoff
14  */
15
16 /*
17  * RSA low level APIs are deprecated for public use, but still ok for
18  * internal use.
19  */
20 #include "internal/deprecated.h"
21
22 #include <stdio.h>
23 #include <time.h>
24 #include "internal/cryptlib.h"
25 #include <openssl/bn.h>
26 #include <openssl/self_test.h>
27 #include "rsa_local.h"
28
29 static int rsa_keygen_pairwise_test(RSA *rsa, OSSL_CALLBACK *cb, void *cbarg);
30 static int rsa_keygen(OPENSSL_CTX *libctx, RSA *rsa, int bits, int primes,
31                       BIGNUM *e_value, BN_GENCB *cb, int pairwise_test);
32
33 /*
34  * NB: this wrapper would normally be placed in rsa_lib.c and the static
35  * implementation would probably be in rsa_eay.c. Nonetheless, is kept here
36  * so that we don't introduce a new linker dependency. Eg. any application
37  * that wasn't previously linking object code related to key-generation won't
38  * have to now just because key-generation is part of RSA_METHOD.
39  */
40 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
41 {
42     if (rsa->meth->rsa_keygen != NULL)
43         return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);
44
45     return RSA_generate_multi_prime_key(rsa, bits, RSA_DEFAULT_PRIME_NUM,
46                                         e_value, cb);
47 }
48
49 int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes,
50                                  BIGNUM *e_value, BN_GENCB *cb)
51 {
52 #ifndef FIPS_MODULE
53     /* multi-prime is only supported with the builtin key generation */
54     if (rsa->meth->rsa_multi_prime_keygen != NULL) {
55         return rsa->meth->rsa_multi_prime_keygen(rsa, bits, primes,
56                                                  e_value, cb);
57     } else if (rsa->meth->rsa_keygen != NULL) {
58         /*
59          * However, if rsa->meth implements only rsa_keygen, then we
60          * have to honour it in 2-prime case and assume that it wouldn't
61          * know what to do with multi-prime key generated by builtin
62          * subroutine...
63          */
64         if (primes == 2)
65             return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);
66         else
67             return 0;
68     }
69 #endif /* FIPS_MODULE */
70     return rsa_keygen(NULL, rsa, bits, primes, e_value, cb, 0);
71 }
72
73 #ifndef FIPS_MODULE
74 static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
75                                  BIGNUM *e_value, BN_GENCB *cb)
76 {
77     BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *prime;
78     int n = 0, bitsr[RSA_MAX_PRIME_NUM], bitse = 0;
79     int i = 0, quo = 0, rmd = 0, adj = 0, retries = 0;
80     RSA_PRIME_INFO *pinfo = NULL;
81     STACK_OF(RSA_PRIME_INFO) *prime_infos = NULL;
82     BN_CTX *ctx = NULL;
83     BN_ULONG bitst = 0;
84     unsigned long error = 0;
85     int ok = -1;
86
87     if (bits < RSA_MIN_MODULUS_BITS) {
88         ok = 0;             /* we set our own err */
89         RSAerr(0, RSA_R_KEY_SIZE_TOO_SMALL);
90         goto err;
91     }
92
93     /* A bad value for e can cause infinite loops */
94     if (e_value != NULL && !rsa_check_public_exponent(e_value)) {
95         RSAerr(0, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
96         return 0;
97     }
98
99     if (primes < RSA_DEFAULT_PRIME_NUM || primes > rsa_multip_cap(bits)) {
100         ok = 0;             /* we set our own err */
101         RSAerr(0, RSA_R_KEY_PRIME_NUM_INVALID);
102         goto err;
103     }
104
105     ctx = BN_CTX_new();
106     if (ctx == NULL)
107         goto err;
108     BN_CTX_start(ctx);
109     r0 = BN_CTX_get(ctx);
110     r1 = BN_CTX_get(ctx);
111     r2 = BN_CTX_get(ctx);
112     if (r2 == NULL)
113         goto err;
114
115     /* divide bits into 'primes' pieces evenly */
116     quo = bits / primes;
117     rmd = bits % primes;
118
119     for (i = 0; i < primes; i++)
120         bitsr[i] = (i < rmd) ? quo + 1 : quo;
121
122     rsa->dirty_cnt++;
123
124     /* We need the RSA components non-NULL */
125     if (!rsa->n && ((rsa->n = BN_new()) == NULL))
126         goto err;
127     if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL))
128         goto err;
129     if (!rsa->e && ((rsa->e = BN_new()) == NULL))
130         goto err;
131     if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL))
132         goto err;
133     if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL))
134         goto err;
135     if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL))
136         goto err;
137     if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL))
138         goto err;
139     if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
140         goto err;
141
142     /* initialize multi-prime components */
143     if (primes > RSA_DEFAULT_PRIME_NUM) {
144         rsa->version = RSA_ASN1_VERSION_MULTI;
145         prime_infos = sk_RSA_PRIME_INFO_new_reserve(NULL, primes - 2);
146         if (prime_infos == NULL)
147             goto err;
148         if (rsa->prime_infos != NULL) {
149             /* could this happen? */
150             sk_RSA_PRIME_INFO_pop_free(rsa->prime_infos, rsa_multip_info_free);
151         }
152         rsa->prime_infos = prime_infos;
153
154         /* prime_info from 2 to |primes| -1 */
155         for (i = 2; i < primes; i++) {
156             pinfo = rsa_multip_info_new();
157             if (pinfo == NULL)
158                 goto err;
159             (void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo);
160         }
161     }
162
163     if (BN_copy(rsa->e, e_value) == NULL)
164         goto err;
165
166     /* generate p, q and other primes (if any) */
167     for (i = 0; i < primes; i++) {
168         adj = 0;
169         retries = 0;
170
171         if (i == 0) {
172             prime = rsa->p;
173         } else if (i == 1) {
174             prime = rsa->q;
175         } else {
176             pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
177             prime = pinfo->r;
178         }
179         BN_set_flags(prime, BN_FLG_CONSTTIME);
180
181         for (;;) {
182  redo:
183             if (!BN_generate_prime_ex(prime, bitsr[i] + adj, 0, NULL, NULL, cb))
184                 goto err;
185             /*
186              * prime should not be equal to p, q, r_3...
187              * (those primes prior to this one)
188              */
189             {
190                 int j;
191
192                 for (j = 0; j < i; j++) {
193                     BIGNUM *prev_prime;
194
195                     if (j == 0)
196                         prev_prime = rsa->p;
197                     else if (j == 1)
198                         prev_prime = rsa->q;
199                     else
200                         prev_prime = sk_RSA_PRIME_INFO_value(prime_infos,
201                                                              j - 2)->r;
202
203                     if (!BN_cmp(prime, prev_prime)) {
204                         goto redo;
205                     }
206                 }
207             }
208             if (!BN_sub(r2, prime, BN_value_one()))
209                 goto err;
210             ERR_set_mark();
211             BN_set_flags(r2, BN_FLG_CONSTTIME);
212             if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) {
213                /* GCD == 1 since inverse exists */
214                 break;
215             }
216             error = ERR_peek_last_error();
217             if (ERR_GET_LIB(error) == ERR_LIB_BN
218                 && ERR_GET_REASON(error) == BN_R_NO_INVERSE) {
219                 /* GCD != 1 */
220                 ERR_pop_to_mark();
221             } else {
222                 goto err;
223             }
224             if (!BN_GENCB_call(cb, 2, n++))
225                 goto err;
226         }
227
228         bitse += bitsr[i];
229
230         /* calculate n immediately to see if it's sufficient */
231         if (i == 1) {
232             /* we get at least 2 primes */
233             if (!BN_mul(r1, rsa->p, rsa->q, ctx))
234                 goto err;
235         } else if (i != 0) {
236             /* modulus n = p * q * r_3 * r_4 ... */
237             if (!BN_mul(r1, rsa->n, prime, ctx))
238                 goto err;
239         } else {
240             /* i == 0, do nothing */
241             if (!BN_GENCB_call(cb, 3, i))
242                 goto err;
243             continue;
244         }
245         /*
246          * if |r1|, product of factors so far, is not as long as expected
247          * (by checking the first 4 bits are less than 0x9 or greater than
248          * 0xF). If so, re-generate the last prime.
249          *
250          * NOTE: This actually can't happen in two-prime case, because of
251          * the way factors are generated.
252          *
253          * Besides, another consideration is, for multi-prime case, even the
254          * length modulus is as long as expected, the modulus could start at
255          * 0x8, which could be utilized to distinguish a multi-prime private
256          * key by using the modulus in a certificate. This is also covered
257          * by checking the length should not be less than 0x9.
258          */
259         if (!BN_rshift(r2, r1, bitse - 4))
260             goto err;
261         bitst = BN_get_word(r2);
262
263         if (bitst < 0x9 || bitst > 0xF) {
264             /*
265              * For keys with more than 4 primes, we attempt longer factor to
266              * meet length requirement.
267              *
268              * Otherwise, we just re-generate the prime with the same length.
269              *
270              * This strategy has the following goals:
271              *
272              * 1. 1024-bit factors are efficient when using 3072 and 4096-bit key
273              * 2. stay the same logic with normal 2-prime key
274              */
275             bitse -= bitsr[i];
276             if (!BN_GENCB_call(cb, 2, n++))
277                 goto err;
278             if (primes > 4) {
279                 if (bitst < 0x9)
280                     adj++;
281                 else
282                     adj--;
283             } else if (retries == 4) {
284                 /*
285                  * re-generate all primes from scratch, mainly used
286                  * in 4 prime case to avoid long loop. Max retry times
287                  * is set to 4.
288                  */
289                 i = -1;
290                 bitse = 0;
291                 continue;
292             }
293             retries++;
294             goto redo;
295         }
296         /* save product of primes for further use, for multi-prime only */
297         if (i > 1 && BN_copy(pinfo->pp, rsa->n) == NULL)
298             goto err;
299         if (BN_copy(rsa->n, r1) == NULL)
300             goto err;
301         if (!BN_GENCB_call(cb, 3, i))
302             goto err;
303     }
304
305     if (BN_cmp(rsa->p, rsa->q) < 0) {
306         tmp = rsa->p;
307         rsa->p = rsa->q;
308         rsa->q = tmp;
309     }
310
311     /* calculate d */
312
313     /* p - 1 */
314     if (!BN_sub(r1, rsa->p, BN_value_one()))
315         goto err;
316     /* q - 1 */
317     if (!BN_sub(r2, rsa->q, BN_value_one()))
318         goto err;
319     /* (p - 1)(q - 1) */
320     if (!BN_mul(r0, r1, r2, ctx))
321         goto err;
322     /* multi-prime */
323     for (i = 2; i < primes; i++) {
324         pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
325         /* save r_i - 1 to pinfo->d temporarily */
326         if (!BN_sub(pinfo->d, pinfo->r, BN_value_one()))
327             goto err;
328         if (!BN_mul(r0, r0, pinfo->d, ctx))
329             goto err;
330     }
331
332     {
333         BIGNUM *pr0 = BN_new();
334
335         if (pr0 == NULL)
336             goto err;
337
338         BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
339         if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
340             BN_free(pr0);
341             goto err;               /* d */
342         }
343         /* We MUST free pr0 before any further use of r0 */
344         BN_free(pr0);
345     }
346
347     {
348         BIGNUM *d = BN_new();
349
350         if (d == NULL)
351             goto err;
352
353         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
354
355         /* calculate d mod (p-1) and d mod (q - 1) */
356         if (!BN_mod(rsa->dmp1, d, r1, ctx)
357             || !BN_mod(rsa->dmq1, d, r2, ctx)) {
358             BN_free(d);
359             goto err;
360         }
361
362         /* calculate CRT exponents */
363         for (i = 2; i < primes; i++) {
364             pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
365             /* pinfo->d == r_i - 1 */
366             if (!BN_mod(pinfo->d, d, pinfo->d, ctx)) {
367                 BN_free(d);
368                 goto err;
369             }
370         }
371
372         /* We MUST free d before any further use of rsa->d */
373         BN_free(d);
374     }
375
376     {
377         BIGNUM *p = BN_new();
378
379         if (p == NULL)
380             goto err;
381         BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
382
383         /* calculate inverse of q mod p */
384         if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
385             BN_free(p);
386             goto err;
387         }
388
389         /* calculate CRT coefficient for other primes */
390         for (i = 2; i < primes; i++) {
391             pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
392             BN_with_flags(p, pinfo->r, BN_FLG_CONSTTIME);
393             if (!BN_mod_inverse(pinfo->t, pinfo->pp, p, ctx)) {
394                 BN_free(p);
395                 goto err;
396             }
397         }
398
399         /* We MUST free p before any further use of rsa->p */
400         BN_free(p);
401     }
402
403     ok = 1;
404  err:
405     if (ok == -1) {
406         RSAerr(0, ERR_LIB_BN);
407         ok = 0;
408     }
409     BN_CTX_end(ctx);
410     BN_CTX_free(ctx);
411     return ok;
412 }
413 #endif /* FIPS_MODULE */
414
415 static int rsa_keygen(OPENSSL_CTX *libctx, RSA *rsa, int bits, int primes,
416                       BIGNUM *e_value, BN_GENCB *cb, int pairwise_test)
417 {
418     int ok = 0;
419
420     /*
421      * Only multi-prime keys or insecure keys with a small key length will use
422      * the older rsa_multiprime_keygen().
423      */
424     if (primes == 2 && bits >= 2048)
425         ok = rsa_sp800_56b_generate_key(rsa, bits, e_value, cb);
426 #ifndef FIPS_MODULE
427     else
428         ok = rsa_multiprime_keygen(rsa, bits, primes, e_value, cb);
429 #endif /* FIPS_MODULE */
430
431 #ifdef FIPS_MODULE
432     pairwise_test = 1; /* FIPS MODE needs to always run the pairwise test */
433 #endif
434     if (pairwise_test && ok > 0) {
435         OSSL_CALLBACK *stcb = NULL;
436         void *stcbarg = NULL;
437
438         OSSL_SELF_TEST_get_callback(libctx, &stcb, &stcbarg);
439         ok = rsa_keygen_pairwise_test(rsa, stcb, stcbarg);
440         if (!ok) {
441             /* Clear intermediate results */
442             BN_clear_free(rsa->d);
443             BN_clear_free(rsa->p);
444             BN_clear_free(rsa->q);
445             BN_clear_free(rsa->dmp1);
446             BN_clear_free(rsa->dmq1);
447             BN_clear_free(rsa->iqmp);
448         }
449     }
450     return ok;
451 }
452
453 /*
454  * For RSA key generation it is not known whether the key pair will be used
455  * for key transport or signatures. FIPS 140-2 IG 9.9 states that in this case
456  * either a signature verification OR an encryption operation may be used to
457  * perform the pairwise consistency check. The simpler encrypt/decrypt operation
458  * has been chosen for this case.
459  */
460 static int rsa_keygen_pairwise_test(RSA *rsa, OSSL_CALLBACK *cb, void *cbarg)
461 {
462     int ret = 0;
463     unsigned int ciphertxt_len;
464     unsigned char *ciphertxt = NULL;
465     const unsigned char plaintxt[16] = {0};
466     unsigned char decoded[256];
467     unsigned int decoded_len;
468     unsigned int plaintxt_len = (unsigned int)sizeof(plaintxt_len);
469     int padding = RSA_PKCS1_PADDING;
470     OSSL_SELF_TEST *st = NULL;
471
472     st = OSSL_SELF_TEST_new(cb, cbarg);
473     if (st == NULL)
474         goto err;
475     OSSL_SELF_TEST_onbegin(st, OSSL_SELF_TEST_TYPE_PCT,
476                            OSSL_SELF_TEST_DESC_PCT_RSA_PKCS1);
477
478     ciphertxt_len = RSA_size(rsa);
479     ciphertxt = OPENSSL_zalloc(ciphertxt_len);
480     if (ciphertxt == NULL)
481         goto err;
482
483     ciphertxt_len = RSA_public_encrypt(plaintxt_len, plaintxt, ciphertxt, rsa,
484                                        padding);
485     if (ciphertxt_len <= 0)
486         goto err;
487     if (ciphertxt_len == plaintxt_len
488         && memcmp(ciphertxt, plaintxt, plaintxt_len) == 0)
489         goto err;
490
491     OSSL_SELF_TEST_oncorrupt_byte(st, ciphertxt);
492
493     decoded_len = RSA_private_decrypt(ciphertxt_len, ciphertxt, decoded, rsa,
494                                       padding);
495     if (decoded_len != plaintxt_len
496         || memcmp(decoded, plaintxt,  decoded_len) != 0)
497         goto err;
498
499     ret = 1;
500 err:
501     OSSL_SELF_TEST_onend(st, ret);
502     OSSL_SELF_TEST_free(st);
503     OPENSSL_free(ciphertxt);
504
505     return ret;
506 }