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