2 * Copyright 1995-2024 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 * RSA low level APIs are deprecated for public use, but still ok for
14 #include "internal/deprecated.h"
16 #include "internal/cryptlib.h"
17 #include "crypto/bn.h"
18 #include "crypto/sparse_array.h"
19 #include "rsa_local.h"
20 #include "internal/constant_time.h"
21 #include <openssl/evp.h>
22 #include <openssl/sha.h>
23 #include <openssl/hmac.h>
25 DEFINE_SPARSE_ARRAY_OF(BN_BLINDING
);
27 static int rsa_ossl_public_encrypt(int flen
, const unsigned char *from
,
28 unsigned char *to
, RSA
*rsa
, int padding
);
29 static int rsa_ossl_private_encrypt(int flen
, const unsigned char *from
,
30 unsigned char *to
, RSA
*rsa
, int padding
);
31 static int rsa_ossl_public_decrypt(int flen
, const unsigned char *from
,
32 unsigned char *to
, RSA
*rsa
, int padding
);
33 static int rsa_ossl_private_decrypt(int flen
, const unsigned char *from
,
34 unsigned char *to
, RSA
*rsa
, int padding
);
35 static int rsa_ossl_mod_exp(BIGNUM
*r0
, const BIGNUM
*i
, RSA
*rsa
,
37 static int rsa_ossl_init(RSA
*rsa
);
38 static int rsa_ossl_finish(RSA
*rsa
);
40 static int rsa_ossl_s390x_mod_exp(BIGNUM
*r0
, const BIGNUM
*i
, RSA
*rsa
,
42 static RSA_METHOD rsa_pkcs1_ossl_meth
= {
44 rsa_ossl_public_encrypt
,
45 rsa_ossl_public_decrypt
, /* signature verification */
46 rsa_ossl_private_encrypt
, /* signing */
47 rsa_ossl_private_decrypt
,
48 rsa_ossl_s390x_mod_exp
,
52 RSA_FLAG_FIPS_METHOD
, /* flags */
56 NULL
, /* rsa_keygen */
57 NULL
/* rsa_multi_prime_keygen */
60 static RSA_METHOD rsa_pkcs1_ossl_meth
= {
62 rsa_ossl_public_encrypt
,
63 rsa_ossl_public_decrypt
, /* signature verification */
64 rsa_ossl_private_encrypt
, /* signing */
65 rsa_ossl_private_decrypt
,
67 BN_mod_exp_mont
, /* XXX probably we should not use Montgomery
71 RSA_FLAG_FIPS_METHOD
, /* flags */
75 NULL
, /* rsa_keygen */
76 NULL
/* rsa_multi_prime_keygen */
80 static const RSA_METHOD
*default_RSA_meth
= &rsa_pkcs1_ossl_meth
;
82 void RSA_set_default_method(const RSA_METHOD
*meth
)
84 default_RSA_meth
= meth
;
87 const RSA_METHOD
*RSA_get_default_method(void)
89 return default_RSA_meth
;
92 const RSA_METHOD
*RSA_PKCS1_OpenSSL(void)
94 return &rsa_pkcs1_ossl_meth
;
97 const RSA_METHOD
*RSA_null_method(void)
102 static int rsa_ossl_public_encrypt(int flen
, const unsigned char *from
,
103 unsigned char *to
, RSA
*rsa
, int padding
)
106 int i
, num
= 0, r
= -1;
107 unsigned char *buf
= NULL
;
110 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_MAX_MODULUS_BITS
) {
111 ERR_raise(ERR_LIB_RSA
, RSA_R_MODULUS_TOO_LARGE
);
115 if (BN_ucmp(rsa
->n
, rsa
->e
) <= 0) {
116 ERR_raise(ERR_LIB_RSA
, RSA_R_BAD_E_VALUE
);
120 /* for large moduli, enforce exponent limit */
121 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_SMALL_MODULUS_BITS
) {
122 if (BN_num_bits(rsa
->e
) > OPENSSL_RSA_MAX_PUBEXP_BITS
) {
123 ERR_raise(ERR_LIB_RSA
, RSA_R_BAD_E_VALUE
);
128 if ((ctx
= BN_CTX_new_ex(rsa
->libctx
)) == NULL
)
132 ret
= BN_CTX_get(ctx
);
133 num
= BN_num_bytes(rsa
->n
);
134 buf
= OPENSSL_malloc(num
);
135 if (ret
== NULL
|| buf
== NULL
)
139 case RSA_PKCS1_PADDING
:
140 i
= ossl_rsa_padding_add_PKCS1_type_2_ex(rsa
->libctx
, buf
, num
,
143 case RSA_PKCS1_OAEP_PADDING
:
144 i
= ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex(rsa
->libctx
, buf
, num
,
149 i
= RSA_padding_add_none(buf
, num
, from
, flen
);
152 ERR_raise(ERR_LIB_RSA
, RSA_R_UNKNOWN_PADDING_TYPE
);
158 if (BN_bin2bn(buf
, num
, f
) == NULL
)
163 * See SP800-56Br2, section 7.1.1.1
164 * RSAEP: 1 < f < (n – 1).
165 * (where f is the plaintext).
167 if (padding
== RSA_NO_PADDING
) {
168 BIGNUM
*nminus1
= BN_CTX_get(ctx
);
170 if (BN_ucmp(f
, BN_value_one()) <= 0) {
171 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_SMALL
);
175 || BN_copy(nminus1
, rsa
->n
) == NULL
176 || !BN_sub_word(nminus1
, 1))
178 if (BN_ucmp(f
, nminus1
) >= 0) {
179 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
185 if (BN_ucmp(f
, rsa
->n
) >= 0) {
186 /* usually the padding functions would catch this */
187 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
192 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
193 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
197 if (!rsa
->meth
->bn_mod_exp(ret
, f
, rsa
->e
, rsa
->n
, ctx
,
202 * BN_bn2binpad puts in leading 0 bytes if the number is less than
203 * the length of the modulus.
205 r
= BN_bn2binpad(ret
, to
, num
);
209 OPENSSL_clear_free(buf
, num
);
213 static void free_bn_blinding(ossl_uintmax_t idx
, BN_BLINDING
*b
, void *arg
)
218 void ossl_rsa_free_blinding(RSA
*rsa
)
220 SPARSE_ARRAY_OF(BN_BLINDING
) *blindings
= rsa
->blindings_sa
;
222 ossl_sa_BN_BLINDING_doall_arg(blindings
, free_bn_blinding
, NULL
);
223 ossl_sa_BN_BLINDING_free(blindings
);
226 void *ossl_rsa_alloc_blinding(void)
228 return ossl_sa_BN_BLINDING_new();
231 static BN_BLINDING
*ossl_rsa_get_thread_bn_blinding(RSA
*rsa
)
233 SPARSE_ARRAY_OF(BN_BLINDING
) *blindings
= rsa
->blindings_sa
;
234 uintptr_t tid
= (uintptr_t)CRYPTO_THREAD_get_current_id();
236 return ossl_sa_BN_BLINDING_get(blindings
, tid
);
239 static int ossl_rsa_set_thread_bn_blinding(RSA
*rsa
, BN_BLINDING
*b
)
241 SPARSE_ARRAY_OF(BN_BLINDING
) *blindings
= rsa
->blindings_sa
;
242 uintptr_t tid
= (uintptr_t)CRYPTO_THREAD_get_current_id();
244 return ossl_sa_BN_BLINDING_set(blindings
, tid
, b
);
247 static BN_BLINDING
*rsa_get_blinding(RSA
*rsa
, BN_CTX
*ctx
)
251 if (!CRYPTO_THREAD_read_lock(rsa
->lock
))
254 ret
= ossl_rsa_get_thread_bn_blinding(rsa
);
255 CRYPTO_THREAD_unlock(rsa
->lock
);
258 ret
= RSA_setup_blinding(rsa
, ctx
);
259 if (!CRYPTO_THREAD_write_lock(rsa
->lock
)) {
260 BN_BLINDING_free(ret
);
263 if (!ossl_rsa_set_thread_bn_blinding(rsa
, ret
)) {
264 BN_BLINDING_free(ret
);
268 CRYPTO_THREAD_unlock(rsa
->lock
);
274 static int rsa_blinding_convert(BN_BLINDING
*b
, BIGNUM
*f
, BN_CTX
*ctx
)
277 * Local blinding: store the unblinding factor in BN_BLINDING.
279 return BN_BLINDING_convert_ex(f
, NULL
, b
, ctx
);
282 static int rsa_blinding_invert(BN_BLINDING
*b
, BIGNUM
*f
, BN_CTX
*ctx
)
285 * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
286 * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
287 * is shared between threads, unblind must be non-null:
288 * BN_BLINDING_invert_ex will then use the local unblinding factor, and
289 * will only read the modulus from BN_BLINDING. In both cases it's safe
290 * to access the blinding without a lock.
292 BN_set_flags(f
, BN_FLG_CONSTTIME
);
293 return BN_BLINDING_invert_ex(f
, NULL
, b
, ctx
);
297 static int rsa_ossl_private_encrypt(int flen
, const unsigned char *from
,
298 unsigned char *to
, RSA
*rsa
, int padding
)
300 BIGNUM
*f
, *ret
, *res
;
301 int i
, num
= 0, r
= -1;
302 unsigned char *buf
= NULL
;
304 BN_BLINDING
*blinding
= NULL
;
306 if ((ctx
= BN_CTX_new_ex(rsa
->libctx
)) == NULL
)
310 ret
= BN_CTX_get(ctx
);
311 num
= BN_num_bytes(rsa
->n
);
312 buf
= OPENSSL_malloc(num
);
313 if (ret
== NULL
|| buf
== NULL
)
317 case RSA_PKCS1_PADDING
:
318 i
= RSA_padding_add_PKCS1_type_1(buf
, num
, from
, flen
);
320 case RSA_X931_PADDING
:
321 i
= RSA_padding_add_X931(buf
, num
, from
, flen
);
324 i
= RSA_padding_add_none(buf
, num
, from
, flen
);
327 ERR_raise(ERR_LIB_RSA
, RSA_R_UNKNOWN_PADDING_TYPE
);
333 if (BN_bin2bn(buf
, num
, f
) == NULL
)
336 if (BN_ucmp(f
, rsa
->n
) >= 0) {
337 /* usually the padding functions would catch this */
338 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
342 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
343 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
347 if (!(rsa
->flags
& RSA_FLAG_NO_BLINDING
)) {
348 blinding
= rsa_get_blinding(rsa
, ctx
);
349 if (blinding
== NULL
) {
350 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
354 if (!rsa_blinding_convert(blinding
, f
, ctx
))
358 if ((rsa
->flags
& RSA_FLAG_EXT_PKEY
) ||
359 (rsa
->version
== RSA_ASN1_VERSION_MULTI
) ||
362 (rsa
->dmp1
!= NULL
) && (rsa
->dmq1
!= NULL
) && (rsa
->iqmp
!= NULL
))) {
363 if (!rsa
->meth
->rsa_mod_exp(ret
, f
, rsa
, ctx
))
366 BIGNUM
*d
= BN_new();
368 ERR_raise(ERR_LIB_RSA
, ERR_R_BN_LIB
);
371 if (rsa
->d
== NULL
) {
372 ERR_raise(ERR_LIB_RSA
, RSA_R_MISSING_PRIVATE_KEY
);
376 BN_with_flags(d
, rsa
->d
, BN_FLG_CONSTTIME
);
378 if (!rsa
->meth
->bn_mod_exp(ret
, f
, d
, rsa
->n
, ctx
,
379 rsa
->_method_mod_n
)) {
383 /* We MUST free d before any further use of rsa->d */
388 if (!rsa_blinding_invert(blinding
, ret
, ctx
))
391 if (padding
== RSA_X931_PADDING
) {
392 if (!BN_sub(f
, rsa
->n
, ret
))
394 if (BN_cmp(ret
, f
) > 0)
403 * BN_bn2binpad puts in leading 0 bytes if the number is less than
404 * the length of the modulus.
406 r
= BN_bn2binpad(res
, to
, num
);
410 OPENSSL_clear_free(buf
, num
);
414 static int derive_kdk(int flen
, const unsigned char *from
, RSA
*rsa
,
415 unsigned char *buf
, int num
, unsigned char *kdk
)
418 HMAC_CTX
*hmac
= NULL
;
420 unsigned int md_len
= SHA256_DIGEST_LENGTH
;
421 unsigned char d_hash
[SHA256_DIGEST_LENGTH
] = {0};
423 * because we use d as a handle to rsa->d we need to keep it local and
424 * free before any further use of rsa->d
426 BIGNUM
*d
= BN_new();
429 ERR_raise(ERR_LIB_RSA
, ERR_R_CRYPTO_LIB
);
432 if (rsa
->d
== NULL
) {
433 ERR_raise(ERR_LIB_RSA
, RSA_R_MISSING_PRIVATE_KEY
);
437 BN_with_flags(d
, rsa
->d
, BN_FLG_CONSTTIME
);
438 if (BN_bn2binpad(d
, buf
, num
) < 0) {
439 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
446 * we use hardcoded hash so that migrating between versions that use
447 * different hash doesn't provide a Bleichenbacher oracle:
448 * if the attacker can see that different versions return different
449 * messages for the same ciphertext, they'll know that the message is
450 * synthetically generated, which means that the padding check failed
452 md
= EVP_MD_fetch(rsa
->libctx
, "sha256", NULL
);
454 ERR_raise(ERR_LIB_RSA
, ERR_R_FETCH_FAILED
);
458 if (EVP_Digest(buf
, num
, d_hash
, NULL
, md
, NULL
) <= 0) {
459 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
463 hmac
= HMAC_CTX_new();
465 ERR_raise(ERR_LIB_RSA
, ERR_R_CRYPTO_LIB
);
469 if (HMAC_Init_ex(hmac
, d_hash
, sizeof(d_hash
), md
, NULL
) <= 0) {
470 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
475 memset(buf
, 0, num
- flen
);
476 if (HMAC_Update(hmac
, buf
, num
- flen
) <= 0) {
477 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
481 if (HMAC_Update(hmac
, from
, flen
) <= 0) {
482 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
486 md_len
= SHA256_DIGEST_LENGTH
;
487 if (HMAC_Final(hmac
, kdk
, &md_len
) <= 0) {
488 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
499 static int rsa_ossl_private_decrypt(int flen
, const unsigned char *from
,
500 unsigned char *to
, RSA
*rsa
, int padding
)
503 int j
, num
= 0, r
= -1;
504 unsigned char *buf
= NULL
;
505 unsigned char kdk
[SHA256_DIGEST_LENGTH
] = {0};
507 BN_BLINDING
*blinding
= NULL
;
510 * we need the value of the private exponent to perform implicit rejection
512 if ((rsa
->flags
& RSA_FLAG_EXT_PKEY
) && (padding
== RSA_PKCS1_PADDING
))
513 padding
= RSA_PKCS1_NO_IMPLICIT_REJECT_PADDING
;
515 if ((ctx
= BN_CTX_new_ex(rsa
->libctx
)) == NULL
)
519 ret
= BN_CTX_get(ctx
);
521 ERR_raise(ERR_LIB_RSA
, ERR_R_BN_LIB
);
524 num
= BN_num_bytes(rsa
->n
);
525 buf
= OPENSSL_malloc(num
);
530 * This check was for equality but PGP does evil things and chops off the
534 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_GREATER_THAN_MOD_LEN
);
539 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_SMALL
);
543 /* make data into a big number */
544 if (BN_bin2bn(from
, (int)flen
, f
) == NULL
)
549 * See SP800-56Br2, section 7.1.2.1
550 * RSADP: 1 < f < (n – 1)
551 * (where f is the ciphertext).
553 if (padding
== RSA_NO_PADDING
) {
554 BIGNUM
*nminus1
= BN_CTX_get(ctx
);
556 if (BN_ucmp(f
, BN_value_one()) <= 0) {
557 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_SMALL
);
561 || BN_copy(nminus1
, rsa
->n
) == NULL
562 || !BN_sub_word(nminus1
, 1))
564 if (BN_ucmp(f
, nminus1
) >= 0) {
565 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
571 if (BN_ucmp(f
, rsa
->n
) >= 0) {
572 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
576 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
577 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
581 if (!(rsa
->flags
& RSA_FLAG_NO_BLINDING
)) {
582 blinding
= rsa_get_blinding(rsa
, ctx
);
583 if (blinding
== NULL
) {
584 ERR_raise(ERR_LIB_RSA
, ERR_R_INTERNAL_ERROR
);
588 if (!rsa_blinding_convert(blinding
, f
, ctx
))
593 if ((rsa
->flags
& RSA_FLAG_EXT_PKEY
) ||
594 (rsa
->version
== RSA_ASN1_VERSION_MULTI
) ||
597 (rsa
->dmp1
!= NULL
) && (rsa
->dmq1
!= NULL
) && (rsa
->iqmp
!= NULL
))) {
598 if (!rsa
->meth
->rsa_mod_exp(ret
, f
, rsa
, ctx
))
601 BIGNUM
*d
= BN_new();
603 ERR_raise(ERR_LIB_RSA
, ERR_R_BN_LIB
);
606 if (rsa
->d
== NULL
) {
607 ERR_raise(ERR_LIB_RSA
, RSA_R_MISSING_PRIVATE_KEY
);
611 BN_with_flags(d
, rsa
->d
, BN_FLG_CONSTTIME
);
612 if (!rsa
->meth
->bn_mod_exp(ret
, f
, d
, rsa
->n
, ctx
,
613 rsa
->_method_mod_n
)) {
617 /* We MUST free d before any further use of rsa->d */
622 if (!rsa_blinding_invert(blinding
, ret
, ctx
))
626 * derive the Key Derivation Key from private exponent and public
629 if (padding
== RSA_PKCS1_PADDING
) {
630 if (derive_kdk(flen
, from
, rsa
, buf
, num
, kdk
) == 0)
634 j
= BN_bn2binpad(ret
, buf
, num
);
639 case RSA_PKCS1_NO_IMPLICIT_REJECT_PADDING
:
640 r
= RSA_padding_check_PKCS1_type_2(to
, num
, buf
, j
, num
);
642 case RSA_PKCS1_PADDING
:
643 r
= ossl_rsa_padding_check_PKCS1_type_2(rsa
->libctx
, to
, num
, buf
, j
, num
, kdk
);
645 case RSA_PKCS1_OAEP_PADDING
:
646 r
= RSA_padding_check_PKCS1_OAEP(to
, num
, buf
, j
, num
, NULL
, 0);
649 memcpy(to
, buf
, (r
= j
));
652 ERR_raise(ERR_LIB_RSA
, RSA_R_UNKNOWN_PADDING_TYPE
);
657 * This trick doesn't work in the FIPS provider because libcrypto manages
658 * the error stack. Instead we opt not to put an error on the stack at all
659 * in case of padding failure in the FIPS provider.
661 ERR_raise(ERR_LIB_RSA
, RSA_R_PADDING_CHECK_FAILED
);
662 err_clear_last_constant_time(1 & ~constant_time_msb(r
));
668 OPENSSL_clear_free(buf
, num
);
672 /* signature verification */
673 static int rsa_ossl_public_decrypt(int flen
, const unsigned char *from
,
674 unsigned char *to
, RSA
*rsa
, int padding
)
677 int i
, num
= 0, r
= -1;
678 unsigned char *buf
= NULL
;
681 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_MAX_MODULUS_BITS
) {
682 ERR_raise(ERR_LIB_RSA
, RSA_R_MODULUS_TOO_LARGE
);
686 if (BN_ucmp(rsa
->n
, rsa
->e
) <= 0) {
687 ERR_raise(ERR_LIB_RSA
, RSA_R_BAD_E_VALUE
);
691 /* for large moduli, enforce exponent limit */
692 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_SMALL_MODULUS_BITS
) {
693 if (BN_num_bits(rsa
->e
) > OPENSSL_RSA_MAX_PUBEXP_BITS
) {
694 ERR_raise(ERR_LIB_RSA
, RSA_R_BAD_E_VALUE
);
699 if ((ctx
= BN_CTX_new_ex(rsa
->libctx
)) == NULL
)
703 ret
= BN_CTX_get(ctx
);
705 ERR_raise(ERR_LIB_RSA
, ERR_R_BN_LIB
);
708 num
= BN_num_bytes(rsa
->n
);
709 buf
= OPENSSL_malloc(num
);
714 * This check was for equality but PGP does evil things and chops off the
718 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_GREATER_THAN_MOD_LEN
);
722 if (BN_bin2bn(from
, flen
, f
) == NULL
)
725 if (BN_ucmp(f
, rsa
->n
) >= 0) {
726 ERR_raise(ERR_LIB_RSA
, RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
730 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
731 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
735 if (!rsa
->meth
->bn_mod_exp(ret
, f
, rsa
->e
, rsa
->n
, ctx
,
739 /* For X9.31: Assuming e is odd it does a 12 mod 16 test */
740 if ((padding
== RSA_X931_PADDING
) && ((bn_get_words(ret
)[0] & 0xf) != 12))
741 if (!BN_sub(ret
, rsa
->n
, ret
))
744 i
= BN_bn2binpad(ret
, buf
, num
);
749 case RSA_PKCS1_PADDING
:
750 r
= RSA_padding_check_PKCS1_type_1(to
, num
, buf
, i
, num
);
752 case RSA_X931_PADDING
:
753 r
= RSA_padding_check_X931(to
, num
, buf
, i
, num
);
756 memcpy(to
, buf
, (r
= i
));
759 ERR_raise(ERR_LIB_RSA
, RSA_R_UNKNOWN_PADDING_TYPE
);
763 ERR_raise(ERR_LIB_RSA
, RSA_R_PADDING_CHECK_FAILED
);
768 OPENSSL_clear_free(buf
, num
);
772 static int rsa_ossl_mod_exp(BIGNUM
*r0
, const BIGNUM
*I
, RSA
*rsa
, BN_CTX
*ctx
)
774 BIGNUM
*r1
, *m1
, *vrfy
;
775 int ret
= 0, smooth
= 0;
777 BIGNUM
*r2
, *m
[RSA_MAX_PRIME_NUM
- 2];
778 int i
, ex_primes
= 0;
779 RSA_PRIME_INFO
*pinfo
;
784 r1
= BN_CTX_get(ctx
);
786 r2
= BN_CTX_get(ctx
);
788 m1
= BN_CTX_get(ctx
);
789 vrfy
= BN_CTX_get(ctx
);
794 if (rsa
->version
== RSA_ASN1_VERSION_MULTI
795 && ((ex_primes
= sk_RSA_PRIME_INFO_num(rsa
->prime_infos
)) <= 0
796 || ex_primes
> RSA_MAX_PRIME_NUM
- 2))
800 if (rsa
->flags
& RSA_FLAG_CACHE_PRIVATE
) {
801 BIGNUM
*factor
= BN_new();
807 * Make sure BN_mod_inverse in Montgomery initialization uses the
808 * BN_FLG_CONSTTIME flag
810 if (!(BN_with_flags(factor
, rsa
->p
, BN_FLG_CONSTTIME
),
811 BN_MONT_CTX_set_locked(&rsa
->_method_mod_p
, rsa
->lock
,
813 || !(BN_with_flags(factor
, rsa
->q
, BN_FLG_CONSTTIME
),
814 BN_MONT_CTX_set_locked(&rsa
->_method_mod_q
, rsa
->lock
,
820 for (i
= 0; i
< ex_primes
; i
++) {
821 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
822 BN_with_flags(factor
, pinfo
->r
, BN_FLG_CONSTTIME
);
823 if (!BN_MONT_CTX_set_locked(&pinfo
->m
, rsa
->lock
, factor
, ctx
)) {
830 * We MUST free |factor| before any further use of the prime factors
834 smooth
= (rsa
->meth
->bn_mod_exp
== BN_mod_exp_mont
)
838 && (BN_num_bits(rsa
->q
) == BN_num_bits(rsa
->p
));
841 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
842 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
848 * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
849 * accepts values in [0-m*2^w) range. w is m's bit width rounded up
850 * to limb width. So that at the very least if |I| is fully reduced,
851 * i.e. less than p*q, we can count on from-to round to perform
852 * below modulo operations on |I|. Unlike BN_mod it's constant time.
854 if (/* m1 = I moq q */
855 !bn_from_mont_fixed_top(m1
, I
, rsa
->_method_mod_q
, ctx
)
856 || !bn_to_mont_fixed_top(m1
, m1
, rsa
->_method_mod_q
, ctx
)
858 || !bn_from_mont_fixed_top(r1
, I
, rsa
->_method_mod_p
, ctx
)
859 || !bn_to_mont_fixed_top(r1
, r1
, rsa
->_method_mod_p
, ctx
)
861 * Use parallel exponentiations optimization if possible,
862 * otherwise fallback to two sequential exponentiations:
866 || !BN_mod_exp_mont_consttime_x2(m1
, m1
, rsa
->dmq1
, rsa
->q
,
868 r1
, r1
, rsa
->dmp1
, rsa
->p
,
871 /* r1 = (r1 - m1) mod p */
873 * bn_mod_sub_fixed_top is not regular modular subtraction,
874 * it can tolerate subtrahend to be larger than modulus, but
875 * not bit-wise wider. This makes up for uncommon q>p case,
876 * when |m1| can be larger than |rsa->p|.
878 || !bn_mod_sub_fixed_top(r1
, r1
, m1
, rsa
->p
)
880 /* r1 = r1 * iqmp mod p */
881 || !bn_to_mont_fixed_top(r1
, r1
, rsa
->_method_mod_p
, ctx
)
882 || !bn_mul_mont_fixed_top(r1
, r1
, rsa
->iqmp
, rsa
->_method_mod_p
,
884 /* r0 = r1 * q + m1 */
885 || !bn_mul_fixed_top(r0
, r1
, rsa
->q
, ctx
)
886 || !bn_mod_add_fixed_top(r0
, r0
, m1
, rsa
->n
))
892 /* compute I mod q */
894 BIGNUM
*c
= BN_new();
897 BN_with_flags(c
, I
, BN_FLG_CONSTTIME
);
899 if (!BN_mod(r1
, c
, rsa
->q
, ctx
)) {
905 BIGNUM
*dmq1
= BN_new();
910 BN_with_flags(dmq1
, rsa
->dmq1
, BN_FLG_CONSTTIME
);
912 /* compute r1^dmq1 mod q */
913 if (!rsa
->meth
->bn_mod_exp(m1
, r1
, dmq1
, rsa
->q
, ctx
,
914 rsa
->_method_mod_q
)) {
919 /* We MUST free dmq1 before any further use of rsa->dmq1 */
923 /* compute I mod p */
924 if (!BN_mod(r1
, c
, rsa
->p
, ctx
)) {
928 /* We MUST free c before any further use of I */
933 BIGNUM
*dmp1
= BN_new();
936 BN_with_flags(dmp1
, rsa
->dmp1
, BN_FLG_CONSTTIME
);
938 /* compute r1^dmp1 mod p */
939 if (!rsa
->meth
->bn_mod_exp(r0
, r1
, dmp1
, rsa
->p
, ctx
,
940 rsa
->_method_mod_p
)) {
944 /* We MUST free dmp1 before any further use of rsa->dmp1 */
950 BIGNUM
*di
= BN_new(), *cc
= BN_new();
952 if (cc
== NULL
|| di
== NULL
) {
958 for (i
= 0; i
< ex_primes
; i
++) {
960 if ((m
[i
] = BN_CTX_get(ctx
)) == NULL
) {
966 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
968 /* prepare c and d_i */
969 BN_with_flags(cc
, I
, BN_FLG_CONSTTIME
);
970 BN_with_flags(di
, pinfo
->d
, BN_FLG_CONSTTIME
);
972 if (!BN_mod(r1
, cc
, pinfo
->r
, ctx
)) {
977 /* compute r1 ^ d_i mod r_i */
978 if (!rsa
->meth
->bn_mod_exp(m
[i
], r1
, di
, pinfo
->r
, ctx
, pinfo
->m
)) {
990 if (!BN_sub(r0
, r0
, m1
))
993 * This will help stop the size of r0 increasing, which does affect the
994 * multiply if it optimised for a power of 2 size
996 if (BN_is_negative(r0
))
997 if (!BN_add(r0
, r0
, rsa
->p
))
1000 if (!BN_mul(r1
, r0
, rsa
->iqmp
, ctx
))
1004 BIGNUM
*pr1
= BN_new();
1007 BN_with_flags(pr1
, r1
, BN_FLG_CONSTTIME
);
1009 if (!BN_mod(r0
, pr1
, rsa
->p
, ctx
)) {
1013 /* We MUST free pr1 before any further use of r1 */
1018 * If p < q it is occasionally possible for the correction of adding 'p'
1019 * if r0 is negative above to leave the result still negative. This can
1020 * break the private key operations: the following second correction
1021 * should *always* correct this rare occurrence. This will *never* happen
1022 * with OpenSSL generated keys because they ensure p > q [steve]
1024 if (BN_is_negative(r0
))
1025 if (!BN_add(r0
, r0
, rsa
->p
))
1027 if (!BN_mul(r1
, r0
, rsa
->q
, ctx
))
1029 if (!BN_add(r0
, r1
, m1
))
1033 /* add m_i to m in multi-prime case */
1034 if (ex_primes
> 0) {
1035 BIGNUM
*pr2
= BN_new();
1040 for (i
= 0; i
< ex_primes
; i
++) {
1041 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
1042 if (!BN_sub(r1
, m
[i
], r0
)) {
1047 if (!BN_mul(r2
, r1
, pinfo
->t
, ctx
)) {
1052 BN_with_flags(pr2
, r2
, BN_FLG_CONSTTIME
);
1054 if (!BN_mod(r1
, pr2
, pinfo
->r
, ctx
)) {
1059 if (BN_is_negative(r1
))
1060 if (!BN_add(r1
, r1
, pinfo
->r
)) {
1064 if (!BN_mul(r1
, r1
, pinfo
->pp
, ctx
)) {
1068 if (!BN_add(r0
, r0
, r1
)) {
1078 if (rsa
->e
&& rsa
->n
) {
1079 if (rsa
->meth
->bn_mod_exp
== BN_mod_exp_mont
) {
1080 if (!BN_mod_exp_mont(vrfy
, r0
, rsa
->e
, rsa
->n
, ctx
,
1081 rsa
->_method_mod_n
))
1085 if (!rsa
->meth
->bn_mod_exp(vrfy
, r0
, rsa
->e
, rsa
->n
, ctx
,
1086 rsa
->_method_mod_n
))
1090 * If 'I' was greater than (or equal to) rsa->n, the operation will
1091 * be equivalent to using 'I mod n'. However, the result of the
1092 * verify will *always* be less than 'n' so we don't check for
1093 * absolute equality, just congruency.
1095 if (!BN_sub(vrfy
, vrfy
, I
))
1097 if (BN_is_zero(vrfy
)) {
1100 goto err
; /* not actually error */
1102 if (!BN_mod(vrfy
, vrfy
, rsa
->n
, ctx
))
1104 if (BN_is_negative(vrfy
))
1105 if (!BN_add(vrfy
, vrfy
, rsa
->n
))
1107 if (!BN_is_zero(vrfy
)) {
1109 * 'I' and 'vrfy' aren't congruent mod n. Don't leak
1110 * miscalculated CRT output, just do a raw (slower) mod_exp and
1111 * return that instead.
1114 BIGNUM
*d
= BN_new();
1117 BN_with_flags(d
, rsa
->d
, BN_FLG_CONSTTIME
);
1119 if (!rsa
->meth
->bn_mod_exp(r0
, I
, d
, rsa
->n
, ctx
,
1120 rsa
->_method_mod_n
)) {
1124 /* We MUST free d before any further use of rsa->d */
1129 * It's unfortunate that we have to bn_correct_top(r0). What hopefully
1130 * saves the day is that correction is highly unlike, and private key
1131 * operations are customarily performed on blinded message. Which means
1132 * that attacker won't observe correlation with chosen plaintext.
1133 * Secondly, remaining code would still handle it in same computational
1134 * time and even conceal memory access pattern around corrected top.
1143 static int rsa_ossl_init(RSA
*rsa
)
1145 rsa
->flags
|= RSA_FLAG_CACHE_PUBLIC
| RSA_FLAG_CACHE_PRIVATE
;
1149 static int rsa_ossl_finish(RSA
*rsa
)
1153 RSA_PRIME_INFO
*pinfo
;
1155 for (i
= 0; i
< sk_RSA_PRIME_INFO_num(rsa
->prime_infos
); i
++) {
1156 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
1157 BN_MONT_CTX_free(pinfo
->m
);
1161 BN_MONT_CTX_free(rsa
->_method_mod_n
);
1162 BN_MONT_CTX_free(rsa
->_method_mod_p
);
1163 BN_MONT_CTX_free(rsa
->_method_mod_q
);
1167 #ifdef S390X_MOD_EXP
1168 static int rsa_ossl_s390x_mod_exp(BIGNUM
*r0
, const BIGNUM
*i
, RSA
*rsa
,
1171 if (rsa
->version
!= RSA_ASN1_VERSION_MULTI
) {
1172 if (s390x_crt(r0
, i
, rsa
->p
, rsa
->q
, rsa
->dmp1
, rsa
->dmq1
, rsa
->iqmp
) == 1)
1175 return rsa_ossl_mod_exp(r0
, i
, rsa
, ctx
);