blob: 3834be5af51f846a8881154ba3325a31b0e2fc0b [file] [log] [blame]
Adam Langley95c29f32014-06-20 12:00:00 -07001/* 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
David Benjamincfa9de82016-03-14 14:19:41 -040059#include <assert.h>
Adam Langley2b2d66d2015-01-30 17:08:37 -080060#include <string.h>
61
Adam Langley95c29f32014-06-20 12:00:00 -070062#include <openssl/bn.h>
63#include <openssl/err.h>
64#include <openssl/mem.h>
Brian Smith054e6822015-03-27 21:12:01 -100065#include <openssl/thread.h>
Adam Langley95c29f32014-06-20 12:00:00 -070066
67#include "internal.h"
David Benjamin0b8dc302016-12-17 14:27:16 -050068#include "../bn/internal.h"
Adam Langley683d7bd2015-04-13 11:04:14 -070069#include "../internal.h"
Adam Langley95c29f32014-06-20 12:00:00 -070070
71
Brian Smith625475f2016-01-12 10:47:25 -100072static int check_modulus_and_exponent_sizes(const RSA *rsa) {
73 unsigned rsa_bits = BN_num_bits(rsa->n);
David Benjamincfa9de82016-03-14 14:19:41 -040074
Brian Smith625475f2016-01-12 10:47:25 -100075 if (rsa_bits > 16 * 1024) {
76 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
77 return 0;
78 }
Adam Langley95c29f32014-06-20 12:00:00 -070079
David Benjamincfa9de82016-03-14 14:19:41 -040080 /* Mitigate DoS attacks by limiting the exponent size. 33 bits was chosen as
81 * the limit based on the recommendations in [1] and [2]. Windows CryptoAPI
82 * doesn't support values larger than 32 bits [3], so it is unlikely that
83 * exponents larger than 32 bits are being used for anything Windows commonly
84 * does.
85 *
86 * [1] https://www.imperialviolet.org/2012/03/16/rsae.html
87 * [2] https://www.imperialviolet.org/2012/03/17/rsados.html
88 * [3] https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx */
89 static const unsigned kMaxExponentBits = 33;
90
91 if (BN_num_bits(rsa->e) > kMaxExponentBits) {
Brian Smith625475f2016-01-12 10:47:25 -100092 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
93 return 0;
94 }
95
David Benjamincfa9de82016-03-14 14:19:41 -040096 /* Verify |n > e|. Comparing |rsa_bits| to |kMaxExponentBits| is a small
97 * shortcut to comparing |n| and |e| directly. In reality, |kMaxExponentBits|
98 * is much smaller than the minimum RSA key size that any application should
99 * accept. */
100 if (rsa_bits <= kMaxExponentBits) {
101 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
Brian Smith625475f2016-01-12 10:47:25 -1000102 return 0;
103 }
David Benjamincfa9de82016-03-14 14:19:41 -0400104 assert(BN_ucmp(rsa->n, rsa->e) > 0);
Brian Smith625475f2016-01-12 10:47:25 -1000105
106 return 1;
107}
Adam Langley95c29f32014-06-20 12:00:00 -0700108
David Benjamind93831d2015-10-29 13:19:12 -0400109size_t rsa_default_size(const RSA *rsa) {
David Benjamin925fee32014-07-11 14:14:08 -0400110 return BN_num_bytes(rsa->n);
111}
112
David Benjamind93831d2015-10-29 13:19:12 -0400113int rsa_default_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
114 const uint8_t *in, size_t in_len, int padding) {
Adam Langley95c29f32014-06-20 12:00:00 -0700115 const unsigned rsa_size = RSA_size(rsa);
Adam Langley95c29f32014-06-20 12:00:00 -0700116 BIGNUM *f, *result;
117 uint8_t *buf = NULL;
118 BN_CTX *ctx = NULL;
Adam Langley6887edb2014-06-20 12:00:00 -0700119 int i, ret = 0;
Adam Langley95c29f32014-06-20 12:00:00 -0700120
Adam Langley95c29f32014-06-20 12:00:00 -0700121 if (max_out < rsa_size) {
David Benjamin3570d732015-06-29 00:28:17 -0400122 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
Adam Langley95c29f32014-06-20 12:00:00 -0700123 return 0;
124 }
125
Brian Smith625475f2016-01-12 10:47:25 -1000126 if (!check_modulus_and_exponent_sizes(rsa)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700127 return 0;
128 }
129
130 ctx = BN_CTX_new();
131 if (ctx == NULL) {
132 goto err;
133 }
134
135 BN_CTX_start(ctx);
136 f = BN_CTX_get(ctx);
137 result = BN_CTX_get(ctx);
138 buf = OPENSSL_malloc(rsa_size);
139 if (!f || !result || !buf) {
David Benjamin3570d732015-06-29 00:28:17 -0400140 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
Adam Langley95c29f32014-06-20 12:00:00 -0700141 goto err;
142 }
143
144 switch (padding) {
145 case RSA_PKCS1_PADDING:
146 i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
147 break;
148 case RSA_PKCS1_OAEP_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700149 /* Use the default parameters: SHA-1 for both hashes and no label. */
150 i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
151 NULL, 0, NULL, NULL);
Adam Langley95c29f32014-06-20 12:00:00 -0700152 break;
Adam Langley95c29f32014-06-20 12:00:00 -0700153 case RSA_NO_PADDING:
154 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
155 break;
156 default:
David Benjamin3570d732015-06-29 00:28:17 -0400157 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
Adam Langley95c29f32014-06-20 12:00:00 -0700158 goto err;
159 }
160
161 if (i <= 0) {
162 goto err;
163 }
164
165 if (BN_bin2bn(buf, rsa_size, f) == NULL) {
166 goto err;
167 }
168
169 if (BN_ucmp(f, rsa->n) >= 0) {
170 /* usually the padding functions would catch this */
David Benjamin3570d732015-06-29 00:28:17 -0400171 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
Adam Langley95c29f32014-06-20 12:00:00 -0700172 goto err;
173 }
174
Brian Smithd0357302016-03-25 10:11:04 -1000175 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
Brian Smith24493a42016-03-25 09:12:48 -1000176 !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700177 goto err;
178 }
179
180 /* put in leading 0 bytes if the number is less than the length of the
181 * modulus */
Adam Langley6887edb2014-06-20 12:00:00 -0700182 if (!BN_bn2bin_padded(out, rsa_size, result)) {
David Benjamin3570d732015-06-29 00:28:17 -0400183 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
Adam Langley6887edb2014-06-20 12:00:00 -0700184 goto err;
Adam Langley95c29f32014-06-20 12:00:00 -0700185 }
186
187 *out_len = rsa_size;
188 ret = 1;
189
190err:
191 if (ctx != NULL) {
192 BN_CTX_end(ctx);
193 BN_CTX_free(ctx);
194 }
195 if (buf != NULL) {
196 OPENSSL_cleanse(buf, rsa_size);
197 OPENSSL_free(buf);
198 }
199
200 return ret;
201}
202
203/* MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
204 * RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
205 * destroyed as needed. */
206#define MAX_BLINDINGS_PER_RSA 1024
207
208/* rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
209 * allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
210 * none are free, the cache will be extended by a extra element and the new
211 * BN_BLINDING is returned.
212 *
213 * On success, the index of the assigned BN_BLINDING is written to
214 * |*index_used| and must be passed to |rsa_blinding_release| when finished. */
215static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
216 BN_CTX *ctx) {
Brian Smith3426d102016-03-17 16:10:04 -1000217 assert(ctx != NULL);
Brian Smithcbf56a52016-03-21 11:25:39 -1000218 assert(rsa->mont_n != NULL);
219
Adam Langley95c29f32014-06-20 12:00:00 -0700220 BN_BLINDING *ret = NULL;
221 BN_BLINDING **new_blindings;
222 uint8_t *new_blindings_inuse;
223 char overflow = 0;
224
Adam Langley683d7bd2015-04-13 11:04:14 -0700225 CRYPTO_MUTEX_lock_write(&rsa->lock);
Adam Langley95c29f32014-06-20 12:00:00 -0700226
Adam Langley33672732015-03-31 18:55:53 -0700227 unsigned i;
228 for (i = 0; i < rsa->num_blindings; i++) {
229 if (rsa->blindings_inuse[i] == 0) {
230 rsa->blindings_inuse[i] = 1;
231 ret = rsa->blindings[i];
232 *index_used = i;
233 break;
Adam Langley95c29f32014-06-20 12:00:00 -0700234 }
235 }
236
237 if (ret != NULL) {
David Benjamin29270de2016-05-24 15:28:36 +0000238 CRYPTO_MUTEX_unlock_write(&rsa->lock);
Adam Langley95c29f32014-06-20 12:00:00 -0700239 return ret;
240 }
241
242 overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA;
243
244 /* We didn't find a free BN_BLINDING to use so increase the length of
245 * the arrays by one and use the newly created element. */
246
David Benjamin29270de2016-05-24 15:28:36 +0000247 CRYPTO_MUTEX_unlock_write(&rsa->lock);
Brian Smith86361a32016-03-26 19:42:31 -1000248 ret = BN_BLINDING_new();
Adam Langley95c29f32014-06-20 12:00:00 -0700249 if (ret == NULL) {
250 return NULL;
251 }
252
253 if (overflow) {
254 /* We cannot add any more cached BN_BLINDINGs so we use |ret|
255 * and mark it for destruction in |rsa_blinding_release|. */
256 *index_used = MAX_BLINDINGS_PER_RSA;
257 return ret;
258 }
259
Adam Langley683d7bd2015-04-13 11:04:14 -0700260 CRYPTO_MUTEX_lock_write(&rsa->lock);
Adam Langley95c29f32014-06-20 12:00:00 -0700261
262 new_blindings =
263 OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1));
264 if (new_blindings == NULL) {
265 goto err1;
266 }
David Benjamin17cf2cb2016-12-13 01:07:13 -0500267 OPENSSL_memcpy(new_blindings, rsa->blindings,
Adam Langley95c29f32014-06-20 12:00:00 -0700268 sizeof(BN_BLINDING *) * rsa->num_blindings);
269 new_blindings[rsa->num_blindings] = ret;
270
271 new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1);
272 if (new_blindings_inuse == NULL) {
273 goto err2;
274 }
David Benjamin17cf2cb2016-12-13 01:07:13 -0500275 OPENSSL_memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
Adam Langley95c29f32014-06-20 12:00:00 -0700276 new_blindings_inuse[rsa->num_blindings] = 1;
277 *index_used = rsa->num_blindings;
278
David Benjamind8b65c82015-04-22 16:09:09 -0400279 OPENSSL_free(rsa->blindings);
Adam Langley95c29f32014-06-20 12:00:00 -0700280 rsa->blindings = new_blindings;
David Benjamind8b65c82015-04-22 16:09:09 -0400281 OPENSSL_free(rsa->blindings_inuse);
Adam Langley95c29f32014-06-20 12:00:00 -0700282 rsa->blindings_inuse = new_blindings_inuse;
283 rsa->num_blindings++;
284
David Benjamin29270de2016-05-24 15:28:36 +0000285 CRYPTO_MUTEX_unlock_write(&rsa->lock);
Adam Langley95c29f32014-06-20 12:00:00 -0700286 return ret;
287
288err2:
289 OPENSSL_free(new_blindings);
290
291err1:
David Benjamin29270de2016-05-24 15:28:36 +0000292 CRYPTO_MUTEX_unlock_write(&rsa->lock);
Adam Langley95c29f32014-06-20 12:00:00 -0700293 BN_BLINDING_free(ret);
294 return NULL;
295}
296
297/* rsa_blinding_release marks the cached BN_BLINDING at the given index as free
298 * for other threads to use. */
299static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
300 unsigned blinding_index) {
301 if (blinding_index == MAX_BLINDINGS_PER_RSA) {
302 /* This blinding wasn't cached. */
303 BN_BLINDING_free(blinding);
304 return;
305 }
306
Adam Langley683d7bd2015-04-13 11:04:14 -0700307 CRYPTO_MUTEX_lock_write(&rsa->lock);
Adam Langley95c29f32014-06-20 12:00:00 -0700308 rsa->blindings_inuse[blinding_index] = 0;
David Benjamin29270de2016-05-24 15:28:36 +0000309 CRYPTO_MUTEX_unlock_write(&rsa->lock);
Adam Langley95c29f32014-06-20 12:00:00 -0700310}
311
312/* signing */
David Benjamind93831d2015-10-29 13:19:12 -0400313int rsa_default_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out,
314 size_t max_out, const uint8_t *in, size_t in_len,
315 int padding) {
Adam Langley95c29f32014-06-20 12:00:00 -0700316 const unsigned rsa_size = RSA_size(rsa);
Adam Langley95c29f32014-06-20 12:00:00 -0700317 uint8_t *buf = NULL;
Adam Langley6887edb2014-06-20 12:00:00 -0700318 int i, ret = 0;
Adam Langley95c29f32014-06-20 12:00:00 -0700319
320 if (max_out < rsa_size) {
David Benjamin3570d732015-06-29 00:28:17 -0400321 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
Adam Langley95c29f32014-06-20 12:00:00 -0700322 return 0;
323 }
324
Adam Langley95c29f32014-06-20 12:00:00 -0700325 buf = OPENSSL_malloc(rsa_size);
Adam Langley6bc658d2014-08-18 13:29:45 -0700326 if (buf == NULL) {
David Benjamin3570d732015-06-29 00:28:17 -0400327 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
Adam Langley95c29f32014-06-20 12:00:00 -0700328 goto err;
329 }
330
331 switch (padding) {
332 case RSA_PKCS1_PADDING:
333 i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
334 break;
335 case RSA_NO_PADDING:
336 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
337 break;
338 default:
David Benjamin3570d732015-06-29 00:28:17 -0400339 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
Adam Langley95c29f32014-06-20 12:00:00 -0700340 goto err;
341 }
Adam Langley6bc658d2014-08-18 13:29:45 -0700342
Adam Langley95c29f32014-06-20 12:00:00 -0700343 if (i <= 0) {
344 goto err;
345 }
346
Adam Langley6bc658d2014-08-18 13:29:45 -0700347 if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
Adam Langley5f5bf6f2015-02-24 13:49:41 -0800348 goto err;
Adam Langley95c29f32014-06-20 12:00:00 -0700349 }
350
351 *out_len = rsa_size;
352 ret = 1;
353
354err:
Adam Langley95c29f32014-06-20 12:00:00 -0700355 if (buf != NULL) {
356 OPENSSL_cleanse(buf, rsa_size);
357 OPENSSL_free(buf);
358 }
Adam Langley95c29f32014-06-20 12:00:00 -0700359
360 return ret;
361}
362
David Benjamind93831d2015-10-29 13:19:12 -0400363int rsa_default_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
364 const uint8_t *in, size_t in_len, int padding) {
Adam Langley95c29f32014-06-20 12:00:00 -0700365 const unsigned rsa_size = RSA_size(rsa);
Adam Langley95c29f32014-06-20 12:00:00 -0700366 int r = -1;
367 uint8_t *buf = NULL;
Adam Langley95c29f32014-06-20 12:00:00 -0700368 int ret = 0;
369
370 if (max_out < rsa_size) {
David Benjamin3570d732015-06-29 00:28:17 -0400371 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
Adam Langley95c29f32014-06-20 12:00:00 -0700372 return 0;
373 }
374
David Benjamin74279b62014-07-24 13:09:19 -0400375 if (padding == RSA_NO_PADDING) {
376 buf = out;
377 } else {
378 /* Allocate a temporary buffer to hold the padded plaintext. */
379 buf = OPENSSL_malloc(rsa_size);
380 if (buf == NULL) {
381 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
382 goto err;
383 }
Adam Langley95c29f32014-06-20 12:00:00 -0700384 }
385
Adam Langley6bc658d2014-08-18 13:29:45 -0700386 if (in_len != rsa_size) {
David Benjamin3570d732015-06-29 00:28:17 -0400387 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
Adam Langley95c29f32014-06-20 12:00:00 -0700388 goto err;
389 }
390
Adam Langley6bc658d2014-08-18 13:29:45 -0700391 if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
Adam Langley6887edb2014-06-20 12:00:00 -0700392 goto err;
393 }
Adam Langley95c29f32014-06-20 12:00:00 -0700394
395 switch (padding) {
396 case RSA_PKCS1_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700397 r = RSA_padding_check_PKCS1_type_2(out, rsa_size, buf, rsa_size);
Adam Langley95c29f32014-06-20 12:00:00 -0700398 break;
399 case RSA_PKCS1_OAEP_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700400 /* Use the default parameters: SHA-1 for both hashes and no label. */
401 r = RSA_padding_check_PKCS1_OAEP_mgf1(out, rsa_size, buf, rsa_size,
402 NULL, 0, NULL, NULL);
Adam Langley95c29f32014-06-20 12:00:00 -0700403 break;
Adam Langley95c29f32014-06-20 12:00:00 -0700404 case RSA_NO_PADDING:
David Benjamin74279b62014-07-24 13:09:19 -0400405 r = rsa_size;
Adam Langley95c29f32014-06-20 12:00:00 -0700406 break;
407 default:
David Benjamin3570d732015-06-29 00:28:17 -0400408 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
Adam Langley95c29f32014-06-20 12:00:00 -0700409 goto err;
410 }
411
412 if (r < 0) {
David Benjamin3570d732015-06-29 00:28:17 -0400413 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
Adam Langley95c29f32014-06-20 12:00:00 -0700414 } else {
415 *out_len = r;
416 ret = 1;
417 }
418
419err:
David Benjamin74279b62014-07-24 13:09:19 -0400420 if (padding != RSA_NO_PADDING && buf != NULL) {
Adam Langley95c29f32014-06-20 12:00:00 -0700421 OPENSSL_cleanse(buf, rsa_size);
422 OPENSSL_free(buf);
423 }
Adam Langley95c29f32014-06-20 12:00:00 -0700424
425 return ret;
426}
427
Brian Smithf08c1c62016-03-25 13:24:46 -1000428static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx);
429
Brian Smithc0b196d2016-03-04 08:54:07 -1000430int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
431 const uint8_t *in, size_t in_len, int padding) {
432 if (rsa->n == NULL || rsa->e == NULL) {
433 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
434 return 0;
435 }
436
Adam Langley95c29f32014-06-20 12:00:00 -0700437 const unsigned rsa_size = RSA_size(rsa);
438 BIGNUM *f, *result;
Adam Langley6887edb2014-06-20 12:00:00 -0700439 int r = -1;
Adam Langley95c29f32014-06-20 12:00:00 -0700440
Adam Langley95c29f32014-06-20 12:00:00 -0700441 if (max_out < rsa_size) {
David Benjamin3570d732015-06-29 00:28:17 -0400442 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
Adam Langley95c29f32014-06-20 12:00:00 -0700443 return 0;
444 }
445
Brian Smith99022622016-03-04 09:20:07 -1000446 if (in_len != rsa_size) {
447 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
448 return 0;
449 }
450
Brian Smith625475f2016-01-12 10:47:25 -1000451 if (!check_modulus_and_exponent_sizes(rsa)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700452 return 0;
453 }
454
Brian Smith2a920312016-03-04 13:42:47 -1000455 BN_CTX *ctx = BN_CTX_new();
Adam Langley95c29f32014-06-20 12:00:00 -0700456 if (ctx == NULL) {
Brian Smith2a920312016-03-04 13:42:47 -1000457 return 0;
Adam Langley95c29f32014-06-20 12:00:00 -0700458 }
459
Brian Smith2a920312016-03-04 13:42:47 -1000460 int ret = 0;
461 uint8_t *buf = NULL;
462
Adam Langley95c29f32014-06-20 12:00:00 -0700463 BN_CTX_start(ctx);
464 f = BN_CTX_get(ctx);
465 result = BN_CTX_get(ctx);
Brian Smith2a920312016-03-04 13:42:47 -1000466 if (f == NULL || result == NULL) {
467 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
468 goto err;
469 }
470
David Benjamin74279b62014-07-24 13:09:19 -0400471 if (padding == RSA_NO_PADDING) {
472 buf = out;
473 } else {
474 /* Allocate a temporary buffer to hold the padded plaintext. */
475 buf = OPENSSL_malloc(rsa_size);
476 if (buf == NULL) {
477 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
478 goto err;
479 }
480 }
Adam Langley95c29f32014-06-20 12:00:00 -0700481
Adam Langley95c29f32014-06-20 12:00:00 -0700482 if (BN_bin2bn(in, in_len, f) == NULL) {
483 goto err;
484 }
485
486 if (BN_ucmp(f, rsa->n) >= 0) {
David Benjamin3570d732015-06-29 00:28:17 -0400487 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
Adam Langley95c29f32014-06-20 12:00:00 -0700488 goto err;
489 }
490
Brian Smithd0357302016-03-25 10:11:04 -1000491 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
Brian Smith24493a42016-03-25 09:12:48 -1000492 !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700493 goto err;
494 }
495
Adam Langley6887edb2014-06-20 12:00:00 -0700496 if (!BN_bn2bin_padded(buf, rsa_size, result)) {
David Benjamin3570d732015-06-29 00:28:17 -0400497 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
Adam Langley6887edb2014-06-20 12:00:00 -0700498 goto err;
499 }
Adam Langley95c29f32014-06-20 12:00:00 -0700500
501 switch (padding) {
502 case RSA_PKCS1_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700503 r = RSA_padding_check_PKCS1_type_1(out, rsa_size, buf, rsa_size);
Adam Langley95c29f32014-06-20 12:00:00 -0700504 break;
505 case RSA_NO_PADDING:
David Benjamin74279b62014-07-24 13:09:19 -0400506 r = rsa_size;
Adam Langley95c29f32014-06-20 12:00:00 -0700507 break;
508 default:
David Benjamin3570d732015-06-29 00:28:17 -0400509 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
Adam Langley95c29f32014-06-20 12:00:00 -0700510 goto err;
511 }
512
513 if (r < 0) {
David Benjamin3570d732015-06-29 00:28:17 -0400514 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
Adam Langley95c29f32014-06-20 12:00:00 -0700515 } else {
516 *out_len = r;
517 ret = 1;
518 }
519
520err:
Brian Smith2a920312016-03-04 13:42:47 -1000521 BN_CTX_end(ctx);
522 BN_CTX_free(ctx);
523 if (buf != out) {
Adam Langley95c29f32014-06-20 12:00:00 -0700524 OPENSSL_free(buf);
525 }
526 return ret;
527}
528
David Benjamind93831d2015-10-29 13:19:12 -0400529int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
530 size_t len) {
Adam Langley6bc658d2014-08-18 13:29:45 -0700531 BIGNUM *f, *result;
532 BN_CTX *ctx = NULL;
533 unsigned blinding_index = 0;
534 BN_BLINDING *blinding = NULL;
535 int ret = 0;
536
537 ctx = BN_CTX_new();
538 if (ctx == NULL) {
539 goto err;
540 }
541 BN_CTX_start(ctx);
542 f = BN_CTX_get(ctx);
543 result = BN_CTX_get(ctx);
544
545 if (f == NULL || result == NULL) {
David Benjamin3570d732015-06-29 00:28:17 -0400546 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
Adam Langley6bc658d2014-08-18 13:29:45 -0700547 goto err;
548 }
549
550 if (BN_bin2bn(in, len, f) == NULL) {
551 goto err;
552 }
553
554 if (BN_ucmp(f, rsa->n) >= 0) {
555 /* Usually the padding functions would catch this. */
David Benjamin3570d732015-06-29 00:28:17 -0400556 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
Adam Langley6bc658d2014-08-18 13:29:45 -0700557 goto err;
558 }
559
Brian Smith86080c32016-03-25 12:23:16 -1000560 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) {
561 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
562 goto err;
563 }
564
Brian Smith598e55a2016-03-26 20:17:37 -1000565 /* We cannot do blinding or verification without |e|, and continuing without
566 * those countermeasures is dangerous. However, the Java/Android RSA API
567 * requires support for keys where only |d| and |n| (and not |e|) are known.
568 * The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|. */
569 int disable_security = (rsa->flags & RSA_FLAG_NO_BLINDING) && rsa->e == NULL;
570
571 if (!disable_security) {
Brian Smith86361a32016-03-26 19:42:31 -1000572 /* Keys without public exponents must have blinding explicitly disabled to
573 * be used. */
574 if (rsa->e == NULL) {
575 OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);
576 goto err;
577 }
578
Adam Langley6bc658d2014-08-18 13:29:45 -0700579 blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
580 if (blinding == NULL) {
David Benjamin3570d732015-06-29 00:28:17 -0400581 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
Adam Langley6bc658d2014-08-18 13:29:45 -0700582 goto err;
583 }
Brian Smith86361a32016-03-26 19:42:31 -1000584 if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {
Adam Langley6bc658d2014-08-18 13:29:45 -0700585 goto err;
586 }
587 }
588
Brian Smith51b0d5b2016-03-25 13:15:39 -1000589 if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&
590 rsa->dmq1 != NULL && rsa->iqmp != NULL) {
Brian Smithf08c1c62016-03-25 13:24:46 -1000591 if (!mod_exp(result, f, rsa, ctx)) {
Adam Langley6bc658d2014-08-18 13:29:45 -0700592 goto err;
593 }
Brian Smith9f05de42016-08-02 18:21:18 -1000594 } else if (!BN_mod_exp_mont_consttime(result, f, rsa->d, rsa->n, ctx,
595 rsa->mont_n)) {
596 goto err;
Brian Smith86080c32016-03-25 12:23:16 -1000597 }
598
599 /* Verify the result to protect against fault attacks as described in the
600 * 1997 paper "On the Importance of Checking Cryptographic Protocols for
601 * Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some
602 * implementations do this only when the CRT is used, but we do it in all
603 * cases. Section 6 of the aforementioned paper describes an attack that
604 * works when the CRT isn't used. That attack is much less likely to succeed
605 * than the CRT attack, but there have likely been improvements since 1997.
606 *
Brian Smith598e55a2016-03-26 20:17:37 -1000607 * This check is cheap assuming |e| is small; it almost always is. */
608 if (!disable_security) {
Brian Smith86080c32016-03-25 12:23:16 -1000609 BIGNUM *vrfy = BN_CTX_get(ctx);
610 if (vrfy == NULL ||
611 !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||
612 !BN_equal_consttime(vrfy, f)) {
613 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
Adam Langley6bc658d2014-08-18 13:29:45 -0700614 goto err;
615 }
Adam Langley6bc658d2014-08-18 13:29:45 -0700616
Brian Smith3426d102016-03-17 16:10:04 -1000617 if (!BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {
Adam Langley6bc658d2014-08-18 13:29:45 -0700618 goto err;
619 }
620 }
621
622 if (!BN_bn2bin_padded(out, len, result)) {
David Benjamin3570d732015-06-29 00:28:17 -0400623 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
Adam Langley6bc658d2014-08-18 13:29:45 -0700624 goto err;
625 }
626
627 ret = 1;
628
629err:
630 if (ctx != NULL) {
631 BN_CTX_end(ctx);
632 BN_CTX_free(ctx);
633 }
634 if (blinding != NULL) {
635 rsa_blinding_release(rsa, blinding, blinding_index);
636 }
637
638 return ret;
639}
640
Adam Langley95c29f32014-06-20 12:00:00 -0700641static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
Brian Smithf08c1c62016-03-25 13:24:46 -1000642 assert(ctx != NULL);
643
Brian Smith51b0d5b2016-03-25 13:15:39 -1000644 assert(rsa->n != NULL);
645 assert(rsa->e != NULL);
646 assert(rsa->d != NULL);
647 assert(rsa->p != NULL);
648 assert(rsa->q != NULL);
649 assert(rsa->dmp1 != NULL);
650 assert(rsa->dmq1 != NULL);
651 assert(rsa->iqmp != NULL);
652
Adam Langley95c29f32014-06-20 12:00:00 -0700653 BIGNUM *r1, *m1, *vrfy;
Adam Langley95c29f32014-06-20 12:00:00 -0700654 int ret = 0;
Adam Langley839b8812015-05-26 11:36:46 -0700655 size_t i, num_additional_primes = 0;
656
657 if (rsa->additional_primes != NULL) {
658 num_additional_primes = sk_RSA_additional_prime_num(rsa->additional_primes);
659 }
Adam Langley95c29f32014-06-20 12:00:00 -0700660
661 BN_CTX_start(ctx);
662 r1 = BN_CTX_get(ctx);
663 m1 = BN_CTX_get(ctx);
664 vrfy = BN_CTX_get(ctx);
Brian Smith7cf60852016-03-19 22:39:37 -1000665 if (r1 == NULL ||
666 m1 == NULL ||
667 vrfy == NULL) {
668 goto err;
669 }
Adam Langley95c29f32014-06-20 12:00:00 -0700670
Brian Smith9f05de42016-08-02 18:21:18 -1000671 if (!BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, rsa->p, ctx) ||
672 !BN_MONT_CTX_set_locked(&rsa->mont_q, &rsa->lock, rsa->q, ctx)) {
673 goto err;
Adam Langley95c29f32014-06-20 12:00:00 -0700674 }
675
Brian Smithd0357302016-03-25 10:11:04 -1000676 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) {
Brian Smith24493a42016-03-25 09:12:48 -1000677 goto err;
Adam Langley95c29f32014-06-20 12:00:00 -0700678 }
679
680 /* compute I mod q */
Brian Smith9f05de42016-08-02 18:21:18 -1000681 if (!BN_mod(r1, I, rsa->q, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700682 goto err;
683 }
684
685 /* compute r1^dmq1 mod q */
Brian Smith9f05de42016-08-02 18:21:18 -1000686 if (!BN_mod_exp_mont_consttime(m1, r1, rsa->dmq1, rsa->q, ctx, rsa->mont_q)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700687 goto err;
688 }
689
690 /* compute I mod p */
Brian Smith9f05de42016-08-02 18:21:18 -1000691 if (!BN_mod(r1, I, rsa->p, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700692 goto err;
693 }
694
695 /* compute r1^dmp1 mod p */
Brian Smith9f05de42016-08-02 18:21:18 -1000696 if (!BN_mod_exp_mont_consttime(r0, r1, rsa->dmp1, rsa->p, ctx, rsa->mont_p)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700697 goto err;
698 }
699
700 if (!BN_sub(r0, r0, m1)) {
701 goto err;
702 }
703 /* This will help stop the size of r0 increasing, which does
704 * affect the multiply if it optimised for a power of 2 size */
705 if (BN_is_negative(r0)) {
706 if (!BN_add(r0, r0, rsa->p)) {
707 goto err;
708 }
709 }
710
711 if (!BN_mul(r1, r0, rsa->iqmp, ctx)) {
712 goto err;
713 }
714
Brian Smith9f05de42016-08-02 18:21:18 -1000715 if (!BN_mod(r0, r1, rsa->p, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700716 goto err;
717 }
718
719 /* If p < q it is occasionally possible for the correction of
720 * adding 'p' if r0 is negative above to leave the result still
721 * negative. This can break the private key operations: the following
722 * second correction should *always* correct this rare occurrence.
723 * This will *never* happen with OpenSSL generated keys because
724 * they ensure p > q [steve] */
725 if (BN_is_negative(r0)) {
726 if (!BN_add(r0, r0, rsa->p)) {
727 goto err;
728 }
729 }
730 if (!BN_mul(r1, r0, rsa->q, ctx)) {
731 goto err;
732 }
733 if (!BN_add(r0, r1, m1)) {
734 goto err;
735 }
736
Adam Langley839b8812015-05-26 11:36:46 -0700737 for (i = 0; i < num_additional_primes; i++) {
738 /* multi-prime RSA. */
Adam Langley839b8812015-05-26 11:36:46 -0700739 RSA_additional_prime *ap =
740 sk_RSA_additional_prime_value(rsa->additional_primes, i);
741
Adam Langley839b8812015-05-26 11:36:46 -0700742 /* c will already point to a BIGNUM with the correct flags. */
Brian Smith9f05de42016-08-02 18:21:18 -1000743 if (!BN_mod(r1, I, ap->prime, ctx)) {
Adam Langley839b8812015-05-26 11:36:46 -0700744 goto err;
745 }
746
Brian Smith9f05de42016-08-02 18:21:18 -1000747 if (!BN_MONT_CTX_set_locked(&ap->mont, &rsa->lock, ap->prime, ctx) ||
748 !BN_mod_exp_mont_consttime(m1, r1, ap->exp, ap->prime, ctx, ap->mont)) {
Adam Langley839b8812015-05-26 11:36:46 -0700749 goto err;
750 }
751
Adam Langley839b8812015-05-26 11:36:46 -0700752 if (!BN_sub(m1, m1, r0) ||
753 !BN_mul(m1, m1, ap->coeff, ctx) ||
Brian Smith9f05de42016-08-02 18:21:18 -1000754 !BN_mod(m1, m1, ap->prime, ctx) ||
755 (BN_is_negative(m1) && !BN_add(m1, m1, ap->prime)) ||
Adam Langley839b8812015-05-26 11:36:46 -0700756 !BN_mul(m1, m1, ap->r, ctx) ||
757 !BN_add(r0, r0, m1)) {
758 goto err;
759 }
760 }
761
Adam Langley95c29f32014-06-20 12:00:00 -0700762 ret = 1;
763
764err:
765 BN_CTX_end(ctx);
766 return ret;
767}
768
David Benjamind93831d2015-10-29 13:19:12 -0400769int rsa_default_multi_prime_keygen(RSA *rsa, int bits, int num_primes,
770 BIGNUM *e_value, BN_GENCB *cb) {
Adam Langley95c29f32014-06-20 12:00:00 -0700771 BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;
Brian Smith9f05de42016-08-02 18:21:18 -1000772 BIGNUM local_r0, local_p;
773 BIGNUM *pr0, *p;
Adam Langley839b8812015-05-26 11:36:46 -0700774 int prime_bits, ok = -1, n = 0, i, j;
Adam Langley95c29f32014-06-20 12:00:00 -0700775 BN_CTX *ctx = NULL;
Adam Langley839b8812015-05-26 11:36:46 -0700776 STACK_OF(RSA_additional_prime) *additional_primes = NULL;
777
778 if (num_primes < 2) {
779 ok = 0; /* we set our own err */
David Benjamin3570d732015-06-29 00:28:17 -0400780 OPENSSL_PUT_ERROR(RSA, RSA_R_MUST_HAVE_AT_LEAST_TWO_PRIMES);
Adam Langley839b8812015-05-26 11:36:46 -0700781 goto err;
782 }
Adam Langley95c29f32014-06-20 12:00:00 -0700783
784 ctx = BN_CTX_new();
785 if (ctx == NULL) {
786 goto err;
787 }
788 BN_CTX_start(ctx);
789 r0 = BN_CTX_get(ctx);
790 r1 = BN_CTX_get(ctx);
791 r2 = BN_CTX_get(ctx);
792 r3 = BN_CTX_get(ctx);
Brian Smithf4bbc2a2015-08-06 10:42:27 -0400793 if (r0 == NULL || r1 == NULL || r2 == NULL || r3 == NULL) {
Adam Langley95c29f32014-06-20 12:00:00 -0700794 goto err;
795 }
796
Adam Langley839b8812015-05-26 11:36:46 -0700797 if (num_primes > 2) {
798 additional_primes = sk_RSA_additional_prime_new_null();
799 if (additional_primes == NULL) {
800 goto err;
801 }
802 }
803
804 for (i = 2; i < num_primes; i++) {
805 RSA_additional_prime *ap = OPENSSL_malloc(sizeof(RSA_additional_prime));
806 if (ap == NULL) {
807 goto err;
808 }
David Benjamin17cf2cb2016-12-13 01:07:13 -0500809 OPENSSL_memset(ap, 0, sizeof(RSA_additional_prime));
Adam Langley839b8812015-05-26 11:36:46 -0700810 ap->prime = BN_new();
811 ap->exp = BN_new();
812 ap->coeff = BN_new();
813 ap->r = BN_new();
814 if (ap->prime == NULL ||
815 ap->exp == NULL ||
816 ap->coeff == NULL ||
817 ap->r == NULL ||
818 !sk_RSA_additional_prime_push(additional_primes, ap)) {
819 RSA_additional_prime_free(ap);
820 goto err;
821 }
822 }
Adam Langley95c29f32014-06-20 12:00:00 -0700823
824 /* We need the RSA components non-NULL */
David Benjamin6eb000d2015-02-11 01:17:41 -0500825 if (!rsa->n && ((rsa->n = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700826 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500827 }
828 if (!rsa->d && ((rsa->d = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700829 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500830 }
831 if (!rsa->e && ((rsa->e = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700832 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500833 }
834 if (!rsa->p && ((rsa->p = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700835 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500836 }
837 if (!rsa->q && ((rsa->q = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700838 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500839 }
840 if (!rsa->dmp1 && ((rsa->dmp1 = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700841 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500842 }
843 if (!rsa->dmq1 && ((rsa->dmq1 = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700844 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500845 }
846 if (!rsa->iqmp && ((rsa->iqmp = BN_new()) == NULL)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700847 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500848 }
Adam Langley95c29f32014-06-20 12:00:00 -0700849
David Benjamin1c703cb2015-06-11 21:42:14 -0400850 if (!BN_copy(rsa->e, e_value)) {
851 goto err;
852 }
Adam Langley95c29f32014-06-20 12:00:00 -0700853
854 /* generate p and q */
Adam Langley839b8812015-05-26 11:36:46 -0700855 prime_bits = (bits + (num_primes - 1)) / num_primes;
Adam Langley95c29f32014-06-20 12:00:00 -0700856 for (;;) {
Adam Langley839b8812015-05-26 11:36:46 -0700857 if (!BN_generate_prime_ex(rsa->p, prime_bits, 0, NULL, NULL, cb) ||
David Benjamin6eb000d2015-02-11 01:17:41 -0500858 !BN_sub(r2, rsa->p, BN_value_one()) ||
859 !BN_gcd(r1, r2, rsa->e, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700860 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500861 }
862 if (BN_is_one(r1)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700863 break;
David Benjamin6eb000d2015-02-11 01:17:41 -0500864 }
865 if (!BN_GENCB_call(cb, 2, n++)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700866 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500867 }
Adam Langley95c29f32014-06-20 12:00:00 -0700868 }
David Benjamin6eb000d2015-02-11 01:17:41 -0500869 if (!BN_GENCB_call(cb, 3, 0)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700870 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500871 }
Adam Langley839b8812015-05-26 11:36:46 -0700872 prime_bits = ((bits - prime_bits) + (num_primes - 2)) / (num_primes - 1);
Adam Langley95c29f32014-06-20 12:00:00 -0700873 for (;;) {
874 /* When generating ridiculously small keys, we can get stuck
875 * continually regenerating the same prime values. Check for
876 * this and bail if it happens 3 times. */
877 unsigned int degenerate = 0;
878 do {
Adam Langley839b8812015-05-26 11:36:46 -0700879 if (!BN_generate_prime_ex(rsa->q, prime_bits, 0, NULL, NULL, cb)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700880 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500881 }
Adam Langley95c29f32014-06-20 12:00:00 -0700882 } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
883 if (degenerate == 3) {
884 ok = 0; /* we set our own err */
David Benjamin3570d732015-06-29 00:28:17 -0400885 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
Adam Langley95c29f32014-06-20 12:00:00 -0700886 goto err;
887 }
David Benjamin6eb000d2015-02-11 01:17:41 -0500888 if (!BN_sub(r2, rsa->q, BN_value_one()) ||
889 !BN_gcd(r1, r2, rsa->e, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700890 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500891 }
892 if (BN_is_one(r1)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700893 break;
David Benjamin6eb000d2015-02-11 01:17:41 -0500894 }
895 if (!BN_GENCB_call(cb, 2, n++)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700896 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500897 }
Adam Langley95c29f32014-06-20 12:00:00 -0700898 }
Adam Langley839b8812015-05-26 11:36:46 -0700899
900 if (!BN_GENCB_call(cb, 3, 1) ||
901 !BN_mul(rsa->n, rsa->p, rsa->q, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700902 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -0500903 }
Adam Langley839b8812015-05-26 11:36:46 -0700904
905 for (i = 2; i < num_primes; i++) {
906 RSA_additional_prime *ap =
907 sk_RSA_additional_prime_value(additional_primes, i - 2);
908 prime_bits = ((bits - BN_num_bits(rsa->n)) + (num_primes - (i + 1))) /
909 (num_primes - i);
910
911 for (;;) {
912 if (!BN_generate_prime_ex(ap->prime, prime_bits, 0, NULL, NULL, cb)) {
913 goto err;
914 }
915 if (BN_cmp(rsa->p, ap->prime) == 0 ||
916 BN_cmp(rsa->q, ap->prime) == 0) {
917 continue;
918 }
919
920 for (j = 0; j < i - 2; j++) {
921 if (BN_cmp(sk_RSA_additional_prime_value(additional_primes, j)->prime,
922 ap->prime) == 0) {
923 break;
924 }
925 }
926 if (j != i - 2) {
927 continue;
928 }
929
930 if (!BN_sub(r2, ap->prime, BN_value_one()) ||
931 !BN_gcd(r1, r2, rsa->e, ctx)) {
932 goto err;
933 }
934
935 if (!BN_is_one(r1)) {
936 continue;
937 }
938 if (i != num_primes - 1) {
939 break;
940 }
941
942 /* For the last prime we'll check that it makes n large enough. In the
943 * two prime case this isn't a problem because we generate primes with
944 * the top two bits set and so the product is always of the expected
945 * size. In the multi prime case, this doesn't follow. */
946 if (!BN_mul(r1, rsa->n, ap->prime, ctx)) {
947 goto err;
948 }
Adam Langley96c2a282015-06-02 14:16:44 -0700949 if (BN_num_bits(r1) == (unsigned) bits) {
Adam Langley839b8812015-05-26 11:36:46 -0700950 break;
951 }
952
953 if (!BN_GENCB_call(cb, 2, n++)) {
954 goto err;
955 }
956 }
957
958 /* ap->r is is the product of all the primes prior to the current one
959 * (including p and q). */
960 if (!BN_copy(ap->r, rsa->n)) {
961 goto err;
962 }
963 if (i == num_primes - 1) {
964 /* In the case of the last prime, we calculated n as |r1| in the loop
965 * above. */
966 if (!BN_copy(rsa->n, r1)) {
967 goto err;
968 }
969 } else if (!BN_mul(rsa->n, rsa->n, ap->prime, ctx)) {
970 goto err;
971 }
972
973 if (!BN_GENCB_call(cb, 3, 1)) {
974 goto err;
975 }
976 }
977
Adam Langley95c29f32014-06-20 12:00:00 -0700978 if (BN_cmp(rsa->p, rsa->q) < 0) {
979 tmp = rsa->p;
980 rsa->p = rsa->q;
981 rsa->q = tmp;
982 }
983
Adam Langley95c29f32014-06-20 12:00:00 -0700984 /* calculate d */
David Benjamin6eb000d2015-02-11 01:17:41 -0500985 if (!BN_sub(r1, rsa->p, BN_value_one())) {
Adam Langley95c29f32014-06-20 12:00:00 -0700986 goto err; /* p-1 */
David Benjamin6eb000d2015-02-11 01:17:41 -0500987 }
988 if (!BN_sub(r2, rsa->q, BN_value_one())) {
Adam Langley95c29f32014-06-20 12:00:00 -0700989 goto err; /* q-1 */
David Benjamin6eb000d2015-02-11 01:17:41 -0500990 }
991 if (!BN_mul(r0, r1, r2, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700992 goto err; /* (p-1)(q-1) */
David Benjamin6eb000d2015-02-11 01:17:41 -0500993 }
Adam Langley839b8812015-05-26 11:36:46 -0700994 for (i = 2; i < num_primes; i++) {
995 RSA_additional_prime *ap =
996 sk_RSA_additional_prime_value(additional_primes, i - 2);
997 if (!BN_sub(r3, ap->prime, BN_value_one()) ||
998 !BN_mul(r0, r0, r3, ctx)) {
999 goto err;
1000 }
1001 }
Adam Langley95c29f32014-06-20 12:00:00 -07001002 pr0 = &local_r0;
1003 BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
David Benjamin6eb000d2015-02-11 01:17:41 -05001004 if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -07001005 goto err; /* d */
David Benjamin6eb000d2015-02-11 01:17:41 -05001006 }
Adam Langley95c29f32014-06-20 12:00:00 -07001007
Adam Langley95c29f32014-06-20 12:00:00 -07001008 /* calculate d mod (p-1) */
Brian Smith9f05de42016-08-02 18:21:18 -10001009 if (!BN_mod(rsa->dmp1, rsa->d, r1, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -07001010 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -05001011 }
Adam Langley95c29f32014-06-20 12:00:00 -07001012
1013 /* calculate d mod (q-1) */
Brian Smith9f05de42016-08-02 18:21:18 -10001014 if (!BN_mod(rsa->dmq1, rsa->d, r2, ctx)) {
Adam Langley95c29f32014-06-20 12:00:00 -07001015 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -05001016 }
Adam Langley95c29f32014-06-20 12:00:00 -07001017
David Benjamin0b8dc302016-12-17 14:27:16 -05001018 /* Calculate inverse of q mod p. Note that although RSA key generation is far
1019 * from constant-time, |bn_mod_inverse_secret_prime| uses the same modular
1020 * exponentation logic as in RSA private key operations and, if the RSAZ-1024
1021 * code is enabled, will be optimized for common RSA prime sizes. */
Adam Langley95c29f32014-06-20 12:00:00 -07001022 p = &local_p;
1023 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
David Benjamin0b8dc302016-12-17 14:27:16 -05001024 if (!BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, rsa->p, ctx) ||
1025 !bn_mod_inverse_secret_prime(rsa->iqmp, rsa->q, p, ctx, rsa->mont_p)) {
Adam Langley95c29f32014-06-20 12:00:00 -07001026 goto err;
David Benjamin6eb000d2015-02-11 01:17:41 -05001027 }
Adam Langley95c29f32014-06-20 12:00:00 -07001028
Adam Langley839b8812015-05-26 11:36:46 -07001029 for (i = 2; i < num_primes; i++) {
1030 RSA_additional_prime *ap =
1031 sk_RSA_additional_prime_value(additional_primes, i - 2);
1032 if (!BN_sub(ap->exp, ap->prime, BN_value_one()) ||
1033 !BN_mod(ap->exp, rsa->d, ap->exp, ctx) ||
David Benjamin0b8dc302016-12-17 14:27:16 -05001034 !BN_MONT_CTX_set_locked(&ap->mont, &rsa->lock, ap->prime, ctx) ||
1035 !bn_mod_inverse_secret_prime(ap->coeff, ap->r, ap->prime, ctx,
1036 ap->mont)) {
Adam Langley839b8812015-05-26 11:36:46 -07001037 goto err;
1038 }
1039 }
1040
Adam Langley839b8812015-05-26 11:36:46 -07001041 rsa->additional_primes = additional_primes;
1042 additional_primes = NULL;
Adam Langley95c29f32014-06-20 12:00:00 -07001043
Brian Smithfebf7712016-03-21 13:47:32 -10001044 /* The key generation process is complex and thus error-prone. It could be
1045 * disastrous to generate and then use a bad key so double-check that the key
1046 * makes sense. */
1047 ok = RSA_check_key(rsa);
1048 if (!ok) {
1049 OPENSSL_PUT_ERROR(RSA, RSA_R_INTERNAL_ERROR);
1050 }
1051
Adam Langley95c29f32014-06-20 12:00:00 -07001052err:
1053 if (ok == -1) {
David Benjamin3570d732015-06-29 00:28:17 -04001054 OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
Adam Langley95c29f32014-06-20 12:00:00 -07001055 ok = 0;
1056 }
1057 if (ctx != NULL) {
1058 BN_CTX_end(ctx);
1059 BN_CTX_free(ctx);
1060 }
Adam Langley839b8812015-05-26 11:36:46 -07001061 sk_RSA_additional_prime_pop_free(additional_primes,
1062 RSA_additional_prime_free);
Adam Langley95c29f32014-06-20 12:00:00 -07001063 return ok;
1064}
1065
David Benjamind93831d2015-10-29 13:19:12 -04001066int rsa_default_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
1067 return rsa_default_multi_prime_keygen(rsa, bits, 2 /* num primes */, e_value,
1068 cb);
Adam Langley839b8812015-05-26 11:36:46 -07001069}
1070
Brian Smithf08c1c62016-03-25 13:24:46 -10001071/* All of the methods are NULL to make it easier for the compiler/linker to drop
1072 * unused functions. The wrapper functions will select the appropriate
1073 * |rsa_default_*| implementation. */
David Benjamind93831d2015-10-29 13:19:12 -04001074const RSA_METHOD RSA_default_method = {
Adam Langley95c29f32014-06-20 12:00:00 -07001075 {
1076 0 /* references */,
1077 1 /* is_static */,
1078 },
1079 NULL /* app_data */,
1080
1081 NULL /* init */,
David Benjamind93831d2015-10-29 13:19:12 -04001082 NULL /* finish (defaults to rsa_default_finish) */,
Adam Langley95c29f32014-06-20 12:00:00 -07001083
David Benjamind93831d2015-10-29 13:19:12 -04001084 NULL /* size (defaults to rsa_default_size) */,
David Benjamin925fee32014-07-11 14:14:08 -04001085
Adam Langley95c29f32014-06-20 12:00:00 -07001086 NULL /* sign */,
1087 NULL /* verify */,
1088
David Benjamind93831d2015-10-29 13:19:12 -04001089 NULL /* encrypt (defaults to rsa_default_encrypt) */,
1090 NULL /* sign_raw (defaults to rsa_default_sign_raw) */,
1091 NULL /* decrypt (defaults to rsa_default_decrypt) */,
1092 NULL /* verify_raw (defaults to rsa_default_verify_raw) */,
Adam Langley95c29f32014-06-20 12:00:00 -07001093
David Benjamind93831d2015-10-29 13:19:12 -04001094 NULL /* private_transform (defaults to rsa_default_private_transform) */,
Adam Langley6bc658d2014-08-18 13:29:45 -07001095
Brian Smithf08c1c62016-03-25 13:24:46 -10001096 NULL /* mod_exp (ignored) */,
1097 NULL /* bn_mod_exp (ignored) */,
Adam Langley95c29f32014-06-20 12:00:00 -07001098
1099 RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,
1100
David Benjamind93831d2015-10-29 13:19:12 -04001101 NULL /* keygen (defaults to rsa_default_keygen) */,
1102 NULL /* multi_prime_keygen (defaults to rsa_default_multi_prime_keygen) */,
Adam Langley626c6862015-09-11 16:17:44 -07001103
1104 NULL /* supports_digest */,
Adam Langley95c29f32014-06-20 12:00:00 -07001105};