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