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