src/third_party/boringssl/src/crypto/rsa/rsa.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.] */
  56
  57 #include <openssl/rsa.h>
  58
  59 #include <openssl/bn.h>
  60 #include <openssl/engine.h>
  61 #include <openssl/err.h>
  62 #include <openssl/ex_data.h>
  63 #include <openssl/mem.h>
  64 #include <openssl/obj.h>
  65
  66 #include "internal.h"
  67
  68
  69 extern const RSA_METHOD RSA_default_method;
  70
  71 RSA *RSA_new(void) { return RSA_new_method(NULL); }
  72
  73 RSA *RSA_new_method(const ENGINE *engine) {
  74   RSA *rsa = (RSA *)OPENSSL_malloc(sizeof(RSA));
  75   if (rsa == NULL) {
  76     OPENSSL_PUT_ERROR(RSA, RSA_new_method, ERR_R_MALLOC_FAILURE);
  77     return NULL;
  78   }
  79
  80   memset(rsa, 0, sizeof(RSA));
  81
  82   if (engine) {
  83     rsa->meth = ENGINE_get_RSA_method(engine);
  84   }
  85
  86   if (rsa->meth == NULL) {
  87     rsa->meth = (RSA_METHOD*) &RSA_default_method;
  88   }
  89   METHOD_ref(rsa->meth);
  90
  91   rsa->references = 1;
  92   rsa->flags = rsa->meth->flags;
  93
  94   if (!CRYPTO_new_ex_data(CRYPTO_EX_INDEX_RSA, rsa, &rsa->ex_data)) {
  95     METHOD_unref(rsa->meth);
  96     OPENSSL_free(rsa);
  97     return NULL;
  98   }
  99
 100   if (rsa->meth->init && !rsa->meth->init(rsa)) {
 101     CRYPTO_free_ex_data(CRYPTO_EX_INDEX_RSA, rsa, &rsa->ex_data);
 102     METHOD_unref(rsa->meth);
 103     OPENSSL_free(rsa);
 104     return NULL;
 105   }
 106
 107   return rsa;
 108 }
 109
 110 void RSA_free(RSA *rsa) {
 111   unsigned u;
 112
 113   if (rsa == NULL) {
 114     return;
 115   }
 116
 117   if (CRYPTO_add(&rsa->references, -1, CRYPTO_LOCK_RSA) > 0) {
 118     return;
 119   }
 120
 121   if (rsa->meth->finish) {
 122     rsa->meth->finish(rsa);
 123   }
 124   METHOD_unref(rsa->meth);
 125
 126   CRYPTO_free_ex_data(CRYPTO_EX_INDEX_DSA, rsa, &rsa->ex_data);
 127
 128   if (rsa->n != NULL)
 129     BN_clear_free(rsa->n);
 130   if (rsa->e != NULL)
 131     BN_clear_free(rsa->e);
 132   if (rsa->d != NULL)
 133     BN_clear_free(rsa->d);
 134   if (rsa->p != NULL)
 135     BN_clear_free(rsa->p);
 136   if (rsa->q != NULL)
 137     BN_clear_free(rsa->q);
 138   if (rsa->dmp1 != NULL)
 139     BN_clear_free(rsa->dmp1);
 140   if (rsa->dmq1 != NULL)
 141     BN_clear_free(rsa->dmq1);
 142   if (rsa->iqmp != NULL)
 143     BN_clear_free(rsa->iqmp);
 144   for (u = 0; u < rsa->num_blindings; u++) {
 145     BN_BLINDING_free(rsa->blindings[u]);
 146   }
 147   if (rsa->blindings != NULL)
 148     OPENSSL_free(rsa->blindings);
 149   if (rsa->blindings_inuse != NULL)
 150     OPENSSL_free(rsa->blindings_inuse);
 151   OPENSSL_free(rsa);
 152 }
 153
 154 int RSA_up_ref(RSA *rsa) {
 155   CRYPTO_add(&rsa->references, 1, CRYPTO_LOCK_RSA);
 156   return 1;
 157 }
 158
 159 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
 160   if (rsa->meth->keygen) {
 161     return rsa->meth->keygen(rsa, bits, e_value, cb);
 162   }
 163
 164   return RSA_default_method.keygen(rsa, bits, e_value, cb);
 165 }
 166
 167 int RSA_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
 168                 const uint8_t *in, size_t in_len, int padding) {
 169   if (rsa->meth->encrypt) {
 170     return rsa->meth->encrypt(rsa, out_len, out, max_out, in, in_len, padding);
 171   }
 172
 173   return RSA_default_method.encrypt(rsa, out_len, out, max_out, in, in_len,
 174                                     padding);
 175 }
 176
 177 int RSA_public_encrypt(int flen, const uint8_t *from, uint8_t *to, RSA *rsa,
 178                        int padding) {
 179   size_t out_len;
 180
 181   if (!RSA_encrypt(rsa, &out_len, to, RSA_size(rsa), from, flen, padding)) {
 182     return -1;
 183   }
 184
 185   return out_len;
 186 }
 187
 188 int RSA_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
 189                  const uint8_t *in, size_t in_len, int padding) {
 190   if (rsa->meth->sign_raw) {
 191     return rsa->meth->sign_raw(rsa, out_len, out, max_out, in, in_len, padding);
 192   }
 193
 194   return RSA_default_method.sign_raw(rsa, out_len, out, max_out, in, in_len,
 195                                      padding);
 196 }
 197
 198 int RSA_private_encrypt(int flen, const uint8_t *from, uint8_t *to, RSA *rsa,
 199                         int padding) {
 200   size_t out_len;
 201
 202   if (!RSA_sign_raw(rsa, &out_len, to, RSA_size(rsa), from, flen, padding)) {
 203     return -1;
 204   }
 205
 206   return out_len;
 207 }
 208
 209 int RSA_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
 210                 const uint8_t *in, size_t in_len, int padding) {
 211   if (rsa->meth->decrypt) {
 212     return rsa->meth->decrypt(rsa, out_len, out, max_out, in, in_len, padding);
 213   }
 214
 215   return RSA_default_method.decrypt(rsa, out_len, out, max_out, in, in_len,
 216                                     padding);
 217 }
 218
 219 int RSA_private_decrypt(int flen, const uint8_t *from, uint8_t *to, RSA *rsa,
 220                         int padding) {
 221   size_t out_len;
 222
 223   if (!RSA_decrypt(rsa, &out_len, to, RSA_size(rsa), from, flen, padding)) {
 224     return -1;
 225   }
 226
 227   return out_len;
 228 }
 229
 230 int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
 231                    const uint8_t *in, size_t in_len, int padding) {
 232   if (rsa->meth->verify_raw) {
 233     return rsa->meth->verify_raw(rsa, out_len, out, max_out, in, in_len, padding);
 234   }
 235
 236   return RSA_default_method.verify_raw(rsa, out_len, out, max_out, in, in_len,
 237                                        padding);
 238 }
 239
 240 int RSA_public_decrypt(int flen, const uint8_t *from, uint8_t *to, RSA *rsa,
 241                        int padding) {
 242   size_t out_len;
 243
 244   if (!RSA_verify_raw(rsa, &out_len, to, RSA_size(rsa), from, flen, padding)) {
 245     return -1;
 246   }
 247
 248   return out_len;
 249 }
 250
 251 unsigned RSA_size(const RSA *rsa) {
 252   if (rsa->meth->size) {
 253     return rsa->meth->size(rsa);
 254   }
 255
 256   return RSA_default_method.size(rsa);
 257 }
 258
 259 int RSA_is_opaque(const RSA *rsa) {
 260   return rsa->meth && (rsa->meth->flags & RSA_FLAG_OPAQUE);
 261 }
 262
 263 int RSA_get_ex_new_index(long argl, void *argp, CRYPTO_EX_new *new_func,
 264                          CRYPTO_EX_dup *dup_func, CRYPTO_EX_free *free_func) {
 265   return CRYPTO_get_ex_new_index(CRYPTO_EX_INDEX_RSA, argl, argp, new_func,
 266                                  dup_func, free_func);
 267 }
 268
 269 int RSA_set_ex_data(RSA *d, int idx, void *arg) {
 270   return CRYPTO_set_ex_data(&d->ex_data, idx, arg);
 271 }
 272
 273 void *RSA_get_ex_data(const RSA *d, int idx) {
 274   return CRYPTO_get_ex_data(&d->ex_data, idx);
 275 }
 276
 277 /* SSL_SIG_LENGTH is the size of an SSL/TLS (prior to TLS 1.2) signature: it's
 278  * the length of an MD5 and SHA1 hash. */
 279 static const unsigned SSL_SIG_LENGTH = 36;
 280
 281 /* pkcs1_sig_prefix contains the ASN.1, DER encoded prefix for a hash that is
 282  * to be signed with PKCS#1. */
 283 struct pkcs1_sig_prefix {
 284   /* nid identifies the hash function. */
 285   int nid;
 286   /* len is the number of bytes of |bytes| which are valid. */
 287   uint8_t len;
 288   /* bytes contains the DER bytes. */
 289   uint8_t bytes[19];
 290 };
 291
 292 /* kPKCS1SigPrefixes contains the ASN.1 prefixes for PKCS#1 signatures with
 293  * different hash functions. */
 294 static const struct pkcs1_sig_prefix kPKCS1SigPrefixes[] = {
 295     {
 296      NID_md5,
 297      18,
 298      {0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d,
 299       0x02, 0x05, 0x05, 0x00, 0x04, 0x10},
 300     },
 301     {
 302      NID_sha1,
 303      15,
 304      {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05,
 305       0x00, 0x04, 0x14},
 306     },
 307     {
 308      NID_sha224,
 309      19,
 310      {0x30, 0x2d, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03,
 311       0x04, 0x02, 0x04, 0x05, 0x00, 0x04, 0x1c},
 312     },
 313     {
 314      NID_sha256,
 315      19,
 316      {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03,
 317       0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20},
 318     },
 319     {
 320      NID_sha384,
 321      19,
 322      {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03,
 323       0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30},
 324     },
 325     {
 326      NID_sha512,
 327      19,
 328      {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03,
 329       0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40},
 330     },
 331     {
 332      NID_ripemd160,
 333      14,
 334      {0x30, 0x20, 0x30, 0x08, 0x06, 0x06, 0x28, 0xcf, 0x06, 0x03, 0x00, 0x31,
 335       0x04, 0x14},
 336     },
 337     {
 338      NID_undef, 0, {0},
 339     },
 340 };
 341
 342 /* TODO(fork): mostly new code, needs careful review. */
 343
 344 /* pkcs1_prefixed_msg builds a PKCS#1, prefixed version of |msg| for the given
 345  * hash function and sets |out_msg| to point to it. On successful return,
 346  * |*out_msg| may be allocated memory and, if so, |*is_alloced| will be 1. */
 347 static int pkcs1_prefixed_msg(uint8_t **out_msg, size_t *out_msg_len,
 348                               int *is_alloced, int hash_nid, const uint8_t *msg,
 349                               size_t msg_len) {
 350   unsigned i;
 351   const uint8_t* prefix = NULL;
 352   unsigned prefix_len;
 353   uint8_t *signed_msg;
 354   unsigned signed_msg_len;
 355
 356   if (hash_nid == NID_md5_sha1) {
 357     /* Special case: SSL signature, just check the length. */
 358     if (msg_len != SSL_SIG_LENGTH) {
 359       OPENSSL_PUT_ERROR(RSA, RSA_sign, RSA_R_INVALID_MESSAGE_LENGTH);
 360       return 0;
 361     }
 362
 363     *out_msg = (uint8_t*) msg;
 364     *out_msg_len = SSL_SIG_LENGTH;
 365     *is_alloced = 0;
 366     return 1;
 367   }
 368
 369   for (i = 0; kPKCS1SigPrefixes[i].nid != NID_undef; i++) {
 370     const struct pkcs1_sig_prefix *sig_prefix = &kPKCS1SigPrefixes[i];
 371     if (sig_prefix->nid == hash_nid) {
 372       prefix = sig_prefix->bytes;
 373       prefix_len = sig_prefix->len;
 374       break;
 375     }
 376   }
 377
 378   if (prefix == NULL) {
 379     OPENSSL_PUT_ERROR(RSA, RSA_sign, RSA_R_UNKNOWN_ALGORITHM_TYPE);
 380     return 0;
 381   }
 382
 383   signed_msg_len = prefix_len + msg_len;
 384   if (signed_msg_len < prefix_len) {
 385     OPENSSL_PUT_ERROR(RSA, RSA_sign, RSA_R_TOO_LONG);
 386     return 0;
 387   }
 388
 389   signed_msg = OPENSSL_malloc(signed_msg_len);
 390   if (!signed_msg) {
 391     OPENSSL_PUT_ERROR(RSA, RSA_sign, ERR_R_MALLOC_FAILURE);
 392     return 0;
 393   }
 394
 395   memcpy(signed_msg, prefix, prefix_len);
 396   memcpy(signed_msg + prefix_len, msg, msg_len);
 397
 398   *out_msg = signed_msg;
 399   *out_msg_len = signed_msg_len;
 400   *is_alloced = 1;
 401
 402   return 1;
 403 }
 404
 405 int RSA_sign(int hash_nid, const uint8_t *in, unsigned in_len, uint8_t *out,
 406              unsigned *out_len, RSA *rsa) {
 407   const unsigned rsa_size = RSA_size(rsa);
 408   int ret = 0;
 409   uint8_t *signed_msg;
 410   size_t signed_msg_len;
 411   int signed_msg_is_alloced = 0;
 412   size_t size_t_out_len;
 413
 414   if (rsa->meth->sign) {
 415     return rsa->meth->sign(hash_nid, in, in_len, out, out_len, rsa);
 416   }
 417
 418   if (!pkcs1_prefixed_msg(&signed_msg, &signed_msg_len, &signed_msg_is_alloced,
 419                           hash_nid, in, in_len)) {
 420     return 0;
 421   }
 422
 423   if (rsa_size < RSA_PKCS1_PADDING_SIZE ||
 424       signed_msg_len > rsa_size - RSA_PKCS1_PADDING_SIZE) {
 425     OPENSSL_PUT_ERROR(RSA, RSA_sign, RSA_R_DIGEST_TOO_BIG_FOR_RSA_KEY);
 426     goto finish;
 427   }
 428
 429   if (RSA_sign_raw(rsa, &size_t_out_len, out, rsa_size, signed_msg,
 430                    signed_msg_len, RSA_PKCS1_PADDING)) {
 431     *out_len = size_t_out_len;
 432     ret = 1;
 433   }
 434
 435 finish:
 436   if (signed_msg_is_alloced) {
 437     OPENSSL_free(signed_msg);
 438   }
 439   return ret;
 440 }
 441
 442 int RSA_verify(int hash_nid, const uint8_t *msg, size_t msg_len,
 443                const uint8_t *sig, size_t sig_len, RSA *rsa) {
 444   const size_t rsa_size = RSA_size(rsa);
 445   uint8_t *buf = NULL;
 446   int ret = 0;
 447   uint8_t *signed_msg = NULL;
 448   size_t signed_msg_len, len;
 449   int signed_msg_is_alloced = 0;
 450
 451   if (rsa->meth->verify) {
 452     return rsa->meth->verify(hash_nid, msg, msg_len, sig, sig_len, rsa);
 453   }
 454
 455   if (sig_len != rsa_size) {
 456     OPENSSL_PUT_ERROR(RSA, RSA_verify, RSA_R_WRONG_SIGNATURE_LENGTH);
 457     return 0;
 458   }
 459
 460   if (hash_nid == NID_md5_sha1 && msg_len != SSL_SIG_LENGTH) {
 461     OPENSSL_PUT_ERROR(RSA, RSA_verify, RSA_R_INVALID_MESSAGE_LENGTH);
 462     return 0;
 463   }
 464
 465   buf = OPENSSL_malloc(rsa_size);
 466   if (!buf) {
 467     OPENSSL_PUT_ERROR(RSA, RSA_verify, ERR_R_MALLOC_FAILURE);
 468     return 0;
 469   }
 470
 471   if (!RSA_verify_raw(rsa, &len, buf, rsa_size, sig, sig_len,
 472                       RSA_PKCS1_PADDING)) {
 473     goto out;
 474   }
 475
 476   if (!pkcs1_prefixed_msg(&signed_msg, &signed_msg_len, &signed_msg_is_alloced,
 477                           hash_nid, msg, msg_len)) {
 478     goto out;
 479   }
 480
 481   if (len != signed_msg_len || CRYPTO_memcmp(buf, signed_msg, len) != 0) {
 482     OPENSSL_PUT_ERROR(RSA, RSA_verify, RSA_R_BAD_SIGNATURE);
 483     goto out;
 484   }
 485
 486   ret = 1;
 487
 488 out:
 489   if (buf != NULL) {
 490     OPENSSL_free(buf);
 491   }
 492   if (signed_msg_is_alloced) {
 493     OPENSSL_free(signed_msg);
 494   }
 495   return ret;
 496 }
 497
 498 static void bn_free_and_null(BIGNUM **bn) {
 499   if (*bn == NULL) {
 500     return;
 501   }
 502
 503   BN_free(*bn);
 504   *bn = NULL;
 505 }
 506
 507 int RSA_check_key(const RSA *key) {
 508   BIGNUM n, pm1, qm1, lcm, gcd, de, dmp1, dmq1, iqmp;
 509   BN_CTX *ctx;
 510   int ok = 0, has_crt_values;
 511
 512   if (RSA_is_opaque(key)) {
 513     /* Opaque keys can't be checked. */
 514     return 1;
 515   }
 516
 517   if ((key->p != NULL) != (key->q != NULL)) {
 518     OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_ONLY_ONE_OF_P_Q_GIVEN);
 519     return 0;
 520   }
 521
 522   if (!key->n || !key->e) {
 523     OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_VALUE_MISSING);
 524     return 0;
 525   }
 526
 527   if (!key->d || !key->p) {
 528     /* For a public key, or without p and q, there's nothing that can be
 529      * checked. */
 530     return 1;
 531   }
 532
 533   ctx = BN_CTX_new();
 534   if (ctx == NULL) {
 535     OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_R_MALLOC_FAILURE);
 536     return 0;
 537   }
 538
 539   BN_init(&n);
 540   BN_init(&pm1);
 541   BN_init(&qm1);
 542   BN_init(&lcm);
 543   BN_init(&gcd);
 544   BN_init(&de);
 545   BN_init(&dmp1);
 546   BN_init(&dmq1);
 547   BN_init(&iqmp);
 548
 549   if (/* n = pq */
 550       !BN_mul(&n, key->p, key->q, ctx) ||
 551       /* lcm = lcm(p-1, q-1) */
 552       !BN_sub(&pm1, key->p, BN_value_one()) ||
 553       !BN_sub(&qm1, key->q, BN_value_one()) ||
 554       !BN_mul(&lcm, &pm1, &qm1, ctx) ||
 555       !BN_gcd(&gcd, &pm1, &qm1, ctx) ||
 556       !BN_div(&lcm, NULL, &lcm, &gcd, ctx) ||
 557       /* de = d*e mod lcm(p-1, q-1) */
 558       !BN_mod_mul(&de, key->d, key->e, &lcm, ctx)) {
 559     OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_LIB_BN);
 560     goto out;
 561   }
 562
 563   if (BN_cmp(&n, key->n) != 0) {
 564     OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_N_NOT_EQUAL_P_Q);
 565     goto out;
 566   }
 567
 568   if (!BN_is_one(&de)) {
 569     OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_D_E_NOT_CONGRUENT_TO_1);
 570     goto out;
 571   }
 572
 573   has_crt_values = key->dmp1 != NULL;
 574   if (has_crt_values != (key->dmq1 != NULL) ||
 575       has_crt_values != (key->iqmp != NULL)) {
 576     OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_INCONSISTENT_SET_OF_CRT_VALUES);
 577     goto out;
 578   }
 579
 580   if (has_crt_values) {
 581     if (/* dmp1 = d mod (p-1) */
 582         !BN_mod(&dmp1, key->d, &pm1, ctx) ||
 583         /* dmq1 = d mod (q-1) */
 584         !BN_mod(&dmq1, key->d, &qm1, ctx) ||
 585         /* iqmp = q^-1 mod p */
 586         !BN_mod_inverse(&iqmp, key->q, key->p, ctx)) {
 587       OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_LIB_BN);
 588       goto out;
 589     }
 590
 591     if (BN_cmp(&dmp1, key->dmp1) != 0 ||
 592         BN_cmp(&dmq1, key->dmq1) != 0 ||
 593         BN_cmp(&iqmp, key->iqmp) != 0) {
 594       OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_CRT_VALUES_INCORRECT);
 595       goto out;
 596     }
 597   }
 598
 599   ok = 1;
 600
 601 out:
 602   BN_free(&n);
 603   BN_free(&pm1);
 604   BN_free(&qm1);
 605   BN_free(&lcm);
 606   BN_free(&gcd);
 607   BN_free(&de);
 608   BN_free(&dmp1);
 609   BN_free(&dmq1);
 610   BN_free(&iqmp);
 611   BN_CTX_free(ctx);
 612
 613   return ok;
 614 }
 615
 616 int RSA_recover_crt_params(RSA *rsa) {
 617   BN_CTX *ctx;
 618   BIGNUM *totient, *rem, *multiple, *p_plus_q, *p_minus_q;
 619   int ok = 0;
 620
 621   if (rsa->n == NULL || rsa->e == NULL || rsa->d == NULL) {
 622     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, RSA_R_EMPTY_PUBLIC_KEY);
 623     return 0;
 624   }
 625
 626   if (rsa->p || rsa->q || rsa->dmp1 || rsa->dmq1 || rsa->iqmp) {
 627     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params,
 628                       RSA_R_CRT_PARAMS_ALREADY_GIVEN);
 629     return 0;
 630   }
 631
 632   /* This uses the algorithm from section 9B of the RSA paper:
 633    * http://people.csail.mit.edu/rivest/Rsapaper.pdf */
 634
 635   ctx = BN_CTX_new();
 636   if (ctx == NULL) {
 637     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_MALLOC_FAILURE);
 638     return 0;
 639   }
 640
 641   BN_CTX_start(ctx);
 642   totient = BN_CTX_get(ctx);
 643   rem = BN_CTX_get(ctx);
 644   multiple = BN_CTX_get(ctx);
 645   p_plus_q = BN_CTX_get(ctx);
 646   p_minus_q = BN_CTX_get(ctx);
 647
 648   if (totient == NULL || rem == NULL || multiple == NULL || p_plus_q == NULL ||
 649       p_minus_q == NULL) {
 650     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_MALLOC_FAILURE);
 651     goto err;
 652   }
 653
 654   /* ed-1 is a small multiple of φ(n). */
 655   if (!BN_mul(totient, rsa->e, rsa->d, ctx) ||
 656       !BN_sub_word(totient, 1) ||
 657       /* φ(n) =
 658        * pq - p - q + 1 =
 659        * n - (p + q) + 1
 660        *
 661        * Thus n is a reasonable estimate for φ(n). So, (ed-1)/n will be very
 662        * close. But, when we calculate the quotient, we'll be truncating it
 663        * because we discard the remainder. Thus (ed-1)/multiple will be >= n,
 664        * which the totient cannot be. So we add one to the estimate.
 665        *
 666        * Consider ed-1 as:
 667        *
 668        * multiple * (n - (p+q) + 1) =
 669        * multiple*n - multiple*(p+q) + multiple
 670        *
 671        * When we divide by n, the first term becomes multiple and, since
 672        * multiple and p+q is tiny compared to n, the second and third terms can
 673        * be ignored. Thus I claim that subtracting one from the estimate is
 674        * sufficient. */
 675       !BN_div(multiple, NULL, totient, rsa->n, ctx) ||
 676       !BN_add_word(multiple, 1) ||
 677       !BN_div(totient, rem, totient, multiple, ctx)) {
 678     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_BN_LIB);
 679     goto err;
 680   }
 681
 682   if (!BN_is_zero(rem)) {
 683     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, RSA_R_BAD_RSA_PARAMETERS);
 684     goto err;
 685   }
 686
 687   rsa->p = BN_new();
 688   rsa->q = BN_new();
 689   rsa->dmp1 = BN_new();
 690   rsa->dmq1 = BN_new();
 691   rsa->iqmp = BN_new();
 692   if (rsa->p == NULL || rsa->q == NULL || rsa->dmp1 == NULL || rsa->dmq1 ==
 693       NULL || rsa->iqmp == NULL) {
 694     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_MALLOC_FAILURE);
 695     goto err;
 696   }
 697
 698   /* φ(n) = n - (p + q) + 1 =>
 699    * n - totient + 1 = p + q */
 700   if (!BN_sub(p_plus_q, rsa->n, totient) ||
 701       !BN_add_word(p_plus_q, 1) ||
 702       /* p - q = sqrt((p+q)^2 - 4n) */
 703       !BN_sqr(rem, p_plus_q, ctx) ||
 704       !BN_lshift(multiple, rsa->n, 2) ||
 705       !BN_sub(rem, rem, multiple) ||
 706       !BN_sqrt(p_minus_q, rem, ctx) ||
 707       /* q is 1/2 (p+q)-(p-q) */
 708       !BN_sub(rsa->q, p_plus_q, p_minus_q) ||
 709       !BN_rshift1(rsa->q, rsa->q) ||
 710       !BN_div(rsa->p, NULL, rsa->n, rsa->q, ctx) ||
 711       !BN_mul(multiple, rsa->p, rsa->q, ctx)) {
 712     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_BN_LIB);
 713     goto err;
 714   }
 715
 716   if (BN_cmp(multiple, rsa->n) != 0) {
 717     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, RSA_R_INTERNAL_ERROR);
 718     goto err;
 719   }
 720
 721   if (!BN_sub(rem, rsa->p, BN_value_one()) ||
 722       !BN_mod(rsa->dmp1, rsa->d, rem, ctx) ||
 723       !BN_sub(rem, rsa->q, BN_value_one()) ||
 724       !BN_mod(rsa->dmq1, rsa->d, rem, ctx) ||
 725       !BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx)) {
 726     OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_BN_LIB);
 727     goto err;
 728   }
 729
 730   ok = 1;
 731
 732 err:
 733   BN_CTX_end(ctx);
 734   BN_CTX_free(ctx);
 735   if (!ok) {
 736     bn_free_and_null(&rsa->p);
 737     bn_free_and_null(&rsa->q);
 738     bn_free_and_null(&rsa->dmp1);
 739     bn_free_and_null(&rsa->dmq1);
 740     bn_free_and_null(&rsa->iqmp);
 741   }
 742   return ok;
 743 }
 744
 745 int RSA_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
 746                           size_t len) {
 747   if (rsa->meth->private_transform) {
 748     return rsa->meth->private_transform(rsa, out, in, len);
 749   }
 750
 751   return RSA_default_method.private_transform(rsa, out, in, len);
 752 }