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