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