crypto/rsa/rsa_ossl.c

   1 /*
   2  * Copyright 1995-2025 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (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 /*
  11  * RSA low level APIs are deprecated for public use, but still ok for
  12  * internal use.
  13  */
  14 #include "internal/deprecated.h"
  15
  16 #include "internal/cryptlib.h"
  17 #include "crypto/bn.h"
  18 #include "crypto/sparse_array.h"
  19 #include "rsa_local.h"
  20 #include "internal/constant_time.h"
  21 #if defined(OPENSSL_SYS_TANDEM)
  22 # include "internal/tsan_assist.h"
  23 # include "internal/threads_common.h"
  24 #endif
  25 #include <openssl/evp.h>
  26 #include <openssl/sha.h>
  27 #include <openssl/hmac.h>
  28
  29 DEFINE_SPARSE_ARRAY_OF(BN_BLINDING);
  30
  31 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
  32                                   unsigned char *to, RSA *rsa, int padding);
  33 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
  34                                    unsigned char *to, RSA *rsa, int padding);
  35 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
  36                                   unsigned char *to, RSA *rsa, int padding);
  37 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
  38                                    unsigned char *to, RSA *rsa, int padding);
  39 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
  40                            BN_CTX *ctx);
  41 static int rsa_ossl_init(RSA *rsa);
  42 static int rsa_ossl_finish(RSA *rsa);
  43 #ifdef S390X_MOD_EXP
  44 static int rsa_ossl_s390x_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
  45                                 BN_CTX *ctx);
  46 static RSA_METHOD rsa_pkcs1_ossl_meth = {
  47     "OpenSSL PKCS#1 RSA",
  48     rsa_ossl_public_encrypt,
  49     rsa_ossl_public_decrypt,     /* signature verification */
  50     rsa_ossl_private_encrypt,    /* signing */
  51     rsa_ossl_private_decrypt,
  52     rsa_ossl_s390x_mod_exp,
  53     s390x_mod_exp,
  54     rsa_ossl_init,
  55     rsa_ossl_finish,
  56     RSA_FLAG_FIPS_METHOD,       /* flags */
  57     NULL,
  58     0,                          /* rsa_sign */
  59     0,                          /* rsa_verify */
  60     NULL,                       /* rsa_keygen */
  61     NULL                        /* rsa_multi_prime_keygen */
  62 };
  63 #else
  64 static RSA_METHOD rsa_pkcs1_ossl_meth = {
  65     "OpenSSL PKCS#1 RSA",
  66     rsa_ossl_public_encrypt,
  67     rsa_ossl_public_decrypt,     /* signature verification */
  68     rsa_ossl_private_encrypt,    /* signing */
  69     rsa_ossl_private_decrypt,
  70     rsa_ossl_mod_exp,
  71     BN_mod_exp_mont,            /* XXX probably we should not use Montgomery
  72                                  * if e == 3 */
  73     rsa_ossl_init,
  74     rsa_ossl_finish,
  75     RSA_FLAG_FIPS_METHOD,       /* flags */
  76     NULL,
  77     0,                          /* rsa_sign */
  78     0,                          /* rsa_verify */
  79     NULL,                       /* rsa_keygen */
  80     NULL                        /* rsa_multi_prime_keygen */
  81 };
  82 #endif
  83
  84 static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth;
  85
  86 void RSA_set_default_method(const RSA_METHOD *meth)
  87 {
  88     default_RSA_meth = meth;
  89 }
  90
  91 const RSA_METHOD *RSA_get_default_method(void)
  92 {
  93     return default_RSA_meth;
  94 }
  95
  96 const RSA_METHOD *RSA_PKCS1_OpenSSL(void)
  97 {
  98     return &rsa_pkcs1_ossl_meth;
  99 }
 100
 101 const RSA_METHOD *RSA_null_method(void)
 102 {
 103     return NULL;
 104 }
 105
 106 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
 107                                   unsigned char *to, RSA *rsa, int padding)
 108 {
 109     BIGNUM *f, *ret;
 110     int i, num = 0, r = -1;
 111     unsigned char *buf = NULL;
 112     BN_CTX *ctx = NULL;
 113
 114     if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
 115         ERR_raise(ERR_LIB_RSA, RSA_R_MODULUS_TOO_LARGE);
 116         return -1;
 117     }
 118
 119     if (BN_ucmp(rsa->n, rsa->e) <= 0) {
 120         ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
 121         return -1;
 122     }
 123
 124     /* for large moduli, enforce exponent limit */
 125     if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
 126         if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
 127             ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
 128             return -1;
 129         }
 130     }
 131
 132     if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
 133         goto err;
 134     BN_CTX_start(ctx);
 135     f = BN_CTX_get(ctx);
 136     ret = BN_CTX_get(ctx);
 137     num = BN_num_bytes(rsa->n);
 138     buf = OPENSSL_malloc(num);
 139     if (ret == NULL || buf == NULL)
 140         goto err;
 141
 142     switch (padding) {
 143     case RSA_PKCS1_PADDING:
 144         i = ossl_rsa_padding_add_PKCS1_type_2_ex(rsa->libctx, buf, num,
 145                                                  from, flen);
 146         break;
 147     case RSA_PKCS1_OAEP_PADDING:
 148         i = ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex(rsa->libctx, buf, num,
 149                                                     from, flen, NULL, 0,
 150                                                     NULL, NULL);
 151         break;
 152     case RSA_NO_PADDING:
 153         i = RSA_padding_add_none(buf, num, from, flen);
 154         break;
 155     default:
 156         ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
 157         goto err;
 158     }
 159     if (i <= 0)
 160         goto err;
 161
 162     if (BN_bin2bn(buf, num, f) == NULL)
 163         goto err;
 164
 165 #ifdef FIPS_MODULE
 166     /*
 167      * See SP800-56Br2, section 7.1.1.1
 168      * RSAEP: 1 < f < (n – 1).
 169      * (where f is the plaintext).
 170      */
 171     if (padding == RSA_NO_PADDING) {
 172         BIGNUM *nminus1 = BN_CTX_get(ctx);
 173
 174         if (BN_ucmp(f, BN_value_one()) <= 0) {
 175             ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_SMALL);
 176             goto err;
 177         }
 178         if (nminus1 == NULL
 179                 || BN_copy(nminus1, rsa->n) == NULL
 180                 || !BN_sub_word(nminus1, 1))
 181             goto err;
 182         if (BN_ucmp(f, nminus1) >= 0) {
 183             ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 184             goto err;
 185         }
 186     } else
 187 #endif
 188     {
 189         if (BN_ucmp(f, rsa->n) >= 0) {
 190             /* usually the padding functions would catch this */
 191             ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 192             goto err;
 193         }
 194     }
 195
 196     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 197         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 198                                     rsa->n, ctx))
 199             goto err;
 200
 201     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
 202                                rsa->_method_mod_n))
 203         goto err;
 204
 205     /*
 206      * BN_bn2binpad puts in leading 0 bytes if the number is less than
 207      * the length of the modulus.
 208      */
 209     r = BN_bn2binpad(ret, to, num);
 210  err:
 211     BN_CTX_end(ctx);
 212     BN_CTX_free(ctx);
 213     OPENSSL_clear_free(buf, num);
 214     return r;
 215 }
 216
 217 #if defined(OPENSSL_SYS_TANDEM)
 218 static TSAN_QUALIFIER uint64_t tsan_thread_id = 1;
 219 #endif
 220
 221 static uintptr_t get_unique_thread_id(void)
 222 {
 223 #if defined(OPENSSL_SYS_TANDEM)
 224     uintptr_t thread_id = (uintptr_t)CRYPTO_THREAD_get_local_ex(CRYPTO_THREAD_LOCAL_TANDEM_ID_KEY,
 225                                                                 NULL);
 226
 227     if (thread_id == 0) {
 228         thread_id = tsan_counter(&tsan_thread_id);
 229         CRYPTO_THREAD_set_local_ex(CRYPTO_THREAD_LOCAL_TANDEM_ID_KEY, NULL, (void *)thread_id);
 230     }
 231     return thread_id;
 232 #else
 233     return (uintptr_t)CRYPTO_THREAD_get_current_id();
 234 #endif
 235 }
 236
 237 static void free_bn_blinding(ossl_uintmax_t idx, BN_BLINDING *b, void *arg)
 238 {
 239     BN_BLINDING_free(b);
 240 }
 241
 242 void ossl_rsa_free_blinding(RSA *rsa)
 243 {
 244     SPARSE_ARRAY_OF(BN_BLINDING) *blindings = rsa->blindings_sa;
 245
 246     ossl_sa_BN_BLINDING_doall_arg(blindings, free_bn_blinding, NULL);
 247     ossl_sa_BN_BLINDING_free(blindings);
 248 }
 249
 250 void *ossl_rsa_alloc_blinding(void)
 251 {
 252     return ossl_sa_BN_BLINDING_new();
 253 }
 254
 255 static BN_BLINDING *ossl_rsa_get_thread_bn_blinding(RSA *rsa)
 256 {
 257     SPARSE_ARRAY_OF(BN_BLINDING) *blindings = rsa->blindings_sa;
 258     uintptr_t tid = get_unique_thread_id();
 259
 260     return ossl_sa_BN_BLINDING_get(blindings, tid);
 261 }
 262
 263 static int ossl_rsa_set_thread_bn_blinding(RSA *rsa, BN_BLINDING *b)
 264 {
 265     SPARSE_ARRAY_OF(BN_BLINDING) *blindings = rsa->blindings_sa;
 266     uintptr_t tid = get_unique_thread_id();
 267
 268     return ossl_sa_BN_BLINDING_set(blindings, tid, b);
 269 }
 270
 271 static BN_BLINDING *rsa_get_blinding(RSA *rsa, BN_CTX *ctx)
 272 {
 273     BN_BLINDING *ret;
 274
 275     if (!CRYPTO_THREAD_read_lock(rsa->lock))
 276         return NULL;
 277
 278     ret = ossl_rsa_get_thread_bn_blinding(rsa);
 279     CRYPTO_THREAD_unlock(rsa->lock);
 280
 281     if (ret == NULL) {
 282         ret = RSA_setup_blinding(rsa, ctx);
 283         if (!CRYPTO_THREAD_write_lock(rsa->lock)) {
 284             BN_BLINDING_free(ret);
 285             ret = NULL;
 286         } else {
 287             if (!ossl_rsa_set_thread_bn_blinding(rsa, ret)) {
 288                 BN_BLINDING_free(ret);
 289                 ret = NULL;
 290             }
 291             CRYPTO_THREAD_unlock(rsa->lock);
 292         }
 293     }
 294
 295     return ret;
 296 }
 297
 298 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BN_CTX *ctx)
 299 {
 300     /*
 301      * Local blinding: store the unblinding factor in BN_BLINDING.
 302      */
 303     return BN_BLINDING_convert_ex(f, NULL, b, ctx);
 304 }
 305
 306 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BN_CTX *ctx)
 307 {
 308     /*
 309      * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
 310      * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
 311      * is shared between threads, unblind must be non-null:
 312      * BN_BLINDING_invert_ex will then use the local unblinding factor, and
 313      * will only read the modulus from BN_BLINDING. In both cases it's safe
 314      * to access the blinding without a lock.
 315      */
 316     BN_set_flags(f, BN_FLG_CONSTTIME);
 317     return BN_BLINDING_invert_ex(f, NULL, b, ctx);
 318 }
 319
 320 /* signing */
 321 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
 322                                    unsigned char *to, RSA *rsa, int padding)
 323 {
 324     BIGNUM *f, *ret, *res;
 325     int i, num = 0, r = -1;
 326     unsigned char *buf = NULL;
 327     BN_CTX *ctx = NULL;
 328     BN_BLINDING *blinding = NULL;
 329
 330     if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
 331         goto err;
 332     BN_CTX_start(ctx);
 333     f = BN_CTX_get(ctx);
 334     ret = BN_CTX_get(ctx);
 335     num = BN_num_bytes(rsa->n);
 336     buf = OPENSSL_malloc(num);
 337     if (ret == NULL || buf == NULL)
 338         goto err;
 339
 340     switch (padding) {
 341     case RSA_PKCS1_PADDING:
 342         i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen);
 343         break;
 344     case RSA_X931_PADDING:
 345         i = RSA_padding_add_X931(buf, num, from, flen);
 346         break;
 347     case RSA_NO_PADDING:
 348         i = RSA_padding_add_none(buf, num, from, flen);
 349         break;
 350     default:
 351         ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
 352         goto err;
 353     }
 354     if (i <= 0)
 355         goto err;
 356
 357     if (BN_bin2bn(buf, num, f) == NULL)
 358         goto err;
 359
 360     if (BN_ucmp(f, rsa->n) >= 0) {
 361         /* usually the padding functions would catch this */
 362         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 363         goto err;
 364     }
 365
 366     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 367         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 368                                     rsa->n, ctx))
 369             goto err;
 370
 371     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
 372         blinding = rsa_get_blinding(rsa, ctx);
 373         if (blinding == NULL) {
 374             ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 375             goto err;
 376         }
 377
 378         if (!rsa_blinding_convert(blinding, f, ctx))
 379             goto err;
 380     }
 381
 382     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
 383         (rsa->version == RSA_ASN1_VERSION_MULTI) ||
 384         ((rsa->p != NULL) &&
 385          (rsa->q != NULL) &&
 386          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
 387         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
 388             goto err;
 389     } else {
 390         BIGNUM *d = BN_new();
 391         if (d == NULL) {
 392             ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
 393             goto err;
 394         }
 395         if (rsa->d == NULL) {
 396             ERR_raise(ERR_LIB_RSA, RSA_R_MISSING_PRIVATE_KEY);
 397             BN_free(d);
 398             goto err;
 399         }
 400         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 401
 402         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
 403                                    rsa->_method_mod_n)) {
 404             BN_free(d);
 405             goto err;
 406         }
 407         /* We MUST free d before any further use of rsa->d */
 408         BN_free(d);
 409     }
 410
 411     if (blinding)
 412         if (!rsa_blinding_invert(blinding, ret, ctx))
 413             goto err;
 414
 415     if (padding == RSA_X931_PADDING) {
 416         if (!BN_sub(f, rsa->n, ret))
 417             goto err;
 418         if (BN_cmp(ret, f) > 0)
 419             res = f;
 420         else
 421             res = ret;
 422     } else {
 423         res = ret;
 424     }
 425
 426     /*
 427      * BN_bn2binpad puts in leading 0 bytes if the number is less than
 428      * the length of the modulus.
 429      */
 430     r = BN_bn2binpad(res, to, num);
 431  err:
 432     BN_CTX_end(ctx);
 433     BN_CTX_free(ctx);
 434     OPENSSL_clear_free(buf, num);
 435     return r;
 436 }
 437
 438 static int derive_kdk(int flen, const unsigned char *from, RSA *rsa,
 439                       unsigned char *buf, int num, unsigned char *kdk)
 440 {
 441     int ret = 0;
 442     HMAC_CTX *hmac = NULL;
 443     EVP_MD *md = NULL;
 444     unsigned int md_len = SHA256_DIGEST_LENGTH;
 445     unsigned char d_hash[SHA256_DIGEST_LENGTH] = {0};
 446     /*
 447      * because we use d as a handle to rsa->d we need to keep it local and
 448      * free before any further use of rsa->d
 449      */
 450     BIGNUM *d = BN_new();
 451
 452     if (d == NULL) {
 453         ERR_raise(ERR_LIB_RSA, ERR_R_CRYPTO_LIB);
 454         goto err;
 455     }
 456     if (rsa->d == NULL) {
 457         ERR_raise(ERR_LIB_RSA, RSA_R_MISSING_PRIVATE_KEY);
 458         BN_free(d);
 459         goto err;
 460     }
 461     BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 462     if (BN_bn2binpad(d, buf, num) < 0) {
 463         ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 464         BN_free(d);
 465         goto err;
 466     }
 467     BN_free(d);
 468
 469     /*
 470      * we use hardcoded hash so that migrating between versions that use
 471      * different hash doesn't provide a Bleichenbacher oracle:
 472      * if the attacker can see that different versions return different
 473      * messages for the same ciphertext, they'll know that the message is
 474      * synthetically generated, which means that the padding check failed
 475      */
 476     md = EVP_MD_fetch(rsa->libctx, "sha256", NULL);
 477     if (md == NULL) {
 478         ERR_raise(ERR_LIB_RSA, ERR_R_FETCH_FAILED);
 479         goto err;
 480     }
 481
 482     if (EVP_Digest(buf, num, d_hash, NULL, md, NULL) <= 0) {
 483         ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 484         goto err;
 485     }
 486
 487     hmac = HMAC_CTX_new();
 488     if (hmac == NULL) {
 489         ERR_raise(ERR_LIB_RSA, ERR_R_CRYPTO_LIB);
 490         goto err;
 491     }
 492
 493     if (HMAC_Init_ex(hmac, d_hash, sizeof(d_hash), md, NULL) <= 0) {
 494         ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 495         goto err;
 496     }
 497
 498     if (flen < num) {
 499         memset(buf, 0, num - flen);
 500         if (HMAC_Update(hmac, buf, num - flen) <= 0) {
 501             ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 502             goto err;
 503         }
 504     }
 505     if (HMAC_Update(hmac, from, flen) <= 0) {
 506         ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 507         goto err;
 508     }
 509
 510     md_len = SHA256_DIGEST_LENGTH;
 511     if (HMAC_Final(hmac, kdk, &md_len) <= 0) {
 512         ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 513         goto err;
 514     }
 515     ret = 1;
 516
 517  err:
 518     HMAC_CTX_free(hmac);
 519     EVP_MD_free(md);
 520     return ret;
 521 }
 522
 523 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
 524                                    unsigned char *to, RSA *rsa, int padding)
 525 {
 526     BIGNUM *f, *ret;
 527     int j, num = 0, r = -1;
 528     unsigned char *buf = NULL;
 529     unsigned char kdk[SHA256_DIGEST_LENGTH] = {0};
 530     BN_CTX *ctx = NULL;
 531     BN_BLINDING *blinding = NULL;
 532
 533     /*
 534      * we need the value of the private exponent to perform implicit rejection
 535      */
 536     if ((rsa->flags & RSA_FLAG_EXT_PKEY) && (padding == RSA_PKCS1_PADDING))
 537         padding = RSA_PKCS1_NO_IMPLICIT_REJECT_PADDING;
 538
 539     if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
 540         goto err;
 541     BN_CTX_start(ctx);
 542     f = BN_CTX_get(ctx);
 543     ret = BN_CTX_get(ctx);
 544     if (ret == NULL) {
 545         ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
 546         goto err;
 547     }
 548     num = BN_num_bytes(rsa->n);
 549     buf = OPENSSL_malloc(num);
 550     if (buf == NULL)
 551         goto err;
 552
 553     /*
 554      * This check was for equality but PGP does evil things and chops off the
 555      * top '0' bytes
 556      */
 557     if (flen > num) {
 558         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_GREATER_THAN_MOD_LEN);
 559         goto err;
 560     }
 561
 562     if (flen < 1) {
 563         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_SMALL);
 564         goto err;
 565     }
 566
 567     /* make data into a big number */
 568     if (BN_bin2bn(from, (int)flen, f) == NULL)
 569         goto err;
 570
 571 #ifdef FIPS_MODULE
 572     /*
 573      * See SP800-56Br2, section 7.1.2.1
 574      * RSADP: 1 < f < (n – 1)
 575      * (where f is the ciphertext).
 576      */
 577     if (padding == RSA_NO_PADDING) {
 578         BIGNUM *nminus1 = BN_CTX_get(ctx);
 579
 580         if (BN_ucmp(f, BN_value_one()) <= 0) {
 581             ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_SMALL);
 582             goto err;
 583         }
 584         if (nminus1 == NULL
 585                 || BN_copy(nminus1, rsa->n) == NULL
 586                 || !BN_sub_word(nminus1, 1))
 587             goto err;
 588         if (BN_ucmp(f, nminus1) >= 0) {
 589             ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 590             goto err;
 591         }
 592     } else
 593 #endif
 594     {
 595         if (BN_ucmp(f, rsa->n) >= 0) {
 596             ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 597             goto err;
 598         }
 599     }
 600     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 601         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 602                                     rsa->n, ctx))
 603             goto err;
 604
 605     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
 606         blinding = rsa_get_blinding(rsa, ctx);
 607         if (blinding == NULL) {
 608             ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 609             goto err;
 610         }
 611
 612         if (!rsa_blinding_convert(blinding, f, ctx))
 613             goto err;
 614     }
 615
 616     /* do the decrypt */
 617     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
 618         (rsa->version == RSA_ASN1_VERSION_MULTI) ||
 619         ((rsa->p != NULL) &&
 620          (rsa->q != NULL) &&
 621          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
 622         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
 623             goto err;
 624     } else {
 625         BIGNUM *d = BN_new();
 626         if (d == NULL) {
 627             ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
 628             goto err;
 629         }
 630         if (rsa->d == NULL) {
 631             ERR_raise(ERR_LIB_RSA, RSA_R_MISSING_PRIVATE_KEY);
 632             BN_free(d);
 633             goto err;
 634         }
 635         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 636         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
 637                                    rsa->_method_mod_n)) {
 638             BN_free(d);
 639             goto err;
 640         }
 641         /* We MUST free d before any further use of rsa->d */
 642         BN_free(d);
 643     }
 644
 645     if (blinding)
 646         if (!rsa_blinding_invert(blinding, ret, ctx))
 647             goto err;
 648
 649     /*
 650      * derive the Key Derivation Key from private exponent and public
 651      * ciphertext
 652      */
 653     if (padding == RSA_PKCS1_PADDING) {
 654         if (derive_kdk(flen, from, rsa, buf, num, kdk) == 0)
 655             goto err;
 656     }
 657
 658     j = BN_bn2binpad(ret, buf, num);
 659     if (j < 0)
 660         goto err;
 661
 662     switch (padding) {
 663     case RSA_PKCS1_NO_IMPLICIT_REJECT_PADDING:
 664         r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num);
 665         break;
 666     case RSA_PKCS1_PADDING:
 667         r = ossl_rsa_padding_check_PKCS1_type_2(rsa->libctx, to, num, buf, j, num, kdk);
 668         break;
 669     case RSA_PKCS1_OAEP_PADDING:
 670         r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0);
 671         break;
 672     case RSA_NO_PADDING:
 673         memcpy(to, buf, (r = j));
 674         break;
 675     default:
 676         ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
 677         goto err;
 678     }
 679 #ifndef FIPS_MODULE
 680     /*
 681      * This trick doesn't work in the FIPS provider because libcrypto manages
 682      * the error stack. Instead we opt not to put an error on the stack at all
 683      * in case of padding failure in the FIPS provider.
 684      */
 685     ERR_raise(ERR_LIB_RSA, RSA_R_PADDING_CHECK_FAILED);
 686     err_clear_last_constant_time(1 & ~constant_time_msb(r));
 687 #endif
 688
 689  err:
 690     BN_CTX_end(ctx);
 691     BN_CTX_free(ctx);
 692     OPENSSL_clear_free(buf, num);
 693     return r;
 694 }
 695
 696 /* signature verification */
 697 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
 698                                   unsigned char *to, RSA *rsa, int padding)
 699 {
 700     BIGNUM *f, *ret;
 701     int i, num = 0, r = -1;
 702     unsigned char *buf = NULL;
 703     BN_CTX *ctx = NULL;
 704
 705     if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
 706         ERR_raise(ERR_LIB_RSA, RSA_R_MODULUS_TOO_LARGE);
 707         return -1;
 708     }
 709
 710     if (BN_ucmp(rsa->n, rsa->e) <= 0) {
 711         ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
 712         return -1;
 713     }
 714
 715     /* for large moduli, enforce exponent limit */
 716     if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
 717         if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
 718             ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
 719             return -1;
 720         }
 721     }
 722
 723     if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
 724         goto err;
 725     BN_CTX_start(ctx);
 726     f = BN_CTX_get(ctx);
 727     ret = BN_CTX_get(ctx);
 728     if (ret == NULL) {
 729         ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
 730         goto err;
 731     }
 732     num = BN_num_bytes(rsa->n);
 733     buf = OPENSSL_malloc(num);
 734     if (buf == NULL)
 735         goto err;
 736
 737     /*
 738      * This check was for equality but PGP does evil things and chops off the
 739      * top '0' bytes
 740      */
 741     if (flen > num) {
 742         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_GREATER_THAN_MOD_LEN);
 743         goto err;
 744     }
 745
 746     if (BN_bin2bn(from, flen, f) == NULL)
 747         goto err;
 748
 749     if (BN_ucmp(f, rsa->n) >= 0) {
 750         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 751         goto err;
 752     }
 753
 754     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 755         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 756                                     rsa->n, ctx))
 757             goto err;
 758
 759     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
 760                                rsa->_method_mod_n))
 761         goto err;
 762
 763     /* For X9.31: Assuming e is odd it does a 12 mod 16 test */
 764     if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12))
 765         if (!BN_sub(ret, rsa->n, ret))
 766             goto err;
 767
 768     i = BN_bn2binpad(ret, buf, num);
 769     if (i < 0)
 770         goto err;
 771
 772     switch (padding) {
 773     case RSA_PKCS1_PADDING:
 774         r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num);
 775         break;
 776     case RSA_X931_PADDING:
 777         r = RSA_padding_check_X931(to, num, buf, i, num);
 778         break;
 779     case RSA_NO_PADDING:
 780         memcpy(to, buf, (r = i));
 781         break;
 782     default:
 783         ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
 784         goto err;
 785     }
 786     if (r < 0)
 787         ERR_raise(ERR_LIB_RSA, RSA_R_PADDING_CHECK_FAILED);
 788
 789  err:
 790     BN_CTX_end(ctx);
 791     BN_CTX_free(ctx);
 792     OPENSSL_clear_free(buf, num);
 793     return r;
 794 }
 795
 796 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 797 {
 798     BIGNUM *r1, *m1, *vrfy;
 799     int ret = 0, smooth = 0;
 800 #ifndef FIPS_MODULE
 801     BIGNUM *r2, *m[RSA_MAX_PRIME_NUM - 2];
 802     int i, ex_primes = 0;
 803     RSA_PRIME_INFO *pinfo;
 804 #endif
 805
 806     BN_CTX_start(ctx);
 807
 808     r1 = BN_CTX_get(ctx);
 809 #ifndef FIPS_MODULE
 810     r2 = BN_CTX_get(ctx);
 811 #endif
 812     m1 = BN_CTX_get(ctx);
 813     vrfy = BN_CTX_get(ctx);
 814     if (vrfy == NULL)
 815         goto err;
 816
 817 #ifndef FIPS_MODULE
 818     if (rsa->version == RSA_ASN1_VERSION_MULTI
 819         && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0
 820              || ex_primes > RSA_MAX_PRIME_NUM - 2))
 821         goto err;
 822 #endif
 823
 824     if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
 825         BIGNUM *factor = BN_new();
 826
 827         if (factor == NULL)
 828             goto err;
 829
 830         /*
 831          * Make sure BN_mod_inverse in Montgomery initialization uses the
 832          * BN_FLG_CONSTTIME flag
 833          */
 834         if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME),
 835               BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock,
 836                                      factor, ctx))
 837             || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME),
 838                  BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock,
 839                                         factor, ctx))) {
 840             BN_free(factor);
 841             goto err;
 842         }
 843 #ifndef FIPS_MODULE
 844         for (i = 0; i < ex_primes; i++) {
 845             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
 846             BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME);
 847             if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) {
 848                 BN_free(factor);
 849                 goto err;
 850             }
 851         }
 852 #endif
 853         /*
 854          * We MUST free |factor| before any further use of the prime factors
 855          */
 856         BN_free(factor);
 857
 858         smooth = (rsa->meth->bn_mod_exp == BN_mod_exp_mont)
 859 #ifndef FIPS_MODULE
 860                  && (ex_primes == 0)
 861 #endif
 862                  && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p));
 863     }
 864
 865     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 866         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 867                                     rsa->n, ctx))
 868             goto err;
 869
 870     if (smooth) {
 871         /*
 872          * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
 873          * accepts values in [0-m*2^w) range. w is m's bit width rounded up
 874          * to limb width. So that at the very least if |I| is fully reduced,
 875          * i.e. less than p*q, we can count on from-to round to perform
 876          * below modulo operations on |I|. Unlike BN_mod it's constant time.
 877          */
 878         if (/* m1 = I moq q */
 879             !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx)
 880             || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx)
 881             /* r1 = I mod p */
 882             || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx)
 883             || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
 884             /*
 885              * Use parallel exponentiations optimization if possible,
 886              * otherwise fallback to two sequential exponentiations:
 887              *    m1 = m1^dmq1 mod q
 888              *    r1 = r1^dmp1 mod p
 889              */
 890             || !BN_mod_exp_mont_consttime_x2(m1, m1, rsa->dmq1, rsa->q,
 891                                              rsa->_method_mod_q,
 892                                              r1, r1, rsa->dmp1, rsa->p,
 893                                              rsa->_method_mod_p,
 894                                              ctx)
 895             /* r1 = (r1 - m1) mod p */
 896             /*
 897              * bn_mod_sub_fixed_top is not regular modular subtraction,
 898              * it can tolerate subtrahend to be larger than modulus, but
 899              * not bit-wise wider. This makes up for uncommon q>p case,
 900              * when |m1| can be larger than |rsa->p|.
 901              */
 902             || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p)
 903
 904             /* r1 = r1 * iqmp mod p */
 905             || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
 906             || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p,
 907                                       ctx)
 908             /* r0 = r1 * q + m1 */
 909             || !bn_mul_fixed_top(r0, r1, rsa->q, ctx)
 910             || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n))
 911             goto err;
 912
 913         goto tail;
 914     }
 915
 916     /* compute I mod q */
 917     {
 918         BIGNUM *c = BN_new();
 919         if (c == NULL)
 920             goto err;
 921         BN_with_flags(c, I, BN_FLG_CONSTTIME);
 922
 923         if (!BN_mod(r1, c, rsa->q, ctx)) {
 924             BN_free(c);
 925             goto err;
 926         }
 927
 928         {
 929             BIGNUM *dmq1 = BN_new();
 930             if (dmq1 == NULL) {
 931                 BN_free(c);
 932                 goto err;
 933             }
 934             BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
 935
 936             /* compute r1^dmq1 mod q */
 937             if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
 938                                        rsa->_method_mod_q)) {
 939                 BN_free(c);
 940                 BN_free(dmq1);
 941                 goto err;
 942             }
 943             /* We MUST free dmq1 before any further use of rsa->dmq1 */
 944             BN_free(dmq1);
 945         }
 946
 947         /* compute I mod p */
 948         if (!BN_mod(r1, c, rsa->p, ctx)) {
 949             BN_free(c);
 950             goto err;
 951         }
 952         /* We MUST free c before any further use of I */
 953         BN_free(c);
 954     }
 955
 956     {
 957         BIGNUM *dmp1 = BN_new();
 958         if (dmp1 == NULL)
 959             goto err;
 960         BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
 961
 962         /* compute r1^dmp1 mod p */
 963         if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
 964                                    rsa->_method_mod_p)) {
 965             BN_free(dmp1);
 966             goto err;
 967         }
 968         /* We MUST free dmp1 before any further use of rsa->dmp1 */
 969         BN_free(dmp1);
 970     }
 971
 972 #ifndef FIPS_MODULE
 973     if (ex_primes > 0) {
 974         BIGNUM *di = BN_new(), *cc = BN_new();
 975
 976         if (cc == NULL || di == NULL) {
 977             BN_free(cc);
 978             BN_free(di);
 979             goto err;
 980         }
 981
 982         for (i = 0; i < ex_primes; i++) {
 983             /* prepare m_i */
 984             if ((m[i] = BN_CTX_get(ctx)) == NULL) {
 985                 BN_free(cc);
 986                 BN_free(di);
 987                 goto err;
 988             }
 989
 990             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
 991
 992             /* prepare c and d_i */
 993             BN_with_flags(cc, I, BN_FLG_CONSTTIME);
 994             BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME);
 995
 996             if (!BN_mod(r1, cc, pinfo->r, ctx)) {
 997                 BN_free(cc);
 998                 BN_free(di);
 999                 goto err;
1000             }
1001             /* compute r1 ^ d_i mod r_i */
1002             if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) {
1003                 BN_free(cc);
1004                 BN_free(di);
1005                 goto err;
1006             }
1007         }
1008
1009         BN_free(cc);
1010         BN_free(di);
1011     }
1012 #endif
1013
1014     if (!BN_sub(r0, r0, m1))
1015         goto err;
1016     /*
1017      * This will help stop the size of r0 increasing, which does affect the
1018      * multiply if it optimised for a power of 2 size
1019      */
1020     if (BN_is_negative(r0))
1021         if (!BN_add(r0, r0, rsa->p))
1022             goto err;
1023
1024     if (!BN_mul(r1, r0, rsa->iqmp, ctx))
1025         goto err;
1026
1027     {
1028         BIGNUM *pr1 = BN_new();
1029         if (pr1 == NULL)
1030             goto err;
1031         BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
1032
1033         if (!BN_mod(r0, pr1, rsa->p, ctx)) {
1034             BN_free(pr1);
1035             goto err;
1036         }
1037         /* We MUST free pr1 before any further use of r1 */
1038         BN_free(pr1);
1039     }
1040
1041     /*
1042      * If p < q it is occasionally possible for the correction of adding 'p'
1043      * if r0 is negative above to leave the result still negative. This can
1044      * break the private key operations: the following second correction
1045      * should *always* correct this rare occurrence. This will *never* happen
1046      * with OpenSSL generated keys because they ensure p > q [steve]
1047      */
1048     if (BN_is_negative(r0))
1049         if (!BN_add(r0, r0, rsa->p))
1050             goto err;
1051     if (!BN_mul(r1, r0, rsa->q, ctx))
1052         goto err;
1053     if (!BN_add(r0, r1, m1))
1054         goto err;
1055
1056 #ifndef FIPS_MODULE
1057     /* add m_i to m in multi-prime case */
1058     if (ex_primes > 0) {
1059         BIGNUM *pr2 = BN_new();
1060
1061         if (pr2 == NULL)
1062             goto err;
1063
1064         for (i = 0; i < ex_primes; i++) {
1065             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
1066             if (!BN_sub(r1, m[i], r0)) {
1067                 BN_free(pr2);
1068                 goto err;
1069             }
1070
1071             if (!BN_mul(r2, r1, pinfo->t, ctx)) {
1072                 BN_free(pr2);
1073                 goto err;
1074             }
1075
1076             BN_with_flags(pr2, r2, BN_FLG_CONSTTIME);
1077
1078             if (!BN_mod(r1, pr2, pinfo->r, ctx)) {
1079                 BN_free(pr2);
1080                 goto err;
1081             }
1082
1083             if (BN_is_negative(r1))
1084                 if (!BN_add(r1, r1, pinfo->r)) {
1085                     BN_free(pr2);
1086                     goto err;
1087                 }
1088             if (!BN_mul(r1, r1, pinfo->pp, ctx)) {
1089                 BN_free(pr2);
1090                 goto err;
1091             }
1092             if (!BN_add(r0, r0, r1)) {
1093                 BN_free(pr2);
1094                 goto err;
1095             }
1096         }
1097         BN_free(pr2);
1098     }
1099 #endif
1100
1101  tail:
1102     if (rsa->e && rsa->n) {
1103         if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) {
1104             if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx,
1105                                  rsa->_method_mod_n))
1106                 goto err;
1107         } else {
1108             bn_correct_top(r0);
1109             if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
1110                                        rsa->_method_mod_n))
1111                 goto err;
1112         }
1113         /*
1114          * If 'I' was greater than (or equal to) rsa->n, the operation will
1115          * be equivalent to using 'I mod n'. However, the result of the
1116          * verify will *always* be less than 'n' so we don't check for
1117          * absolute equality, just congruency.
1118          */
1119         if (!BN_sub(vrfy, vrfy, I))
1120             goto err;
1121         if (BN_is_zero(vrfy)) {
1122             bn_correct_top(r0);
1123             ret = 1;
1124             goto err;   /* not actually error */
1125         }
1126         if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
1127             goto err;
1128         if (BN_is_negative(vrfy))
1129             if (!BN_add(vrfy, vrfy, rsa->n))
1130                 goto err;
1131         if (!BN_is_zero(vrfy)) {
1132             /*
1133              * 'I' and 'vrfy' aren't congruent mod n. Don't leak
1134              * miscalculated CRT output, just do a raw (slower) mod_exp and
1135              * return that instead.
1136              */
1137
1138             BIGNUM *d = BN_new();
1139             if (d == NULL)
1140                 goto err;
1141             BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
1142
1143             if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
1144                                        rsa->_method_mod_n)) {
1145                 BN_free(d);
1146                 goto err;
1147             }
1148             /* We MUST free d before any further use of rsa->d */
1149             BN_free(d);
1150         }
1151     }
1152     /*
1153      * It's unfortunate that we have to bn_correct_top(r0). What hopefully
1154      * saves the day is that correction is highly unlike, and private key
1155      * operations are customarily performed on blinded message. Which means
1156      * that attacker won't observe correlation with chosen plaintext.
1157      * Secondly, remaining code would still handle it in same computational
1158      * time and even conceal memory access pattern around corrected top.
1159      */
1160     bn_correct_top(r0);
1161     ret = 1;
1162  err:
1163     BN_CTX_end(ctx);
1164     return ret;
1165 }
1166
1167 static int rsa_ossl_init(RSA *rsa)
1168 {
1169     rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
1170     return 1;
1171 }
1172
1173 static int rsa_ossl_finish(RSA *rsa)
1174 {
1175 #ifndef FIPS_MODULE
1176     int i;
1177     RSA_PRIME_INFO *pinfo;
1178
1179     for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) {
1180         pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
1181         BN_MONT_CTX_free(pinfo->m);
1182     }
1183 #endif
1184
1185     BN_MONT_CTX_free(rsa->_method_mod_n);
1186     BN_MONT_CTX_free(rsa->_method_mod_p);
1187     BN_MONT_CTX_free(rsa->_method_mod_q);
1188     return 1;
1189 }
1190
1191 #ifdef S390X_MOD_EXP
1192 static int rsa_ossl_s390x_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
1193                                 BN_CTX *ctx)
1194 {
1195     if (rsa->version != RSA_ASN1_VERSION_MULTI) {
1196         if (s390x_crt(r0, i, rsa->p, rsa->q, rsa->dmp1, rsa->dmq1, rsa->iqmp) == 1)
1197             return 1;
1198     }
1199     return rsa_ossl_mod_exp(r0, i, rsa, ctx);
1200 }
1201
1202 #endif