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