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