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