1 /* $NetBSD: rsa.c,v 1.1.1.2 2014/04/24 12:45:30 pettai Exp $ */ 2 3 /* 4 * Copyright (c) 2006 - 2008 Kungliga Tekniska Högskolan 5 * (Royal Institute of Technology, Stockholm, Sweden). 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * 3. Neither the name of the Institute nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #include <config.h> 37 38 #include <stdio.h> 39 #include <stdlib.h> 40 #include <krb5/krb5-types.h> 41 #include <krb5/rfc2459_asn1.h> 42 43 #include <krb5/der.h> 44 45 #include <rsa.h> 46 47 #include "common.h" 48 49 #include <krb5/roken.h> 50 51 /** 52 * @page page_rsa RSA - public-key cryptography 53 * 54 * RSA is named by its inventors (Ron Rivest, Adi Shamir, and Leonard 55 * Adleman) (published in 1977), patented expired in 21 September 2000. 56 * 57 * 58 * Speed for RSA in seconds 59 * no key blinding 60 * 1000 iteration, 61 * same rsa keys (1024 and 2048) 62 * operation performed each eteration sign, verify, encrypt, decrypt on a random bit pattern 63 * 64 * name 1024 2048 4098 65 * ================================= 66 * gmp: 0.73 6.60 44.80 67 * tfm: 2.45 -- -- 68 * ltm: 3.79 20.74 105.41 (default in hcrypto) 69 * openssl: 4.04 11.90 82.59 70 * cdsa: 15.89 102.89 721.40 71 * imath: 40.62 -- -- 72 * 73 * See the library functions here: @ref hcrypto_rsa 74 */ 75 76 /** 77 * Same as RSA_new_method() using NULL as engine. 78 * 79 * @return a newly allocated RSA object. Free with RSA_free(). 80 * 81 * @ingroup hcrypto_rsa 82 */ 83 84 RSA * 85 RSA_new(void) 86 { 87 return RSA_new_method(NULL); 88 } 89 90 /** 91 * Allocate a new RSA object using the engine, if NULL is specified as 92 * the engine, use the default RSA engine as returned by 93 * ENGINE_get_default_RSA(). 94 * 95 * @param engine Specific what ENGINE RSA provider should be used. 96 * 97 * @return a newly allocated RSA object. Free with RSA_free(). 98 * 99 * @ingroup hcrypto_rsa 100 */ 101 102 RSA * 103 RSA_new_method(ENGINE *engine) 104 { 105 RSA *rsa; 106 107 rsa = calloc(1, sizeof(*rsa)); 108 if (rsa == NULL) 109 return NULL; 110 111 rsa->references = 1; 112 113 if (engine) { 114 ENGINE_up_ref(engine); 115 rsa->engine = engine; 116 } else { 117 rsa->engine = ENGINE_get_default_RSA(); 118 } 119 120 if (rsa->engine) { 121 rsa->meth = ENGINE_get_RSA(rsa->engine); 122 if (rsa->meth == NULL) { 123 ENGINE_finish(engine); 124 free(rsa); 125 return 0; 126 } 127 } 128 129 if (rsa->meth == NULL) 130 rsa->meth = rk_UNCONST(RSA_get_default_method()); 131 132 (*rsa->meth->init)(rsa); 133 134 return rsa; 135 } 136 137 /** 138 * Free an allocation RSA object. 139 * 140 * @param rsa the RSA object to free. 141 * @ingroup hcrypto_rsa 142 */ 143 144 void 145 RSA_free(RSA *rsa) 146 { 147 if (rsa->references <= 0) 148 abort(); 149 150 if (--rsa->references > 0) 151 return; 152 153 (*rsa->meth->finish)(rsa); 154 155 if (rsa->engine) 156 ENGINE_finish(rsa->engine); 157 158 #define free_if(f) if (f) { BN_free(f); } 159 free_if(rsa->n); 160 free_if(rsa->e); 161 free_if(rsa->d); 162 free_if(rsa->p); 163 free_if(rsa->q); 164 free_if(rsa->dmp1); 165 free_if(rsa->dmq1); 166 free_if(rsa->iqmp); 167 #undef free_if 168 169 memset(rsa, 0, sizeof(*rsa)); 170 free(rsa); 171 } 172 173 /** 174 * Add an extra reference to the RSA object. The object should be free 175 * with RSA_free() to drop the reference. 176 * 177 * @param rsa the object to add reference counting too. 178 * 179 * @return the current reference count, can't safely be used except 180 * for debug printing. 181 * 182 * @ingroup hcrypto_rsa 183 */ 184 185 int 186 RSA_up_ref(RSA *rsa) 187 { 188 return ++rsa->references; 189 } 190 191 /** 192 * Return the RSA_METHOD used for this RSA object. 193 * 194 * @param rsa the object to get the method from. 195 * 196 * @return the method used for this RSA object. 197 * 198 * @ingroup hcrypto_rsa 199 */ 200 201 const RSA_METHOD * 202 RSA_get_method(const RSA *rsa) 203 { 204 return rsa->meth; 205 } 206 207 /** 208 * Set a new method for the RSA keypair. 209 * 210 * @param rsa rsa parameter. 211 * @param method the new method for the RSA parameter. 212 * 213 * @return 1 on success. 214 * 215 * @ingroup hcrypto_rsa 216 */ 217 218 int 219 RSA_set_method(RSA *rsa, const RSA_METHOD *method) 220 { 221 (*rsa->meth->finish)(rsa); 222 223 if (rsa->engine) { 224 ENGINE_finish(rsa->engine); 225 rsa->engine = NULL; 226 } 227 228 rsa->meth = method; 229 (*rsa->meth->init)(rsa); 230 return 1; 231 } 232 233 /** 234 * Set the application data for the RSA object. 235 * 236 * @param rsa the rsa object to set the parameter for 237 * @param arg the data object to store 238 * 239 * @return 1 on success. 240 * 241 * @ingroup hcrypto_rsa 242 */ 243 244 int 245 RSA_set_app_data(RSA *rsa, void *arg) 246 { 247 rsa->ex_data.sk = arg; 248 return 1; 249 } 250 251 /** 252 * Get the application data for the RSA object. 253 * 254 * @param rsa the rsa object to get the parameter for 255 * 256 * @return the data object 257 * 258 * @ingroup hcrypto_rsa 259 */ 260 261 void * 262 RSA_get_app_data(const RSA *rsa) 263 { 264 return rsa->ex_data.sk; 265 } 266 267 int 268 RSA_check_key(const RSA *key) 269 { 270 static const unsigned char inbuf[] = "hello, world!"; 271 RSA *rsa = rk_UNCONST(key); 272 void *buffer; 273 int ret; 274 275 /* 276 * XXX I have no clue how to implement this w/o a bignum library. 277 * Well, when we have a RSA key pair, we can try to encrypt/sign 278 * and then decrypt/verify. 279 */ 280 281 if ((rsa->d == NULL || rsa->n == NULL) && 282 (rsa->p == NULL || rsa->q || rsa->dmp1 == NULL || rsa->dmq1 == NULL || rsa->iqmp == NULL)) 283 return 0; 284 285 buffer = malloc(RSA_size(rsa)); 286 if (buffer == NULL) 287 return 0; 288 289 ret = RSA_private_encrypt(sizeof(inbuf), inbuf, buffer, 290 rsa, RSA_PKCS1_PADDING); 291 if (ret == -1) { 292 free(buffer); 293 return 0; 294 } 295 296 ret = RSA_public_decrypt(ret, buffer, buffer, 297 rsa, RSA_PKCS1_PADDING); 298 if (ret == -1) { 299 free(buffer); 300 return 0; 301 } 302 303 if (ret == sizeof(inbuf) && ct_memcmp(buffer, inbuf, sizeof(inbuf)) == 0) { 304 free(buffer); 305 return 1; 306 } 307 free(buffer); 308 return 0; 309 } 310 311 int 312 RSA_size(const RSA *rsa) 313 { 314 return BN_num_bytes(rsa->n); 315 } 316 317 #define RSAFUNC(name, body) \ 318 int \ 319 name(int flen,const unsigned char* f, unsigned char* t, RSA* r, int p){\ 320 return body; \ 321 } 322 323 RSAFUNC(RSA_public_encrypt, (r)->meth->rsa_pub_enc(flen, f, t, r, p)) 324 RSAFUNC(RSA_public_decrypt, (r)->meth->rsa_pub_dec(flen, f, t, r, p)) 325 RSAFUNC(RSA_private_encrypt, (r)->meth->rsa_priv_enc(flen, f, t, r, p)) 326 RSAFUNC(RSA_private_decrypt, (r)->meth->rsa_priv_dec(flen, f, t, r, p)) 327 328 static const heim_octet_string null_entry_oid = { 2, rk_UNCONST("\x05\x00") }; 329 330 static const unsigned sha1_oid_tree[] = { 1, 3, 14, 3, 2, 26 }; 331 static const AlgorithmIdentifier _signature_sha1_data = { 332 { 6, rk_UNCONST(sha1_oid_tree) }, rk_UNCONST(&null_entry_oid) 333 }; 334 static const unsigned sha256_oid_tree[] = { 2, 16, 840, 1, 101, 3, 4, 2, 1 }; 335 static const AlgorithmIdentifier _signature_sha256_data = { 336 { 9, rk_UNCONST(sha256_oid_tree) }, rk_UNCONST(&null_entry_oid) 337 }; 338 static const unsigned md5_oid_tree[] = { 1, 2, 840, 113549, 2, 5 }; 339 static const AlgorithmIdentifier _signature_md5_data = { 340 { 6, rk_UNCONST(md5_oid_tree) }, rk_UNCONST(&null_entry_oid) 341 }; 342 343 344 int 345 RSA_sign(int type, const unsigned char *from, unsigned int flen, 346 unsigned char *to, unsigned int *tlen, RSA *rsa) 347 { 348 if (rsa->meth->rsa_sign) 349 return rsa->meth->rsa_sign(type, from, flen, to, tlen, rsa); 350 351 if (rsa->meth->rsa_priv_enc) { 352 heim_octet_string indata; 353 DigestInfo di; 354 size_t size; 355 int ret; 356 357 memset(&di, 0, sizeof(di)); 358 359 if (type == NID_sha1) { 360 di.digestAlgorithm = _signature_sha1_data; 361 } else if (type == NID_md5) { 362 di.digestAlgorithm = _signature_md5_data; 363 } else if (type == NID_sha256) { 364 di.digestAlgorithm = _signature_sha256_data; 365 } else 366 return -1; 367 368 di.digest.data = rk_UNCONST(from); 369 di.digest.length = flen; 370 371 ASN1_MALLOC_ENCODE(DigestInfo, 372 indata.data, 373 indata.length, 374 &di, 375 &size, 376 ret); 377 if (ret) 378 return ret; 379 if (indata.length != size) 380 abort(); 381 382 ret = rsa->meth->rsa_priv_enc(indata.length, indata.data, to, 383 rsa, RSA_PKCS1_PADDING); 384 free(indata.data); 385 if (ret > 0) { 386 *tlen = ret; 387 ret = 1; 388 } else 389 ret = 0; 390 391 return ret; 392 } 393 394 return 0; 395 } 396 397 int 398 RSA_verify(int type, const unsigned char *from, unsigned int flen, 399 unsigned char *sigbuf, unsigned int siglen, RSA *rsa) 400 { 401 if (rsa->meth->rsa_verify) 402 return rsa->meth->rsa_verify(type, from, flen, sigbuf, siglen, rsa); 403 404 if (rsa->meth->rsa_pub_dec) { 405 const AlgorithmIdentifier *digest_alg; 406 void *data; 407 DigestInfo di; 408 size_t size; 409 int ret, ret2; 410 411 data = malloc(RSA_size(rsa)); 412 if (data == NULL) 413 return -1; 414 415 memset(&di, 0, sizeof(di)); 416 417 ret = rsa->meth->rsa_pub_dec(siglen, sigbuf, data, rsa, RSA_PKCS1_PADDING); 418 if (ret <= 0) { 419 free(data); 420 return -2; 421 } 422 423 ret2 = decode_DigestInfo(data, ret, &di, &size); 424 free(data); 425 if (ret2 != 0) 426 return -3; 427 if (ret != size) { 428 free_DigestInfo(&di); 429 return -4; 430 } 431 432 if (flen != di.digest.length || memcmp(di.digest.data, from, flen) != 0) { 433 free_DigestInfo(&di); 434 return -5; 435 } 436 437 if (type == NID_sha1) { 438 digest_alg = &_signature_sha1_data; 439 } else if (type == NID_md5) { 440 digest_alg = &_signature_md5_data; 441 } else if (type == NID_sha256) { 442 digest_alg = &_signature_sha256_data; 443 } else { 444 free_DigestInfo(&di); 445 return -1; 446 } 447 448 ret = der_heim_oid_cmp(&digest_alg->algorithm, 449 &di.digestAlgorithm.algorithm); 450 free_DigestInfo(&di); 451 452 if (ret != 0) 453 return 0; 454 return 1; 455 } 456 457 return 0; 458 } 459 460 /* 461 * A NULL RSA_METHOD that returns failure for all operations. This is 462 * used as the default RSA method if we don't have any native 463 * support. 464 */ 465 466 static RSAFUNC(null_rsa_public_encrypt, -1) 467 static RSAFUNC(null_rsa_public_decrypt, -1) 468 static RSAFUNC(null_rsa_private_encrypt, -1) 469 static RSAFUNC(null_rsa_private_decrypt, -1) 470 471 /* 472 * 473 */ 474 475 int 476 RSA_generate_key_ex(RSA *r, int bits, BIGNUM *e, BN_GENCB *cb) 477 { 478 if (r->meth->rsa_keygen) 479 return (*r->meth->rsa_keygen)(r, bits, e, cb); 480 return 0; 481 } 482 483 484 /* 485 * 486 */ 487 488 static int 489 null_rsa_init(RSA *rsa) 490 { 491 return 1; 492 } 493 494 static int 495 null_rsa_finish(RSA *rsa) 496 { 497 return 1; 498 } 499 500 static const RSA_METHOD rsa_null_method = { 501 "hcrypto null RSA", 502 null_rsa_public_encrypt, 503 null_rsa_public_decrypt, 504 null_rsa_private_encrypt, 505 null_rsa_private_decrypt, 506 NULL, 507 NULL, 508 null_rsa_init, 509 null_rsa_finish, 510 0, 511 NULL, 512 NULL, 513 NULL 514 }; 515 516 const RSA_METHOD * 517 RSA_null_method(void) 518 { 519 return &rsa_null_method; 520 } 521 522 extern const RSA_METHOD hc_rsa_gmp_method; 523 extern const RSA_METHOD hc_rsa_tfm_method; 524 extern const RSA_METHOD hc_rsa_ltm_method; 525 static const RSA_METHOD *default_rsa_method = &hc_rsa_ltm_method; 526 527 528 const RSA_METHOD * 529 RSA_get_default_method(void) 530 { 531 return default_rsa_method; 532 } 533 534 void 535 RSA_set_default_method(const RSA_METHOD *meth) 536 { 537 default_rsa_method = meth; 538 } 539 540 /* 541 * 542 */ 543 544 RSA * 545 d2i_RSAPrivateKey(RSA *rsa, const unsigned char **pp, size_t len) 546 { 547 RSAPrivateKey data; 548 RSA *k = rsa; 549 size_t size; 550 int ret; 551 552 ret = decode_RSAPrivateKey(*pp, len, &data, &size); 553 if (ret) 554 return NULL; 555 556 *pp += size; 557 558 if (k == NULL) { 559 k = RSA_new(); 560 if (k == NULL) { 561 free_RSAPrivateKey(&data); 562 return NULL; 563 } 564 } 565 566 k->n = _hc_integer_to_BN(&data.modulus, NULL); 567 k->e = _hc_integer_to_BN(&data.publicExponent, NULL); 568 k->d = _hc_integer_to_BN(&data.privateExponent, NULL); 569 k->p = _hc_integer_to_BN(&data.prime1, NULL); 570 k->q = _hc_integer_to_BN(&data.prime2, NULL); 571 k->dmp1 = _hc_integer_to_BN(&data.exponent1, NULL); 572 k->dmq1 = _hc_integer_to_BN(&data.exponent2, NULL); 573 k->iqmp = _hc_integer_to_BN(&data.coefficient, NULL); 574 free_RSAPrivateKey(&data); 575 576 if (k->n == NULL || k->e == NULL || k->d == NULL || k->p == NULL || 577 k->q == NULL || k->dmp1 == NULL || k->dmq1 == NULL || k->iqmp == NULL) 578 { 579 RSA_free(k); 580 return NULL; 581 } 582 583 return k; 584 } 585 586 int 587 i2d_RSAPrivateKey(RSA *rsa, unsigned char **pp) 588 { 589 RSAPrivateKey data; 590 size_t size; 591 int ret; 592 593 if (rsa->n == NULL || rsa->e == NULL || rsa->d == NULL || rsa->p == NULL || 594 rsa->q == NULL || rsa->dmp1 == NULL || rsa->dmq1 == NULL || 595 rsa->iqmp == NULL) 596 return -1; 597 598 memset(&data, 0, sizeof(data)); 599 600 ret = _hc_BN_to_integer(rsa->n, &data.modulus); 601 ret |= _hc_BN_to_integer(rsa->e, &data.publicExponent); 602 ret |= _hc_BN_to_integer(rsa->d, &data.privateExponent); 603 ret |= _hc_BN_to_integer(rsa->p, &data.prime1); 604 ret |= _hc_BN_to_integer(rsa->q, &data.prime2); 605 ret |= _hc_BN_to_integer(rsa->dmp1, &data.exponent1); 606 ret |= _hc_BN_to_integer(rsa->dmq1, &data.exponent2); 607 ret |= _hc_BN_to_integer(rsa->iqmp, &data.coefficient); 608 if (ret) { 609 free_RSAPrivateKey(&data); 610 return -1; 611 } 612 613 if (pp == NULL) { 614 size = length_RSAPrivateKey(&data); 615 free_RSAPrivateKey(&data); 616 } else { 617 void *p; 618 size_t len; 619 620 ASN1_MALLOC_ENCODE(RSAPrivateKey, p, len, &data, &size, ret); 621 free_RSAPrivateKey(&data); 622 if (ret) 623 return -1; 624 if (len != size) 625 abort(); 626 627 memcpy(*pp, p, size); 628 free(p); 629 630 *pp += size; 631 632 } 633 return size; 634 } 635 636 int 637 i2d_RSAPublicKey(RSA *rsa, unsigned char **pp) 638 { 639 RSAPublicKey data; 640 size_t size; 641 int ret; 642 643 memset(&data, 0, sizeof(data)); 644 645 if (_hc_BN_to_integer(rsa->n, &data.modulus) || 646 _hc_BN_to_integer(rsa->e, &data.publicExponent)) 647 { 648 free_RSAPublicKey(&data); 649 return -1; 650 } 651 652 if (pp == NULL) { 653 size = length_RSAPublicKey(&data); 654 free_RSAPublicKey(&data); 655 } else { 656 void *p; 657 size_t len; 658 659 ASN1_MALLOC_ENCODE(RSAPublicKey, p, len, &data, &size, ret); 660 free_RSAPublicKey(&data); 661 if (ret) 662 return -1; 663 if (len != size) 664 abort(); 665 666 memcpy(*pp, p, size); 667 free(p); 668 669 *pp += size; 670 } 671 672 return size; 673 } 674 675 RSA * 676 d2i_RSAPublicKey(RSA *rsa, const unsigned char **pp, size_t len) 677 { 678 RSAPublicKey data; 679 RSA *k = rsa; 680 size_t size; 681 int ret; 682 683 ret = decode_RSAPublicKey(*pp, len, &data, &size); 684 if (ret) 685 return NULL; 686 687 *pp += size; 688 689 if (k == NULL) { 690 k = RSA_new(); 691 if (k == NULL) { 692 free_RSAPublicKey(&data); 693 return NULL; 694 } 695 } 696 697 k->n = _hc_integer_to_BN(&data.modulus, NULL); 698 k->e = _hc_integer_to_BN(&data.publicExponent, NULL); 699 700 free_RSAPublicKey(&data); 701 702 if (k->n == NULL || k->e == NULL) { 703 RSA_free(k); 704 return NULL; 705 } 706 707 return k; 708 } 709