crypto/dist/heimdal/lib/hcrypto/rsa-imath.c

   1 /*
   2  * Copyright (c) 2006 - 2007 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #ifdef HAVE_CONFIG_H
  35 #include <config.h>
  36 #endif
  37
  38 __RCSID("$Heimdal: rsa-imath.c 21154 2007-06-18 21:58:12Z lha $"
  39         "$NetBSD$");
  40
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <krb5-types.h>
  44 #include <assert.h>
  45
  46 #include <rsa.h>
  47
  48 #include <roken.h>
  49
  50 #include "imath/imath.h"
  51 #include "imath/iprime.h"
  52
  53 static void
  54 BN2mpz(mpz_t *s, const BIGNUM *bn)
  55 {
  56     size_t len;
  57     void *p;
  58
  59     mp_int_init(s);
  60
  61     len = BN_num_bytes(bn);
  62     p = malloc(len);
  63     BN_bn2bin(bn, p);
  64     mp_int_read_unsigned(s, p, len);
  65     free(p);
  66 }
  67
  68 static BIGNUM *
  69 mpz2BN(mpz_t *s)
  70 {
  71     size_t size;
  72     BIGNUM *bn;
  73     void *p;
  74
  75     size = mp_int_unsigned_len(s);
  76     p = malloc(size);
  77     if (p == NULL && size != 0)
  78         return NULL;
  79     mp_int_to_unsigned(s, p, size);
  80
  81     bn = BN_bin2bn(p, size, NULL);
  82     free(p);
  83     return bn;
  84 }
  85
  86 static int random_num(mp_int, size_t);
  87
  88 static void
  89 setup_blind(mp_int n, mp_int b, mp_int bi)
  90 {
  91     mp_int_init(b);
  92     mp_int_init(bi);
  93     random_num(b, mp_int_count_bits(n));
  94     mp_int_mod(b, n, b);
  95     mp_int_invmod(b, n, bi);
  96 }
  97
  98 static void
  99 blind(mp_int in, mp_int b, mp_int e, mp_int n)
 100 {
 101     mpz_t t1;
 102     mp_int_init(&t1);
 103     /* in' = (in * b^e) mod n */
 104     mp_int_exptmod(b, e, n, &t1);
 105     mp_int_mul(&t1, in, in);
 106     mp_int_mod(in, n, in);
 107     mp_int_clear(&t1);
 108 }
 109
 110 static void
 111 unblind(mp_int out, mp_int bi, mp_int n)
 112 {
 113     /* out' = (out * 1/b) mod n */
 114     mp_int_mul(out, bi, out);
 115     mp_int_mod(out, n, out);
 116 }
 117
 118 static mp_result
 119 rsa_private_calculate(mp_int in, mp_int p,  mp_int q,
 120                       mp_int dmp1, mp_int dmq1, mp_int iqmp,
 121                       mp_int out)
 122 {
 123     mpz_t vp, vq, u;
 124     mp_int_init(&vp); mp_int_init(&vq); mp_int_init(&u);
 125
 126     /* vq = c ^ (d mod (q - 1)) mod q */
 127     /* vp = c ^ (d mod (p - 1)) mod p */
 128     mp_int_mod(in, p, &u);
 129     mp_int_exptmod(&u, dmp1, p, &vp);
 130     mp_int_mod(in, q, &u);
 131     mp_int_exptmod(&u, dmq1, q, &vq);
 132
 133     /* C2 = 1/q mod p  (iqmp) */
 134     /* u = (vp - vq)C2 mod p. */
 135     mp_int_sub(&vp, &vq, &u);
 136     if (mp_int_compare_zero(&u) < 0)
 137         mp_int_add(&u, p, &u);
 138     mp_int_mul(&u, iqmp, &u);
 139     mp_int_mod(&u, p, &u);
 140
 141     /* c ^ d mod n = vq + u q */
 142     mp_int_mul(&u, q, &u);
 143     mp_int_add(&u, &vq, out);
 144
 145     mp_int_clear(&vp);
 146     mp_int_clear(&vq);
 147     mp_int_clear(&u);
 148
 149     return MP_OK;
 150 }
 151
 152 /*
 153  *
 154  */
 155
 156 static int
 157 imath_rsa_public_encrypt(int flen, const unsigned char* from,
 158                         unsigned char* to, RSA* rsa, int padding)
 159 {
 160     unsigned char *p, *p0;
 161     mp_result res;
 162     size_t size, padlen;
 163     mpz_t enc, dec, n, e;
 164
 165     if (padding != RSA_PKCS1_PADDING)
 166         return -1;
 167
 168     size = RSA_size(rsa);
 169
 170     if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
 171         return -2;
 172
 173     BN2mpz(&n, rsa->n);
 174     BN2mpz(&e, rsa->e);
 175
 176     p = p0 = malloc(size - 1);
 177     if (p0 == NULL) {
 178         mp_int_clear(&e);
 179         mp_int_clear(&n);
 180         return -3;
 181     }
 182
 183     padlen = size - flen - 3;
 184
 185     *p++ = 2;
 186     if (RAND_bytes(p, padlen) != 1) {
 187         mp_int_clear(&e);
 188         mp_int_clear(&n);
 189         free(p0);
 190         return -4;
 191     }
 192     while(padlen) {
 193         if (*p == 0)
 194             *p = 1;
 195         padlen--;
 196         p++;
 197     }
 198     *p++ = 0;
 199     memcpy(p, from, flen);
 200     p += flen;
 201     assert((p - p0) == size - 1);
 202
 203     mp_int_init(&enc);
 204     mp_int_init(&dec);
 205     mp_int_read_unsigned(&dec, p0, size - 1);
 206     free(p0);
 207
 208     res = mp_int_exptmod(&dec, &e, &n, &enc);
 209
 210     mp_int_clear(&dec);
 211     mp_int_clear(&e);
 212     mp_int_clear(&n);
 213     {
 214         size_t ssize;
 215         ssize = mp_int_unsigned_len(&enc);
 216         assert(size >= ssize);
 217         mp_int_to_unsigned(&enc, to, ssize);
 218         size = ssize;
 219     }
 220     mp_int_clear(&enc);
 221
 222     return size;
 223 }
 224
 225 static int
 226 imath_rsa_public_decrypt(int flen, const unsigned char* from,
 227                          unsigned char* to, RSA* rsa, int padding)
 228 {
 229     unsigned char *p;
 230     mp_result res;
 231     size_t size;
 232     mpz_t s, us, n, e;
 233
 234     if (padding != RSA_PKCS1_PADDING)
 235         return -1;
 236
 237     if (flen > RSA_size(rsa))
 238         return -2;
 239
 240     BN2mpz(&n, rsa->n);
 241     BN2mpz(&e, rsa->e);
 242
 243 #if 0
 244     /* Check that the exponent is larger then 3 */
 245     if (mp_int_compare_value(&e, 3) <= 0) {
 246         mp_int_clear(&n);
 247         mp_int_clear(&e);
 248         return -3;
 249     }
 250 #endif
 251
 252     mp_int_init(&s);
 253     mp_int_init(&us);
 254     mp_int_read_unsigned(&s, rk_UNCONST(from), flen);
 255
 256     if (mp_int_compare(&s, &n) >= 0) {
 257         mp_int_clear(&n);
 258         mp_int_clear(&e);
 259         return -4;
 260     }
 261
 262     res = mp_int_exptmod(&s, &e, &n, &us);
 263
 264     mp_int_clear(&s);
 265     mp_int_clear(&n);
 266     mp_int_clear(&e);
 267
 268     if (res != MP_OK)
 269         return -5;
 270     p = to;
 271
 272
 273     size = mp_int_unsigned_len(&us);
 274     assert(size <= RSA_size(rsa));
 275     mp_int_to_unsigned(&us, p, size);
 276
 277     mp_int_clear(&us);
 278
 279     /* head zero was skipped by mp_int_to_unsigned */
 280     if (*p == 0)
 281         return -6;
 282     if (*p != 1)
 283         return -7;
 284     size--; p++;
 285     while (size && *p == 0xff) {
 286         size--; p++;
 287     }
 288     if (size == 0 || *p != 0)
 289         return -8;
 290     size--; p++;
 291
 292     memmove(to, p, size);
 293
 294     return size;
 295 }
 296
 297 static int
 298 imath_rsa_private_encrypt(int flen, const unsigned char* from,
 299                           unsigned char* to, RSA* rsa, int padding)
 300 {
 301     unsigned char *p, *p0;
 302     mp_result res;
 303     size_t size;
 304     mpz_t in, out, n, e, b, bi;
 305     int blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
 306
 307     if (padding != RSA_PKCS1_PADDING)
 308         return -1;
 309
 310     size = RSA_size(rsa);
 311
 312     if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
 313         return -2;
 314
 315     p0 = p = malloc(size);
 316     *p++ = 0;
 317     *p++ = 1;
 318     memset(p, 0xff, size - flen - 3);
 319     p += size - flen - 3;
 320     *p++ = 0;
 321     memcpy(p, from, flen);
 322     p += flen;
 323     assert((p - p0) == size);
 324
 325     BN2mpz(&n, rsa->n);
 326     BN2mpz(&e, rsa->e);
 327
 328     mp_int_init(&in);
 329     mp_int_init(&out);
 330     mp_int_read_unsigned(&in, p0, size);
 331     free(p0);
 332
 333     if(mp_int_compare_zero(&in) < 0 ||
 334        mp_int_compare(&in, &n) >= 0) {
 335         size = 0;
 336         goto out;
 337     }
 338
 339     if (blinding) {
 340         setup_blind(&n, &b, &bi);
 341         blind(&in, &b, &e, &n);
 342     }
 343
 344     if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
 345         mpz_t p, q, dmp1, dmq1, iqmp;
 346
 347         BN2mpz(&p, rsa->p);
 348         BN2mpz(&q, rsa->q);
 349         BN2mpz(&dmp1, rsa->dmp1);
 350         BN2mpz(&dmq1, rsa->dmq1);
 351         BN2mpz(&iqmp, rsa->iqmp);
 352
 353         res = rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
 354
 355         mp_int_clear(&p);
 356         mp_int_clear(&q);
 357         mp_int_clear(&dmp1);
 358         mp_int_clear(&dmq1);
 359         mp_int_clear(&iqmp);
 360     } else {
 361         mpz_t d;
 362
 363         BN2mpz(&d, rsa->d);
 364         res = mp_int_exptmod(&in, &d, &n, &out);
 365         mp_int_clear(&d);
 366         if (res != MP_OK) {
 367             size = 0;
 368             goto out;
 369         }
 370     }
 371
 372     if (blinding) {
 373         unblind(&out, &bi, &n);
 374         mp_int_clear(&b);
 375         mp_int_clear(&bi);
 376     }
 377
 378     {
 379         size_t ssize;
 380         ssize = mp_int_unsigned_len(&out);
 381         assert(size >= ssize);
 382         mp_int_to_unsigned(&out, to, size);
 383         size = ssize;
 384     }
 385
 386 out:
 387     mp_int_clear(&e);
 388     mp_int_clear(&n);
 389     mp_int_clear(&in);
 390     mp_int_clear(&out);
 391
 392     return size;
 393 }
 394
 395 static int
 396 imath_rsa_private_decrypt(int flen, const unsigned char* from,
 397                           unsigned char* to, RSA* rsa, int padding)
 398 {
 399     unsigned char *ptr;
 400     mp_result res;
 401     size_t size;
 402     mpz_t in, out, n, e, b, bi;
 403     int blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
 404
 405     if (padding != RSA_PKCS1_PADDING)
 406         return -1;
 407
 408     size = RSA_size(rsa);
 409     if (flen > size)
 410         return -2;
 411
 412     mp_int_init(&in);
 413     mp_int_init(&out);
 414
 415     BN2mpz(&n, rsa->n);
 416     BN2mpz(&e, rsa->e);
 417
 418     res = mp_int_read_unsigned(&in, rk_UNCONST(from), flen);
 419     if (res != MP_OK) {
 420         size = -1;
 421         goto out;
 422     }
 423
 424     if(mp_int_compare_zero(&in) < 0 ||
 425        mp_int_compare(&in, &n) >= 0) {
 426         size = 0;
 427         goto out;
 428     }
 429
 430     if (blinding) {
 431         setup_blind(&n, &b, &bi);
 432         blind(&in, &b, &e, &n);
 433     }
 434
 435     if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
 436         mpz_t p, q, dmp1, dmq1, iqmp;
 437
 438         BN2mpz(&p, rsa->p);
 439         BN2mpz(&q, rsa->q);
 440         BN2mpz(&dmp1, rsa->dmp1);
 441         BN2mpz(&dmq1, rsa->dmq1);
 442         BN2mpz(&iqmp, rsa->iqmp);
 443
 444         res = rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
 445
 446         mp_int_clear(&p);
 447         mp_int_clear(&q);
 448         mp_int_clear(&dmp1);
 449         mp_int_clear(&dmq1);
 450         mp_int_clear(&iqmp);
 451     } else {
 452         mpz_t d;
 453
 454         if(mp_int_compare_zero(&in) < 0 ||
 455            mp_int_compare(&in, &n) >= 0)
 456             return MP_RANGE;
 457
 458         BN2mpz(&d, rsa->d);
 459         res = mp_int_exptmod(&in, &d, &n, &out);
 460         mp_int_clear(&d);
 461         if (res != MP_OK) {
 462             size = 0;
 463             goto out;
 464         }
 465     }
 466
 467     if (blinding) {
 468         unblind(&out, &bi, &n);
 469         mp_int_clear(&b);
 470         mp_int_clear(&bi);
 471     }
 472
 473     ptr = to;
 474     {
 475         size_t ssize;
 476         ssize = mp_int_unsigned_len(&out);
 477         assert(size >= ssize);
 478         mp_int_to_unsigned(&out, ptr, ssize);
 479         size = ssize;
 480     }
 481
 482     /* head zero was skipped by mp_int_to_unsigned */
 483     if (*ptr != 2)
 484         return -3;
 485     size--; ptr++;
 486     while (size && *ptr != 0) {
 487         size--; ptr++;
 488     }
 489     if (size == 0)
 490         return -4;
 491     size--; ptr++;
 492
 493     memmove(to, ptr, size);
 494
 495 out:
 496     mp_int_clear(&e);
 497     mp_int_clear(&n);
 498     mp_int_clear(&in);
 499     mp_int_clear(&out);
 500
 501     return size;
 502 }
 503
 504 static int
 505 random_num(mp_int num, size_t len)
 506 {
 507     unsigned char *p;
 508     mp_result res;
 509
 510     len = (len + 7) / 8;
 511     p = malloc(len);
 512     if (p == NULL)
 513         return 1;
 514     if (RAND_bytes(p, len) != 1) {
 515         free(p);
 516         return 1;
 517     }
 518     res = mp_int_read_unsigned(num, p, len);
 519     free(p);
 520     if (res != MP_OK)
 521         return 1;
 522     return 0;
 523 }
 524
 525 #define CHECK(f, v) if ((f) != (v)) { goto out; }
 526
 527 static int
 528 imath_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
 529 {
 530     mpz_t el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
 531     int counter, ret;
 532
 533     if (bits < 789)
 534         return -1;
 535
 536     ret = -1;
 537
 538     mp_int_init(&el);
 539     mp_int_init(&p);
 540     mp_int_init(&q);
 541     mp_int_init(&n);
 542     mp_int_init(&d);
 543     mp_int_init(&dmp1);
 544     mp_int_init(&dmq1);
 545     mp_int_init(&iqmp);
 546     mp_int_init(&t1);
 547     mp_int_init(&t2);
 548     mp_int_init(&t3);
 549
 550     BN2mpz(&el, e);
 551
 552     /* generate p and q so that p != q and bits(pq) ~ bits */
 553     counter = 0;
 554     do {
 555         BN_GENCB_call(cb, 2, counter++);
 556         CHECK(random_num(&p, bits / 2 + 1), 0);
 557         CHECK(mp_int_find_prime(&p), MP_TRUE);
 558
 559         CHECK(mp_int_sub_value(&p, 1, &t1), MP_OK);
 560         CHECK(mp_int_gcd(&t1, &el, &t2), MP_OK);
 561     } while(mp_int_compare_value(&t2, 1) != 0);
 562
 563     BN_GENCB_call(cb, 3, 0);
 564
 565     counter = 0;
 566     do {
 567         BN_GENCB_call(cb, 2, counter++);
 568         CHECK(random_num(&q, bits / 2 + 1), 0);
 569         CHECK(mp_int_find_prime(&q), MP_TRUE);
 570
 571         if (mp_int_compare(&p, &q) == 0) /* don't let p and q be the same */
 572             continue;
 573
 574         CHECK(mp_int_sub_value(&q, 1, &t1), MP_OK);
 575         CHECK(mp_int_gcd(&t1, &el, &t2), MP_OK);
 576     } while(mp_int_compare_value(&t2, 1) != 0);
 577
 578     /* make p > q */
 579     if (mp_int_compare(&p, &q) < 0)
 580         mp_int_swap(&p, &q);
 581
 582     BN_GENCB_call(cb, 3, 1);
 583
 584     /* calculate n,             n = p * q */
 585     CHECK(mp_int_mul(&p, &q, &n), MP_OK);
 586
 587     /* calculate d,             d = 1/e mod (p - 1)(q - 1) */
 588     CHECK(mp_int_sub_value(&p, 1, &t1), MP_OK);
 589     CHECK(mp_int_sub_value(&q, 1, &t2), MP_OK);
 590     CHECK(mp_int_mul(&t1, &t2, &t3), MP_OK);
 591     CHECK(mp_int_invmod(&el, &t3, &d), MP_OK);
 592
 593     /* calculate dmp1           dmp1 = d mod (p-1) */
 594     CHECK(mp_int_mod(&d, &t1, &dmp1), MP_OK);
 595     /* calculate dmq1           dmq1 = d mod (q-1) */
 596     CHECK(mp_int_mod(&d, &t2, &dmq1), MP_OK);
 597     /* calculate iqmp           iqmp = 1/q mod p */
 598     CHECK(mp_int_invmod(&q, &p, &iqmp), MP_OK);
 599
 600     /* fill in RSA key */
 601
 602     rsa->e = mpz2BN(&el);
 603     rsa->p = mpz2BN(&p);
 604     rsa->q = mpz2BN(&q);
 605     rsa->n = mpz2BN(&n);
 606     rsa->d = mpz2BN(&d);
 607     rsa->dmp1 = mpz2BN(&dmp1);
 608     rsa->dmq1 = mpz2BN(&dmq1);
 609     rsa->iqmp = mpz2BN(&iqmp);
 610
 611     ret = 1;
 612 out:
 613     mp_int_clear(&el);
 614     mp_int_clear(&p);
 615     mp_int_clear(&q);
 616     mp_int_clear(&n);
 617     mp_int_clear(&d);
 618     mp_int_clear(&dmp1);
 619     mp_int_clear(&dmq1);
 620     mp_int_clear(&iqmp);
 621     mp_int_clear(&t1);
 622     mp_int_clear(&t2);
 623     mp_int_clear(&t3);
 624
 625     return ret;
 626 }
 627
 628 static int
 629 imath_rsa_init(RSA *rsa)
 630 {
 631     return 1;
 632 }
 633
 634 static int
 635 imath_rsa_finish(RSA *rsa)
 636 {
 637     return 1;
 638 }
 639
 640 const RSA_METHOD hc_rsa_imath_method = {
 641     "hcrypto imath RSA",
 642     imath_rsa_public_encrypt,
 643     imath_rsa_public_decrypt,
 644     imath_rsa_private_encrypt,
 645     imath_rsa_private_decrypt,
 646     NULL,
 647     NULL,
 648     imath_rsa_init,
 649     imath_rsa_finish,
 650     0,
 651     NULL,
 652     NULL,
 653     NULL,
 654     imath_rsa_generate_key
 655 };
 656
 657 const RSA_METHOD *
 658 RSA_imath_method(void)
 659 {
 660     return &hc_rsa_imath_method;
 661 }