1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
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.
7 *
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).
14 *
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.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
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)"
39 *
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
50 * SUCH DAMAGE.
51 *
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.] */
56
57#include <openssl/rsa.h>
58
59#include <assert.h>
60#include <limits.h>
61#include <string.h>
62
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>
68
69#include "internal.h"
70#include "../bn/internal.h"
71#include "../../internal.h"
72#include "../delocate.h"
73
74
75static int check_modulus_and_exponent_sizes(const RSA *rsa) {
76 unsigned rsa_bits = BN_num_bits(rsa->n);
77
78 if (rsa_bits > 16 * 1024) {
79 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
80 return 0;
81 }
82
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
87 // does.
88 //
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;
93
94 if (BN_num_bits(rsa->e) > kMaxExponentBits) {
95 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
96 return 0;
97 }
98
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
102 // accept.
103 if (rsa_bits <= kMaxExponentBits) {
104 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
105 return 0;
106 }
107 assert(BN_ucmp(rsa->n, rsa->e) > 0);
108
109 return 1;
110}
111
112static int ensure_fixed_copy(BIGNUM **out, const BIGNUM *in, int width) {
113 if (*out != NULL) {
114 return 1;
115 }
116 BIGNUM *copy = BN_dup(in);
117 if (copy == NULL ||
118 !bn_resize_words(copy, width)) {
119 BN_free(copy);
120 return 0;
121 }
122 *out = copy;
123 CONSTTIME_SECRET(copy->d, sizeof(BN_ULONG) * width);
124
125 return 1;
126}
127
128// freeze_private_key finishes initializing |rsa|'s private key components.
129// After this function has returned, |rsa| may not be changed. This is needed
130// because |RSA| is a public struct and, additionally, OpenSSL 1.1.0 opaquified
131// it wrong (see https://github.com/openssl/openssl/issues/5158).
132static int freeze_private_key(RSA *rsa, BN_CTX *ctx) {
133 CRYPTO_MUTEX_lock_read(&rsa->lock);
134 int frozen = rsa->private_key_frozen;
135 CRYPTO_MUTEX_unlock_read(&rsa->lock);
136 if (frozen) {
137 return 1;
138 }
139
140 int ret = 0;
141 CRYPTO_MUTEX_lock_write(&rsa->lock);
142 if (rsa->private_key_frozen) {
143 ret = 1;
144 goto err;
145 }
146
147 // Pre-compute various intermediate values, as well as copies of private
148 // exponents with correct widths. Note that other threads may concurrently
149 // read from |rsa->n|, |rsa->e|, etc., so any fixes must be in separate
150 // copies. We use |mont_n->N|, |mont_p->N|, and |mont_q->N| as copies of |n|,
151 // |p|, and |q| with the correct minimal widths.
152
153 if (rsa->mont_n == NULL) {
154 rsa->mont_n = BN_MONT_CTX_new_for_modulus(rsa->n, ctx);
155 if (rsa->mont_n == NULL) {
156 goto err;
157 }
158 }
159 const BIGNUM *n_fixed = &rsa->mont_n->N;
160
161 // The only public upper-bound of |rsa->d| is the bit length of |rsa->n|. The
162 // ASN.1 serialization of RSA private keys unfortunately leaks the byte length
163 // of |rsa->d|, but normalize it so we only leak it once, rather than per
164 // operation.
165 if (rsa->d != NULL &&
166 !ensure_fixed_copy(&rsa->d_fixed, rsa->d, n_fixed->width)) {
167 goto err;
168 }
169
170 if (rsa->p != NULL && rsa->q != NULL) {
171 // TODO: p and q are also CONSTTIME_SECRET but not yet marked as such
172 // because the Montgomery code does things like test whether or not values
173 // are zero. So the secret marking probably needs to happen inside that
174 // code.
175
176 if (rsa->mont_p == NULL) {
177 rsa->mont_p = BN_MONT_CTX_new_consttime(rsa->p, ctx);
178 if (rsa->mont_p == NULL) {
179 goto err;
180 }
181 }
182 const BIGNUM *p_fixed = &rsa->mont_p->N;
183
184 if (rsa->mont_q == NULL) {
185 rsa->mont_q = BN_MONT_CTX_new_consttime(rsa->q, ctx);
186 if (rsa->mont_q == NULL) {
187 goto err;
188 }
189 }
190 const BIGNUM *q_fixed = &rsa->mont_q->N;
191
192 if (rsa->dmp1 != NULL && rsa->dmq1 != NULL) {
193 // Key generation relies on this function to compute |iqmp|.
194 if (rsa->iqmp == NULL) {
195 BIGNUM *iqmp = BN_new();
196 if (iqmp == NULL ||
197 !bn_mod_inverse_secret_prime(iqmp, rsa->q, rsa->p, ctx,
198 rsa->mont_p)) {
199 BN_free(iqmp);
200 goto err;
201 }
202 rsa->iqmp = iqmp;
203 }
204
205 // CRT components are only publicly bounded by their corresponding
206 // moduli's bit lengths. |rsa->iqmp| is unused outside of this one-time
207 // setup, so we do not compute a fixed-width version of it.
208 if (!ensure_fixed_copy(&rsa->dmp1_fixed, rsa->dmp1, p_fixed->width) ||
209 !ensure_fixed_copy(&rsa->dmq1_fixed, rsa->dmq1, q_fixed->width)) {
210 goto err;
211 }
212
213 // Compute |inv_small_mod_large_mont|. Note that it is always modulo the
214 // larger prime, independent of what is stored in |rsa->iqmp|.
215 if (rsa->inv_small_mod_large_mont == NULL) {
216 BIGNUM *inv_small_mod_large_mont = BN_new();
217 int ok;
218 if (BN_cmp(rsa->p, rsa->q) < 0) {
219 ok = inv_small_mod_large_mont != NULL &&
220 bn_mod_inverse_secret_prime(inv_small_mod_large_mont, rsa->p,
221 rsa->q, ctx, rsa->mont_q) &&
222 BN_to_montgomery(inv_small_mod_large_mont,
223 inv_small_mod_large_mont, rsa->mont_q, ctx);
224 } else {
225 ok = inv_small_mod_large_mont != NULL &&
226 BN_to_montgomery(inv_small_mod_large_mont, rsa->iqmp,
227 rsa->mont_p, ctx);
228 }
229 if (!ok) {
230 BN_free(inv_small_mod_large_mont);
231 goto err;
232 }
233 rsa->inv_small_mod_large_mont = inv_small_mod_large_mont;
234 CONSTTIME_SECRET(
235 rsa->inv_small_mod_large_mont->d,
236 sizeof(BN_ULONG) * rsa->inv_small_mod_large_mont->width);
237 }
238 }
239 }
240
241 rsa->private_key_frozen = 1;
242 ret = 1;
243
244err:
245 CRYPTO_MUTEX_unlock_write(&rsa->lock);
246 return ret;
247}
248
249size_t rsa_default_size(const RSA *rsa) {
250 return BN_num_bytes(rsa->n);
251}
252
253int RSA_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
254 const uint8_t *in, size_t in_len, int padding) {
255 if (rsa->n == NULL || rsa->e == NULL) {
256 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
257 return 0;
258 }
259
260 const unsigned rsa_size = RSA_size(rsa);
261 BIGNUM *f, *result;
262 uint8_t *buf = NULL;
263 BN_CTX *ctx = NULL;
264 int i, ret = 0;
265
266 if (max_out < rsa_size) {
267 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
268 return 0;
269 }
270
271 if (!check_modulus_and_exponent_sizes(rsa)) {
272 return 0;
273 }
274
275 ctx = BN_CTX_new();
276 if (ctx == NULL) {
277 goto err;
278 }
279
280 BN_CTX_start(ctx);
281 f = BN_CTX_get(ctx);
282 result = BN_CTX_get(ctx);
283 buf = OPENSSL_malloc(rsa_size);
284 if (!f || !result || !buf) {
285 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
286 goto err;
287 }
288
289 switch (padding) {
290 case RSA_PKCS1_PADDING:
291 i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
292 break;
293 case RSA_PKCS1_OAEP_PADDING:
294 // Use the default parameters: SHA-1 for both hashes and no label.
295 i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
296 NULL, 0, NULL, NULL);
297 break;
298 case RSA_NO_PADDING:
299 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
300 break;
301 default:
302 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
303 goto err;
304 }
305
306 if (i <= 0) {
307 goto err;
308 }
309
310 if (BN_bin2bn(buf, rsa_size, f) == NULL) {
311 goto err;
312 }
313
314 if (BN_ucmp(f, rsa->n) >= 0) {
315 // usually the padding functions would catch this
316 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
317 goto err;
318 }
319
320 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
321 !BN_mod_exp_mont(result, f, rsa->e, &rsa->mont_n->N, ctx, rsa->mont_n)) {
322 goto err;
323 }
324
325 // put in leading 0 bytes if the number is less than the length of the
326 // modulus
327 if (!BN_bn2bin_padded(out, rsa_size, result)) {
328 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
329 goto err;
330 }
331
332 *out_len = rsa_size;
333 ret = 1;
334
335err:
336 if (ctx != NULL) {
337 BN_CTX_end(ctx);
338 BN_CTX_free(ctx);
339 }
340 OPENSSL_free(buf);
341
342 return ret;
343}
344
345// MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
346// RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
347// destroyed as needed.
348#define MAX_BLINDINGS_PER_RSA 1024
349
350// rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
351// allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
352// none are free, the cache will be extended by a extra element and the new
353// BN_BLINDING is returned.
354//
355// On success, the index of the assigned BN_BLINDING is written to
356// |*index_used| and must be passed to |rsa_blinding_release| when finished.
357static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
358 BN_CTX *ctx) {
359 assert(ctx != NULL);
360 assert(rsa->mont_n != NULL);
361
362 BN_BLINDING *ret = NULL;
363 BN_BLINDING **new_blindings;
364 uint8_t *new_blindings_inuse;
365 char overflow = 0;
366
367 CRYPTO_MUTEX_lock_write(&rsa->lock);
368
369 unsigned i;
370 for (i = 0; i < rsa->num_blindings; i++) {
371 if (rsa->blindings_inuse[i] == 0) {
372 rsa->blindings_inuse[i] = 1;
373 ret = rsa->blindings[i];
374 *index_used = i;
375 break;
376 }
377 }
378
379 if (ret != NULL) {
380 CRYPTO_MUTEX_unlock_write(&rsa->lock);
381 return ret;
382 }
383
384 overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA;
385
386 // We didn't find a free BN_BLINDING to use so increase the length of
387 // the arrays by one and use the newly created element.
388
389 CRYPTO_MUTEX_unlock_write(&rsa->lock);
390 ret = BN_BLINDING_new();
391 if (ret == NULL) {
392 return NULL;
393 }
394
395 if (overflow) {
396 // We cannot add any more cached BN_BLINDINGs so we use |ret|
397 // and mark it for destruction in |rsa_blinding_release|.
398 *index_used = MAX_BLINDINGS_PER_RSA;
399 return ret;
400 }
401
402 CRYPTO_MUTEX_lock_write(&rsa->lock);
403
404 new_blindings =
405 OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1));
406 if (new_blindings == NULL) {
407 goto err1;
408 }
409 OPENSSL_memcpy(new_blindings, rsa->blindings,
410 sizeof(BN_BLINDING *) * rsa->num_blindings);
411 new_blindings[rsa->num_blindings] = ret;
412
413 new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1);
414 if (new_blindings_inuse == NULL) {
415 goto err2;
416 }
417 OPENSSL_memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
418 new_blindings_inuse[rsa->num_blindings] = 1;
419 *index_used = rsa->num_blindings;
420
421 OPENSSL_free(rsa->blindings);
422 rsa->blindings = new_blindings;
423 OPENSSL_free(rsa->blindings_inuse);
424 rsa->blindings_inuse = new_blindings_inuse;
425 rsa->num_blindings++;
426
427 CRYPTO_MUTEX_unlock_write(&rsa->lock);
428 return ret;
429
430err2:
431 OPENSSL_free(new_blindings);
432
433err1:
434 CRYPTO_MUTEX_unlock_write(&rsa->lock);
435 BN_BLINDING_free(ret);
436 return NULL;
437}
438
439// rsa_blinding_release marks the cached BN_BLINDING at the given index as free
440// for other threads to use.
441static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
442 unsigned blinding_index) {
443 if (blinding_index == MAX_BLINDINGS_PER_RSA) {
444 // This blinding wasn't cached.
445 BN_BLINDING_free(blinding);
446 return;
447 }
448
449 CRYPTO_MUTEX_lock_write(&rsa->lock);
450 rsa->blindings_inuse[blinding_index] = 0;
451 CRYPTO_MUTEX_unlock_write(&rsa->lock);
452}
453
454// signing
455int rsa_default_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out,
456 size_t max_out, const uint8_t *in, size_t in_len,
457 int padding) {
458 const unsigned rsa_size = RSA_size(rsa);
459 uint8_t *buf = NULL;
460 int i, ret = 0;
461
462 if (max_out < rsa_size) {
463 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
464 return 0;
465 }
466
467 buf = OPENSSL_malloc(rsa_size);
468 if (buf == NULL) {
469 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
470 goto err;
471 }
472
473 switch (padding) {
474 case RSA_PKCS1_PADDING:
475 i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
476 break;
477 case RSA_NO_PADDING:
478 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
479 break;
480 default:
481 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
482 goto err;
483 }
484
485 if (i <= 0) {
486 goto err;
487 }
488
489 if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
490 goto err;
491 }
492
493 CONSTTIME_DECLASSIFY(out, rsa_size);
494 *out_len = rsa_size;
495 ret = 1;
496
497err:
498 OPENSSL_free(buf);
499
500 return ret;
501}
502
503int rsa_default_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
504 const uint8_t *in, size_t in_len, int padding) {
505 const unsigned rsa_size = RSA_size(rsa);
506 uint8_t *buf = NULL;
507 int ret = 0;
508
509 if (max_out < rsa_size) {
510 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
511 return 0;
512 }
513
514 if (padding == RSA_NO_PADDING) {
515 buf = out;
516 } else {
517 // Allocate a temporary buffer to hold the padded plaintext.
518 buf = OPENSSL_malloc(rsa_size);
519 if (buf == NULL) {
520 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
521 goto err;
522 }
523 }
524
525 if (in_len != rsa_size) {
526 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
527 goto err;
528 }
529
530 if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
531 goto err;
532 }
533
534 switch (padding) {
535 case RSA_PKCS1_PADDING:
536 ret =
537 RSA_padding_check_PKCS1_type_2(out, out_len, rsa_size, buf, rsa_size);
538 break;
539 case RSA_PKCS1_OAEP_PADDING:
540 // Use the default parameters: SHA-1 for both hashes and no label.
541 ret = RSA_padding_check_PKCS1_OAEP_mgf1(out, out_len, rsa_size, buf,
542 rsa_size, NULL, 0, NULL, NULL);
543 break;
544 case RSA_NO_PADDING:
545 *out_len = rsa_size;
546 ret = 1;
547 break;
548 default:
549 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
550 goto err;
551 }
552
553 CONSTTIME_DECLASSIFY(&ret, sizeof(ret));
554 if (!ret) {
555 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
556 } else {
557 CONSTTIME_DECLASSIFY(out, out_len);
558 }
559
560err:
561 if (padding != RSA_NO_PADDING) {
562 OPENSSL_free(buf);
563 }
564
565 return ret;
566}
567
568static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx);
569
570int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
571 const uint8_t *in, size_t in_len, int padding) {
572 if (rsa->n == NULL || rsa->e == NULL) {
573 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
574 return 0;
575 }
576
577 const unsigned rsa_size = RSA_size(rsa);
578 BIGNUM *f, *result;
579
580 if (max_out < rsa_size) {
581 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
582 return 0;
583 }
584
585 if (in_len != rsa_size) {
586 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
587 return 0;
588 }
589
590 if (!check_modulus_and_exponent_sizes(rsa)) {
591 return 0;
592 }
593
594 BN_CTX *ctx = BN_CTX_new();
595 if (ctx == NULL) {
596 return 0;
597 }
598
599 int ret = 0;
600 uint8_t *buf = NULL;
601
602 BN_CTX_start(ctx);
603 f = BN_CTX_get(ctx);
604 result = BN_CTX_get(ctx);
605 if (f == NULL || result == NULL) {
606 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
607 goto err;
608 }
609
610 if (padding == RSA_NO_PADDING) {
611 buf = out;
612 } else {
613 // Allocate a temporary buffer to hold the padded plaintext.
614 buf = OPENSSL_malloc(rsa_size);
615 if (buf == NULL) {
616 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
617 goto err;
618 }
619 }
620
621 if (BN_bin2bn(in, in_len, f) == NULL) {
622 goto err;
623 }
624
625 if (BN_ucmp(f, rsa->n) >= 0) {
626 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
627 goto err;
628 }
629
630 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
631 !BN_mod_exp_mont(result, f, rsa->e, &rsa->mont_n->N, ctx, rsa->mont_n)) {
632 goto err;
633 }
634
635 if (!BN_bn2bin_padded(buf, rsa_size, result)) {
636 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
637 goto err;
638 }
639
640 switch (padding) {
641 case RSA_PKCS1_PADDING:
642 ret =
643 RSA_padding_check_PKCS1_type_1(out, out_len, rsa_size, buf, rsa_size);
644 break;
645 case RSA_NO_PADDING:
646 ret = 1;
647 *out_len = rsa_size;
648 break;
649 default:
650 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
651 goto err;
652 }
653
654 if (!ret) {
655 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
656 goto err;
657 }
658
659err:
660 BN_CTX_end(ctx);
661 BN_CTX_free(ctx);
662 if (buf != out) {
663 OPENSSL_free(buf);
664 }
665 return ret;
666}
667
668int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
669 size_t len) {
670 if (rsa->n == NULL || rsa->d == NULL) {
671 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
672 return 0;
673 }
674
675 BIGNUM *f, *result;
676 BN_CTX *ctx = NULL;
677 unsigned blinding_index = 0;
678 BN_BLINDING *blinding = NULL;
679 int ret = 0;
680
681 ctx = BN_CTX_new();
682 if (ctx == NULL) {
683 goto err;
684 }
685 BN_CTX_start(ctx);
686 f = BN_CTX_get(ctx);
687 result = BN_CTX_get(ctx);
688
689 if (f == NULL || result == NULL) {
690 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
691 goto err;
692 }
693
694 if (BN_bin2bn(in, len, f) == NULL) {
695 goto err;
696 }
697
698 if (BN_ucmp(f, rsa->n) >= 0) {
699 // Usually the padding functions would catch this.
700 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
701 goto err;
702 }
703
704 if (!freeze_private_key(rsa, ctx)) {
705 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
706 goto err;
707 }
708
709 const int do_blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
710
711 if (rsa->e == NULL && do_blinding) {
712 // We cannot do blinding or verification without |e|, and continuing without
713 // those countermeasures is dangerous. However, the Java/Android RSA API
714 // requires support for keys where only |d| and |n| (and not |e|) are known.
715 // The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|.
716 OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);
717 goto err;
718 }
719
720 if (do_blinding) {
721 blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
722 if (blinding == NULL) {
723 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
724 goto err;
725 }
726 if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {
727 goto err;
728 }
729 }
730
731 if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&
732 rsa->dmq1 != NULL && rsa->iqmp != NULL &&
733 // Require that we can reduce |f| by |rsa->p| and |rsa->q| in constant
734 // time, which requires primes be the same size, rounded to the Montgomery
735 // coefficient. (See |mod_montgomery|.) This is not required by RFC 8017,
736 // but it is true for keys generated by us and all common implementations.
737 bn_less_than_montgomery_R(rsa->q, rsa->mont_p) &&
738 bn_less_than_montgomery_R(rsa->p, rsa->mont_q)) {
739 if (!mod_exp(result, f, rsa, ctx)) {
740 goto err;
741 }
742 } else if (!BN_mod_exp_mont_consttime(result, f, rsa->d_fixed, rsa->n, ctx,
743 rsa->mont_n)) {
744 goto err;
745 }
746
747 // Verify the result to protect against fault attacks as described in the
748 // 1997 paper "On the Importance of Checking Cryptographic Protocols for
749 // Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some
750 // implementations do this only when the CRT is used, but we do it in all
751 // cases. Section 6 of the aforementioned paper describes an attack that
752 // works when the CRT isn't used. That attack is much less likely to succeed
753 // than the CRT attack, but there have likely been improvements since 1997.
754 //
755 // This check is cheap assuming |e| is small; it almost always is.
756 if (rsa->e != NULL) {
757 BIGNUM *vrfy = BN_CTX_get(ctx);
758 if (vrfy == NULL ||
759 !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||
760 !BN_equal_consttime(vrfy, f)) {
761 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
762 goto err;
763 }
764
765 }
766
767 if (do_blinding &&
768 !BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {
769 goto err;
770 }
771
772 // The computation should have left |result| as a maximally-wide number, so
773 // that it and serializing does not leak information about the magnitude of
774 // the result.
775 //
776 // See Falko Strenzke, "Manger's Attack revisited", ICICS 2010.
777 assert(result->width == rsa->mont_n->N.width);
778 if (!BN_bn2bin_padded(out, len, result)) {
779 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
780 goto err;
781 }
782
783 ret = 1;
784
785err:
786 if (ctx != NULL) {
787 BN_CTX_end(ctx);
788 BN_CTX_free(ctx);
789 }
790 if (blinding != NULL) {
791 rsa_blinding_release(rsa, blinding, blinding_index);
792 }
793
794 return ret;
795}
796
797// mod_montgomery sets |r| to |I| mod |p|. |I| must already be fully reduced
798// modulo |p| times |q|. It returns one on success and zero on error.
799static int mod_montgomery(BIGNUM *r, const BIGNUM *I, const BIGNUM *p,
800 const BN_MONT_CTX *mont_p, const BIGNUM *q,
801 BN_CTX *ctx) {
802 // Reducing in constant-time with Montgomery reduction requires I <= p * R. We
803 // have I < p * q, so this follows if q < R. The caller should have checked
804 // this already.
805 if (!bn_less_than_montgomery_R(q, mont_p)) {
806 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
807 return 0;
808 }
809
810 if (// Reduce mod p with Montgomery reduction. This computes I * R^-1 mod p.
811 !BN_from_montgomery(r, I, mont_p, ctx) ||
812 // Multiply by R^2 and do another Montgomery reduction to compute
813 // I * R^-1 * R^2 * R^-1 = I mod p.
814 !BN_to_montgomery(r, r, mont_p, ctx)) {
815 return 0;
816 }
817
818 // By precomputing R^3 mod p (normally |BN_MONT_CTX| only uses R^2 mod p) and
819 // adjusting the API for |BN_mod_exp_mont_consttime|, we could instead compute
820 // I * R mod p here and save a reduction per prime. But this would require
821 // changing the RSAZ code and may not be worth it. Note that the RSAZ code
822 // uses a different radix, so it uses R' = 2^1044. There we'd actually want
823 // R^2 * R', and would futher benefit from a precomputed R'^2. It currently
824 // converts |mont_p->RR| to R'^2.
825 return 1;
826}
827
828static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
829 assert(ctx != NULL);
830
831 assert(rsa->n != NULL);
832 assert(rsa->e != NULL);
833 assert(rsa->d != NULL);
834 assert(rsa->p != NULL);
835 assert(rsa->q != NULL);
836 assert(rsa->dmp1 != NULL);
837 assert(rsa->dmq1 != NULL);
838 assert(rsa->iqmp != NULL);
839
840 BIGNUM *r1, *m1;
841 int ret = 0;
842
843 BN_CTX_start(ctx);
844 r1 = BN_CTX_get(ctx);
845 m1 = BN_CTX_get(ctx);
846 if (r1 == NULL ||
847 m1 == NULL) {
848 goto err;
849 }
850
851 if (!freeze_private_key(rsa, ctx)) {
852 goto err;
853 }
854
855 // Implementing RSA with CRT in constant-time is sensitive to which prime is
856 // larger. Canonicalize fields so that |p| is the larger prime.
857 const BIGNUM *dmp1 = rsa->dmp1_fixed, *dmq1 = rsa->dmq1_fixed;
858 const BN_MONT_CTX *mont_p = rsa->mont_p, *mont_q = rsa->mont_q;
859 if (BN_cmp(rsa->p, rsa->q) < 0) {
860 mont_p = rsa->mont_q;
861 mont_q = rsa->mont_p;
862 dmp1 = rsa->dmq1_fixed;
863 dmq1 = rsa->dmp1_fixed;
864 }
865
866 // Use the minimal-width versions of |n|, |p|, and |q|. Either works, but if
867 // someone gives us non-minimal values, these will be slightly more efficient
868 // on the non-Montgomery operations.
869 const BIGNUM *n = &rsa->mont_n->N;
870 const BIGNUM *p = &mont_p->N;
871 const BIGNUM *q = &mont_q->N;
872
873 // This is a pre-condition for |mod_montgomery|. It was already checked by the
874 // caller.
875 assert(BN_ucmp(I, n) < 0);
876
877 if (// |m1| is the result modulo |q|.
878 !mod_montgomery(r1, I, q, mont_q, p, ctx) ||
879 !BN_mod_exp_mont_consttime(m1, r1, dmq1, q, ctx, mont_q) ||
880 // |r0| is the result modulo |p|.
881 !mod_montgomery(r1, I, p, mont_p, q, ctx) ||
882 !BN_mod_exp_mont_consttime(r0, r1, dmp1, p, ctx, mont_p) ||
883 // Compute r0 = r0 - m1 mod p. |p| is the larger prime, so |m1| is already
884 // fully reduced mod |p|.
885 !bn_mod_sub_consttime(r0, r0, m1, p, ctx) ||
886 // r0 = r0 * iqmp mod p. We use Montgomery multiplication to compute this
887 // in constant time. |inv_small_mod_large_mont| is in Montgomery form and
888 // r0 is not, so the result is taken out of Montgomery form.
889 !BN_mod_mul_montgomery(r0, r0, rsa->inv_small_mod_large_mont, mont_p,
890 ctx) ||
891 // r0 = r0 * q + m1 gives the final result. Reducing modulo q gives m1, so
892 // it is correct mod p. Reducing modulo p gives (r0-m1)*iqmp*q + m1 = r0,
893 // so it is correct mod q. Finally, the result is bounded by [m1, n + m1),
894 // and the result is at least |m1|, so this must be the unique answer in
895 // [0, n).
896 !bn_mul_consttime(r0, r0, q, ctx) ||
897 !bn_uadd_consttime(r0, r0, m1) ||
898 // The result should be bounded by |n|, but fixed-width operations may
899 // bound the width slightly higher, so fix it.
900 !bn_resize_words(r0, n->width)) {
901 goto err;
902 }
903
904 ret = 1;
905
906err:
907 BN_CTX_end(ctx);
908 return ret;
909}
910
911static int ensure_bignum(BIGNUM **out) {
912 if (*out == NULL) {
913 *out = BN_new();
914 }
915 return *out != NULL;
916}
917
918// kBoringSSLRSASqrtTwo is the BIGNUM representation of ⌊2¹⁵³⁵×√2⌋. This is
919// chosen to give enough precision for 3072-bit RSA, the largest key size FIPS
920// specifies. Key sizes beyond this will round up.
921//
922// To verify this number, check that n² < 2³⁰⁷¹ < (n+1)², where n is value
923// represented here. Note the components are listed in little-endian order. Here
924// is some sample Python code to check:
925//
926// >>> TOBN = lambda a, b: a << 32 | b
927// >>> l = [ <paste the contents of kSqrtTwo> ]
928// >>> n = sum(a * 2**(64*i) for i, a in enumerate(l))
929// >>> n**2 < 2**3071 < (n+1)**2
930// True
931const BN_ULONG kBoringSSLRSASqrtTwo[] = {
932 TOBN(0xdea06241, 0xf7aa81c2), TOBN(0xf6a1be3f, 0xca221307),
933 TOBN(0x332a5e9f, 0x7bda1ebf), TOBN(0x0104dc01, 0xfe32352f),
934 TOBN(0xb8cf341b, 0x6f8236c7), TOBN(0x4264dabc, 0xd528b651),
935 TOBN(0xf4d3a02c, 0xebc93e0c), TOBN(0x81394ab6, 0xd8fd0efd),
936 TOBN(0xeaa4a089, 0x9040ca4a), TOBN(0xf52f120f, 0x836e582e),
937 TOBN(0xcb2a6343, 0x31f3c84d), TOBN(0xc6d5a8a3, 0x8bb7e9dc),
938 TOBN(0x460abc72, 0x2f7c4e33), TOBN(0xcab1bc91, 0x1688458a),
939 TOBN(0x53059c60, 0x11bc337b), TOBN(0xd2202e87, 0x42af1f4e),
940 TOBN(0x78048736, 0x3dfa2768), TOBN(0x0f74a85e, 0x439c7b4a),
941 TOBN(0xa8b1fe6f, 0xdc83db39), TOBN(0x4afc8304, 0x3ab8a2c3),
942 TOBN(0xed17ac85, 0x83339915), TOBN(0x1d6f60ba, 0x893ba84c),
943 TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484),
944};
945const size_t kBoringSSLRSASqrtTwoLen = OPENSSL_ARRAY_SIZE(kBoringSSLRSASqrtTwo);
946
947// generate_prime sets |out| to a prime with length |bits| such that |out|-1 is
948// relatively prime to |e|. If |p| is non-NULL, |out| will also not be close to
949// |p|. |sqrt2| must be ⌊2^(bits-1)×√2⌋ (or a slightly overestimate for large
950// sizes), and |pow2_bits_100| must be 2^(bits-100).
951//
952// This function fails with probability around 2^-21.
953static int generate_prime(BIGNUM *out, int bits, const BIGNUM *e,
954 const BIGNUM *p, const BIGNUM *sqrt2,
955 const BIGNUM *pow2_bits_100, BN_CTX *ctx,
956 BN_GENCB *cb) {
957 if (bits < 128 || (bits % BN_BITS2) != 0) {
958 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
959 return 0;
960 }
961 assert(BN_is_pow2(pow2_bits_100));
962 assert(BN_is_bit_set(pow2_bits_100, bits - 100));
963
964 // See FIPS 186-4 appendix B.3.3, steps 4 and 5. Note |bits| here is nlen/2.
965
966 // Use the limit from steps 4.7 and 5.8 for most values of |e|. When |e| is 3,
967 // the 186-4 limit is too low, so we use a higher one. Note this case is not
968 // reachable from |RSA_generate_key_fips|.
969 //
970 // |limit| determines the failure probability. We must find a prime that is
971 // not 1 mod |e|. By the prime number theorem, we'll find one with probability
972 // p = (e-1)/e * 2/(ln(2)*bits). Note the second term is doubled because we
973 // discard even numbers.
974 //
975 // The failure probability is thus (1-p)^limit. To convert that to a power of
976 // two, we take logs. -log_2((1-p)^limit) = -limit * ln(1-p) / ln(2).
977 //
978 // >>> def f(bits, e, limit):
979 // ... p = (e-1.0)/e * 2.0/(math.log(2)*bits)
980 // ... return -limit * math.log(1 - p) / math.log(2)
981 // ...
982 // >>> f(1024, 65537, 5*1024)
983 // 20.842750558272634
984 // >>> f(1536, 65537, 5*1536)
985 // 20.83294549602474
986 // >>> f(2048, 65537, 5*2048)
987 // 20.828047576234948
988 // >>> f(1024, 3, 8*1024)
989 // 22.222147925962307
990 // >>> f(1536, 3, 8*1536)
991 // 22.21518251065506
992 // >>> f(2048, 3, 8*2048)
993 // 22.211701985875937
994 if (bits >= INT_MAX/32) {
995 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
996 return 0;
997 }
998 int limit = BN_is_word(e, 3) ? bits * 8 : bits * 5;
999
1000 int ret = 0, tries = 0, rand_tries = 0;
1001 BN_CTX_start(ctx);
1002 BIGNUM *tmp = BN_CTX_get(ctx);
1003 if (tmp == NULL) {
1004 goto err;
1005 }
1006
1007 for (;;) {
1008 // Generate a random number of length |bits| where the bottom bit is set
1009 // (steps 4.2, 4.3, 5.2 and 5.3) and the top bit is set (implied by the
1010 // bound checked below in steps 4.4 and 5.5).
1011 if (!BN_rand(out, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD) ||
1012 !BN_GENCB_call(cb, BN_GENCB_GENERATED, rand_tries++)) {
1013 goto err;
1014 }
1015
1016 if (p != NULL) {
1017 // If |p| and |out| are too close, try again (step 5.4).
1018 if (!bn_abs_sub_consttime(tmp, out, p, ctx)) {
1019 goto err;
1020 }
1021 if (BN_cmp(tmp, pow2_bits_100) <= 0) {
1022 continue;
1023 }
1024 }
1025
1026 // If out < 2^(bits-1)×√2, try again (steps 4.4 and 5.5). This is equivalent
1027 // to out <= ⌊2^(bits-1)×√2⌋, or out <= sqrt2 for FIPS key sizes.
1028 //
1029 // For larger keys, the comparison is approximate, leaning towards
1030 // retrying. That is, we reject a negligible fraction of primes that are
1031 // within the FIPS bound, but we will never accept a prime outside the
1032 // bound, ensuring the resulting RSA key is the right size.
1033 if (BN_cmp(out, sqrt2) <= 0) {
1034 continue;
1035 }
1036
1037 // RSA key generation's bottleneck is discarding composites. If it fails
1038 // trial division, do not bother computing a GCD or performing Rabin-Miller.
1039 if (!bn_odd_number_is_obviously_composite(out)) {
1040 // Check gcd(out-1, e) is one (steps 4.5 and 5.6).
1041 int relatively_prime;
1042 if (!BN_sub(tmp, out, BN_value_one()) ||
1043 !bn_is_relatively_prime(&relatively_prime, tmp, e, ctx)) {
1044 goto err;
1045 }
1046 if (relatively_prime) {
1047 // Test |out| for primality (steps 4.5.1 and 5.6.1).
1048 int is_probable_prime;
1049 if (!BN_primality_test(&is_probable_prime, out, BN_prime_checks, ctx, 0,
1050 cb)) {
1051 goto err;
1052 }
1053 if (is_probable_prime) {
1054 ret = 1;
1055 goto err;
1056 }
1057 }
1058 }
1059
1060 // If we've tried too many times to find a prime, abort (steps 4.7 and
1061 // 5.8).
1062 tries++;
1063 if (tries >= limit) {
1064 OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);
1065 goto err;
1066 }
1067 if (!BN_GENCB_call(cb, 2, tries)) {
1068 goto err;
1069 }
1070 }
1071
1072err:
1073 BN_CTX_end(ctx);
1074 return ret;
1075}
1076
1077// rsa_generate_key_impl generates an RSA key using a generalized version of
1078// FIPS 186-4 appendix B.3. |RSA_generate_key_fips| performs additional checks
1079// for FIPS-compliant key generation.
1080//
1081// This function returns one on success and zero on failure. It has a failure
1082// probability of about 2^-20.
1083static int rsa_generate_key_impl(RSA *rsa, int bits, const BIGNUM *e_value,
1084 BN_GENCB *cb) {
1085 // See FIPS 186-4 appendix B.3. This function implements a generalized version
1086 // of the FIPS algorithm. |RSA_generate_key_fips| performs additional checks
1087 // for FIPS-compliant key generation.
1088
1089 // Always generate RSA keys which are a multiple of 128 bits. Round |bits|
1090 // down as needed.
1091 bits &= ~127;
1092
1093 // Reject excessively small keys.
1094 if (bits < 256) {
1095 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
1096 return 0;
1097 }
1098
1099 // Reject excessively large public exponents. Windows CryptoAPI and Go don't
1100 // support values larger than 32 bits, so match their limits for generating
1101 // keys. (|check_modulus_and_exponent_sizes| uses a slightly more conservative
1102 // value, but we don't need to support generating such keys.)
1103 // https://github.com/golang/go/issues/3161
1104 // https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx
1105 if (BN_num_bits(e_value) > 32) {
1106 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
1107 return 0;
1108 }
1109
1110 int ret = 0;
1111 int prime_bits = bits / 2;
1112 BN_CTX *ctx = BN_CTX_new();
1113 if (ctx == NULL) {
1114 goto bn_err;
1115 }
1116 BN_CTX_start(ctx);
1117 BIGNUM *totient = BN_CTX_get(ctx);
1118 BIGNUM *pm1 = BN_CTX_get(ctx);
1119 BIGNUM *qm1 = BN_CTX_get(ctx);
1120 BIGNUM *sqrt2 = BN_CTX_get(ctx);
1121 BIGNUM *pow2_prime_bits_100 = BN_CTX_get(ctx);
1122 BIGNUM *pow2_prime_bits = BN_CTX_get(ctx);
1123 if (totient == NULL || pm1 == NULL || qm1 == NULL || sqrt2 == NULL ||
1124 pow2_prime_bits_100 == NULL || pow2_prime_bits == NULL ||
1125 !BN_set_bit(pow2_prime_bits_100, prime_bits - 100) ||
1126 !BN_set_bit(pow2_prime_bits, prime_bits)) {
1127 goto bn_err;
1128 }
1129
1130 // We need the RSA components non-NULL.
1131 if (!ensure_bignum(&rsa->n) ||
1132 !ensure_bignum(&rsa->d) ||
1133 !ensure_bignum(&rsa->e) ||
1134 !ensure_bignum(&rsa->p) ||
1135 !ensure_bignum(&rsa->q) ||
1136 !ensure_bignum(&rsa->dmp1) ||
1137 !ensure_bignum(&rsa->dmq1)) {
1138 goto bn_err;
1139 }
1140
1141 if (!BN_copy(rsa->e, e_value)) {
1142 goto bn_err;
1143 }
1144
1145 // Compute sqrt2 >= ⌊2^(prime_bits-1)×√2⌋.
1146 if (!bn_set_words(sqrt2, kBoringSSLRSASqrtTwo, kBoringSSLRSASqrtTwoLen)) {
1147 goto bn_err;
1148 }
1149 int sqrt2_bits = kBoringSSLRSASqrtTwoLen * BN_BITS2;
1150 assert(sqrt2_bits == (int)BN_num_bits(sqrt2));
1151 if (sqrt2_bits > prime_bits) {
1152 // For key sizes up to 3072 (prime_bits = 1536), this is exactly
1153 // ⌊2^(prime_bits-1)×√2⌋.
1154 if (!BN_rshift(sqrt2, sqrt2, sqrt2_bits - prime_bits)) {
1155 goto bn_err;
1156 }
1157 } else if (prime_bits > sqrt2_bits) {
1158 // For key sizes beyond 3072, this is approximate. We err towards retrying
1159 // to ensure our key is the right size and round up.
1160 if (!BN_add_word(sqrt2, 1) ||
1161 !BN_lshift(sqrt2, sqrt2, prime_bits - sqrt2_bits)) {
1162 goto bn_err;
1163 }
1164 }
1165 assert(prime_bits == (int)BN_num_bits(sqrt2));
1166
1167 do {
1168 // Generate p and q, each of size |prime_bits|, using the steps outlined in
1169 // appendix FIPS 186-4 appendix B.3.3.
1170 //
1171 // Each call to |generate_prime| fails with probability p = 2^-21. The
1172 // probability that either call fails is 1 - (1-p)^2, which is around 2^-20.
1173 if (!generate_prime(rsa->p, prime_bits, rsa->e, NULL, sqrt2,
1174 pow2_prime_bits_100, ctx, cb) ||
1175 !BN_GENCB_call(cb, 3, 0) ||
1176 !generate_prime(rsa->q, prime_bits, rsa->e, rsa->p, sqrt2,
1177 pow2_prime_bits_100, ctx, cb) ||
1178 !BN_GENCB_call(cb, 3, 1)) {
1179 goto bn_err;
1180 }
1181
1182 if (BN_cmp(rsa->p, rsa->q) < 0) {
1183 BIGNUM *tmp = rsa->p;
1184 rsa->p = rsa->q;
1185 rsa->q = tmp;
1186 }
1187
1188 // Calculate d = e^(-1) (mod lcm(p-1, q-1)), per FIPS 186-4. This differs
1189 // from typical RSA implementations which use (p-1)*(q-1).
1190 //
1191 // Note this means the size of d might reveal information about p-1 and
1192 // q-1. However, we do operations with Chinese Remainder Theorem, so we only
1193 // use d (mod p-1) and d (mod q-1) as exponents. Using a minimal totient
1194 // does not affect those two values.
1195 int no_inverse;
1196 if (!bn_usub_consttime(pm1, rsa->p, BN_value_one()) ||
1197 !bn_usub_consttime(qm1, rsa->q, BN_value_one()) ||
1198 !bn_lcm_consttime(totient, pm1, qm1, ctx) ||
1199 !bn_mod_inverse_consttime(rsa->d, &no_inverse, rsa->e, totient, ctx)) {
1200 goto bn_err;
1201 }
1202
1203 // Retry if |rsa->d| <= 2^|prime_bits|. See appendix B.3.1's guidance on
1204 // values for d.
1205 } while (BN_cmp(rsa->d, pow2_prime_bits) <= 0);
1206
1207 if (// Calculate n.
1208 !bn_mul_consttime(rsa->n, rsa->p, rsa->q, ctx) ||
1209 // Calculate d mod (p-1).
1210 !bn_div_consttime(NULL, rsa->dmp1, rsa->d, pm1, ctx) ||
1211 // Calculate d mod (q-1)
1212 !bn_div_consttime(NULL, rsa->dmq1, rsa->d, qm1, ctx)) {
1213 goto bn_err;
1214 }
1215 bn_set_minimal_width(rsa->n);
1216
1217 // Sanity-check that |rsa->n| has the specified size. This is implied by
1218 // |generate_prime|'s bounds.
1219 if (BN_num_bits(rsa->n) != (unsigned)bits) {
1220 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
1221 goto err;
1222 }
1223
1224 // Call |freeze_private_key| to compute the inverse of q mod p, by way of
1225 // |rsa->mont_p|.
1226 if (!freeze_private_key(rsa, ctx)) {
1227 goto bn_err;
1228 }
1229
1230 // The key generation process is complex and thus error-prone. It could be
1231 // disastrous to generate and then use a bad key so double-check that the key
1232 // makes sense.
1233 if (!RSA_check_key(rsa)) {
1234 OPENSSL_PUT_ERROR(RSA, RSA_R_INTERNAL_ERROR);
1235 goto err;
1236 }
1237
1238 ret = 1;
1239
1240bn_err:
1241 if (!ret) {
1242 OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
1243 }
1244err:
1245 if (ctx != NULL) {
1246 BN_CTX_end(ctx);
1247 BN_CTX_free(ctx);
1248 }
1249 return ret;
1250}
1251
1252static void replace_bignum(BIGNUM **out, BIGNUM **in) {
1253 BN_free(*out);
1254 *out = *in;
1255 *in = NULL;
1256}
1257
1258static void replace_bn_mont_ctx(BN_MONT_CTX **out, BN_MONT_CTX **in) {
1259 BN_MONT_CTX_free(*out);
1260 *out = *in;
1261 *in = NULL;
1262}
1263
1264int RSA_generate_key_ex(RSA *rsa, int bits, const BIGNUM *e_value,
1265 BN_GENCB *cb) {
1266 // |rsa_generate_key_impl|'s 2^-20 failure probability is too high at scale,
1267 // so we run the FIPS algorithm four times, bringing it down to 2^-80. We
1268 // should just adjust the retry limit, but FIPS 186-4 prescribes that value
1269 // and thus results in unnecessary complexity.
1270 for (int i = 0; i < 4; i++) {
1271 ERR_clear_error();
1272 // Generate into scratch space, to avoid leaving partial work on failure.
1273 RSA *tmp = RSA_new();
1274 if (tmp == NULL) {
1275 return 0;
1276 }
1277 if (rsa_generate_key_impl(tmp, bits, e_value, cb)) {
1278 replace_bignum(&rsa->n, &tmp->n);
1279 replace_bignum(&rsa->e, &tmp->e);
1280 replace_bignum(&rsa->d, &tmp->d);
1281 replace_bignum(&rsa->p, &tmp->p);
1282 replace_bignum(&rsa->q, &tmp->q);
1283 replace_bignum(&rsa->dmp1, &tmp->dmp1);
1284 replace_bignum(&rsa->dmq1, &tmp->dmq1);
1285 replace_bignum(&rsa->iqmp, &tmp->iqmp);
1286 replace_bn_mont_ctx(&rsa->mont_n, &tmp->mont_n);
1287 replace_bn_mont_ctx(&rsa->mont_p, &tmp->mont_p);
1288 replace_bn_mont_ctx(&rsa->mont_q, &tmp->mont_q);
1289 replace_bignum(&rsa->d_fixed, &tmp->d_fixed);
1290 replace_bignum(&rsa->dmp1_fixed, &tmp->dmp1_fixed);
1291 replace_bignum(&rsa->dmq1_fixed, &tmp->dmq1_fixed);
1292 replace_bignum(&rsa->inv_small_mod_large_mont,
1293 &tmp->inv_small_mod_large_mont);
1294 rsa->private_key_frozen = tmp->private_key_frozen;
1295 RSA_free(tmp);
1296 return 1;
1297 }
1298 uint32_t err = ERR_peek_error();
1299 RSA_free(tmp);
1300 tmp = NULL;
1301 // Only retry on |RSA_R_TOO_MANY_ITERATIONS|. This is so a caller-induced
1302 // failure in |BN_GENCB_call| is still fatal.
1303 if (ERR_GET_LIB(err) != ERR_LIB_RSA ||
1304 ERR_GET_REASON(err) != RSA_R_TOO_MANY_ITERATIONS) {
1305 return 0;
1306 }
1307 }
1308
1309 return 0;
1310}
1311
1312int RSA_generate_key_fips(RSA *rsa, int bits, BN_GENCB *cb) {
1313 // FIPS 186-4 allows 2048-bit and 3072-bit RSA keys (1024-bit and 1536-bit
1314 // primes, respectively) with the prime generation method we use.
1315 if (bits != 2048 && bits != 3072) {
1316 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_RSA_PARAMETERS);
1317 return 0;
1318 }
1319
1320 BIGNUM *e = BN_new();
1321 int ret = e != NULL &&
1322 BN_set_word(e, RSA_F4) &&
1323 RSA_generate_key_ex(rsa, bits, e, cb) &&
1324 RSA_check_fips(rsa);
1325 BN_free(e);
1326 return ret;
1327}
1328
1329DEFINE_METHOD_FUNCTION(RSA_METHOD, RSA_default_method) {
1330 // All of the methods are NULL to make it easier for the compiler/linker to
1331 // drop unused functions. The wrapper functions will select the appropriate
1332 // |rsa_default_*| implementation.
1333 OPENSSL_memset(out, 0, sizeof(RSA_METHOD));
1334 out->common.is_static = 1;
1335}
1336