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