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 49static void 50BN2mpz(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 64static int 65tfm_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 101static int 102tfm_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 169static int 170tfm_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 236static int 237tfm_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 318static int 319tfm_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 409static BIGNUM * 410mpz2BN(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 428static int 429random_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 448static int 449tfm_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 530out: 531 fp_zero_multi(&el, &p, &q, &n, &d, &dmp1, 532 &dmq1, &iqmp, &t1, &t2, &t3, NULL); 533 534 return ret; 535} 536 537static int 538tfm_rsa_init(RSA *rsa) 539{ 540 return 1; 541} 542 543static int 544tfm_rsa_finish(RSA *rsa) 545{ 546 return 1; 547} 548 549const 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 568const RSA_METHOD * 569RSA_tfm_method(void) 570{ 571#ifdef USE_HCRYPTO_TFM 572 return &hc_rsa_tfm_method; 573#else 574 return NULL; 575#endif 576} 577 578#endif 579