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