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