1 /* 2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include "internal/cryptlib.h" 11 #include "internal/bn_int.h" 12 #include "rsa_locl.h" 13 14 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, 15 unsigned char *to, RSA *rsa, int padding); 16 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, 17 unsigned char *to, RSA *rsa, int padding); 18 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, 19 unsigned char *to, RSA *rsa, int padding); 20 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, 21 unsigned char *to, RSA *rsa, int padding); 22 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa, 23 BN_CTX *ctx); 24 static int rsa_ossl_init(RSA *rsa); 25 static int rsa_ossl_finish(RSA *rsa); 26 static RSA_METHOD rsa_pkcs1_ossl_meth = { 27 "OpenSSL PKCS#1 RSA", 28 rsa_ossl_public_encrypt, 29 rsa_ossl_public_decrypt, /* signature verification */ 30 rsa_ossl_private_encrypt, /* signing */ 31 rsa_ossl_private_decrypt, 32 rsa_ossl_mod_exp, 33 BN_mod_exp_mont, /* XXX probably we should not use Montgomery 34 * if e == 3 */ 35 rsa_ossl_init, 36 rsa_ossl_finish, 37 RSA_FLAG_FIPS_METHOD, /* flags */ 38 NULL, 39 0, /* rsa_sign */ 40 0, /* rsa_verify */ 41 NULL, /* rsa_keygen */ 42 NULL /* rsa_multi_prime_keygen */ 43 }; 44 45 static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth; 46 47 void RSA_set_default_method(const RSA_METHOD *meth) 48 { 49 default_RSA_meth = meth; 50 } 51 52 const RSA_METHOD *RSA_get_default_method(void) 53 { 54 return default_RSA_meth; 55 } 56 57 const RSA_METHOD *RSA_PKCS1_OpenSSL(void) 58 { 59 return &rsa_pkcs1_ossl_meth; 60 } 61 62 const RSA_METHOD *RSA_null_method(void) 63 { 64 return NULL; 65 } 66 67 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, 68 unsigned char *to, RSA *rsa, int padding) 69 { 70 BIGNUM *f, *ret; 71 int i, num = 0, r = -1; 72 unsigned char *buf = NULL; 73 BN_CTX *ctx = NULL; 74 75 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) { 76 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_MODULUS_TOO_LARGE); 77 return -1; 78 } 79 80 if (BN_ucmp(rsa->n, rsa->e) <= 0) { 81 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE); 82 return -1; 83 } 84 85 /* for large moduli, enforce exponent limit */ 86 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) { 87 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) { 88 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE); 89 return -1; 90 } 91 } 92 93 if ((ctx = BN_CTX_new()) == NULL) 94 goto err; 95 BN_CTX_start(ctx); 96 f = BN_CTX_get(ctx); 97 ret = BN_CTX_get(ctx); 98 num = BN_num_bytes(rsa->n); 99 buf = OPENSSL_malloc(num); 100 if (ret == NULL || buf == NULL) { 101 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE); 102 goto err; 103 } 104 105 switch (padding) { 106 case RSA_PKCS1_PADDING: 107 i = RSA_padding_add_PKCS1_type_2(buf, num, from, flen); 108 break; 109 case RSA_PKCS1_OAEP_PADDING: 110 i = RSA_padding_add_PKCS1_OAEP(buf, num, from, flen, NULL, 0); 111 break; 112 case RSA_SSLV23_PADDING: 113 i = RSA_padding_add_SSLv23(buf, num, from, flen); 114 break; 115 case RSA_NO_PADDING: 116 i = RSA_padding_add_none(buf, num, from, flen); 117 break; 118 default: 119 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 120 goto err; 121 } 122 if (i <= 0) 123 goto err; 124 125 if (BN_bin2bn(buf, num, f) == NULL) 126 goto err; 127 128 if (BN_ucmp(f, rsa->n) >= 0) { 129 /* usually the padding functions would catch this */ 130 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, 131 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 132 goto err; 133 } 134 135 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 136 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 137 rsa->n, ctx)) 138 goto err; 139 140 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, 141 rsa->_method_mod_n)) 142 goto err; 143 144 /* 145 * BN_bn2binpad puts in leading 0 bytes if the number is less than 146 * the length of the modulus. 147 */ 148 r = BN_bn2binpad(ret, to, num); 149 err: 150 if (ctx != NULL) 151 BN_CTX_end(ctx); 152 BN_CTX_free(ctx); 153 OPENSSL_clear_free(buf, num); 154 return r; 155 } 156 157 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx) 158 { 159 BN_BLINDING *ret; 160 161 CRYPTO_THREAD_write_lock(rsa->lock); 162 163 if (rsa->blinding == NULL) { 164 rsa->blinding = RSA_setup_blinding(rsa, ctx); 165 } 166 167 ret = rsa->blinding; 168 if (ret == NULL) 169 goto err; 170 171 if (BN_BLINDING_is_current_thread(ret)) { 172 /* rsa->blinding is ours! */ 173 174 *local = 1; 175 } else { 176 /* resort to rsa->mt_blinding instead */ 177 178 /* 179 * instructs rsa_blinding_convert(), rsa_blinding_invert() that the 180 * BN_BLINDING is shared, meaning that accesses require locks, and 181 * that the blinding factor must be stored outside the BN_BLINDING 182 */ 183 *local = 0; 184 185 if (rsa->mt_blinding == NULL) { 186 rsa->mt_blinding = RSA_setup_blinding(rsa, ctx); 187 } 188 ret = rsa->mt_blinding; 189 } 190 191 err: 192 CRYPTO_THREAD_unlock(rsa->lock); 193 return ret; 194 } 195 196 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind, 197 BN_CTX *ctx) 198 { 199 if (unblind == NULL) { 200 /* 201 * Local blinding: store the unblinding factor in BN_BLINDING. 202 */ 203 return BN_BLINDING_convert_ex(f, NULL, b, ctx); 204 } else { 205 /* 206 * Shared blinding: store the unblinding factor outside BN_BLINDING. 207 */ 208 int ret; 209 210 BN_BLINDING_lock(b); 211 ret = BN_BLINDING_convert_ex(f, unblind, b, ctx); 212 BN_BLINDING_unlock(b); 213 214 return ret; 215 } 216 } 217 218 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind, 219 BN_CTX *ctx) 220 { 221 /* 222 * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex 223 * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING 224 * is shared between threads, unblind must be non-null: 225 * BN_BLINDING_invert_ex will then use the local unblinding factor, and 226 * will only read the modulus from BN_BLINDING. In both cases it's safe 227 * to access the blinding without a lock. 228 */ 229 return BN_BLINDING_invert_ex(f, unblind, b, ctx); 230 } 231 232 /* signing */ 233 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, 234 unsigned char *to, RSA *rsa, int padding) 235 { 236 BIGNUM *f, *ret, *res; 237 int i, num = 0, r = -1; 238 unsigned char *buf = NULL; 239 BN_CTX *ctx = NULL; 240 int local_blinding = 0; 241 /* 242 * Used only if the blinding structure is shared. A non-NULL unblind 243 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store 244 * the unblinding factor outside the blinding structure. 245 */ 246 BIGNUM *unblind = NULL; 247 BN_BLINDING *blinding = NULL; 248 249 if ((ctx = BN_CTX_new()) == NULL) 250 goto err; 251 BN_CTX_start(ctx); 252 f = BN_CTX_get(ctx); 253 ret = BN_CTX_get(ctx); 254 num = BN_num_bytes(rsa->n); 255 buf = OPENSSL_malloc(num); 256 if (ret == NULL || buf == NULL) { 257 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); 258 goto err; 259 } 260 261 switch (padding) { 262 case RSA_PKCS1_PADDING: 263 i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen); 264 break; 265 case RSA_X931_PADDING: 266 i = RSA_padding_add_X931(buf, num, from, flen); 267 break; 268 case RSA_NO_PADDING: 269 i = RSA_padding_add_none(buf, num, from, flen); 270 break; 271 case RSA_SSLV23_PADDING: 272 default: 273 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 274 goto err; 275 } 276 if (i <= 0) 277 goto err; 278 279 if (BN_bin2bn(buf, num, f) == NULL) 280 goto err; 281 282 if (BN_ucmp(f, rsa->n) >= 0) { 283 /* usually the padding functions would catch this */ 284 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, 285 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 286 goto err; 287 } 288 289 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) { 290 blinding = rsa_get_blinding(rsa, &local_blinding, ctx); 291 if (blinding == NULL) { 292 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_INTERNAL_ERROR); 293 goto err; 294 } 295 } 296 297 if (blinding != NULL) { 298 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) { 299 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); 300 goto err; 301 } 302 if (!rsa_blinding_convert(blinding, f, unblind, ctx)) 303 goto err; 304 } 305 306 if ((rsa->flags & RSA_FLAG_EXT_PKEY) || 307 (rsa->version == RSA_ASN1_VERSION_MULTI) || 308 ((rsa->p != NULL) && 309 (rsa->q != NULL) && 310 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) { 311 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx)) 312 goto err; 313 } else { 314 BIGNUM *d = BN_new(); 315 if (d == NULL) { 316 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); 317 goto err; 318 } 319 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 320 321 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 322 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 323 rsa->n, ctx)) { 324 BN_free(d); 325 goto err; 326 } 327 328 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, 329 rsa->_method_mod_n)) { 330 BN_free(d); 331 goto err; 332 } 333 /* We MUST free d before any further use of rsa->d */ 334 BN_free(d); 335 } 336 337 if (blinding) 338 if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) 339 goto err; 340 341 if (padding == RSA_X931_PADDING) { 342 if (!BN_sub(f, rsa->n, ret)) 343 goto err; 344 if (BN_cmp(ret, f) > 0) 345 res = f; 346 else 347 res = ret; 348 } else { 349 res = ret; 350 } 351 352 /* 353 * BN_bn2binpad puts in leading 0 bytes if the number is less than 354 * the length of the modulus. 355 */ 356 r = BN_bn2binpad(res, to, num); 357 err: 358 if (ctx != NULL) 359 BN_CTX_end(ctx); 360 BN_CTX_free(ctx); 361 OPENSSL_clear_free(buf, num); 362 return r; 363 } 364 365 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, 366 unsigned char *to, RSA *rsa, int padding) 367 { 368 BIGNUM *f, *ret; 369 int j, num = 0, r = -1; 370 unsigned char *buf = NULL; 371 BN_CTX *ctx = NULL; 372 int local_blinding = 0; 373 /* 374 * Used only if the blinding structure is shared. A non-NULL unblind 375 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store 376 * the unblinding factor outside the blinding structure. 377 */ 378 BIGNUM *unblind = NULL; 379 BN_BLINDING *blinding = NULL; 380 381 if ((ctx = BN_CTX_new()) == NULL) 382 goto err; 383 BN_CTX_start(ctx); 384 f = BN_CTX_get(ctx); 385 ret = BN_CTX_get(ctx); 386 num = BN_num_bytes(rsa->n); 387 buf = OPENSSL_malloc(num); 388 if (ret == NULL || buf == NULL) { 389 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 390 goto err; 391 } 392 393 /* 394 * This check was for equality but PGP does evil things and chops off the 395 * top '0' bytes 396 */ 397 if (flen > num) { 398 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, 399 RSA_R_DATA_GREATER_THAN_MOD_LEN); 400 goto err; 401 } 402 403 /* make data into a big number */ 404 if (BN_bin2bn(from, (int)flen, f) == NULL) 405 goto err; 406 407 if (BN_ucmp(f, rsa->n) >= 0) { 408 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, 409 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 410 goto err; 411 } 412 413 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) { 414 blinding = rsa_get_blinding(rsa, &local_blinding, ctx); 415 if (blinding == NULL) { 416 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_INTERNAL_ERROR); 417 goto err; 418 } 419 } 420 421 if (blinding != NULL) { 422 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) { 423 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 424 goto err; 425 } 426 if (!rsa_blinding_convert(blinding, f, unblind, ctx)) 427 goto err; 428 } 429 430 /* do the decrypt */ 431 if ((rsa->flags & RSA_FLAG_EXT_PKEY) || 432 (rsa->version == RSA_ASN1_VERSION_MULTI) || 433 ((rsa->p != NULL) && 434 (rsa->q != NULL) && 435 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) { 436 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx)) 437 goto err; 438 } else { 439 BIGNUM *d = BN_new(); 440 if (d == NULL) { 441 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 442 goto err; 443 } 444 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 445 446 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 447 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 448 rsa->n, ctx)) { 449 BN_free(d); 450 goto err; 451 } 452 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, 453 rsa->_method_mod_n)) { 454 BN_free(d); 455 goto err; 456 } 457 /* We MUST free d before any further use of rsa->d */ 458 BN_free(d); 459 } 460 461 if (blinding) 462 if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) 463 goto err; 464 465 j = BN_bn2binpad(ret, buf, num); 466 467 switch (padding) { 468 case RSA_PKCS1_PADDING: 469 r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num); 470 break; 471 case RSA_PKCS1_OAEP_PADDING: 472 r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0); 473 break; 474 case RSA_SSLV23_PADDING: 475 r = RSA_padding_check_SSLv23(to, num, buf, j, num); 476 break; 477 case RSA_NO_PADDING: 478 memcpy(to, buf, (r = j)); 479 break; 480 default: 481 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 482 goto err; 483 } 484 if (r < 0) 485 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED); 486 487 err: 488 if (ctx != NULL) 489 BN_CTX_end(ctx); 490 BN_CTX_free(ctx); 491 OPENSSL_clear_free(buf, num); 492 return r; 493 } 494 495 /* signature verification */ 496 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, 497 unsigned char *to, RSA *rsa, int padding) 498 { 499 BIGNUM *f, *ret; 500 int i, num = 0, r = -1; 501 unsigned char *buf = NULL; 502 BN_CTX *ctx = NULL; 503 504 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) { 505 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE); 506 return -1; 507 } 508 509 if (BN_ucmp(rsa->n, rsa->e) <= 0) { 510 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); 511 return -1; 512 } 513 514 /* for large moduli, enforce exponent limit */ 515 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) { 516 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) { 517 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); 518 return -1; 519 } 520 } 521 522 if ((ctx = BN_CTX_new()) == NULL) 523 goto err; 524 BN_CTX_start(ctx); 525 f = BN_CTX_get(ctx); 526 ret = BN_CTX_get(ctx); 527 num = BN_num_bytes(rsa->n); 528 buf = OPENSSL_malloc(num); 529 if (ret == NULL || buf == NULL) { 530 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE); 531 goto err; 532 } 533 534 /* 535 * This check was for equality but PGP does evil things and chops off the 536 * top '0' bytes 537 */ 538 if (flen > num) { 539 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN); 540 goto err; 541 } 542 543 if (BN_bin2bn(from, flen, f) == NULL) 544 goto err; 545 546 if (BN_ucmp(f, rsa->n) >= 0) { 547 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, 548 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 549 goto err; 550 } 551 552 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 553 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 554 rsa->n, ctx)) 555 goto err; 556 557 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, 558 rsa->_method_mod_n)) 559 goto err; 560 561 if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12)) 562 if (!BN_sub(ret, rsa->n, ret)) 563 goto err; 564 565 i = BN_bn2binpad(ret, buf, num); 566 567 switch (padding) { 568 case RSA_PKCS1_PADDING: 569 r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num); 570 break; 571 case RSA_X931_PADDING: 572 r = RSA_padding_check_X931(to, num, buf, i, num); 573 break; 574 case RSA_NO_PADDING: 575 memcpy(to, buf, (r = i)); 576 break; 577 default: 578 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 579 goto err; 580 } 581 if (r < 0) 582 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED); 583 584 err: 585 if (ctx != NULL) 586 BN_CTX_end(ctx); 587 BN_CTX_free(ctx); 588 OPENSSL_clear_free(buf, num); 589 return r; 590 } 591 592 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) 593 { 594 BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM - 2]; 595 int ret = 0, i, ex_primes = 0, smooth = 0; 596 RSA_PRIME_INFO *pinfo; 597 598 BN_CTX_start(ctx); 599 600 r1 = BN_CTX_get(ctx); 601 r2 = BN_CTX_get(ctx); 602 m1 = BN_CTX_get(ctx); 603 vrfy = BN_CTX_get(ctx); 604 if (vrfy == NULL) 605 goto err; 606 607 if (rsa->version == RSA_ASN1_VERSION_MULTI 608 && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0 609 || ex_primes > RSA_MAX_PRIME_NUM - 2)) 610 goto err; 611 612 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { 613 BIGNUM *factor = BN_new(); 614 615 if (factor == NULL) 616 goto err; 617 618 /* 619 * Make sure BN_mod_inverse in Montgomery initialization uses the 620 * BN_FLG_CONSTTIME flag 621 */ 622 if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME), 623 BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock, 624 factor, ctx)) 625 || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME), 626 BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock, 627 factor, ctx))) { 628 BN_free(factor); 629 goto err; 630 } 631 for (i = 0; i < ex_primes; i++) { 632 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 633 BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME); 634 if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) { 635 BN_free(factor); 636 goto err; 637 } 638 } 639 /* 640 * We MUST free |factor| before any further use of the prime factors 641 */ 642 BN_free(factor); 643 644 smooth = (ex_primes == 0) 645 && (rsa->meth->bn_mod_exp == BN_mod_exp_mont) 646 && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p)); 647 } 648 649 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 650 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 651 rsa->n, ctx)) 652 goto err; 653 654 if (smooth) { 655 /* 656 * Conversion from Montgomery domain, a.k.a. Montgomery reduction, 657 * accepts values in [0-m*2^w) range. w is m's bit width rounded up 658 * to limb width. So that at the very least if |I| is fully reduced, 659 * i.e. less than p*q, we can count on from-to round to perform 660 * below modulo operations on |I|. Unlike BN_mod it's constant time. 661 */ 662 if (/* m1 = I moq q */ 663 !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx) 664 || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx) 665 /* m1 = m1^dmq1 mod q */ 666 || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx, 667 rsa->_method_mod_q) 668 /* r1 = I mod p */ 669 || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx) 670 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) 671 /* r1 = r1^dmp1 mod p */ 672 || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx, 673 rsa->_method_mod_p) 674 /* r1 = (r1 - m1) mod p */ 675 /* 676 * bn_mod_sub_fixed_top is not regular modular subtraction, 677 * it can tolerate subtrahend to be larger than modulus, but 678 * not bit-wise wider. This makes up for uncommon q>p case, 679 * when |m1| can be larger than |rsa->p|. 680 */ 681 || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p) 682 683 /* r1 = r1 * iqmp mod p */ 684 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) 685 || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p, 686 ctx) 687 /* r0 = r1 * q + m1 */ 688 || !bn_mul_fixed_top(r0, r1, rsa->q, ctx) 689 || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n)) 690 goto err; 691 692 goto tail; 693 } 694 695 /* compute I mod q */ 696 { 697 BIGNUM *c = BN_new(); 698 if (c == NULL) 699 goto err; 700 BN_with_flags(c, I, BN_FLG_CONSTTIME); 701 702 if (!BN_mod(r1, c, rsa->q, ctx)) { 703 BN_free(c); 704 goto err; 705 } 706 707 { 708 BIGNUM *dmq1 = BN_new(); 709 if (dmq1 == NULL) { 710 BN_free(c); 711 goto err; 712 } 713 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); 714 715 /* compute r1^dmq1 mod q */ 716 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, 717 rsa->_method_mod_q)) { 718 BN_free(c); 719 BN_free(dmq1); 720 goto err; 721 } 722 /* We MUST free dmq1 before any further use of rsa->dmq1 */ 723 BN_free(dmq1); 724 } 725 726 /* compute I mod p */ 727 if (!BN_mod(r1, c, rsa->p, ctx)) { 728 BN_free(c); 729 goto err; 730 } 731 /* We MUST free c before any further use of I */ 732 BN_free(c); 733 } 734 735 { 736 BIGNUM *dmp1 = BN_new(); 737 if (dmp1 == NULL) 738 goto err; 739 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); 740 741 /* compute r1^dmp1 mod p */ 742 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, 743 rsa->_method_mod_p)) { 744 BN_free(dmp1); 745 goto err; 746 } 747 /* We MUST free dmp1 before any further use of rsa->dmp1 */ 748 BN_free(dmp1); 749 } 750 751 /* 752 * calculate m_i in multi-prime case 753 * 754 * TODO: 755 * 1. squash the following two loops and calculate |m_i| there. 756 * 2. remove cc and reuse |c|. 757 * 3. remove |dmq1| and |dmp1| in previous block and use |di|. 758 * 759 * If these things are done, the code will be more readable. 760 */ 761 if (ex_primes > 0) { 762 BIGNUM *di = BN_new(), *cc = BN_new(); 763 764 if (cc == NULL || di == NULL) { 765 BN_free(cc); 766 BN_free(di); 767 goto err; 768 } 769 770 for (i = 0; i < ex_primes; i++) { 771 /* prepare m_i */ 772 if ((m[i] = BN_CTX_get(ctx)) == NULL) { 773 BN_free(cc); 774 BN_free(di); 775 goto err; 776 } 777 778 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 779 780 /* prepare c and d_i */ 781 BN_with_flags(cc, I, BN_FLG_CONSTTIME); 782 BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME); 783 784 if (!BN_mod(r1, cc, pinfo->r, ctx)) { 785 BN_free(cc); 786 BN_free(di); 787 goto err; 788 } 789 /* compute r1 ^ d_i mod r_i */ 790 if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) { 791 BN_free(cc); 792 BN_free(di); 793 goto err; 794 } 795 } 796 797 BN_free(cc); 798 BN_free(di); 799 } 800 801 if (!BN_sub(r0, r0, m1)) 802 goto err; 803 /* 804 * This will help stop the size of r0 increasing, which does affect the 805 * multiply if it optimised for a power of 2 size 806 */ 807 if (BN_is_negative(r0)) 808 if (!BN_add(r0, r0, rsa->p)) 809 goto err; 810 811 if (!BN_mul(r1, r0, rsa->iqmp, ctx)) 812 goto err; 813 814 { 815 BIGNUM *pr1 = BN_new(); 816 if (pr1 == NULL) 817 goto err; 818 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); 819 820 if (!BN_mod(r0, pr1, rsa->p, ctx)) { 821 BN_free(pr1); 822 goto err; 823 } 824 /* We MUST free pr1 before any further use of r1 */ 825 BN_free(pr1); 826 } 827 828 /* 829 * If p < q it is occasionally possible for the correction of adding 'p' 830 * if r0 is negative above to leave the result still negative. This can 831 * break the private key operations: the following second correction 832 * should *always* correct this rare occurrence. This will *never* happen 833 * with OpenSSL generated keys because they ensure p > q [steve] 834 */ 835 if (BN_is_negative(r0)) 836 if (!BN_add(r0, r0, rsa->p)) 837 goto err; 838 if (!BN_mul(r1, r0, rsa->q, ctx)) 839 goto err; 840 if (!BN_add(r0, r1, m1)) 841 goto err; 842 843 /* add m_i to m in multi-prime case */ 844 if (ex_primes > 0) { 845 BIGNUM *pr2 = BN_new(); 846 847 if (pr2 == NULL) 848 goto err; 849 850 for (i = 0; i < ex_primes; i++) { 851 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 852 if (!BN_sub(r1, m[i], r0)) { 853 BN_free(pr2); 854 goto err; 855 } 856 857 if (!BN_mul(r2, r1, pinfo->t, ctx)) { 858 BN_free(pr2); 859 goto err; 860 } 861 862 BN_with_flags(pr2, r2, BN_FLG_CONSTTIME); 863 864 if (!BN_mod(r1, pr2, pinfo->r, ctx)) { 865 BN_free(pr2); 866 goto err; 867 } 868 869 if (BN_is_negative(r1)) 870 if (!BN_add(r1, r1, pinfo->r)) { 871 BN_free(pr2); 872 goto err; 873 } 874 if (!BN_mul(r1, r1, pinfo->pp, ctx)) { 875 BN_free(pr2); 876 goto err; 877 } 878 if (!BN_add(r0, r0, r1)) { 879 BN_free(pr2); 880 goto err; 881 } 882 } 883 BN_free(pr2); 884 } 885 886 tail: 887 if (rsa->e && rsa->n) { 888 if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) { 889 if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx, 890 rsa->_method_mod_n)) 891 goto err; 892 } else { 893 bn_correct_top(r0); 894 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, 895 rsa->_method_mod_n)) 896 goto err; 897 } 898 /* 899 * If 'I' was greater than (or equal to) rsa->n, the operation will 900 * be equivalent to using 'I mod n'. However, the result of the 901 * verify will *always* be less than 'n' so we don't check for 902 * absolute equality, just congruency. 903 */ 904 if (!BN_sub(vrfy, vrfy, I)) 905 goto err; 906 if (BN_is_zero(vrfy)) { 907 bn_correct_top(r0); 908 ret = 1; 909 goto err; /* not actually error */ 910 } 911 if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) 912 goto err; 913 if (BN_is_negative(vrfy)) 914 if (!BN_add(vrfy, vrfy, rsa->n)) 915 goto err; 916 if (!BN_is_zero(vrfy)) { 917 /* 918 * 'I' and 'vrfy' aren't congruent mod n. Don't leak 919 * miscalculated CRT output, just do a raw (slower) mod_exp and 920 * return that instead. 921 */ 922 923 BIGNUM *d = BN_new(); 924 if (d == NULL) 925 goto err; 926 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 927 928 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, 929 rsa->_method_mod_n)) { 930 BN_free(d); 931 goto err; 932 } 933 /* We MUST free d before any further use of rsa->d */ 934 BN_free(d); 935 } 936 } 937 /* 938 * It's unfortunate that we have to bn_correct_top(r0). What hopefully 939 * saves the day is that correction is highly unlike, and private key 940 * operations are customarily performed on blinded message. Which means 941 * that attacker won't observe correlation with chosen plaintext. 942 * Secondly, remaining code would still handle it in same computational 943 * time and even conceal memory access pattern around corrected top. 944 */ 945 bn_correct_top(r0); 946 ret = 1; 947 err: 948 BN_CTX_end(ctx); 949 return ret; 950 } 951 952 static int rsa_ossl_init(RSA *rsa) 953 { 954 rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE; 955 return 1; 956 } 957 958 static int rsa_ossl_finish(RSA *rsa) 959 { 960 int i; 961 RSA_PRIME_INFO *pinfo; 962 963 BN_MONT_CTX_free(rsa->_method_mod_n); 964 BN_MONT_CTX_free(rsa->_method_mod_p); 965 BN_MONT_CTX_free(rsa->_method_mod_q); 966 for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) { 967 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 968 BN_MONT_CTX_free(pinfo->m); 969 } 970 return 1; 971 } 972