crypto/external/bsd/heimdal/dist/lib/hcrypto/rsa.c

   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 }