crypto/external/bsd/heimdal/dist/lib/hcrypto/rsa-gmp.c

   1 /*      $NetBSD: rsa-gmp.c,v 1.1.1.1 2011/04/13 18:14:51 elric Exp $    */
   2
   3 /*
   4  * Copyright (c) 2006 - 2007 Kungliga Tekniska Högskolan
   5  * (Royal Institute of Technology, Stockholm, Sweden).
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  *
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * 3. Neither the name of the Institute nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 #include <config.h>
  37
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40 #include <krb5/krb5-types.h>
  41 #include <assert.h>
  42
  43 #include <rsa.h>
  44
  45 #include <krb5/roken.h>
  46
  47 #ifdef HAVE_GMP
  48
  49 #include <gmp.h>
  50
  51 static void
  52 BN2mpz(mpz_t s, const BIGNUM *bn)
  53 {
  54     size_t len;
  55     void *p;
  56
  57     len = BN_num_bytes(bn);
  58     p = malloc(len);
  59     BN_bn2bin(bn, p);
  60     mpz_init(s);
  61     mpz_import(s, len, 1, 1, 1, 0, p);
  62
  63     free(p);
  64 }
  65
  66
  67 static BIGNUM *
  68 mpz2BN(mpz_t s)
  69 {
  70     size_t size;
  71     BIGNUM *bn;
  72     void *p;
  73
  74     mpz_export(NULL, &size, 1, 1, 1, 0, s);
  75     p = malloc(size);
  76     if (p == NULL && size != 0)
  77         return NULL;
  78     mpz_export(p, &size, 1, 1, 1, 0, s);
  79     bn = BN_bin2bn(p, size, NULL);
  80     free(p);
  81     return bn;
  82 }
  83
  84 static int
  85 rsa_private_calculate(mpz_t in, mpz_t p,  mpz_t q,
  86                       mpz_t dmp1, mpz_t dmq1, mpz_t iqmp,
  87                       mpz_t out)
  88 {
  89     mpz_t vp, vq, u;
  90     mpz_init(vp); mpz_init(vq); mpz_init(u);
  91
  92     /* vq = c ^ (d mod (q - 1)) mod q */
  93     /* vp = c ^ (d mod (p - 1)) mod p */
  94     mpz_fdiv_r(vp, in, p);
  95     mpz_powm(vp, vp, dmp1, p);
  96     mpz_fdiv_r(vq, in, q);
  97     mpz_powm(vq, vq, dmq1, q);
  98
  99     /* C2 = 1/q mod p  (iqmp) */
 100     /* u = (vp - vq)C2 mod p. */
 101     mpz_sub(u, vp, vq);
 102 #if 0
 103     if (mp_int_compare_zero(&u) < 0)
 104         mp_int_add(&u, p, &u);
 105 #endif
 106     mpz_mul(u, iqmp, u);
 107     mpz_fdiv_r(u, u, p);
 108
 109     /* c ^ d mod n = vq + u q */
 110     mpz_mul(u, q, u);
 111     mpz_add(out, u, vq);
 112
 113     mpz_clear(vp);
 114     mpz_clear(vq);
 115     mpz_clear(u);
 116
 117     return 0;
 118 }
 119
 120 /*
 121  *
 122  */
 123
 124 static int
 125 gmp_rsa_public_encrypt(int flen, const unsigned char* from,
 126                         unsigned char* to, RSA* rsa, int padding)
 127 {
 128     unsigned char *p, *p0;
 129     size_t size, padlen;
 130     mpz_t enc, dec, n, e;
 131
 132     if (padding != RSA_PKCS1_PADDING)
 133         return -1;
 134
 135     size = RSA_size(rsa);
 136
 137     if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
 138         return -2;
 139
 140     BN2mpz(n, rsa->n);
 141     BN2mpz(e, rsa->e);
 142
 143     p = p0 = malloc(size - 1);
 144     if (p0 == NULL) {
 145         mpz_clear(e);
 146         mpz_clear(n);
 147         return -3;
 148     }
 149
 150     padlen = size - flen - 3;
 151     assert(padlen >= 8);
 152
 153     *p++ = 2;
 154     if (RAND_bytes(p, padlen) != 1) {
 155         mpz_clear(e);
 156         mpz_clear(n);
 157         free(p0);
 158         return -4;
 159     }
 160     while(padlen) {
 161         if (*p == 0)
 162             *p = 1;
 163         padlen--;
 164         p++;
 165     }
 166     *p++ = 0;
 167     memcpy(p, from, flen);
 168     p += flen;
 169     assert((p - p0) == size - 1);
 170
 171     mpz_init(enc);
 172     mpz_init(dec);
 173     mpz_import(dec, size - 1, 1, 1, 1, 0, p0);
 174     free(p0);
 175
 176     mpz_powm(enc, dec, e, n);
 177
 178     mpz_clear(dec);
 179     mpz_clear(e);
 180     mpz_clear(n);
 181     {
 182         size_t ssize;
 183         mpz_export(to, &ssize, 1, 1, 1, 0, enc);
 184         assert(size >= ssize);
 185         size = ssize;
 186     }
 187     mpz_clear(enc);
 188
 189     return size;
 190 }
 191
 192 static int
 193 gmp_rsa_public_decrypt(int flen, const unsigned char* from,
 194                          unsigned char* to, RSA* rsa, int padding)
 195 {
 196     unsigned char *p;
 197     size_t size;
 198     mpz_t s, us, n, e;
 199
 200     if (padding != RSA_PKCS1_PADDING)
 201         return -1;
 202
 203     if (flen > RSA_size(rsa))
 204         return -2;
 205
 206     BN2mpz(n, rsa->n);
 207     BN2mpz(e, rsa->e);
 208
 209 #if 0
 210     /* Check that the exponent is larger then 3 */
 211     if (mp_int_compare_value(&e, 3) <= 0) {
 212         mp_int_clear(&n);
 213         mp_int_clear(&e);
 214         return -3;
 215     }
 216 #endif
 217
 218     mpz_init(s);
 219     mpz_init(us);
 220     mpz_import(s, flen, 1, 1, 1, 0, rk_UNCONST(from));
 221
 222     if (mpz_cmp(s, n) >= 0) {
 223         mpz_clear(n);
 224         mpz_clear(e);
 225         return -4;
 226     }
 227
 228     mpz_powm(us, s, e, n);
 229
 230     mpz_clear(s);
 231     mpz_clear(n);
 232     mpz_clear(e);
 233
 234     p = to;
 235
 236     mpz_export(p, &size, 1, 1, 1, 0, us);
 237     assert(size <= RSA_size(rsa));
 238
 239     mpz_clear(us);
 240
 241     /* head zero was skipped by mp_int_to_unsigned */
 242     if (*p == 0)
 243         return -6;
 244     if (*p != 1)
 245         return -7;
 246     size--; p++;
 247     while (size && *p == 0xff) {
 248         size--; p++;
 249     }
 250     if (size == 0 || *p != 0)
 251         return -8;
 252     size--; p++;
 253
 254     memmove(to, p, size);
 255
 256     return size;
 257 }
 258
 259 static int
 260 gmp_rsa_private_encrypt(int flen, const unsigned char* from,
 261                           unsigned char* to, RSA* rsa, int padding)
 262 {
 263     unsigned char *p, *p0;
 264     size_t size;
 265     mpz_t in, out, n, e;
 266
 267     if (padding != RSA_PKCS1_PADDING)
 268         return -1;
 269
 270     size = RSA_size(rsa);
 271
 272     if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
 273         return -2;
 274
 275     p0 = p = malloc(size);
 276     *p++ = 0;
 277     *p++ = 1;
 278     memset(p, 0xff, size - flen - 3);
 279     p += size - flen - 3;
 280     *p++ = 0;
 281     memcpy(p, from, flen);
 282     p += flen;
 283     assert((p - p0) == size);
 284
 285     BN2mpz(n, rsa->n);
 286     BN2mpz(e, rsa->e);
 287
 288     mpz_init(in);
 289     mpz_init(out);
 290     mpz_import(in, size, 1, 1, 1, 0, p0);
 291     free(p0);
 292
 293 #if 0
 294     if(mp_int_compare_zero(&in) < 0 ||
 295        mp_int_compare(&in, &n) >= 0) {
 296         size = 0;
 297         goto out;
 298     }
 299 #endif
 300
 301     if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
 302         mpz_t p, q, dmp1, dmq1, iqmp;
 303
 304         BN2mpz(p, rsa->p);
 305         BN2mpz(q, rsa->q);
 306         BN2mpz(dmp1, rsa->dmp1);
 307         BN2mpz(dmq1, rsa->dmq1);
 308         BN2mpz(iqmp, rsa->iqmp);
 309
 310         rsa_private_calculate(in, p, q, dmp1, dmq1, iqmp, out);
 311
 312         mpz_clear(p);
 313         mpz_clear(q);
 314         mpz_clear(dmp1);
 315         mpz_clear(dmq1);
 316         mpz_clear(iqmp);
 317     } else {
 318         mpz_t d;
 319
 320         BN2mpz(d, rsa->d);
 321         mpz_powm(out, in, d, n);
 322         mpz_clear(d);
 323     }
 324
 325     {
 326         size_t ssize;
 327         mpz_export(to, &ssize, 1, 1, 1, 0, out);
 328         assert(size >= ssize);
 329         size = ssize;
 330     }
 331
 332     mpz_clear(e);
 333     mpz_clear(n);
 334     mpz_clear(in);
 335     mpz_clear(out);
 336
 337     return size;
 338 }
 339
 340 static int
 341 gmp_rsa_private_decrypt(int flen, const unsigned char* from,
 342                           unsigned char* to, RSA* rsa, int padding)
 343 {
 344     unsigned char *ptr;
 345     size_t size;
 346     mpz_t in, out, n, e;
 347
 348     if (padding != RSA_PKCS1_PADDING)
 349         return -1;
 350
 351     size = RSA_size(rsa);
 352     if (flen > size)
 353         return -2;
 354
 355     mpz_init(in);
 356     mpz_init(out);
 357
 358     BN2mpz(n, rsa->n);
 359     BN2mpz(e, rsa->e);
 360
 361     mpz_import(in, flen, 1, 1, 1, 0, from);
 362
 363     if(mpz_cmp_ui(in, 0) < 0 ||
 364        mpz_cmp(in, n) >= 0) {
 365         size = 0;
 366         goto out;
 367     }
 368
 369     if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
 370         mpz_t p, q, dmp1, dmq1, iqmp;
 371
 372         BN2mpz(p, rsa->p);
 373         BN2mpz(q, rsa->q);
 374         BN2mpz(dmp1, rsa->dmp1);
 375         BN2mpz(dmq1, rsa->dmq1);
 376         BN2mpz(iqmp, rsa->iqmp);
 377
 378         rsa_private_calculate(in, p, q, dmp1, dmq1, iqmp, out);
 379
 380         mpz_clear(p);
 381         mpz_clear(q);
 382         mpz_clear(dmp1);
 383         mpz_clear(dmq1);
 384         mpz_clear(iqmp);
 385     } else {
 386         mpz_t d;
 387
 388 #if 0
 389         if(mp_int_compare_zero(&in) < 0 ||
 390            mp_int_compare(&in, &n) >= 0)
 391             return MP_RANGE;
 392 #endif
 393
 394         BN2mpz(d, rsa->d);
 395         mpz_powm(out, in, d, n);
 396         mpz_clear(d);
 397     }
 398
 399     ptr = to;
 400     {
 401         size_t ssize;
 402         mpz_export(ptr, &ssize, 1, 1, 1, 0, out);
 403         assert(size >= ssize);
 404         size = ssize;
 405     }
 406
 407     /* head zero was skipped by mp_int_to_unsigned */
 408     if (*ptr != 2)
 409         return -3;
 410     size--; ptr++;
 411     while (size && *ptr != 0) {
 412         size--; ptr++;
 413     }
 414     if (size == 0)
 415         return -4;
 416     size--; ptr++;
 417
 418     memmove(to, ptr, size);
 419
 420 out:
 421     mpz_clear(e);
 422     mpz_clear(n);
 423     mpz_clear(in);
 424     mpz_clear(out);
 425
 426     return size;
 427 }
 428
 429 static int
 430 random_num(mpz_t num, size_t len)
 431 {
 432     unsigned char *p;
 433
 434     len = (len + 7) / 8;
 435     p = malloc(len);
 436     if (p == NULL)
 437         return 1;
 438     if (RAND_bytes(p, len) != 1) {
 439         free(p);
 440         return 1;
 441     }
 442     mpz_import(num, len, 1, 1, 1, 0, p);
 443     free(p);
 444     return 0;
 445 }
 446
 447
 448 static int
 449 gmp_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
 450 {
 451     mpz_t el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
 452     int counter, ret;
 453
 454     if (bits < 789)
 455         return -1;
 456
 457     ret = -1;
 458
 459     mpz_init(el);
 460     mpz_init(p);
 461     mpz_init(q);
 462     mpz_init(n);
 463     mpz_init(d);
 464     mpz_init(dmp1);
 465     mpz_init(dmq1);
 466     mpz_init(iqmp);
 467     mpz_init(t1);
 468     mpz_init(t2);
 469     mpz_init(t3);
 470
 471     BN2mpz(el, e);
 472
 473     /* generate p and q so that p != q and bits(pq) ~ bits */
 474
 475     counter = 0;
 476     do {
 477         BN_GENCB_call(cb, 2, counter++);
 478         random_num(p, bits / 2 + 1);
 479         mpz_nextprime(p, p);
 480
 481         mpz_sub_ui(t1, p, 1);
 482         mpz_gcd(t2, t1, el);
 483     } while(mpz_cmp_ui(t2, 1) != 0);
 484
 485     BN_GENCB_call(cb, 3, 0);
 486
 487     counter = 0;
 488     do {
 489         BN_GENCB_call(cb, 2, counter++);
 490         random_num(q, bits / 2 + 1);
 491         mpz_nextprime(q, q);
 492
 493         mpz_sub_ui(t1, q, 1);
 494         mpz_gcd(t2, t1, el);
 495     } while(mpz_cmp_ui(t2, 1) != 0);
 496
 497     /* make p > q */
 498     if (mpz_cmp(p, q) < 0)
 499         mpz_swap(p, q);
 500
 501     BN_GENCB_call(cb, 3, 1);
 502
 503     /* calculate n,             n = p * q */
 504     mpz_mul(n, p, q);
 505
 506     /* calculate d,             d = 1/e mod (p - 1)(q - 1) */
 507     mpz_sub_ui(t1, p, 1);
 508     mpz_sub_ui(t2, q, 1);
 509     mpz_mul(t3, t1, t2);
 510     mpz_invert(d, el, t3);
 511
 512     /* calculate dmp1           dmp1 = d mod (p-1) */
 513     mpz_mod(dmp1, d, t1);
 514     /* calculate dmq1           dmq1 = d mod (q-1) */
 515     mpz_mod(dmq1, d, t2);
 516     /* calculate iqmp           iqmp = 1/q mod p */
 517     mpz_invert(iqmp, q, p);
 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
 532     mpz_clear(el);
 533     mpz_clear(p);
 534     mpz_clear(q);
 535     mpz_clear(n);
 536     mpz_clear(d);
 537     mpz_clear(dmp1);
 538     mpz_clear(dmq1);
 539     mpz_clear(iqmp);
 540     mpz_clear(t1);
 541     mpz_clear(t2);
 542     mpz_clear(t3);
 543
 544     return ret;
 545 }
 546
 547 static int
 548 gmp_rsa_init(RSA *rsa)
 549 {
 550     return 1;
 551 }
 552
 553 static int
 554 gmp_rsa_finish(RSA *rsa)
 555 {
 556     return 1;
 557 }
 558
 559 const RSA_METHOD hc_rsa_gmp_method = {
 560     "hcrypto GMP RSA",
 561     gmp_rsa_public_encrypt,
 562     gmp_rsa_public_decrypt,
 563     gmp_rsa_private_encrypt,
 564     gmp_rsa_private_decrypt,
 565     NULL,
 566     NULL,
 567     gmp_rsa_init,
 568     gmp_rsa_finish,
 569     0,
 570     NULL,
 571     NULL,
 572     NULL,
 573     gmp_rsa_generate_key
 574 };
 575
 576 #endif /* HAVE_GMP */
 577
 578 /**
 579  * RSA implementation using Gnu Multipresistion Library.
 580  */
 581
 582 const RSA_METHOD *
 583 RSA_gmp_method(void)
 584 {
 585 #ifdef HAVE_GMP
 586     return &hc_rsa_gmp_method;
 587 #else
 588     return NULL;
 589 #endif
 590 }