source4/heimdal/lib/hcrypto/rsa-ltm.c

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