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