1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.] */
57 #include <openssl/rsa.h>
63 #include <openssl/bn.h>
64 #include <openssl/err.h>
65 #include <openssl/mem.h>
66 #include <openssl/thread.h>
67 #include <openssl/type_check.h>
70 #include "../bn/internal.h"
71 #include "../../internal.h"
72 #include "../delocate.h"
75 static int check_modulus_and_exponent_sizes(const RSA *rsa) {
76 unsigned rsa_bits = BN_num_bits(rsa->n);
78 if (rsa_bits > 16 * 1024) {
79 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
83 // Mitigate DoS attacks by limiting the exponent size. 33 bits was chosen as
84 // the limit based on the recommendations in [1] and [2]. Windows CryptoAPI
85 // doesn't support values larger than 32 bits [3], so it is unlikely that
86 // exponents larger than 32 bits are being used for anything Windows commonly
89 // [1] https://www.imperialviolet.org/2012/03/16/rsae.html
90 // [2] https://www.imperialviolet.org/2012/03/17/rsados.html
91 // [3] https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx
92 static const unsigned kMaxExponentBits = 33;
94 if (BN_num_bits(rsa->e) > kMaxExponentBits) {
95 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
99 // Verify |n > e|. Comparing |rsa_bits| to |kMaxExponentBits| is a small
100 // shortcut to comparing |n| and |e| directly. In reality, |kMaxExponentBits|
101 // is much smaller than the minimum RSA key size that any application should
103 if (rsa_bits <= kMaxExponentBits) {
104 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
107 assert(BN_ucmp(rsa->n, rsa->e) > 0);
112 static int ensure_fixed_copy(BIGNUM **out, const BIGNUM *in, int width) {
116 BIGNUM *copy = BN_dup(in);
118 !bn_resize_words(copy, width)) {
126 // freeze_private_key finishes initializing |rsa|'s private key components.
127 // After this function has returned, |rsa| may not be changed. This is needed
128 // because |RSA| is a public struct and, additionally, OpenSSL 1.1.0 opaquified
129 // it wrong (see https://github.com/openssl/openssl/issues/5158).
130 static int freeze_private_key(RSA *rsa, BN_CTX *ctx) {
131 CRYPTO_MUTEX_lock_read(&rsa->lock);
132 int frozen = rsa->private_key_frozen;
133 CRYPTO_MUTEX_unlock_read(&rsa->lock);
139 CRYPTO_MUTEX_lock_write(&rsa->lock);
140 if (rsa->private_key_frozen) {
145 // Pre-compute various intermediate values, as well as copies of private
146 // exponents with correct widths. Note that other threads may concurrently
147 // read from |rsa->n|, |rsa->e|, etc., so any fixes must be in separate
148 // copies. We use |mont_n->N|, |mont_p->N|, and |mont_q->N| as copies of |n|,
149 // |p|, and |q| with the correct minimal widths.
151 if (rsa->mont_n == NULL) {
152 rsa->mont_n = BN_MONT_CTX_new_for_modulus(rsa->n, ctx);
153 if (rsa->mont_n == NULL) {
157 const BIGNUM *n_fixed = &rsa->mont_n->N;
159 // The only public upper-bound of |rsa->d| is the bit length of |rsa->n|. The
160 // ASN.1 serialization of RSA private keys unfortunately leaks the byte length
161 // of |rsa->d|, but normalize it so we only leak it once, rather than per
163 if (rsa->d != NULL &&
164 !ensure_fixed_copy(&rsa->d_fixed, rsa->d, n_fixed->width)) {
168 if (rsa->p != NULL && rsa->q != NULL) {
169 if (rsa->mont_p == NULL) {
170 rsa->mont_p = BN_MONT_CTX_new_for_modulus(rsa->p, ctx);
171 if (rsa->mont_p == NULL) {
175 const BIGNUM *p_fixed = &rsa->mont_p->N;
177 if (rsa->mont_q == NULL) {
178 rsa->mont_q = BN_MONT_CTX_new_for_modulus(rsa->q, ctx);
179 if (rsa->mont_q == NULL) {
183 const BIGNUM *q_fixed = &rsa->mont_q->N;
185 if (rsa->dmp1 != NULL && rsa->dmq1 != NULL) {
186 // Key generation relies on this function to compute |iqmp|.
187 if (rsa->iqmp == NULL) {
188 BIGNUM *iqmp = BN_new();
190 !bn_mod_inverse_secret_prime(iqmp, rsa->q, rsa->p, ctx,
198 // CRT components are only publicly bounded by their corresponding
199 // moduli's bit lengths. |rsa->iqmp| is unused outside of this one-time
200 // setup, so we do not compute a fixed-width version of it.
201 if (!ensure_fixed_copy(&rsa->dmp1_fixed, rsa->dmp1, p_fixed->width) ||
202 !ensure_fixed_copy(&rsa->dmq1_fixed, rsa->dmq1, q_fixed->width)) {
206 // Compute |inv_small_mod_large_mont|. Note that it is always modulo the
207 // larger prime, independent of what is stored in |rsa->iqmp|.
208 if (rsa->inv_small_mod_large_mont == NULL) {
209 BIGNUM *inv_small_mod_large_mont = BN_new();
211 if (BN_cmp(rsa->p, rsa->q) < 0) {
212 ok = inv_small_mod_large_mont != NULL &&
213 bn_mod_inverse_secret_prime(inv_small_mod_large_mont, rsa->p,
214 rsa->q, ctx, rsa->mont_q) &&
215 BN_to_montgomery(inv_small_mod_large_mont,
216 inv_small_mod_large_mont, rsa->mont_q, ctx);
218 ok = inv_small_mod_large_mont != NULL &&
219 BN_to_montgomery(inv_small_mod_large_mont, rsa->iqmp,
223 BN_free(inv_small_mod_large_mont);
226 rsa->inv_small_mod_large_mont = inv_small_mod_large_mont;
231 rsa->private_key_frozen = 1;
235 CRYPTO_MUTEX_unlock_write(&rsa->lock);
239 size_t rsa_default_size(const RSA *rsa) {
240 return BN_num_bytes(rsa->n);
243 int RSA_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
244 const uint8_t *in, size_t in_len, int padding) {
245 if (rsa->n == NULL || rsa->e == NULL) {
246 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
250 const unsigned rsa_size = RSA_size(rsa);
256 if (max_out < rsa_size) {
257 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
261 if (!check_modulus_and_exponent_sizes(rsa)) {
272 result = BN_CTX_get(ctx);
273 buf = OPENSSL_malloc(rsa_size);
274 if (!f || !result || !buf) {
275 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
280 case RSA_PKCS1_PADDING:
281 i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
283 case RSA_PKCS1_OAEP_PADDING:
284 // Use the default parameters: SHA-1 for both hashes and no label.
285 i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
286 NULL, 0, NULL, NULL);
289 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
292 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
300 if (BN_bin2bn(buf, rsa_size, f) == NULL) {
304 if (BN_ucmp(f, rsa->n) >= 0) {
305 // usually the padding functions would catch this
306 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE);
310 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
311 !BN_mod_exp_mont(result, f, rsa->e, &rsa->mont_n->N, ctx, rsa->mont_n)) {
315 // put in leading 0 bytes if the number is less than the length of the
317 if (!BN_bn2bin_padded(out, rsa_size, result)) {
318 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
335 // MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
336 // RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
337 // destroyed as needed.
338 #define MAX_BLINDINGS_PER_RSA 1024
340 // rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
341 // allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
342 // none are free, the cache will be extended by a extra element and the new
343 // BN_BLINDING is returned.
345 // On success, the index of the assigned BN_BLINDING is written to
346 // |*index_used| and must be passed to |rsa_blinding_release| when finished.
347 static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
350 assert(rsa->mont_n != NULL);
352 BN_BLINDING *ret = NULL;
353 BN_BLINDING **new_blindings;
354 uint8_t *new_blindings_inuse;
357 CRYPTO_MUTEX_lock_write(&rsa->lock);
360 for (i = 0; i < rsa->num_blindings; i++) {
361 if (rsa->blindings_inuse[i] == 0) {
362 rsa->blindings_inuse[i] = 1;
363 ret = rsa->blindings[i];
370 CRYPTO_MUTEX_unlock_write(&rsa->lock);
374 overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA;
376 // We didn't find a free BN_BLINDING to use so increase the length of
377 // the arrays by one and use the newly created element.
379 CRYPTO_MUTEX_unlock_write(&rsa->lock);
380 ret = BN_BLINDING_new();
386 // We cannot add any more cached BN_BLINDINGs so we use |ret|
387 // and mark it for destruction in |rsa_blinding_release|.
388 *index_used = MAX_BLINDINGS_PER_RSA;
392 CRYPTO_MUTEX_lock_write(&rsa->lock);
395 OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1));
396 if (new_blindings == NULL) {
399 OPENSSL_memcpy(new_blindings, rsa->blindings,
400 sizeof(BN_BLINDING *) * rsa->num_blindings);
401 new_blindings[rsa->num_blindings] = ret;
403 new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1);
404 if (new_blindings_inuse == NULL) {
407 OPENSSL_memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
408 new_blindings_inuse[rsa->num_blindings] = 1;
409 *index_used = rsa->num_blindings;
411 OPENSSL_free(rsa->blindings);
412 rsa->blindings = new_blindings;
413 OPENSSL_free(rsa->blindings_inuse);
414 rsa->blindings_inuse = new_blindings_inuse;
415 rsa->num_blindings++;
417 CRYPTO_MUTEX_unlock_write(&rsa->lock);
421 OPENSSL_free(new_blindings);
424 CRYPTO_MUTEX_unlock_write(&rsa->lock);
425 BN_BLINDING_free(ret);
429 // rsa_blinding_release marks the cached BN_BLINDING at the given index as free
430 // for other threads to use.
431 static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
432 unsigned blinding_index) {
433 if (blinding_index == MAX_BLINDINGS_PER_RSA) {
434 // This blinding wasn't cached.
435 BN_BLINDING_free(blinding);
439 CRYPTO_MUTEX_lock_write(&rsa->lock);
440 rsa->blindings_inuse[blinding_index] = 0;
441 CRYPTO_MUTEX_unlock_write(&rsa->lock);
445 int rsa_default_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out,
446 size_t max_out, const uint8_t *in, size_t in_len,
448 const unsigned rsa_size = RSA_size(rsa);
452 if (max_out < rsa_size) {
453 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
457 buf = OPENSSL_malloc(rsa_size);
459 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
464 case RSA_PKCS1_PADDING:
465 i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
468 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
471 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
479 if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
492 int rsa_default_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
493 const uint8_t *in, size_t in_len, int padding) {
494 const unsigned rsa_size = RSA_size(rsa);
498 if (max_out < rsa_size) {
499 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
503 if (padding == RSA_NO_PADDING) {
506 // Allocate a temporary buffer to hold the padded plaintext.
507 buf = OPENSSL_malloc(rsa_size);
509 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
514 if (in_len != rsa_size) {
515 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
519 if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
524 case RSA_PKCS1_PADDING:
526 RSA_padding_check_PKCS1_type_2(out, out_len, rsa_size, buf, rsa_size);
528 case RSA_PKCS1_OAEP_PADDING:
529 // Use the default parameters: SHA-1 for both hashes and no label.
530 ret = RSA_padding_check_PKCS1_OAEP_mgf1(out, out_len, rsa_size, buf,
531 rsa_size, NULL, 0, NULL, NULL);
538 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
543 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
547 if (padding != RSA_NO_PADDING) {
554 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx);
556 int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
557 const uint8_t *in, size_t in_len, int padding) {
558 if (rsa->n == NULL || rsa->e == NULL) {
559 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
563 const unsigned rsa_size = RSA_size(rsa);
566 if (max_out < rsa_size) {
567 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
571 if (in_len != rsa_size) {
572 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
576 if (!check_modulus_and_exponent_sizes(rsa)) {
580 BN_CTX *ctx = BN_CTX_new();
590 result = BN_CTX_get(ctx);
591 if (f == NULL || result == NULL) {
592 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
596 if (padding == RSA_NO_PADDING) {
599 // Allocate a temporary buffer to hold the padded plaintext.
600 buf = OPENSSL_malloc(rsa_size);
602 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
607 if (BN_bin2bn(in, in_len, f) == NULL) {
611 if (BN_ucmp(f, rsa->n) >= 0) {
612 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE);
616 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
617 !BN_mod_exp_mont(result, f, rsa->e, &rsa->mont_n->N, ctx, rsa->mont_n)) {
621 if (!BN_bn2bin_padded(buf, rsa_size, result)) {
622 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
627 case RSA_PKCS1_PADDING:
629 RSA_padding_check_PKCS1_type_1(out, out_len, rsa_size, buf, rsa_size);
636 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
641 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
654 int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
656 if (rsa->n == NULL || rsa->d == NULL) {
657 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
663 unsigned blinding_index = 0;
664 BN_BLINDING *blinding = NULL;
673 result = BN_CTX_get(ctx);
675 if (f == NULL || result == NULL) {
676 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
680 if (BN_bin2bn(in, len, f) == NULL) {
684 if (BN_ucmp(f, rsa->n) >= 0) {
685 // Usually the padding functions would catch this.
686 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE);
690 if (!freeze_private_key(rsa, ctx)) {
691 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
695 const int do_blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
697 if (rsa->e == NULL && do_blinding) {
698 // We cannot do blinding or verification without |e|, and continuing without
699 // those countermeasures is dangerous. However, the Java/Android RSA API
700 // requires support for keys where only |d| and |n| (and not |e|) are known.
701 // The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|.
702 OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);
707 blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
708 if (blinding == NULL) {
709 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
712 if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {
717 if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&
718 rsa->dmq1 != NULL && rsa->iqmp != NULL) {
719 if (!mod_exp(result, f, rsa, ctx)) {
722 } else if (!BN_mod_exp_mont_consttime(result, f, rsa->d_fixed, rsa->n, ctx,
727 // Verify the result to protect against fault attacks as described in the
728 // 1997 paper "On the Importance of Checking Cryptographic Protocols for
729 // Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some
730 // implementations do this only when the CRT is used, but we do it in all
731 // cases. Section 6 of the aforementioned paper describes an attack that
732 // works when the CRT isn't used. That attack is much less likely to succeed
733 // than the CRT attack, but there have likely been improvements since 1997.
735 // This check is cheap assuming |e| is small; it almost always is.
736 if (rsa->e != NULL) {
737 BIGNUM *vrfy = BN_CTX_get(ctx);
739 !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||
740 !BN_equal_consttime(vrfy, f)) {
741 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
748 !BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {
752 // The computation should have left |result| as a maximally-wide number, so
753 // that it and serializing does not leak information about the magnitude of
756 // See Falko Stenzke, "Manger's Attack revisited", ICICS 2010.
757 assert(result->width == rsa->mont_n->N.width);
758 if (!BN_bn2bin_padded(out, len, result)) {
759 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
770 if (blinding != NULL) {
771 rsa_blinding_release(rsa, blinding, blinding_index);
777 // mod_montgomery sets |r| to |I| mod |p|. |I| must already be fully reduced
778 // modulo |p| times |q|. It returns one on success and zero on error.
779 static int mod_montgomery(BIGNUM *r, const BIGNUM *I, const BIGNUM *p,
780 const BN_MONT_CTX *mont_p, const BIGNUM *q,
782 // Reducing in constant-time with Montgomery reduction requires I <= p * R. We
783 // have I < p * q, so this follows if q < R. In particular, this always holds
784 // if p and q are the same size, which is true for any RSA keys we or anyone
785 // sane generates. For other keys, we fall back to |BN_mod|.
786 if (!bn_less_than_montgomery_R(q, mont_p)) {
787 return BN_mod(r, I, p, ctx);
790 if (// Reduce mod p with Montgomery reduction. This computes I * R^-1 mod p.
791 !BN_from_montgomery(r, I, mont_p, ctx) ||
792 // Multiply by R^2 and do another Montgomery reduction to compute
793 // I * R^-1 * R^2 * R^-1 = I mod p.
794 !BN_to_montgomery(r, r, mont_p, ctx)) {
798 // By precomputing R^3 mod p (normally |BN_MONT_CTX| only uses R^2 mod p) and
799 // adjusting the API for |BN_mod_exp_mont_consttime|, we could instead compute
800 // I * R mod p here and save a reduction per prime. But this would require
801 // changing the RSAZ code and may not be worth it. Note that the RSAZ code
802 // uses a different radix, so it uses R' = 2^1044. There we'd actually want
803 // R^2 * R', and would futher benefit from a precomputed R'^2. It currently
804 // converts |mont_p->RR| to R'^2.
808 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
811 assert(rsa->n != NULL);
812 assert(rsa->e != NULL);
813 assert(rsa->d != NULL);
814 assert(rsa->p != NULL);
815 assert(rsa->q != NULL);
816 assert(rsa->dmp1 != NULL);
817 assert(rsa->dmq1 != NULL);
818 assert(rsa->iqmp != NULL);
824 r1 = BN_CTX_get(ctx);
825 m1 = BN_CTX_get(ctx);
831 if (!freeze_private_key(rsa, ctx)) {
835 // Implementing RSA with CRT in constant-time is sensitive to which prime is
836 // larger. Canonicalize fields so that |p| is the larger prime.
837 const BIGNUM *dmp1 = rsa->dmp1_fixed, *dmq1 = rsa->dmq1_fixed;
838 const BN_MONT_CTX *mont_p = rsa->mont_p, *mont_q = rsa->mont_q;
839 if (BN_cmp(rsa->p, rsa->q) < 0) {
840 mont_p = rsa->mont_q;
841 mont_q = rsa->mont_p;
842 dmp1 = rsa->dmq1_fixed;
843 dmq1 = rsa->dmp1_fixed;
846 // Use the minimal-width versions of |n|, |p|, and |q|. Either works, but if
847 // someone gives us non-minimal values, these will be slightly more efficient
848 // on the non-Montgomery operations.
849 const BIGNUM *n = &rsa->mont_n->N;
850 const BIGNUM *p = &mont_p->N;
851 const BIGNUM *q = &mont_q->N;
853 // This is a pre-condition for |mod_montgomery|. It was already checked by the
855 assert(BN_ucmp(I, n) < 0);
857 if (// |m1| is the result modulo |q|.
858 !mod_montgomery(r1, I, q, mont_q, p, ctx) ||
859 !BN_mod_exp_mont_consttime(m1, r1, dmq1, q, ctx, mont_q) ||
860 // |r0| is the result modulo |p|.
861 !mod_montgomery(r1, I, p, mont_p, q, ctx) ||
862 !BN_mod_exp_mont_consttime(r0, r1, dmp1, p, ctx, mont_p) ||
863 // Compute r0 = r0 - m1 mod p. |p| is the larger prime, so |m1| is already
864 // fully reduced mod |p|.
865 !bn_mod_sub_consttime(r0, r0, m1, p, ctx) ||
866 // r0 = r0 * iqmp mod p. We use Montgomery multiplication to compute this
867 // in constant time. |inv_small_mod_large_mont| is in Montgomery form and
868 // r0 is not, so the result is taken out of Montgomery form.
869 !BN_mod_mul_montgomery(r0, r0, rsa->inv_small_mod_large_mont, mont_p,
871 // r0 = r0 * q + m1 gives the final result. Reducing modulo q gives m1, so
872 // it is correct mod p. Reducing modulo p gives (r0-m1)*iqmp*q + m1 = r0,
873 // so it is correct mod q. Finally, the result is bounded by [m1, n + m1),
874 // and the result is at least |m1|, so this must be the unique answer in
876 !bn_mul_consttime(r0, r0, q, ctx) ||
877 !bn_uadd_consttime(r0, r0, m1) ||
878 // The result should be bounded by |n|, but fixed-width operations may
879 // bound the width slightly higher, so fix it.
880 !bn_resize_words(r0, n->width)) {
891 static int ensure_bignum(BIGNUM **out) {
898 // kBoringSSLRSASqrtTwo is the BIGNUM representation of ⌊2¹⁵³⁵×√2⌋. This is
899 // chosen to give enough precision for 3072-bit RSA, the largest key size FIPS
900 // specifies. Key sizes beyond this will round up.
902 // To verify this number, check that n² < 2³⁰⁷¹ < (n+1)², where n is value
903 // represented here. Note the components are listed in little-endian order. Here
904 // is some sample Python code to check:
906 // >>> TOBN = lambda a, b: a << 32 | b
907 // >>> l = [ <paste the contents of kSqrtTwo> ]
908 // >>> n = sum(a * 2**(64*i) for i, a in enumerate(l))
909 // >>> n**2 < 2**3071 < (n+1)**2
911 const BN_ULONG kBoringSSLRSASqrtTwo[] = {
912 TOBN(0xdea06241, 0xf7aa81c2), TOBN(0xf6a1be3f, 0xca221307),
913 TOBN(0x332a5e9f, 0x7bda1ebf), TOBN(0x0104dc01, 0xfe32352f),
914 TOBN(0xb8cf341b, 0x6f8236c7), TOBN(0x4264dabc, 0xd528b651),
915 TOBN(0xf4d3a02c, 0xebc93e0c), TOBN(0x81394ab6, 0xd8fd0efd),
916 TOBN(0xeaa4a089, 0x9040ca4a), TOBN(0xf52f120f, 0x836e582e),
917 TOBN(0xcb2a6343, 0x31f3c84d), TOBN(0xc6d5a8a3, 0x8bb7e9dc),
918 TOBN(0x460abc72, 0x2f7c4e33), TOBN(0xcab1bc91, 0x1688458a),
919 TOBN(0x53059c60, 0x11bc337b), TOBN(0xd2202e87, 0x42af1f4e),
920 TOBN(0x78048736, 0x3dfa2768), TOBN(0x0f74a85e, 0x439c7b4a),
921 TOBN(0xa8b1fe6f, 0xdc83db39), TOBN(0x4afc8304, 0x3ab8a2c3),
922 TOBN(0xed17ac85, 0x83339915), TOBN(0x1d6f60ba, 0x893ba84c),
923 TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484),
925 const size_t kBoringSSLRSASqrtTwoLen = OPENSSL_ARRAY_SIZE(kBoringSSLRSASqrtTwo);
927 // generate_prime sets |out| to a prime with length |bits| such that |out|-1 is
928 // relatively prime to |e|. If |p| is non-NULL, |out| will also not be close to
929 // |p|. |sqrt2| must be ⌊2^(bits-1)×√2⌋ (or a slightly overestimate for large
930 // sizes), and |pow2_bits_100| must be 2^(bits-100).
931 static int generate_prime(BIGNUM *out, int bits, const BIGNUM *e,
932 const BIGNUM *p, const BIGNUM *sqrt2,
933 const BIGNUM *pow2_bits_100, BN_CTX *ctx,
935 if (bits < 128 || (bits % BN_BITS2) != 0) {
936 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
939 assert(BN_is_pow2(pow2_bits_100));
940 assert(BN_is_bit_set(pow2_bits_100, bits - 100));
942 // See FIPS 186-4 appendix B.3.3, steps 4 and 5. Note |bits| here is nlen/2.
944 // Use the limit from steps 4.7 and 5.8 for most values of |e|. When |e| is 3,
945 // the 186-4 limit is too low, so we use a higher one. Note this case is not
946 // reachable from |RSA_generate_key_fips|.
947 if (bits >= INT_MAX/32) {
948 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
951 int limit = BN_is_word(e, 3) ? bits * 32 : bits * 5;
953 int ret = 0, tries = 0, rand_tries = 0;
955 BIGNUM *tmp = BN_CTX_get(ctx);
961 // Generate a random number of length |bits| where the bottom bit is set
962 // (steps 4.2, 4.3, 5.2 and 5.3) and the top bit is set (implied by the
963 // bound checked below in steps 4.4 and 5.5).
964 if (!BN_rand(out, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD) ||
965 !BN_GENCB_call(cb, BN_GENCB_GENERATED, rand_tries++)) {
970 // If |p| and |out| are too close, try again (step 5.4).
971 if (!bn_abs_sub_consttime(tmp, out, p, ctx)) {
974 if (BN_cmp(tmp, pow2_bits_100) <= 0) {
979 // If out < 2^(bits-1)×√2, try again (steps 4.4 and 5.5). This is equivalent
980 // to out <= ⌊2^(bits-1)×√2⌋, or out <= sqrt2 for FIPS key sizes.
982 // For larger keys, the comparison is approximate, leaning towards
983 // retrying. That is, we reject a negligible fraction of primes that are
984 // within the FIPS bound, but we will never accept a prime outside the
985 // bound, ensuring the resulting RSA key is the right size.
986 if (BN_cmp(out, sqrt2) <= 0) {
990 // RSA key generation's bottleneck is discarding composites. If it fails
991 // trial division, do not bother computing a GCD or performing Rabin-Miller.
992 if (!bn_odd_number_is_obviously_composite(out)) {
993 // Check gcd(out-1, e) is one (steps 4.5 and 5.6).
994 int relatively_prime;
995 if (!BN_sub(tmp, out, BN_value_one()) ||
996 !bn_is_relatively_prime(&relatively_prime, tmp, e, ctx)) {
999 if (relatively_prime) {
1000 // Test |out| for primality (steps 4.5.1 and 5.6.1).
1001 int is_probable_prime;
1002 if (!BN_primality_test(&is_probable_prime, out, BN_prime_checks, ctx, 0,
1006 if (is_probable_prime) {
1013 // If we've tried too many times to find a prime, abort (steps 4.7 and
1016 if (tries >= limit) {
1017 OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);
1020 if (!BN_GENCB_call(cb, 2, tries)) {
1030 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
1031 // See FIPS 186-4 appendix B.3. This function implements a generalized version
1032 // of the FIPS algorithm. |RSA_generate_key_fips| performs additional checks
1033 // for FIPS-compliant key generation.
1035 // Always generate RSA keys which are a multiple of 128 bits. Round |bits|
1039 // Reject excessively small keys.
1041 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
1045 // Reject excessively large public exponents. Windows CryptoAPI and Go don't
1046 // support values larger than 32 bits, so match their limits for generating
1047 // keys. (|check_modulus_and_exponent_sizes| uses a slightly more conservative
1048 // value, but we don't need to support generating such keys.)
1049 // https://github.com/golang/go/issues/3161
1050 // https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx
1051 if (BN_num_bits(e_value) > 32) {
1052 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
1057 int prime_bits = bits / 2;
1058 BN_CTX *ctx = BN_CTX_new();
1063 BIGNUM *totient = BN_CTX_get(ctx);
1064 BIGNUM *pm1 = BN_CTX_get(ctx);
1065 BIGNUM *qm1 = BN_CTX_get(ctx);
1066 BIGNUM *sqrt2 = BN_CTX_get(ctx);
1067 BIGNUM *pow2_prime_bits_100 = BN_CTX_get(ctx);
1068 BIGNUM *pow2_prime_bits = BN_CTX_get(ctx);
1069 if (totient == NULL || pm1 == NULL || qm1 == NULL || sqrt2 == NULL ||
1070 pow2_prime_bits_100 == NULL || pow2_prime_bits == NULL ||
1071 !BN_set_bit(pow2_prime_bits_100, prime_bits - 100) ||
1072 !BN_set_bit(pow2_prime_bits, prime_bits)) {
1076 // We need the RSA components non-NULL.
1077 if (!ensure_bignum(&rsa->n) ||
1078 !ensure_bignum(&rsa->d) ||
1079 !ensure_bignum(&rsa->e) ||
1080 !ensure_bignum(&rsa->p) ||
1081 !ensure_bignum(&rsa->q) ||
1082 !ensure_bignum(&rsa->dmp1) ||
1083 !ensure_bignum(&rsa->dmq1)) {
1087 if (!BN_copy(rsa->e, e_value)) {
1091 // Compute sqrt2 >= ⌊2^(prime_bits-1)×√2⌋.
1092 if (!bn_set_words(sqrt2, kBoringSSLRSASqrtTwo, kBoringSSLRSASqrtTwoLen)) {
1095 int sqrt2_bits = kBoringSSLRSASqrtTwoLen * BN_BITS2;
1096 assert(sqrt2_bits == (int)BN_num_bits(sqrt2));
1097 if (sqrt2_bits > prime_bits) {
1098 // For key sizes up to 3072 (prime_bits = 1536), this is exactly
1099 // ⌊2^(prime_bits-1)×√2⌋.
1100 if (!BN_rshift(sqrt2, sqrt2, sqrt2_bits - prime_bits)) {
1103 } else if (prime_bits > sqrt2_bits) {
1104 // For key sizes beyond 3072, this is approximate. We err towards retrying
1105 // to ensure our key is the right size and round up.
1106 if (!BN_add_word(sqrt2, 1) ||
1107 !BN_lshift(sqrt2, sqrt2, prime_bits - sqrt2_bits)) {
1111 assert(prime_bits == (int)BN_num_bits(sqrt2));
1114 // Generate p and q, each of size |prime_bits|, using the steps outlined in
1115 // appendix FIPS 186-4 appendix B.3.3.
1116 if (!generate_prime(rsa->p, prime_bits, rsa->e, NULL, sqrt2,
1117 pow2_prime_bits_100, ctx, cb) ||
1118 !BN_GENCB_call(cb, 3, 0) ||
1119 !generate_prime(rsa->q, prime_bits, rsa->e, rsa->p, sqrt2,
1120 pow2_prime_bits_100, ctx, cb) ||
1121 !BN_GENCB_call(cb, 3, 1)) {
1125 if (BN_cmp(rsa->p, rsa->q) < 0) {
1126 BIGNUM *tmp = rsa->p;
1131 // Calculate d = e^(-1) (mod lcm(p-1, q-1)), per FIPS 186-4. This differs
1132 // from typical RSA implementations which use (p-1)*(q-1).
1134 // Note this means the size of d might reveal information about p-1 and
1135 // q-1. However, we do operations with Chinese Remainder Theorem, so we only
1136 // use d (mod p-1) and d (mod q-1) as exponents. Using a minimal totient
1137 // does not affect those two values.
1139 if (!bn_usub_consttime(pm1, rsa->p, BN_value_one()) ||
1140 !bn_usub_consttime(qm1, rsa->q, BN_value_one()) ||
1141 !bn_lcm_consttime(totient, pm1, qm1, ctx) ||
1142 !bn_mod_inverse_consttime(rsa->d, &no_inverse, rsa->e, totient, ctx)) {
1146 // Retry if |rsa->d| <= 2^|prime_bits|. See appendix B.3.1's guidance on
1148 } while (BN_cmp(rsa->d, pow2_prime_bits) <= 0);
1151 !bn_mul_consttime(rsa->n, rsa->p, rsa->q, ctx) ||
1152 // Calculate d mod (p-1).
1153 !bn_div_consttime(NULL, rsa->dmp1, rsa->d, pm1, ctx) ||
1154 // Calculate d mod (q-1)
1155 !bn_div_consttime(NULL, rsa->dmq1, rsa->d, qm1, ctx)) {
1158 bn_set_minimal_width(rsa->n);
1160 // Sanity-check that |rsa->n| has the specified size. This is implied by
1161 // |generate_prime|'s bounds.
1162 if (BN_num_bits(rsa->n) != (unsigned)bits) {
1163 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
1167 // Call |freeze_private_key| to compute the inverse of q mod p, by way of
1169 if (!freeze_private_key(rsa, ctx)) {
1173 // The key generation process is complex and thus error-prone. It could be
1174 // disastrous to generate and then use a bad key so double-check that the key
1176 if (!RSA_check_key(rsa)) {
1177 OPENSSL_PUT_ERROR(RSA, RSA_R_INTERNAL_ERROR);
1185 OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
1195 int RSA_generate_key_fips(RSA *rsa, int bits, BN_GENCB *cb) {
1196 // FIPS 186-4 allows 2048-bit and 3072-bit RSA keys (1024-bit and 1536-bit
1197 // primes, respectively) with the prime generation method we use.
1198 if (bits != 2048 && bits != 3072) {
1199 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_RSA_PARAMETERS);
1203 BIGNUM *e = BN_new();
1204 int ret = e != NULL &&
1205 BN_set_word(e, RSA_F4) &&
1206 RSA_generate_key_ex(rsa, bits, e, cb) &&
1207 RSA_check_fips(rsa);
1212 DEFINE_METHOD_FUNCTION(RSA_METHOD, RSA_default_method) {
1213 // All of the methods are NULL to make it easier for the compiler/linker to
1214 // drop unused functions. The wrapper functions will select the appropriate
1215 // |rsa_default_*| implementation.
1216 OPENSSL_memset(out, 0, sizeof(RSA_METHOD));
1217 out->common.is_static = 1;