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 <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 } 753
