2 * Copyright 1995-2018 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
10 #include "internal/cryptlib.h"
11 #include "crypto/bn.h"
13 #include "internal/constant_time_locl.h"
15 static int rsa_ossl_public_encrypt(int flen
, const unsigned char *from
,
16 unsigned char *to
, RSA
*rsa
, int padding
);
17 static int rsa_ossl_private_encrypt(int flen
, const unsigned char *from
,
18 unsigned char *to
, RSA
*rsa
, int padding
);
19 static int rsa_ossl_public_decrypt(int flen
, const unsigned char *from
,
20 unsigned char *to
, RSA
*rsa
, int padding
);
21 static int rsa_ossl_private_decrypt(int flen
, const unsigned char *from
,
22 unsigned char *to
, RSA
*rsa
, int padding
);
23 static int rsa_ossl_mod_exp(BIGNUM
*r0
, const BIGNUM
*i
, RSA
*rsa
,
25 static int rsa_ossl_init(RSA
*rsa
);
26 static int rsa_ossl_finish(RSA
*rsa
);
27 static RSA_METHOD rsa_pkcs1_ossl_meth
= {
29 rsa_ossl_public_encrypt
,
30 rsa_ossl_public_decrypt
, /* signature verification */
31 rsa_ossl_private_encrypt
, /* signing */
32 rsa_ossl_private_decrypt
,
34 BN_mod_exp_mont
, /* XXX probably we should not use Montgomery
38 RSA_FLAG_FIPS_METHOD
, /* flags */
42 NULL
, /* rsa_keygen */
43 NULL
/* rsa_multi_prime_keygen */
46 static const RSA_METHOD
*default_RSA_meth
= &rsa_pkcs1_ossl_meth
;
48 void RSA_set_default_method(const RSA_METHOD
*meth
)
50 default_RSA_meth
= meth
;
53 const RSA_METHOD
*RSA_get_default_method(void)
55 return default_RSA_meth
;
58 const RSA_METHOD
*RSA_PKCS1_OpenSSL(void)
60 return &rsa_pkcs1_ossl_meth
;
63 const RSA_METHOD
*RSA_null_method(void)
68 static int rsa_ossl_public_encrypt(int flen
, const unsigned char *from
,
69 unsigned char *to
, RSA
*rsa
, int padding
)
72 int i
, num
= 0, r
= -1;
73 unsigned char *buf
= NULL
;
76 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_MAX_MODULUS_BITS
) {
77 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT
, RSA_R_MODULUS_TOO_LARGE
);
81 if (BN_ucmp(rsa
->n
, rsa
->e
) <= 0) {
82 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT
, RSA_R_BAD_E_VALUE
);
86 /* for large moduli, enforce exponent limit */
87 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_SMALL_MODULUS_BITS
) {
88 if (BN_num_bits(rsa
->e
) > OPENSSL_RSA_MAX_PUBEXP_BITS
) {
89 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT
, RSA_R_BAD_E_VALUE
);
94 if ((ctx
= BN_CTX_new()) == NULL
)
98 ret
= BN_CTX_get(ctx
);
99 num
= BN_num_bytes(rsa
->n
);
100 buf
= OPENSSL_malloc(num
);
101 if (ret
== NULL
|| buf
== NULL
) {
102 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT
, ERR_R_MALLOC_FAILURE
);
107 case RSA_PKCS1_PADDING
:
108 i
= RSA_padding_add_PKCS1_type_2(buf
, num
, from
, flen
);
110 case RSA_PKCS1_OAEP_PADDING
:
111 i
= RSA_padding_add_PKCS1_OAEP(buf
, num
, from
, flen
, NULL
, 0);
113 case RSA_SSLV23_PADDING
:
114 i
= RSA_padding_add_SSLv23(buf
, num
, from
, flen
);
117 i
= RSA_padding_add_none(buf
, num
, from
, flen
);
120 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT
, RSA_R_UNKNOWN_PADDING_TYPE
);
126 if (BN_bin2bn(buf
, num
, f
) == NULL
)
129 if (BN_ucmp(f
, rsa
->n
) >= 0) {
130 /* usually the padding functions would catch this */
131 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT
,
132 RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
136 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
137 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
141 if (!rsa
->meth
->bn_mod_exp(ret
, f
, rsa
->e
, rsa
->n
, ctx
,
146 * BN_bn2binpad puts in leading 0 bytes if the number is less than
147 * the length of the modulus.
149 r
= BN_bn2binpad(ret
, to
, num
);
153 OPENSSL_clear_free(buf
, num
);
157 static BN_BLINDING
*rsa_get_blinding(RSA
*rsa
, int *local
, BN_CTX
*ctx
)
161 CRYPTO_THREAD_write_lock(rsa
->lock
);
163 if (rsa
->blinding
== NULL
) {
164 rsa
->blinding
= RSA_setup_blinding(rsa
, ctx
);
171 if (BN_BLINDING_is_current_thread(ret
)) {
172 /* rsa->blinding is ours! */
176 /* resort to rsa->mt_blinding instead */
179 * instructs rsa_blinding_convert(), rsa_blinding_invert() that the
180 * BN_BLINDING is shared, meaning that accesses require locks, and
181 * that the blinding factor must be stored outside the BN_BLINDING
185 if (rsa
->mt_blinding
== NULL
) {
186 rsa
->mt_blinding
= RSA_setup_blinding(rsa
, ctx
);
188 ret
= rsa
->mt_blinding
;
192 CRYPTO_THREAD_unlock(rsa
->lock
);
196 static int rsa_blinding_convert(BN_BLINDING
*b
, BIGNUM
*f
, BIGNUM
*unblind
,
199 if (unblind
== NULL
) {
201 * Local blinding: store the unblinding factor in BN_BLINDING.
203 return BN_BLINDING_convert_ex(f
, NULL
, b
, ctx
);
206 * Shared blinding: store the unblinding factor outside BN_BLINDING.
211 ret
= BN_BLINDING_convert_ex(f
, unblind
, b
, ctx
);
212 BN_BLINDING_unlock(b
);
218 static int rsa_blinding_invert(BN_BLINDING
*b
, BIGNUM
*f
, BIGNUM
*unblind
,
222 * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
223 * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
224 * is shared between threads, unblind must be non-null:
225 * BN_BLINDING_invert_ex will then use the local unblinding factor, and
226 * will only read the modulus from BN_BLINDING. In both cases it's safe
227 * to access the blinding without a lock.
229 return BN_BLINDING_invert_ex(f
, unblind
, b
, ctx
);
233 static int rsa_ossl_private_encrypt(int flen
, const unsigned char *from
,
234 unsigned char *to
, RSA
*rsa
, int padding
)
236 BIGNUM
*f
, *ret
, *res
;
237 int i
, num
= 0, r
= -1;
238 unsigned char *buf
= NULL
;
240 int local_blinding
= 0;
242 * Used only if the blinding structure is shared. A non-NULL unblind
243 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
244 * the unblinding factor outside the blinding structure.
246 BIGNUM
*unblind
= NULL
;
247 BN_BLINDING
*blinding
= NULL
;
249 if ((ctx
= BN_CTX_new()) == NULL
)
253 ret
= BN_CTX_get(ctx
);
254 num
= BN_num_bytes(rsa
->n
);
255 buf
= OPENSSL_malloc(num
);
256 if (ret
== NULL
|| buf
== NULL
) {
257 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT
, ERR_R_MALLOC_FAILURE
);
262 case RSA_PKCS1_PADDING
:
263 i
= RSA_padding_add_PKCS1_type_1(buf
, num
, from
, flen
);
265 case RSA_X931_PADDING
:
266 i
= RSA_padding_add_X931(buf
, num
, from
, flen
);
269 i
= RSA_padding_add_none(buf
, num
, from
, flen
);
271 case RSA_SSLV23_PADDING
:
273 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT
, RSA_R_UNKNOWN_PADDING_TYPE
);
279 if (BN_bin2bn(buf
, num
, f
) == NULL
)
282 if (BN_ucmp(f
, rsa
->n
) >= 0) {
283 /* usually the padding functions would catch this */
284 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT
,
285 RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
289 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
290 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
294 if (!(rsa
->flags
& RSA_FLAG_NO_BLINDING
)) {
295 blinding
= rsa_get_blinding(rsa
, &local_blinding
, ctx
);
296 if (blinding
== NULL
) {
297 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT
, ERR_R_INTERNAL_ERROR
);
302 if (blinding
!= NULL
) {
303 if (!local_blinding
&& ((unblind
= BN_CTX_get(ctx
)) == NULL
)) {
304 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT
, ERR_R_MALLOC_FAILURE
);
307 if (!rsa_blinding_convert(blinding
, f
, unblind
, ctx
))
311 if ((rsa
->flags
& RSA_FLAG_EXT_PKEY
) ||
312 (rsa
->version
== RSA_ASN1_VERSION_MULTI
) ||
315 (rsa
->dmp1
!= NULL
) && (rsa
->dmq1
!= NULL
) && (rsa
->iqmp
!= NULL
))) {
316 if (!rsa
->meth
->rsa_mod_exp(ret
, f
, rsa
, ctx
))
319 BIGNUM
*d
= BN_new();
321 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT
, ERR_R_MALLOC_FAILURE
);
324 if (rsa
->d
== NULL
) {
325 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT
, RSA_R_MISSING_PRIVATE_KEY
);
329 BN_with_flags(d
, rsa
->d
, BN_FLG_CONSTTIME
);
331 if (!rsa
->meth
->bn_mod_exp(ret
, f
, d
, rsa
->n
, ctx
,
332 rsa
->_method_mod_n
)) {
336 /* We MUST free d before any further use of rsa->d */
341 if (!rsa_blinding_invert(blinding
, ret
, unblind
, ctx
))
344 if (padding
== RSA_X931_PADDING
) {
345 if (!BN_sub(f
, rsa
->n
, ret
))
347 if (BN_cmp(ret
, f
) > 0)
356 * BN_bn2binpad puts in leading 0 bytes if the number is less than
357 * the length of the modulus.
359 r
= BN_bn2binpad(res
, to
, num
);
363 OPENSSL_clear_free(buf
, num
);
367 static int rsa_ossl_private_decrypt(int flen
, const unsigned char *from
,
368 unsigned char *to
, RSA
*rsa
, int padding
)
371 int j
, num
= 0, r
= -1;
372 unsigned char *buf
= NULL
;
374 int local_blinding
= 0;
376 * Used only if the blinding structure is shared. A non-NULL unblind
377 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
378 * the unblinding factor outside the blinding structure.
380 BIGNUM
*unblind
= NULL
;
381 BN_BLINDING
*blinding
= NULL
;
383 if ((ctx
= BN_CTX_new()) == NULL
)
387 ret
= BN_CTX_get(ctx
);
388 num
= BN_num_bytes(rsa
->n
);
389 buf
= OPENSSL_malloc(num
);
390 if (ret
== NULL
|| buf
== NULL
) {
391 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
, ERR_R_MALLOC_FAILURE
);
396 * This check was for equality but PGP does evil things and chops off the
400 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
,
401 RSA_R_DATA_GREATER_THAN_MOD_LEN
);
405 /* make data into a big number */
406 if (BN_bin2bn(from
, (int)flen
, f
) == NULL
)
409 if (BN_ucmp(f
, rsa
->n
) >= 0) {
410 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
,
411 RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
415 if (!(rsa
->flags
& RSA_FLAG_NO_BLINDING
)) {
416 blinding
= rsa_get_blinding(rsa
, &local_blinding
, ctx
);
417 if (blinding
== NULL
) {
418 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
, ERR_R_INTERNAL_ERROR
);
423 if (blinding
!= NULL
) {
424 if (!local_blinding
&& ((unblind
= BN_CTX_get(ctx
)) == NULL
)) {
425 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
, ERR_R_MALLOC_FAILURE
);
428 if (!rsa_blinding_convert(blinding
, f
, unblind
, ctx
))
433 if ((rsa
->flags
& RSA_FLAG_EXT_PKEY
) ||
434 (rsa
->version
== RSA_ASN1_VERSION_MULTI
) ||
437 (rsa
->dmp1
!= NULL
) && (rsa
->dmq1
!= NULL
) && (rsa
->iqmp
!= NULL
))) {
438 if (!rsa
->meth
->rsa_mod_exp(ret
, f
, rsa
, ctx
))
441 BIGNUM
*d
= BN_new();
443 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
, ERR_R_MALLOC_FAILURE
);
446 if (rsa
->d
== NULL
) {
447 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
, RSA_R_MISSING_PRIVATE_KEY
);
451 BN_with_flags(d
, rsa
->d
, BN_FLG_CONSTTIME
);
453 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
454 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
459 if (!rsa
->meth
->bn_mod_exp(ret
, f
, d
, rsa
->n
, ctx
,
460 rsa
->_method_mod_n
)) {
464 /* We MUST free d before any further use of rsa->d */
469 if (!rsa_blinding_invert(blinding
, ret
, unblind
, ctx
))
472 j
= BN_bn2binpad(ret
, buf
, num
);
477 case RSA_PKCS1_PADDING
:
478 r
= RSA_padding_check_PKCS1_type_2(to
, num
, buf
, j
, num
);
480 case RSA_PKCS1_OAEP_PADDING
:
481 r
= RSA_padding_check_PKCS1_OAEP(to
, num
, buf
, j
, num
, NULL
, 0);
483 case RSA_SSLV23_PADDING
:
484 r
= RSA_padding_check_SSLv23(to
, num
, buf
, j
, num
);
487 memcpy(to
, buf
, (r
= j
));
490 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
, RSA_R_UNKNOWN_PADDING_TYPE
);
493 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT
, RSA_R_PADDING_CHECK_FAILED
);
494 err_clear_last_constant_time(1 & ~constant_time_msb(r
));
499 OPENSSL_clear_free(buf
, num
);
503 /* signature verification */
504 static int rsa_ossl_public_decrypt(int flen
, const unsigned char *from
,
505 unsigned char *to
, RSA
*rsa
, int padding
)
508 int i
, num
= 0, r
= -1;
509 unsigned char *buf
= NULL
;
512 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_MAX_MODULUS_BITS
) {
513 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
, RSA_R_MODULUS_TOO_LARGE
);
517 if (BN_ucmp(rsa
->n
, rsa
->e
) <= 0) {
518 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
, RSA_R_BAD_E_VALUE
);
522 /* for large moduli, enforce exponent limit */
523 if (BN_num_bits(rsa
->n
) > OPENSSL_RSA_SMALL_MODULUS_BITS
) {
524 if (BN_num_bits(rsa
->e
) > OPENSSL_RSA_MAX_PUBEXP_BITS
) {
525 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
, RSA_R_BAD_E_VALUE
);
530 if ((ctx
= BN_CTX_new()) == NULL
)
534 ret
= BN_CTX_get(ctx
);
535 num
= BN_num_bytes(rsa
->n
);
536 buf
= OPENSSL_malloc(num
);
537 if (ret
== NULL
|| buf
== NULL
) {
538 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
, ERR_R_MALLOC_FAILURE
);
543 * This check was for equality but PGP does evil things and chops off the
547 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
, RSA_R_DATA_GREATER_THAN_MOD_LEN
);
551 if (BN_bin2bn(from
, flen
, f
) == NULL
)
554 if (BN_ucmp(f
, rsa
->n
) >= 0) {
555 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
,
556 RSA_R_DATA_TOO_LARGE_FOR_MODULUS
);
560 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
561 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
565 if (!rsa
->meth
->bn_mod_exp(ret
, f
, rsa
->e
, rsa
->n
, ctx
,
569 if ((padding
== RSA_X931_PADDING
) && ((bn_get_words(ret
)[0] & 0xf) != 12))
570 if (!BN_sub(ret
, rsa
->n
, ret
))
573 i
= BN_bn2binpad(ret
, buf
, num
);
578 case RSA_PKCS1_PADDING
:
579 r
= RSA_padding_check_PKCS1_type_1(to
, num
, buf
, i
, num
);
581 case RSA_X931_PADDING
:
582 r
= RSA_padding_check_X931(to
, num
, buf
, i
, num
);
585 memcpy(to
, buf
, (r
= i
));
588 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
, RSA_R_UNKNOWN_PADDING_TYPE
);
592 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT
, RSA_R_PADDING_CHECK_FAILED
);
597 OPENSSL_clear_free(buf
, num
);
601 static int rsa_ossl_mod_exp(BIGNUM
*r0
, const BIGNUM
*I
, RSA
*rsa
, BN_CTX
*ctx
)
603 BIGNUM
*r1
, *m1
, *vrfy
, *r2
, *m
[RSA_MAX_PRIME_NUM
- 2];
604 int ret
= 0, i
, ex_primes
= 0, smooth
= 0;
605 RSA_PRIME_INFO
*pinfo
;
609 r1
= BN_CTX_get(ctx
);
610 r2
= BN_CTX_get(ctx
);
611 m1
= BN_CTX_get(ctx
);
612 vrfy
= BN_CTX_get(ctx
);
616 if (rsa
->version
== RSA_ASN1_VERSION_MULTI
617 && ((ex_primes
= sk_RSA_PRIME_INFO_num(rsa
->prime_infos
)) <= 0
618 || ex_primes
> RSA_MAX_PRIME_NUM
- 2))
621 if (rsa
->flags
& RSA_FLAG_CACHE_PRIVATE
) {
622 BIGNUM
*factor
= BN_new();
628 * Make sure BN_mod_inverse in Montgomery initialization uses the
629 * BN_FLG_CONSTTIME flag
631 if (!(BN_with_flags(factor
, rsa
->p
, BN_FLG_CONSTTIME
),
632 BN_MONT_CTX_set_locked(&rsa
->_method_mod_p
, rsa
->lock
,
634 || !(BN_with_flags(factor
, rsa
->q
, BN_FLG_CONSTTIME
),
635 BN_MONT_CTX_set_locked(&rsa
->_method_mod_q
, rsa
->lock
,
640 for (i
= 0; i
< ex_primes
; i
++) {
641 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
642 BN_with_flags(factor
, pinfo
->r
, BN_FLG_CONSTTIME
);
643 if (!BN_MONT_CTX_set_locked(&pinfo
->m
, rsa
->lock
, factor
, ctx
)) {
649 * We MUST free |factor| before any further use of the prime factors
653 smooth
= (ex_primes
== 0)
654 && (rsa
->meth
->bn_mod_exp
== BN_mod_exp_mont
)
655 && (BN_num_bits(rsa
->q
) == BN_num_bits(rsa
->p
));
658 if (rsa
->flags
& RSA_FLAG_CACHE_PUBLIC
)
659 if (!BN_MONT_CTX_set_locked(&rsa
->_method_mod_n
, rsa
->lock
,
665 * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
666 * accepts values in [0-m*2^w) range. w is m's bit width rounded up
667 * to limb width. So that at the very least if |I| is fully reduced,
668 * i.e. less than p*q, we can count on from-to round to perform
669 * below modulo operations on |I|. Unlike BN_mod it's constant time.
671 if (/* m1 = I moq q */
672 !bn_from_mont_fixed_top(m1
, I
, rsa
->_method_mod_q
, ctx
)
673 || !bn_to_mont_fixed_top(m1
, m1
, rsa
->_method_mod_q
, ctx
)
674 /* m1 = m1^dmq1 mod q */
675 || !BN_mod_exp_mont_consttime(m1
, m1
, rsa
->dmq1
, rsa
->q
, ctx
,
678 || !bn_from_mont_fixed_top(r1
, I
, rsa
->_method_mod_p
, ctx
)
679 || !bn_to_mont_fixed_top(r1
, r1
, rsa
->_method_mod_p
, ctx
)
680 /* r1 = r1^dmp1 mod p */
681 || !BN_mod_exp_mont_consttime(r1
, r1
, rsa
->dmp1
, rsa
->p
, ctx
,
683 /* r1 = (r1 - m1) mod p */
685 * bn_mod_sub_fixed_top is not regular modular subtraction,
686 * it can tolerate subtrahend to be larger than modulus, but
687 * not bit-wise wider. This makes up for uncommon q>p case,
688 * when |m1| can be larger than |rsa->p|.
690 || !bn_mod_sub_fixed_top(r1
, r1
, m1
, rsa
->p
)
692 /* r1 = r1 * iqmp mod p */
693 || !bn_to_mont_fixed_top(r1
, r1
, rsa
->_method_mod_p
, ctx
)
694 || !bn_mul_mont_fixed_top(r1
, r1
, rsa
->iqmp
, rsa
->_method_mod_p
,
696 /* r0 = r1 * q + m1 */
697 || !bn_mul_fixed_top(r0
, r1
, rsa
->q
, ctx
)
698 || !bn_mod_add_fixed_top(r0
, r0
, m1
, rsa
->n
))
704 /* compute I mod q */
706 BIGNUM
*c
= BN_new();
709 BN_with_flags(c
, I
, BN_FLG_CONSTTIME
);
711 if (!BN_mod(r1
, c
, rsa
->q
, ctx
)) {
717 BIGNUM
*dmq1
= BN_new();
722 BN_with_flags(dmq1
, rsa
->dmq1
, BN_FLG_CONSTTIME
);
724 /* compute r1^dmq1 mod q */
725 if (!rsa
->meth
->bn_mod_exp(m1
, r1
, dmq1
, rsa
->q
, ctx
,
726 rsa
->_method_mod_q
)) {
731 /* We MUST free dmq1 before any further use of rsa->dmq1 */
735 /* compute I mod p */
736 if (!BN_mod(r1
, c
, rsa
->p
, ctx
)) {
740 /* We MUST free c before any further use of I */
745 BIGNUM
*dmp1
= BN_new();
748 BN_with_flags(dmp1
, rsa
->dmp1
, BN_FLG_CONSTTIME
);
750 /* compute r1^dmp1 mod p */
751 if (!rsa
->meth
->bn_mod_exp(r0
, r1
, dmp1
, rsa
->p
, ctx
,
752 rsa
->_method_mod_p
)) {
756 /* We MUST free dmp1 before any further use of rsa->dmp1 */
761 * calculate m_i in multi-prime case
764 * 1. squash the following two loops and calculate |m_i| there.
765 * 2. remove cc and reuse |c|.
766 * 3. remove |dmq1| and |dmp1| in previous block and use |di|.
768 * If these things are done, the code will be more readable.
771 BIGNUM
*di
= BN_new(), *cc
= BN_new();
773 if (cc
== NULL
|| di
== NULL
) {
779 for (i
= 0; i
< ex_primes
; i
++) {
781 if ((m
[i
] = BN_CTX_get(ctx
)) == NULL
) {
787 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
789 /* prepare c and d_i */
790 BN_with_flags(cc
, I
, BN_FLG_CONSTTIME
);
791 BN_with_flags(di
, pinfo
->d
, BN_FLG_CONSTTIME
);
793 if (!BN_mod(r1
, cc
, pinfo
->r
, ctx
)) {
798 /* compute r1 ^ d_i mod r_i */
799 if (!rsa
->meth
->bn_mod_exp(m
[i
], r1
, di
, pinfo
->r
, ctx
, pinfo
->m
)) {
810 if (!BN_sub(r0
, r0
, m1
))
813 * This will help stop the size of r0 increasing, which does affect the
814 * multiply if it optimised for a power of 2 size
816 if (BN_is_negative(r0
))
817 if (!BN_add(r0
, r0
, rsa
->p
))
820 if (!BN_mul(r1
, r0
, rsa
->iqmp
, ctx
))
824 BIGNUM
*pr1
= BN_new();
827 BN_with_flags(pr1
, r1
, BN_FLG_CONSTTIME
);
829 if (!BN_mod(r0
, pr1
, rsa
->p
, ctx
)) {
833 /* We MUST free pr1 before any further use of r1 */
838 * If p < q it is occasionally possible for the correction of adding 'p'
839 * if r0 is negative above to leave the result still negative. This can
840 * break the private key operations: the following second correction
841 * should *always* correct this rare occurrence. This will *never* happen
842 * with OpenSSL generated keys because they ensure p > q [steve]
844 if (BN_is_negative(r0
))
845 if (!BN_add(r0
, r0
, rsa
->p
))
847 if (!BN_mul(r1
, r0
, rsa
->q
, ctx
))
849 if (!BN_add(r0
, r1
, m1
))
852 /* add m_i to m in multi-prime case */
854 BIGNUM
*pr2
= BN_new();
859 for (i
= 0; i
< ex_primes
; i
++) {
860 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
861 if (!BN_sub(r1
, m
[i
], r0
)) {
866 if (!BN_mul(r2
, r1
, pinfo
->t
, ctx
)) {
871 BN_with_flags(pr2
, r2
, BN_FLG_CONSTTIME
);
873 if (!BN_mod(r1
, pr2
, pinfo
->r
, ctx
)) {
878 if (BN_is_negative(r1
))
879 if (!BN_add(r1
, r1
, pinfo
->r
)) {
883 if (!BN_mul(r1
, r1
, pinfo
->pp
, ctx
)) {
887 if (!BN_add(r0
, r0
, r1
)) {
896 if (rsa
->e
&& rsa
->n
) {
897 if (rsa
->meth
->bn_mod_exp
== BN_mod_exp_mont
) {
898 if (!BN_mod_exp_mont(vrfy
, r0
, rsa
->e
, rsa
->n
, ctx
,
903 if (!rsa
->meth
->bn_mod_exp(vrfy
, r0
, rsa
->e
, rsa
->n
, ctx
,
908 * If 'I' was greater than (or equal to) rsa->n, the operation will
909 * be equivalent to using 'I mod n'. However, the result of the
910 * verify will *always* be less than 'n' so we don't check for
911 * absolute equality, just congruency.
913 if (!BN_sub(vrfy
, vrfy
, I
))
915 if (BN_is_zero(vrfy
)) {
918 goto err
; /* not actually error */
920 if (!BN_mod(vrfy
, vrfy
, rsa
->n
, ctx
))
922 if (BN_is_negative(vrfy
))
923 if (!BN_add(vrfy
, vrfy
, rsa
->n
))
925 if (!BN_is_zero(vrfy
)) {
927 * 'I' and 'vrfy' aren't congruent mod n. Don't leak
928 * miscalculated CRT output, just do a raw (slower) mod_exp and
929 * return that instead.
932 BIGNUM
*d
= BN_new();
935 BN_with_flags(d
, rsa
->d
, BN_FLG_CONSTTIME
);
937 if (!rsa
->meth
->bn_mod_exp(r0
, I
, d
, rsa
->n
, ctx
,
938 rsa
->_method_mod_n
)) {
942 /* We MUST free d before any further use of rsa->d */
947 * It's unfortunate that we have to bn_correct_top(r0). What hopefully
948 * saves the day is that correction is highly unlike, and private key
949 * operations are customarily performed on blinded message. Which means
950 * that attacker won't observe correlation with chosen plaintext.
951 * Secondly, remaining code would still handle it in same computational
952 * time and even conceal memory access pattern around corrected top.
961 static int rsa_ossl_init(RSA
*rsa
)
963 rsa
->flags
|= RSA_FLAG_CACHE_PUBLIC
| RSA_FLAG_CACHE_PRIVATE
;
967 static int rsa_ossl_finish(RSA
*rsa
)
970 RSA_PRIME_INFO
*pinfo
;
972 BN_MONT_CTX_free(rsa
->_method_mod_n
);
973 BN_MONT_CTX_free(rsa
->_method_mod_p
);
974 BN_MONT_CTX_free(rsa
->_method_mod_q
);
975 for (i
= 0; i
< sk_RSA_PRIME_INFO_num(rsa
->prime_infos
); i
++) {
976 pinfo
= sk_RSA_PRIME_INFO_value(rsa
->prime_infos
, i
);
977 BN_MONT_CTX_free(pinfo
->m
);