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 <string.h>
60
61 #include <openssl/bn.h>
62 #include <openssl/err.h>
63 #include <openssl/mem.h>
64 #include <openssl/thread.h>
65
66 #include "internal.h"
67 #include "../internal.h"
68
69
70 #define OPENSSL_RSA_MAX_MODULUS_BITS 16384
71 #define OPENSSL_RSA_SMALL_MODULUS_BITS 3072
72 #define OPENSSL_RSA_MAX_PUBEXP_BITS \
73 64 /* exponent limit enforced for "large" modulus only */
74
75
finish(RSA * rsa)76 static int finish(RSA *rsa) {
77 BN_MONT_CTX_free(rsa->_method_mod_n);
78 BN_MONT_CTX_free(rsa->_method_mod_p);
79 BN_MONT_CTX_free(rsa->_method_mod_q);
80
81 return 1;
82 }
83
size(const RSA * rsa)84 static size_t size(const RSA *rsa) {
85 return BN_num_bytes(rsa->n);
86 }
87
encrypt(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)88 static int encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
89 const uint8_t *in, size_t in_len, int padding) {
90 const unsigned rsa_size = RSA_size(rsa);
91 BIGNUM *f, *result;
92 uint8_t *buf = NULL;
93 BN_CTX *ctx = NULL;
94 int i, ret = 0;
95
96 if (rsa_size > OPENSSL_RSA_MAX_MODULUS_BITS) {
97 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_MODULUS_TOO_LARGE);
98 return 0;
99 }
100
101 if (max_out < rsa_size) {
102 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
103 return 0;
104 }
105
106 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
107 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_BAD_E_VALUE);
108 return 0;
109 }
110
111 /* for large moduli, enforce exponent limit */
112 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
113 BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
114 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_BAD_E_VALUE);
115 return 0;
116 }
117
118 ctx = BN_CTX_new();
119 if (ctx == NULL) {
120 goto err;
121 }
122
123 BN_CTX_start(ctx);
124 f = BN_CTX_get(ctx);
125 result = BN_CTX_get(ctx);
126 buf = OPENSSL_malloc(rsa_size);
127 if (!f || !result || !buf) {
128 OPENSSL_PUT_ERROR(RSA, encrypt, ERR_R_MALLOC_FAILURE);
129 goto err;
130 }
131
132 switch (padding) {
133 case RSA_PKCS1_PADDING:
134 i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
135 break;
136 case RSA_PKCS1_OAEP_PADDING:
137 /* Use the default parameters: SHA-1 for both hashes and no label. */
138 i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
139 NULL, 0, NULL, NULL);
140 break;
141 case RSA_NO_PADDING:
142 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
143 break;
144 default:
145 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_UNKNOWN_PADDING_TYPE);
146 goto err;
147 }
148
149 if (i <= 0) {
150 goto err;
151 }
152
153 if (BN_bin2bn(buf, rsa_size, f) == NULL) {
154 goto err;
155 }
156
157 if (BN_ucmp(f, rsa->n) >= 0) {
158 /* usually the padding functions would catch this */
159 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
160 goto err;
161 }
162
163 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
164 if (BN_MONT_CTX_set_locked(&rsa->_method_mod_n, &rsa->lock, rsa->n, ctx) ==
165 NULL) {
166 goto err;
167 }
168 }
169
170 if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx,
171 rsa->_method_mod_n)) {
172 goto err;
173 }
174
175 /* put in leading 0 bytes if the number is less than the length of the
176 * modulus */
177 if (!BN_bn2bin_padded(out, rsa_size, result)) {
178 OPENSSL_PUT_ERROR(RSA, encrypt, ERR_R_INTERNAL_ERROR);
179 goto err;
180 }
181
182 *out_len = rsa_size;
183 ret = 1;
184
185 err:
186 if (ctx != NULL) {
187 BN_CTX_end(ctx);
188 BN_CTX_free(ctx);
189 }
190 if (buf != NULL) {
191 OPENSSL_cleanse(buf, rsa_size);
192 OPENSSL_free(buf);
193 }
194
195 return ret;
196 }
197
198 /* MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
199 * RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
200 * destroyed as needed. */
201 #define MAX_BLINDINGS_PER_RSA 1024
202
203 /* rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
204 * allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
205 * none are free, the cache will be extended by a extra element and the new
206 * BN_BLINDING is returned.
207 *
208 * On success, the index of the assigned BN_BLINDING is written to
209 * |*index_used| and must be passed to |rsa_blinding_release| when finished. */
rsa_blinding_get(RSA * rsa,unsigned * index_used,BN_CTX * ctx)210 static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
211 BN_CTX *ctx) {
212 BN_BLINDING *ret = NULL;
213 BN_BLINDING **new_blindings;
214 uint8_t *new_blindings_inuse;
215 char overflow = 0;
216
217 CRYPTO_MUTEX_lock_write(&rsa->lock);
218
219 unsigned i;
220 for (i = 0; i < rsa->num_blindings; i++) {
221 if (rsa->blindings_inuse[i] == 0) {
222 rsa->blindings_inuse[i] = 1;
223 ret = rsa->blindings[i];
224 *index_used = i;
225 break;
226 }
227 }
228
229 if (ret != NULL) {
230 CRYPTO_MUTEX_unlock(&rsa->lock);
231 return ret;
232 }
233
234 overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA;
235
236 /* We didn't find a free BN_BLINDING to use so increase the length of
237 * the arrays by one and use the newly created element. */
238
239 CRYPTO_MUTEX_unlock(&rsa->lock);
240 ret = rsa_setup_blinding(rsa, ctx);
241 if (ret == NULL) {
242 return NULL;
243 }
244
245 if (overflow) {
246 /* We cannot add any more cached BN_BLINDINGs so we use |ret|
247 * and mark it for destruction in |rsa_blinding_release|. */
248 *index_used = MAX_BLINDINGS_PER_RSA;
249 return ret;
250 }
251
252 CRYPTO_MUTEX_lock_write(&rsa->lock);
253
254 new_blindings =
255 OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1));
256 if (new_blindings == NULL) {
257 goto err1;
258 }
259 memcpy(new_blindings, rsa->blindings,
260 sizeof(BN_BLINDING *) * rsa->num_blindings);
261 new_blindings[rsa->num_blindings] = ret;
262
263 new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1);
264 if (new_blindings_inuse == NULL) {
265 goto err2;
266 }
267 memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
268 new_blindings_inuse[rsa->num_blindings] = 1;
269 *index_used = rsa->num_blindings;
270
271 OPENSSL_free(rsa->blindings);
272 rsa->blindings = new_blindings;
273 OPENSSL_free(rsa->blindings_inuse);
274 rsa->blindings_inuse = new_blindings_inuse;
275 rsa->num_blindings++;
276
277 CRYPTO_MUTEX_unlock(&rsa->lock);
278 return ret;
279
280 err2:
281 OPENSSL_free(new_blindings);
282
283 err1:
284 CRYPTO_MUTEX_unlock(&rsa->lock);
285 BN_BLINDING_free(ret);
286 return NULL;
287 }
288
289 /* rsa_blinding_release marks the cached BN_BLINDING at the given index as free
290 * for other threads to use. */
rsa_blinding_release(RSA * rsa,BN_BLINDING * blinding,unsigned blinding_index)291 static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
292 unsigned blinding_index) {
293 if (blinding_index == MAX_BLINDINGS_PER_RSA) {
294 /* This blinding wasn't cached. */
295 BN_BLINDING_free(blinding);
296 return;
297 }
298
299 CRYPTO_MUTEX_lock_write(&rsa->lock);
300 rsa->blindings_inuse[blinding_index] = 0;
301 CRYPTO_MUTEX_unlock(&rsa->lock);
302 }
303
304 /* signing */
sign_raw(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)305 static int sign_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
306 const uint8_t *in, size_t in_len, int padding) {
307 const unsigned rsa_size = RSA_size(rsa);
308 uint8_t *buf = NULL;
309 int i, ret = 0;
310
311 if (max_out < rsa_size) {
312 OPENSSL_PUT_ERROR(RSA, sign_raw, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
313 return 0;
314 }
315
316 buf = OPENSSL_malloc(rsa_size);
317 if (buf == NULL) {
318 OPENSSL_PUT_ERROR(RSA, sign_raw, ERR_R_MALLOC_FAILURE);
319 goto err;
320 }
321
322 switch (padding) {
323 case RSA_PKCS1_PADDING:
324 i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
325 break;
326 case RSA_NO_PADDING:
327 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
328 break;
329 default:
330 OPENSSL_PUT_ERROR(RSA, sign_raw, RSA_R_UNKNOWN_PADDING_TYPE);
331 goto err;
332 }
333
334 if (i <= 0) {
335 goto err;
336 }
337
338 if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
339 goto err;
340 }
341
342 *out_len = rsa_size;
343 ret = 1;
344
345 err:
346 if (buf != NULL) {
347 OPENSSL_cleanse(buf, rsa_size);
348 OPENSSL_free(buf);
349 }
350
351 return ret;
352 }
353
decrypt(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)354 static int decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
355 const uint8_t *in, size_t in_len, int padding) {
356 const unsigned rsa_size = RSA_size(rsa);
357 int r = -1;
358 uint8_t *buf = NULL;
359 int ret = 0;
360
361 if (max_out < rsa_size) {
362 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
363 return 0;
364 }
365
366 buf = OPENSSL_malloc(rsa_size);
367 if (buf == NULL) {
368 OPENSSL_PUT_ERROR(RSA, decrypt, ERR_R_MALLOC_FAILURE);
369 goto err;
370 }
371
372 if (in_len != rsa_size) {
373 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
374 goto err;
375 }
376
377 if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
378 goto err;
379 }
380
381 switch (padding) {
382 case RSA_PKCS1_PADDING:
383 r = RSA_padding_check_PKCS1_type_2(out, rsa_size, buf, rsa_size);
384 break;
385 case RSA_PKCS1_OAEP_PADDING:
386 /* Use the default parameters: SHA-1 for both hashes and no label. */
387 r = RSA_padding_check_PKCS1_OAEP_mgf1(out, rsa_size, buf, rsa_size,
388 NULL, 0, NULL, NULL);
389 break;
390 case RSA_NO_PADDING:
391 r = RSA_padding_check_none(out, rsa_size, buf, rsa_size);
392 break;
393 default:
394 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_UNKNOWN_PADDING_TYPE);
395 goto err;
396 }
397
398 if (r < 0) {
399 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_PADDING_CHECK_FAILED);
400 } else {
401 *out_len = r;
402 ret = 1;
403 }
404
405 err:
406 if (buf != NULL) {
407 OPENSSL_cleanse(buf, rsa_size);
408 OPENSSL_free(buf);
409 }
410
411 return ret;
412 }
413
verify_raw(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)414 static int verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
415 const uint8_t *in, size_t in_len, int padding) {
416 const unsigned rsa_size = RSA_size(rsa);
417 BIGNUM *f, *result;
418 int ret = 0;
419 int r = -1;
420 uint8_t *buf = NULL;
421 BN_CTX *ctx = NULL;
422
423 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
424 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_MODULUS_TOO_LARGE);
425 return 0;
426 }
427
428 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
429 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_BAD_E_VALUE);
430 return 0;
431 }
432
433 if (max_out < rsa_size) {
434 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
435 return 0;
436 }
437
438 /* for large moduli, enforce exponent limit */
439 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
440 BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
441 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_BAD_E_VALUE);
442 return 0;
443 }
444
445 ctx = BN_CTX_new();
446 if (ctx == NULL) {
447 goto err;
448 }
449
450 BN_CTX_start(ctx);
451 f = BN_CTX_get(ctx);
452 result = BN_CTX_get(ctx);
453 buf = OPENSSL_malloc(rsa_size);
454 if (!f || !result || !buf) {
455 OPENSSL_PUT_ERROR(RSA, verify_raw, ERR_R_MALLOC_FAILURE);
456 goto err;
457 }
458
459 if (in_len != rsa_size) {
460 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
461 goto err;
462 }
463
464 if (BN_bin2bn(in, in_len, f) == NULL) {
465 goto err;
466 }
467
468 if (BN_ucmp(f, rsa->n) >= 0) {
469 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
470 goto err;
471 }
472
473 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
474 if (BN_MONT_CTX_set_locked(&rsa->_method_mod_n, &rsa->lock, rsa->n, ctx) ==
475 NULL) {
476 goto err;
477 }
478 }
479
480 if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx,
481 rsa->_method_mod_n)) {
482 goto err;
483 }
484
485 if (!BN_bn2bin_padded(buf, rsa_size, result)) {
486 OPENSSL_PUT_ERROR(RSA, verify_raw, ERR_R_INTERNAL_ERROR);
487 goto err;
488 }
489
490 switch (padding) {
491 case RSA_PKCS1_PADDING:
492 r = RSA_padding_check_PKCS1_type_1(out, rsa_size, buf, rsa_size);
493 break;
494 case RSA_NO_PADDING:
495 r = RSA_padding_check_none(out, rsa_size, buf, rsa_size);
496 break;
497 default:
498 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_UNKNOWN_PADDING_TYPE);
499 goto err;
500 }
501
502 if (r < 0) {
503 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_PADDING_CHECK_FAILED);
504 } else {
505 *out_len = r;
506 ret = 1;
507 }
508
509 err:
510 if (ctx != NULL) {
511 BN_CTX_end(ctx);
512 BN_CTX_free(ctx);
513 }
514 if (buf != NULL) {
515 OPENSSL_cleanse(buf, rsa_size);
516 OPENSSL_free(buf);
517 }
518 return ret;
519 }
520
private_transform(RSA * rsa,uint8_t * out,const uint8_t * in,size_t len)521 static int private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
522 size_t len) {
523 BIGNUM *f, *result;
524 BN_CTX *ctx = NULL;
525 unsigned blinding_index = 0;
526 BN_BLINDING *blinding = NULL;
527 int ret = 0;
528
529 ctx = BN_CTX_new();
530 if (ctx == NULL) {
531 goto err;
532 }
533 BN_CTX_start(ctx);
534 f = BN_CTX_get(ctx);
535 result = BN_CTX_get(ctx);
536
537 if (f == NULL || result == NULL) {
538 OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_MALLOC_FAILURE);
539 goto err;
540 }
541
542 if (BN_bin2bn(in, len, f) == NULL) {
543 goto err;
544 }
545
546 if (BN_ucmp(f, rsa->n) >= 0) {
547 /* Usually the padding functions would catch this. */
548 OPENSSL_PUT_ERROR(RSA, private_transform, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
549 goto err;
550 }
551
552 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
553 blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
554 if (blinding == NULL) {
555 OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_INTERNAL_ERROR);
556 goto err;
557 }
558 if (!BN_BLINDING_convert_ex(f, NULL, blinding, ctx)) {
559 goto err;
560 }
561 }
562
563 if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
564 ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) &&
565 (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
566 if (!rsa->meth->mod_exp(result, f, rsa, ctx)) {
567 goto err;
568 }
569 } else {
570 BIGNUM local_d;
571 BIGNUM *d = NULL;
572
573 BN_init(&local_d);
574 d = &local_d;
575 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
576
577 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
578 if (BN_MONT_CTX_set_locked(&rsa->_method_mod_n, &rsa->lock, rsa->n,
579 ctx) == NULL) {
580 goto err;
581 }
582 }
583
584 if (!rsa->meth->bn_mod_exp(result, f, d, rsa->n, ctx, rsa->_method_mod_n)) {
585 goto err;
586 }
587 }
588
589 if (blinding) {
590 if (!BN_BLINDING_invert_ex(result, NULL, blinding, ctx)) {
591 goto err;
592 }
593 }
594
595 if (!BN_bn2bin_padded(out, len, result)) {
596 OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_INTERNAL_ERROR);
597 goto err;
598 }
599
600 ret = 1;
601
602 err:
603 if (ctx != NULL) {
604 BN_CTX_end(ctx);
605 BN_CTX_free(ctx);
606 }
607 if (blinding != NULL) {
608 rsa_blinding_release(rsa, blinding, blinding_index);
609 }
610
611 return ret;
612 }
613
mod_exp(BIGNUM * r0,const BIGNUM * I,RSA * rsa,BN_CTX * ctx)614 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
615 BIGNUM *r1, *m1, *vrfy;
616 BIGNUM local_dmp1, local_dmq1, local_c, local_r1;
617 BIGNUM *dmp1, *dmq1, *c, *pr1;
618 int ret = 0;
619
620 BN_CTX_start(ctx);
621 r1 = BN_CTX_get(ctx);
622 m1 = BN_CTX_get(ctx);
623 vrfy = BN_CTX_get(ctx);
624
625 {
626 BIGNUM local_p, local_q;
627 BIGNUM *p = NULL, *q = NULL;
628
629 /* Make sure BN_mod_inverse in Montgomery intialization uses the
630 * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set) */
631 BN_init(&local_p);
632 p = &local_p;
633 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
634
635 BN_init(&local_q);
636 q = &local_q;
637 BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
638
639 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
640 if (BN_MONT_CTX_set_locked(&rsa->_method_mod_p, &rsa->lock, p, ctx) ==
641 NULL) {
642 goto err;
643 }
644 if (BN_MONT_CTX_set_locked(&rsa->_method_mod_q, &rsa->lock, q, ctx) ==
645 NULL) {
646 goto err;
647 }
648 }
649 }
650
651 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
652 if (BN_MONT_CTX_set_locked(&rsa->_method_mod_n, &rsa->lock, rsa->n, ctx) ==
653 NULL) {
654 goto err;
655 }
656 }
657
658 /* compute I mod q */
659 c = &local_c;
660 BN_with_flags(c, I, BN_FLG_CONSTTIME);
661 if (!BN_mod(r1, c, rsa->q, ctx)) {
662 goto err;
663 }
664
665 /* compute r1^dmq1 mod q */
666 dmq1 = &local_dmq1;
667 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
668 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, rsa->_method_mod_q)) {
669 goto err;
670 }
671
672 /* compute I mod p */
673 c = &local_c;
674 BN_with_flags(c, I, BN_FLG_CONSTTIME);
675 if (!BN_mod(r1, c, rsa->p, ctx)) {
676 goto err;
677 }
678
679 /* compute r1^dmp1 mod p */
680 dmp1 = &local_dmp1;
681 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
682 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, rsa->_method_mod_p)) {
683 goto err;
684 }
685
686 if (!BN_sub(r0, r0, m1)) {
687 goto err;
688 }
689 /* This will help stop the size of r0 increasing, which does
690 * affect the multiply if it optimised for a power of 2 size */
691 if (BN_is_negative(r0)) {
692 if (!BN_add(r0, r0, rsa->p)) {
693 goto err;
694 }
695 }
696
697 if (!BN_mul(r1, r0, rsa->iqmp, ctx)) {
698 goto err;
699 }
700
701 /* Turn BN_FLG_CONSTTIME flag on before division operation */
702 pr1 = &local_r1;
703 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
704
705 if (!BN_mod(r0, pr1, rsa->p, ctx)) {
706 goto err;
707 }
708
709 /* If p < q it is occasionally possible for the correction of
710 * adding 'p' if r0 is negative above to leave the result still
711 * negative. This can break the private key operations: the following
712 * second correction should *always* correct this rare occurrence.
713 * This will *never* happen with OpenSSL generated keys because
714 * they ensure p > q [steve] */
715 if (BN_is_negative(r0)) {
716 if (!BN_add(r0, r0, rsa->p)) {
717 goto err;
718 }
719 }
720 if (!BN_mul(r1, r0, rsa->q, ctx)) {
721 goto err;
722 }
723 if (!BN_add(r0, r1, m1)) {
724 goto err;
725 }
726
727 if (rsa->e && rsa->n) {
728 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
729 rsa->_method_mod_n)) {
730 goto err;
731 }
732 /* If 'I' was greater than (or equal to) rsa->n, the operation
733 * will be equivalent to using 'I mod n'. However, the result of
734 * the verify will *always* be less than 'n' so we don't check
735 * for absolute equality, just congruency. */
736 if (!BN_sub(vrfy, vrfy, I)) {
737 goto err;
738 }
739 if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) {
740 goto err;
741 }
742 if (BN_is_negative(vrfy)) {
743 if (!BN_add(vrfy, vrfy, rsa->n)) {
744 goto err;
745 }
746 }
747 if (!BN_is_zero(vrfy)) {
748 /* 'I' and 'vrfy' aren't congruent mod n. Don't leak
749 * miscalculated CRT output, just do a raw (slower)
750 * mod_exp and return that instead. */
751
752 BIGNUM local_d;
753 BIGNUM *d = NULL;
754
755 d = &local_d;
756 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
757 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, rsa->_method_mod_n)) {
758 goto err;
759 }
760 }
761 }
762 ret = 1;
763
764 err:
765 BN_CTX_end(ctx);
766 return ret;
767 }
768
keygen(RSA * rsa,int bits,BIGNUM * e_value,BN_GENCB * cb)769 static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
770 BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;
771 BIGNUM local_r0, local_d, local_p;
772 BIGNUM *pr0, *d, *p;
773 int bitsp, bitsq, ok = -1, n = 0;
774 BN_CTX *ctx = NULL;
775
776 ctx = BN_CTX_new();
777 if (ctx == NULL) {
778 goto err;
779 }
780 BN_CTX_start(ctx);
781 r0 = BN_CTX_get(ctx);
782 r1 = BN_CTX_get(ctx);
783 r2 = BN_CTX_get(ctx);
784 r3 = BN_CTX_get(ctx);
785 if (r3 == NULL) {
786 goto err;
787 }
788
789 bitsp = (bits + 1) / 2;
790 bitsq = bits - bitsp;
791
792 /* We need the RSA components non-NULL */
793 if (!rsa->n && ((rsa->n = BN_new()) == NULL)) {
794 goto err;
795 }
796 if (!rsa->d && ((rsa->d = BN_new()) == NULL)) {
797 goto err;
798 }
799 if (!rsa->e && ((rsa->e = BN_new()) == NULL)) {
800 goto err;
801 }
802 if (!rsa->p && ((rsa->p = BN_new()) == NULL)) {
803 goto err;
804 }
805 if (!rsa->q && ((rsa->q = BN_new()) == NULL)) {
806 goto err;
807 }
808 if (!rsa->dmp1 && ((rsa->dmp1 = BN_new()) == NULL)) {
809 goto err;
810 }
811 if (!rsa->dmq1 && ((rsa->dmq1 = BN_new()) == NULL)) {
812 goto err;
813 }
814 if (!rsa->iqmp && ((rsa->iqmp = BN_new()) == NULL)) {
815 goto err;
816 }
817
818 BN_copy(rsa->e, e_value);
819
820 /* generate p and q */
821 for (;;) {
822 if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb) ||
823 !BN_sub(r2, rsa->p, BN_value_one()) ||
824 !BN_gcd(r1, r2, rsa->e, ctx)) {
825 goto err;
826 }
827 if (BN_is_one(r1)) {
828 break;
829 }
830 if (!BN_GENCB_call(cb, 2, n++)) {
831 goto err;
832 }
833 }
834 if (!BN_GENCB_call(cb, 3, 0)) {
835 goto err;
836 }
837 for (;;) {
838 /* When generating ridiculously small keys, we can get stuck
839 * continually regenerating the same prime values. Check for
840 * this and bail if it happens 3 times. */
841 unsigned int degenerate = 0;
842 do {
843 if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb)) {
844 goto err;
845 }
846 } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
847 if (degenerate == 3) {
848 ok = 0; /* we set our own err */
849 OPENSSL_PUT_ERROR(RSA, keygen, RSA_R_KEY_SIZE_TOO_SMALL);
850 goto err;
851 }
852 if (!BN_sub(r2, rsa->q, BN_value_one()) ||
853 !BN_gcd(r1, r2, rsa->e, ctx)) {
854 goto err;
855 }
856 if (BN_is_one(r1)) {
857 break;
858 }
859 if (!BN_GENCB_call(cb, 2, n++)) {
860 goto err;
861 }
862 }
863 if (!BN_GENCB_call(cb, 3, 1)) {
864 goto err;
865 }
866 if (BN_cmp(rsa->p, rsa->q) < 0) {
867 tmp = rsa->p;
868 rsa->p = rsa->q;
869 rsa->q = tmp;
870 }
871
872 /* calculate n */
873 if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx)) {
874 goto err;
875 }
876
877 /* calculate d */
878 if (!BN_sub(r1, rsa->p, BN_value_one())) {
879 goto err; /* p-1 */
880 }
881 if (!BN_sub(r2, rsa->q, BN_value_one())) {
882 goto err; /* q-1 */
883 }
884 if (!BN_mul(r0, r1, r2, ctx)) {
885 goto err; /* (p-1)(q-1) */
886 }
887 pr0 = &local_r0;
888 BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
889 if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
890 goto err; /* d */
891 }
892
893 /* set up d for correct BN_FLG_CONSTTIME flag */
894 d = &local_d;
895 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
896
897 /* calculate d mod (p-1) */
898 if (!BN_mod(rsa->dmp1, d, r1, ctx)) {
899 goto err;
900 }
901
902 /* calculate d mod (q-1) */
903 if (!BN_mod(rsa->dmq1, d, r2, ctx)) {
904 goto err;
905 }
906
907 /* calculate inverse of q mod p */
908 p = &local_p;
909 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
910
911 if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
912 goto err;
913 }
914
915 ok = 1;
916
917 err:
918 if (ok == -1) {
919 OPENSSL_PUT_ERROR(RSA, keygen, ERR_LIB_BN);
920 ok = 0;
921 }
922 if (ctx != NULL) {
923 BN_CTX_end(ctx);
924 BN_CTX_free(ctx);
925 }
926
927 return ok;
928 }
929
930 const struct rsa_meth_st RSA_default_method = {
931 {
932 0 /* references */,
933 1 /* is_static */,
934 },
935 NULL /* app_data */,
936
937 NULL /* init */,
938 finish,
939
940 size,
941
942 NULL /* sign */,
943 NULL /* verify */,
944
945 encrypt,
946 sign_raw,
947 decrypt,
948 verify_raw,
949
950 private_transform,
951
952 mod_exp /* mod_exp */,
953 BN_mod_exp_mont /* bn_mod_exp */,
954
955 RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,
956
957 keygen,
958 };
959