2 * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
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
11 * NB: these functions have been "upgraded", the deprecated versions (which
12 * are compatibility wrappers using these functions) are in rsa_depr.c. -
17 * RSA low level APIs are deprecated for public use, but still ok for
20 #include "internal/deprecated.h"
24 #include "internal/cryptlib.h"
25 #include <openssl/bn.h>
26 #include <openssl/self_test.h>
27 #include "prov/providercommon.h"
28 #include "rsa_local.h"
30 static int rsa_keygen_pairwise_test(RSA
*rsa
, OSSL_CALLBACK
*cb
, void *cbarg
);
31 static int rsa_keygen(OSSL_LIB_CTX
*libctx
, RSA
*rsa
, int bits
, int primes
,
32 BIGNUM
*e_value
, BN_GENCB
*cb
, int pairwise_test
);
35 * NB: this wrapper would normally be placed in rsa_lib.c and the static
36 * implementation would probably be in rsa_eay.c. Nonetheless, is kept here
37 * so that we don't introduce a new linker dependency. Eg. any application
38 * that wasn't previously linking object code related to key-generation won't
39 * have to now just because key-generation is part of RSA_METHOD.
41 int RSA_generate_key_ex(RSA
*rsa
, int bits
, BIGNUM
*e_value
, BN_GENCB
*cb
)
43 if (rsa
->meth
->rsa_keygen
!= NULL
)
44 return rsa
->meth
->rsa_keygen(rsa
, bits
, e_value
, cb
);
46 return RSA_generate_multi_prime_key(rsa
, bits
, RSA_DEFAULT_PRIME_NUM
,
50 int RSA_generate_multi_prime_key(RSA
*rsa
, int bits
, int primes
,
51 BIGNUM
*e_value
, BN_GENCB
*cb
)
54 /* multi-prime is only supported with the builtin key generation */
55 if (rsa
->meth
->rsa_multi_prime_keygen
!= NULL
) {
56 return rsa
->meth
->rsa_multi_prime_keygen(rsa
, bits
, primes
,
58 } else if (rsa
->meth
->rsa_keygen
!= NULL
) {
60 * However, if rsa->meth implements only rsa_keygen, then we
61 * have to honour it in 2-prime case and assume that it wouldn't
62 * know what to do with multi-prime key generated by builtin
66 return rsa
->meth
->rsa_keygen(rsa
, bits
, e_value
, cb
);
70 #endif /* FIPS_MODULE */
71 return rsa_keygen(rsa
->libctx
, rsa
, bits
, primes
, e_value
, cb
, 0);
74 DEFINE_STACK_OF(BIGNUM
)
77 * Given input values, q, p, n, d and e, derive the exponents
78 * and coefficients for each prime in this key, placing the result
79 * on their respective exps and coeffs stacks
82 int ossl_rsa_multiprime_derive(RSA
*rsa
, int bits
, int primes
,
84 STACK_OF(BIGNUM
) *factors
,
85 STACK_OF(BIGNUM
) *exps
,
86 STACK_OF(BIGNUM
) *coeffs
)
88 STACK_OF(BIGNUM
) *pplist
= NULL
, *pdlist
= NULL
;
89 BIGNUM
*factor
= NULL
, *newpp
= NULL
, *newpd
= NULL
;
90 BIGNUM
*dval
= NULL
, *newexp
= NULL
, *newcoeff
= NULL
;
91 BIGNUM
*p
= NULL
, *q
= NULL
;
92 BIGNUM
*dmp1
= NULL
, *dmq1
= NULL
, *iqmp
= NULL
;
93 BIGNUM
*r0
= NULL
, *r1
= NULL
, *r2
= NULL
;
99 ctx
= BN_CTX_new_ex(rsa
->libctx
);
105 pplist
= sk_BIGNUM_new_null();
109 pdlist
= sk_BIGNUM_new_null();
113 r0
= BN_CTX_get(ctx
);
114 r1
= BN_CTX_get(ctx
);
115 r2
= BN_CTX_get(ctx
);
120 BN_set_flags(r0
, BN_FLG_CONSTTIME
);
121 BN_set_flags(r1
, BN_FLG_CONSTTIME
);
122 BN_set_flags(r2
, BN_FLG_CONSTTIME
);
124 if (BN_copy(r1
, rsa
->n
) == NULL
)
127 p
= sk_BIGNUM_value(factors
, 0);
128 q
= sk_BIGNUM_value(factors
, 1);
130 /* Build list of partial products of primes */
131 for (i
= 0; i
< sk_BIGNUM_num(factors
); i
++) {
134 /* our first prime, p */
135 if (!BN_sub(r2
, p
, BN_value_one()))
137 BN_set_flags(r2
, BN_FLG_CONSTTIME
);
138 if (BN_mod_inverse(r1
, r2
, rsa
->e
, ctx
) == NULL
)
143 if (!BN_mul(r1
, p
, q
, ctx
))
148 if (!sk_BIGNUM_insert(pplist
, tmp
, sk_BIGNUM_num(pplist
)))
152 factor
= sk_BIGNUM_value(factors
, i
);
153 /* all other primes */
154 if (!BN_mul(r1
, r1
, factor
, ctx
))
159 if (!sk_BIGNUM_insert(pplist
, tmp
, sk_BIGNUM_num(pplist
)))
165 /* build list of relative d values */
167 if (!BN_sub(r1
, p
, BN_value_one()))
169 if (!BN_sub(r2
, q
, BN_value_one()))
171 if (!BN_mul(r0
, r1
, r2
, ctx
))
173 for (i
= 2; i
< sk_BIGNUM_num(factors
); i
++) {
174 factor
= sk_BIGNUM_value(factors
, i
);
178 BN_set_flags(dval
, BN_FLG_CONSTTIME
);
179 if (!BN_sub(dval
, factor
, BN_value_one()))
181 if (!BN_mul(r0
, r0
, dval
, ctx
))
183 if (!sk_BIGNUM_insert(pdlist
, dval
, sk_BIGNUM_num(pdlist
)))
187 /* Calculate dmp1, dmq1 and additional exponents */
188 dmp1
= BN_secure_new();
191 dmq1
= BN_secure_new();
195 if (!BN_mod(dmp1
, rsa
->d
, r1
, ctx
))
197 if (!sk_BIGNUM_insert(exps
, dmp1
, sk_BIGNUM_num(exps
)))
201 if (!BN_mod(dmq1
, rsa
->d
, r2
, ctx
))
203 if (!sk_BIGNUM_insert(exps
, dmq1
, sk_BIGNUM_num(exps
)))
207 for (i
= 2; i
< sk_BIGNUM_num(factors
); i
++) {
208 newpd
= sk_BIGNUM_value(pdlist
, i
- 2);
212 if (!BN_mod(newexp
, rsa
->d
, newpd
, ctx
)) {
216 if (!sk_BIGNUM_insert(exps
, newexp
, sk_BIGNUM_num(exps
)))
220 /* Calculate iqmp and additional coefficients */
225 if (BN_mod_inverse(iqmp
, sk_BIGNUM_value(factors
, 1),
226 sk_BIGNUM_value(factors
, 0), ctx
) == NULL
)
228 if (!sk_BIGNUM_insert(coeffs
, iqmp
, sk_BIGNUM_num(coeffs
)))
232 for (i
= 2; i
< sk_BIGNUM_num(factors
); i
++) {
233 newpp
= sk_BIGNUM_value(pplist
, i
- 2);
235 if (newcoeff
== NULL
)
237 if (BN_mod_inverse(newcoeff
, newpp
, sk_BIGNUM_value(factors
, i
),
242 if (!sk_BIGNUM_insert(coeffs
, newcoeff
, sk_BIGNUM_num(coeffs
)))
248 sk_BIGNUM_pop_free(pplist
, BN_free
);
249 sk_BIGNUM_pop_free(pdlist
, BN_free
);
258 static int rsa_multiprime_keygen(RSA
*rsa
, int bits
, int primes
,
259 BIGNUM
*e_value
, BN_GENCB
*cb
)
261 BIGNUM
*r0
= NULL
, *r1
= NULL
, *r2
= NULL
, *tmp
, *tmp2
, *prime
;
262 int n
= 0, bitsr
[RSA_MAX_PRIME_NUM
], bitse
= 0;
263 int i
= 0, quo
= 0, rmd
= 0, adj
= 0, retries
= 0;
264 RSA_PRIME_INFO
*pinfo
= NULL
;
265 STACK_OF(RSA_PRIME_INFO
) *prime_infos
= NULL
;
266 STACK_OF(BIGNUM
) *factors
= NULL
;
267 STACK_OF(BIGNUM
) *exps
= NULL
;
268 STACK_OF(BIGNUM
) *coeffs
= NULL
;
271 unsigned long error
= 0;
274 if (bits
< RSA_MIN_MODULUS_BITS
) {
275 ERR_raise(ERR_LIB_RSA
, RSA_R_KEY_SIZE_TOO_SMALL
);
278 if (e_value
== NULL
) {
279 ERR_raise(ERR_LIB_RSA
, RSA_R_BAD_E_VALUE
);
282 /* A bad value for e can cause infinite loops */
283 if (!ossl_rsa_check_public_exponent(e_value
)) {
284 ERR_raise(ERR_LIB_RSA
, RSA_R_PUB_EXPONENT_OUT_OF_RANGE
);
288 if (primes
< RSA_DEFAULT_PRIME_NUM
|| primes
> ossl_rsa_multip_cap(bits
)) {
289 ERR_raise(ERR_LIB_RSA
, RSA_R_KEY_PRIME_NUM_INVALID
);
293 factors
= sk_BIGNUM_new_null();
297 exps
= sk_BIGNUM_new_null();
301 coeffs
= sk_BIGNUM_new_null();
305 ctx
= BN_CTX_new_ex(rsa
->libctx
);
309 r0
= BN_CTX_get(ctx
);
310 r1
= BN_CTX_get(ctx
);
311 r2
= BN_CTX_get(ctx
);
315 /* divide bits into 'primes' pieces evenly */
319 for (i
= 0; i
< primes
; i
++)
320 bitsr
[i
] = (i
< rmd
) ? quo
+ 1 : quo
;
324 /* We need the RSA components non-NULL */
325 if (!rsa
->n
&& ((rsa
->n
= BN_new()) == NULL
))
327 if (!rsa
->d
&& ((rsa
->d
= BN_secure_new()) == NULL
))
329 BN_set_flags(rsa
->d
, BN_FLG_CONSTTIME
);
330 if (!rsa
->e
&& ((rsa
->e
= BN_new()) == NULL
))
332 if (!rsa
->p
&& ((rsa
->p
= BN_secure_new()) == NULL
))
334 BN_set_flags(rsa
->p
, BN_FLG_CONSTTIME
);
335 if (!rsa
->q
&& ((rsa
->q
= BN_secure_new()) == NULL
))
337 BN_set_flags(rsa
->q
, BN_FLG_CONSTTIME
);
339 /* initialize multi-prime components */
340 if (primes
> RSA_DEFAULT_PRIME_NUM
) {
341 rsa
->version
= RSA_ASN1_VERSION_MULTI
;
342 prime_infos
= sk_RSA_PRIME_INFO_new_reserve(NULL
, primes
- 2);
343 if (prime_infos
== NULL
)
345 if (rsa
->prime_infos
!= NULL
) {
346 /* could this happen? */
347 sk_RSA_PRIME_INFO_pop_free(rsa
->prime_infos
,
348 ossl_rsa_multip_info_free
);
350 rsa
->prime_infos
= prime_infos
;
352 /* prime_info from 2 to |primes| -1 */
353 for (i
= 2; i
< primes
; i
++) {
354 pinfo
= ossl_rsa_multip_info_new();
357 (void)sk_RSA_PRIME_INFO_push(prime_infos
, pinfo
);
361 if (BN_copy(rsa
->e
, e_value
) == NULL
)
364 /* generate p, q and other primes (if any) */
365 for (i
= 0; i
< primes
; i
++) {
374 pinfo
= sk_RSA_PRIME_INFO_value(prime_infos
, i
- 2);
377 BN_set_flags(prime
, BN_FLG_CONSTTIME
);
381 if (!BN_generate_prime_ex2(prime
, bitsr
[i
] + adj
, 0, NULL
, NULL
,
385 * prime should not be equal to p, q, r_3...
386 * (those primes prior to this one)
391 for (j
= 0; j
< i
; j
++) {
399 prev_prime
= sk_RSA_PRIME_INFO_value(prime_infos
,
402 if (!BN_cmp(prime
, prev_prime
)) {
407 if (!BN_sub(r2
, prime
, BN_value_one()))
410 BN_set_flags(r2
, BN_FLG_CONSTTIME
);
411 if (BN_mod_inverse(r1
, r2
, rsa
->e
, ctx
) != NULL
) {
412 /* GCD == 1 since inverse exists */
415 error
= ERR_peek_last_error();
416 if (ERR_GET_LIB(error
) == ERR_LIB_BN
417 && ERR_GET_REASON(error
) == BN_R_NO_INVERSE
) {
423 if (!BN_GENCB_call(cb
, 2, n
++))
429 /* calculate n immediately to see if it's sufficient */
431 /* we get at least 2 primes */
432 if (!BN_mul(r1
, rsa
->p
, rsa
->q
, ctx
))
435 /* modulus n = p * q * r_3 * r_4 ... */
436 if (!BN_mul(r1
, rsa
->n
, prime
, ctx
))
439 /* i == 0, do nothing */
440 if (!BN_GENCB_call(cb
, 3, i
))
445 if (!sk_BIGNUM_insert(factors
, tmp
, sk_BIGNUM_num(factors
)))
451 * if |r1|, product of factors so far, is not as long as expected
452 * (by checking the first 4 bits are less than 0x9 or greater than
453 * 0xF). If so, re-generate the last prime.
455 * NOTE: This actually can't happen in two-prime case, because of
456 * the way factors are generated.
458 * Besides, another consideration is, for multi-prime case, even the
459 * length modulus is as long as expected, the modulus could start at
460 * 0x8, which could be utilized to distinguish a multi-prime private
461 * key by using the modulus in a certificate. This is also covered
462 * by checking the length should not be less than 0x9.
464 if (!BN_rshift(r2
, r1
, bitse
- 4))
466 bitst
= BN_get_word(r2
);
468 if (bitst
< 0x9 || bitst
> 0xF) {
470 * For keys with more than 4 primes, we attempt longer factor to
471 * meet length requirement.
473 * Otherwise, we just re-generate the prime with the same length.
475 * This strategy has the following goals:
477 * 1. 1024-bit factors are efficient when using 3072 and 4096-bit key
478 * 2. stay the same logic with normal 2-prime key
481 if (!BN_GENCB_call(cb
, 2, n
++))
488 } else if (retries
== 4) {
490 * re-generate all primes from scratch, mainly used
491 * in 4 prime case to avoid long loop. Max retry times
496 sk_BIGNUM_pop_free(factors
, BN_clear_free
);
497 factors
= sk_BIGNUM_new_null();
505 /* save product of primes for further use, for multi-prime only */
506 if (i
> 1 && BN_copy(pinfo
->pp
, rsa
->n
) == NULL
)
508 if (BN_copy(rsa
->n
, r1
) == NULL
)
510 if (!BN_GENCB_call(cb
, 3, i
))
515 if (!sk_BIGNUM_insert(factors
, tmp
, sk_BIGNUM_num(factors
)))
519 if (BN_cmp(rsa
->p
, rsa
->q
) < 0) {
523 /* mirror this in our factor stack */
524 if (!sk_BIGNUM_insert(factors
, sk_BIGNUM_delete(factors
, 0), 1))
531 if (!BN_sub(r1
, rsa
->p
, BN_value_one()))
534 if (!BN_sub(r2
, rsa
->q
, BN_value_one()))
537 if (!BN_mul(r0
, r1
, r2
, ctx
))
540 for (i
= 2; i
< primes
; i
++) {
541 pinfo
= sk_RSA_PRIME_INFO_value(prime_infos
, i
- 2);
542 /* save r_i - 1 to pinfo->d temporarily */
543 if (!BN_sub(pinfo
->d
, pinfo
->r
, BN_value_one()))
545 if (!BN_mul(r0
, r0
, pinfo
->d
, ctx
))
550 BN_set_flags(r0
, BN_FLG_CONSTTIME
);
551 if (BN_mod_inverse(rsa
->d
, rsa
->e
, r0
, ctx
) == NULL
) {
555 /* derive any missing exponents and coefficients */
556 if (!ossl_rsa_multiprime_derive(rsa
, bits
, primes
, e_value
,
557 factors
, exps
, coeffs
))
561 * first 2 factors/exps are already tracked in p/q/dmq1/dmp1
562 * and the first coeff is in iqmp, so pop those off the stack
563 * Note, the first 2 factors/exponents are already tracked by p and q
564 * assign dmp1/dmq1 and iqmp
565 * the remaining pinfo values are separately allocated, so copy and delete
568 BN_clear_free(sk_BIGNUM_delete(factors
, 0));
569 BN_clear_free(sk_BIGNUM_delete(factors
, 0));
570 rsa
->dmp1
= sk_BIGNUM_delete(exps
, 0);
571 rsa
->dmq1
= sk_BIGNUM_delete(exps
, 0);
572 rsa
->iqmp
= sk_BIGNUM_delete(coeffs
, 0);
573 for (i
= 2; i
< primes
; i
++) {
574 pinfo
= sk_RSA_PRIME_INFO_value(prime_infos
, i
- 2);
575 tmp
= sk_BIGNUM_delete(factors
, 0);
576 BN_copy(pinfo
->r
, tmp
);
578 tmp
= sk_BIGNUM_delete(exps
, 0);
579 tmp2
= BN_copy(pinfo
->d
, tmp
);
583 tmp
= sk_BIGNUM_delete(coeffs
, 0);
584 tmp2
= BN_copy(pinfo
->t
, tmp
);
591 sk_BIGNUM_free(factors
);
592 sk_BIGNUM_free(exps
);
593 sk_BIGNUM_free(coeffs
);
595 ERR_raise(ERR_LIB_RSA
, ERR_R_BN_LIB
);
602 #endif /* FIPS_MODULE */
604 static int rsa_keygen(OSSL_LIB_CTX
*libctx
, RSA
*rsa
, int bits
, int primes
,
605 BIGNUM
*e_value
, BN_GENCB
*cb
, int pairwise_test
)
610 ok
= ossl_rsa_sp800_56b_generate_key(rsa
, bits
, e_value
, cb
);
611 pairwise_test
= 1; /* FIPS MODE needs to always run the pairwise test */
614 * Only multi-prime keys or insecure keys with a small key length or a
615 * public exponent <= 2^16 will use the older rsa_multiprime_keygen().
619 && (e_value
== NULL
|| BN_num_bits(e_value
) > 16))
620 ok
= ossl_rsa_sp800_56b_generate_key(rsa
, bits
, e_value
, cb
);
622 ok
= rsa_multiprime_keygen(rsa
, bits
, primes
, e_value
, cb
);
623 #endif /* FIPS_MODULE */
625 if (pairwise_test
&& ok
> 0) {
626 OSSL_CALLBACK
*stcb
= NULL
;
627 void *stcbarg
= NULL
;
629 OSSL_SELF_TEST_get_callback(libctx
, &stcb
, &stcbarg
);
630 ok
= rsa_keygen_pairwise_test(rsa
, stcb
, stcbarg
);
632 ossl_set_error_state(OSSL_SELF_TEST_TYPE_PCT
);
633 /* Clear intermediate results */
634 BN_clear_free(rsa
->d
);
635 BN_clear_free(rsa
->p
);
636 BN_clear_free(rsa
->q
);
637 BN_clear_free(rsa
->dmp1
);
638 BN_clear_free(rsa
->dmq1
);
639 BN_clear_free(rsa
->iqmp
);
652 * For RSA key generation it is not known whether the key pair will be used
653 * for key transport or signatures. FIPS 140-2 IG 9.9 states that in this case
654 * either a signature verification OR an encryption operation may be used to
655 * perform the pairwise consistency check. The simpler encrypt/decrypt operation
656 * has been chosen for this case.
658 static int rsa_keygen_pairwise_test(RSA
*rsa
, OSSL_CALLBACK
*cb
, void *cbarg
)
661 unsigned int ciphertxt_len
;
662 unsigned char *ciphertxt
= NULL
;
663 const unsigned char plaintxt
[16] = {0};
664 unsigned char *decoded
= NULL
;
665 unsigned int decoded_len
;
666 unsigned int plaintxt_len
= (unsigned int)sizeof(plaintxt_len
);
667 int padding
= RSA_PKCS1_PADDING
;
668 OSSL_SELF_TEST
*st
= NULL
;
670 st
= OSSL_SELF_TEST_new(cb
, cbarg
);
673 OSSL_SELF_TEST_onbegin(st
, OSSL_SELF_TEST_TYPE_PCT
,
674 OSSL_SELF_TEST_DESC_PCT_RSA_PKCS1
);
676 ciphertxt_len
= RSA_size(rsa
);
678 * RSA_private_encrypt() and RSA_private_decrypt() requires the 'to'
679 * parameter to be a maximum of RSA_size() - allocate space for both.
681 ciphertxt
= OPENSSL_zalloc(ciphertxt_len
* 2);
682 if (ciphertxt
== NULL
)
684 decoded
= ciphertxt
+ ciphertxt_len
;
686 ciphertxt_len
= RSA_public_encrypt(plaintxt_len
, plaintxt
, ciphertxt
, rsa
,
688 if (ciphertxt_len
<= 0)
690 if (ciphertxt_len
== plaintxt_len
691 && memcmp(ciphertxt
, plaintxt
, plaintxt_len
) == 0)
694 OSSL_SELF_TEST_oncorrupt_byte(st
, ciphertxt
);
696 decoded_len
= RSA_private_decrypt(ciphertxt_len
, ciphertxt
, decoded
, rsa
,
698 if (decoded_len
!= plaintxt_len
699 || memcmp(decoded
, plaintxt
, decoded_len
) != 0)
704 OSSL_SELF_TEST_onend(st
, ret
);
705 OSSL_SELF_TEST_free(st
);
706 OPENSSL_free(ciphertxt
);