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