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