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, size;
 389     mp_int in, out, n, e, b, bi;
 390     int blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
 391     int do_unblind = 0;
 392
 393     if (padding != RSA_PKCS1_PADDING)
 394         return -1;
 395
 396     size = RSA_size(rsa);
 397     if (flen > size)
 398         return -2;
 399
 400     mp_init_multi(&in, &n, &e, &out, &b, &bi, NULL);
 401
 402     BN2mpz(&n, rsa->n);
 403     BN2mpz(&e, rsa->e);
 404
 405     mp_read_unsigned_bin(&in, rk_UNCONST(from), flen);
 406
 407     if(mp_isneg(&in) || mp_cmp(&in, &n) >= 0) {
 408         size = -2;
 409         goto out;
 410     }
 411
 412     if (blinding) {
 413         setup_blind(&n, &b, &bi);
 414         blind(&in, &b, &e, &n);
 415         do_unblind = 1;
 416     }
 417
 418     if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
 419         mp_int p, q, dmp1, dmq1, iqmp;
 420
 421         mp_init_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
 422
 423         BN2mpz(&p, rsa->p);
 424         BN2mpz(&q, rsa->q);
 425         BN2mpz(&dmp1, rsa->dmp1);
 426         BN2mpz(&dmq1, rsa->dmq1);
 427         BN2mpz(&iqmp, rsa->iqmp);
 428
 429         res = ltm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
 430
 431         mp_clear_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
 432
 433         if (res != 0) {
 434             size = -3;
 435             goto out;
 436         }
 437
 438     } else {
 439         mp_int d;
 440
 441         if(mp_isneg(&in) || mp_cmp(&in, &n) >= 0)
 442             return -4;
 443
 444         BN2mpz(&d, rsa->d);
 445         res = mp_exptmod(&in, &d, &n, &out);
 446         mp_clear(&d);
 447         if (res != 0) {
 448             size = -5;
 449             goto out;
 450         }
 451     }
 452
 453     if (do_unblind)
 454         unblind(&out, &bi, &n);
 455
 456     ptr = to;
 457     {
 458         size_t ssize;
 459         ssize = mp_unsigned_bin_size(&out);
 460         assert(size >= ssize);
 461         mp_to_unsigned_bin(&out, ptr);
 462         size = ssize;
 463     }
 464
 465     /* head zero was skipped by mp_int_to_unsigned */
 466     if (*ptr != 2) {
 467         size = -6;
 468         goto out;
 469     }
 470     size--; ptr++;
 471     while (size && *ptr != 0) {
 472         size--; ptr++;
 473     }
 474     if (size == 0)
 475         return -7;
 476     size--; ptr++;
 477
 478     memmove(to, ptr, size);
 479
 480  out:
 481     mp_clear_multi(&e, &n, &in, &out, &b, &bi, NULL);
 482
 483     return size;
 484 }
 485
 486 static BIGNUM *
 487 mpz2BN(mp_int *s)
 488 {
 489     size_t size;
 490     BIGNUM *bn;
 491     void *p;
 492
 493     size = mp_unsigned_bin_size(s);
 494     p = malloc(size);
 495     if (p == NULL && size != 0)
 496         return NULL;
 497
 498     mp_to_unsigned_bin(s, p);
 499
 500     bn = BN_bin2bn(p, size, NULL);
 501     free(p);
 502     return bn;
 503 }
 504
 505 #define CHECK(f, v) if ((f) != (v)) { goto out; }
 506
 507 static int
 508 ltm_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
 509 {
 510     mp_int el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
 511     int counter, ret, bitsp;
 512
 513     if (bits < 789)
 514         return -1;
 515
 516     bitsp = (bits + 1) / 2;
 517
 518     ret = -1;
 519
 520     mp_init_multi(&el, &p, &q, &n, &d,
 521                   &dmp1, &dmq1, &iqmp,
 522                   &t1, &t2, &t3, NULL);
 523
 524     BN2mpz(&el, e);
 525
 526     /* generate p and q so that p != q and bits(pq) ~ bits */
 527     counter = 0;
 528     do {
 529         BN_GENCB_call(cb, 2, counter++);
 530         CHECK(random_num(&p, bitsp), 0);
 531         CHECK(mp_find_prime(&p), MP_YES);
 532
 533         mp_sub_d(&p, 1, &t1);
 534         mp_gcd(&t1, &el, &t2);
 535     } while(mp_cmp_d(&t2, 1) != 0);
 536
 537     BN_GENCB_call(cb, 3, 0);
 538
 539     counter = 0;
 540     do {
 541         BN_GENCB_call(cb, 2, counter++);
 542         CHECK(random_num(&q, bits - bitsp), 0);
 543         CHECK(mp_find_prime(&q), MP_YES);
 544
 545         if (mp_cmp(&p, &q) == 0) /* don't let p and q be the same */
 546             continue;
 547
 548         mp_sub_d(&q, 1, &t1);
 549         mp_gcd(&t1, &el, &t2);
 550     } while(mp_cmp_d(&t2, 1) != 0);
 551
 552     /* make p > q */
 553     if (mp_cmp(&p, &q) < 0) {
 554         mp_int c;
 555         c = p;
 556         p = q;
 557         q = c;
 558     }
 559
 560     BN_GENCB_call(cb, 3, 1);
 561
 562     /* calculate n,             n = p * q */
 563     mp_mul(&p, &q, &n);
 564
 565     /* calculate d,             d = 1/e mod (p - 1)(q - 1) */
 566     mp_sub_d(&p, 1, &t1);
 567     mp_sub_d(&q, 1, &t2);
 568     mp_mul(&t1, &t2, &t3);
 569     mp_invmod(&el, &t3, &d);
 570
 571     /* calculate dmp1           dmp1 = d mod (p-1) */
 572     mp_mod(&d, &t1, &dmp1);
 573     /* calculate dmq1           dmq1 = d mod (q-1) */
 574     mp_mod(&d, &t2, &dmq1);
 575     /* calculate iqmp           iqmp = 1/q mod p */
 576     mp_invmod(&q, &p, &iqmp);
 577
 578     /* fill in RSA key */
 579
 580     rsa->e = mpz2BN(&el);
 581     rsa->p = mpz2BN(&p);
 582     rsa->q = mpz2BN(&q);
 583     rsa->n = mpz2BN(&n);
 584     rsa->d = mpz2BN(&d);
 585     rsa->dmp1 = mpz2BN(&dmp1);
 586     rsa->dmq1 = mpz2BN(&dmq1);
 587     rsa->iqmp = mpz2BN(&iqmp);
 588
 589     ret = 1;
 590
 591 out:
 592     mp_clear_multi(&el, &p, &q, &n, &d,
 593                    &dmp1, &dmq1, &iqmp,
 594                    &t1, &t2, &t3, NULL);
 595
 596     return ret;
 597 }
 598
 599 static int
 600 ltm_rsa_init(RSA *rsa)
 601 {
 602     return 1;
 603 }
 604
 605 static int
 606 ltm_rsa_finish(RSA *rsa)
 607 {
 608     return 1;
 609 }
 610
 611 const RSA_METHOD hc_rsa_ltm_method = {
 612     "hcrypto ltm RSA",
 613     ltm_rsa_public_encrypt,
 614     ltm_rsa_public_decrypt,
 615     ltm_rsa_private_encrypt,
 616     ltm_rsa_private_decrypt,
 617     NULL,
 618     NULL,
 619     ltm_rsa_init,
 620     ltm_rsa_finish,
 621     0,
 622     NULL,
 623     NULL,
 624     NULL,
 625     ltm_rsa_generate_key
 626 };
 627
 628 const RSA_METHOD *
 629 RSA_ltm_method(void)
 630 {
 631     return &hc_rsa_ltm_method;
 632 }