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