1/* $NetBSD: rsa-tfm.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */ 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#include <krb5/roken.h> 38#include <krb5/krb5-types.h> 39#include <assert.h> 40 41#include <rsa.h> 42 43#ifdef USE_HCRYPTO_TFM 44 45#include "tfm.h" 46 47static void 48BN2mpz(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 62static int 63tfm_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 99static int 100tfm_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 167static int 168tfm_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 234static int 235tfm_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 316static int 317tfm_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 int 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 407static BIGNUM * 408mpz2BN(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 426static int 427random_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 446static int 447tfm_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 528out: 529 fp_zero_multi(&el, &p, &q, &n, &d, &dmp1, 530 &dmq1, &iqmp, &t1, &t2, &t3, NULL); 531 532 return ret; 533} 534 535static int 536tfm_rsa_init(RSA *rsa) 537{ 538 return 1; 539} 540 541static int 542tfm_rsa_finish(RSA *rsa) 543{ 544 return 1; 545} 546 547const 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#endif 565 566const RSA_METHOD * 567RSA_tfm_method(void) 568{ 569#ifdef USE_HCRYPTO_TFM 570 return &hc_rsa_tfm_method; 571#else 572 return NULL; 573#endif 574} 575 576