src/libstrongswan/plugins/gmp/gmp_rsa_private_key.c

   1 /*
   2  * Copyright (C) 2005-2009 Martin Willi
   3  * Copyright (C) 2005 Jan Hutter
   4  * Hochschule fuer Technik Rapperswil
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2 of the License, or (at your
   9  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * for more details.
  15  */
  16
  17 #include <gmp.h>
  18 #include <sys/stat.h>
  19 #include <unistd.h>
  20 #include <string.h>
  21
  22 #include "gmp_rsa_private_key.h"
  23 #include "gmp_rsa_public_key.h"
  24
  25 #include <debug.h>
  26 #include <asn1/oid.h>
  27 #include <asn1/asn1.h>
  28 #include <asn1/asn1_parser.h>
  29
  30 /**
  31  *  Public exponent to use for key generation.
  32  */
  33 #define PUBLIC_EXPONENT 0x10001
  34
  35 typedef struct private_gmp_rsa_private_key_t private_gmp_rsa_private_key_t;
  36
  37 /**
  38  * Private data of a gmp_rsa_private_key_t object.
  39  */
  40 struct private_gmp_rsa_private_key_t {
  41         /**
  42          * Public interface for this signer.
  43          */
  44         gmp_rsa_private_key_t public;
  45
  46         /**
  47          * Public modulus.
  48          */
  49         mpz_t n;
  50
  51         /**
  52          * Public exponent.
  53          */
  54         mpz_t e;
  55
  56         /**
  57          * Private prime 1.
  58          */
  59         mpz_t p;
  60
  61         /**
  62          * Private Prime 2.
  63          */
  64         mpz_t q;
  65
  66         /**
  67          * Private exponent.
  68          */
  69         mpz_t d;
  70
  71         /**
  72          * Private exponent 1.
  73          */
  74         mpz_t exp1;
  75
  76         /**
  77          * Private exponent 2.
  78          */
  79         mpz_t exp2;
  80
  81         /**
  82          * Private coefficient.
  83          */
  84         mpz_t coeff;
  85
  86         /**
  87          * Keysize in bytes.
  88          */
  89         size_t k;
  90
  91         /**
  92          * reference count
  93          */
  94         refcount_t ref;
  95 };
  96
  97 /**
  98  * Convert a MP integer into a chunk_t
  99  */
 100 chunk_t gmp_mpz_to_chunk(const mpz_t value)
 101 {
 102         chunk_t n;
 103
 104         n.len = 1 + mpz_sizeinbase(value, 2) / BITS_PER_BYTE;
 105         n.ptr = mpz_export(NULL, NULL, 1, n.len, 1, 0, value);
 106         if (n.ptr == NULL)
 107         {       /* if we have zero in "value", gmp returns NULL */
 108                 n.len = 0;
 109         }
 110         return n;
 111 }
 112
 113 /**
 114  * Auxiliary function overwriting private key material with zero bytes
 115  */
 116 static void mpz_clear_sensitive(mpz_t z)
 117 {
 118         size_t len = mpz_size(z) * GMP_LIMB_BITS / BITS_PER_BYTE;
 119         u_int8_t *random = alloca(len);
 120
 121         memset(random, 0, len);
 122         /* overwrite mpz_t with zero bytes before clearing it */
 123         mpz_import(z, len, 1, 1, 1, 0, random);
 124         mpz_clear(z);
 125 }
 126
 127 /**
 128  * Create a mpz prime of at least prime_size
 129  */
 130 static status_t compute_prime(private_gmp_rsa_private_key_t *this,
 131                                                           size_t prime_size, mpz_t *prime)
 132 {
 133         rng_t *rng;
 134         chunk_t random_bytes;
 135
 136         rng = lib->crypto->create_rng(lib->crypto, RNG_TRUE);
 137         if (!rng)
 138         {
 139                 DBG1("no RNG of quality %N found", rng_quality_names, RNG_TRUE);
 140                 return FAILED;
 141         }
 142
 143         mpz_init(*prime);
 144         do
 145         {
 146                 rng->allocate_bytes(rng, prime_size, &random_bytes);
 147                 /* make sure most significant bit is set */
 148                 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
 149
 150                 mpz_import(*prime, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
 151                 mpz_nextprime (*prime, *prime);
 152                 chunk_clear(&random_bytes);
 153         }
 154         /* check if it isn't too large */
 155         while (((mpz_sizeinbase(*prime, 2) + 7) / 8) > prime_size);
 156
 157         rng->destroy(rng);
 158         return SUCCESS;
 159 }
 160
 161 /**
 162  * PKCS#1 RSADP function
 163  */
 164 static chunk_t rsadp(private_gmp_rsa_private_key_t *this, chunk_t data)
 165 {
 166         mpz_t t1, t2;
 167         chunk_t decrypted;
 168
 169         mpz_init(t1);
 170         mpz_init(t2);
 171
 172         mpz_import(t1, data.len, 1, 1, 1, 0, data.ptr);
 173
 174         mpz_powm(t2, t1, this->exp1, this->p);  /* m1 = c^dP mod p */
 175         mpz_powm(t1, t1, this->exp2, this->q);  /* m2 = c^dQ mod Q */
 176         mpz_sub(t2, t2, t1);                                    /* h = qInv (m1 - m2) mod p */
 177         mpz_mod(t2, t2, this->p);
 178         mpz_mul(t2, t2, this->coeff);
 179         mpz_mod(t2, t2, this->p);
 180
 181         mpz_mul(t2, t2, this->q);                               /* m = m2 + h q */
 182         mpz_add(t1, t1, t2);
 183
 184         decrypted.len = this->k;
 185         decrypted.ptr = mpz_export(NULL, NULL, 1, decrypted.len, 1, 0, t1);
 186         if (decrypted.ptr == NULL)
 187         {
 188                 decrypted.len = 0;
 189         }
 190
 191         mpz_clear_sensitive(t1);
 192         mpz_clear_sensitive(t2);
 193
 194         return decrypted;
 195 }
 196
 197 /**
 198  * PKCS#1 RSASP1 function
 199  */
 200 static chunk_t rsasp1(private_gmp_rsa_private_key_t *this, chunk_t data)
 201 {
 202         return rsadp(this, data);
 203 }
 204
 205 /**
 206  * Implementation of gmp_rsa_private_key_t.build_emsa_pkcs1_signature.
 207  */
 208 static bool build_emsa_pkcs1_signature(private_gmp_rsa_private_key_t *this,
 209                                                                            hash_algorithm_t hash_algorithm,
 210                                                                            chunk_t data, chunk_t *signature)
 211 {
 212         chunk_t digestInfo = chunk_empty;
 213         chunk_t em;
 214
 215         if (hash_algorithm != HASH_UNKNOWN)
 216         {
 217                 hasher_t *hasher;
 218                 chunk_t hash;
 219                 int hash_oid = hasher_algorithm_to_oid(hash_algorithm);
 220
 221                 if (hash_oid == OID_UNKNOWN)
 222                 {
 223                         return FALSE;
 224                 }
 225
 226                 hasher = lib->crypto->create_hasher(lib->crypto, hash_algorithm);
 227                 if (hasher == NULL)
 228                 {
 229                         return FALSE;
 230                 }
 231                 hasher->allocate_hash(hasher, data, &hash);
 232                 hasher->destroy(hasher);
 233
 234                 /* build DER-encoded digestInfo */
 235                 digestInfo = asn1_wrap(ASN1_SEQUENCE, "mm",
 236                                                 asn1_algorithmIdentifier(hash_oid),
 237                                                 asn1_simple_object(ASN1_OCTET_STRING, hash)
 238                                           );
 239                 chunk_free(&hash);
 240                 data = digestInfo;
 241         }
 242
 243         if (data.len > this->k - 3)
 244         {
 245                 free(digestInfo.ptr);
 246                 DBG1("unable to sign %d bytes using a %dbit key", data.len, this->k * 8);
 247                 return FALSE;
 248         }
 249
 250         /* build chunk to rsa-decrypt:
 251          * EM = 0x00 || 0x01 || PS || 0x00 || T.
 252          * PS = 0xFF padding, with length to fill em
 253          * T = encoded_hash
 254          */
 255         em.len = this->k;
 256         em.ptr = malloc(em.len);
 257
 258         /* fill em with padding */
 259         memset(em.ptr, 0xFF, em.len);
 260         /* set magic bytes */
 261         *(em.ptr) = 0x00;
 262         *(em.ptr+1) = 0x01;
 263         *(em.ptr + em.len - data.len - 1) = 0x00;
 264         /* set DER-encoded hash */
 265         memcpy(em.ptr + em.len - data.len, data.ptr, data.len);
 266
 267         /* build signature */
 268         *signature = rsasp1(this, em);
 269
 270         free(digestInfo.ptr);
 271         free(em.ptr);
 272
 273         return TRUE;
 274 }
 275
 276 /**
 277  * Implementation of gmp_rsa_private_key.get_type.
 278  */
 279 static key_type_t get_type(private_gmp_rsa_private_key_t *this)
 280 {
 281         return KEY_RSA;
 282 }
 283
 284 /**
 285  * Implementation of gmp_rsa_private_key.sign.
 286  */
 287 static bool sign(private_gmp_rsa_private_key_t *this, signature_scheme_t scheme,
 288                                  chunk_t data, chunk_t *signature)
 289 {
 290         switch (scheme)
 291         {
 292                 case SIGN_RSA_EMSA_PKCS1_NULL:
 293                         return build_emsa_pkcs1_signature(this, HASH_UNKNOWN, data, signature);
 294                 case SIGN_RSA_EMSA_PKCS1_SHA1:
 295                         return build_emsa_pkcs1_signature(this, HASH_SHA1, data, signature);
 296                 case SIGN_RSA_EMSA_PKCS1_SHA224:
 297                         return build_emsa_pkcs1_signature(this, HASH_SHA224, data, signature);
 298                 case SIGN_RSA_EMSA_PKCS1_SHA256:
 299                         return build_emsa_pkcs1_signature(this, HASH_SHA256, data, signature);
 300                 case SIGN_RSA_EMSA_PKCS1_SHA384:
 301                         return build_emsa_pkcs1_signature(this, HASH_SHA384, data, signature);
 302                 case SIGN_RSA_EMSA_PKCS1_SHA512:
 303                         return build_emsa_pkcs1_signature(this, HASH_SHA512, data, signature);
 304                 case SIGN_RSA_EMSA_PKCS1_MD5:
 305                         return build_emsa_pkcs1_signature(this, HASH_MD5, data, signature);
 306                 default:
 307                         DBG1("signature scheme %N not supported in RSA",
 308                                  signature_scheme_names, scheme);
 309                         return FALSE;
 310         }
 311 }
 312
 313 /**
 314  * Implementation of gmp_rsa_private_key.decrypt.
 315  */
 316 static bool decrypt(private_gmp_rsa_private_key_t *this, chunk_t crypto,
 317                                         chunk_t *plain)
 318 {
 319         chunk_t em, stripped;
 320         bool success = FALSE;
 321
 322         /* rsa decryption using PKCS#1 RSADP */
 323         stripped = em = rsadp(this, crypto);
 324
 325         /* PKCS#1 v1.5 8.1 encryption-block formatting (EB = 00 || 02 || PS || 00 || D) */
 326
 327         /* check for hex pattern 00 02 in decrypted message */
 328         if ((*stripped.ptr++ != 0x00) || (*(stripped.ptr++) != 0x02))
 329         {
 330                 DBG1("incorrect padding - probably wrong rsa key");
 331                 goto end;
 332         }
 333         stripped.len -= 2;
 334
 335         /* the plaintext data starts after first 0x00 byte */
 336         while (stripped.len-- > 0 && *stripped.ptr++ != 0x00)
 337
 338         if (stripped.len == 0)
 339         {
 340                 DBG1("no plaintext data");
 341                 goto end;
 342         }
 343
 344         *plain = chunk_clone(stripped);
 345         success = TRUE;
 346
 347 end:
 348         chunk_clear(&em);
 349         return success;
 350 }
 351
 352 /**
 353  * Implementation of gmp_rsa_private_key.get_keysize.
 354  */
 355 static size_t get_keysize(private_gmp_rsa_private_key_t *this)
 356 {
 357         return this->k;
 358 }
 359
 360 /**
 361  * Implementation of gmp_rsa_private_key.get_public_key.
 362  */
 363 static public_key_t* get_public_key(private_gmp_rsa_private_key_t *this)
 364 {
 365         chunk_t n, e;
 366         public_key_t *public;
 367
 368         n = gmp_mpz_to_chunk(this->n);
 369         e = gmp_mpz_to_chunk(this->e);
 370
 371         public = lib->creds->create(lib->creds, CRED_PUBLIC_KEY, KEY_RSA,
 372                                                 BUILD_RSA_MODULUS, n, BUILD_RSA_PUB_EXP, e, BUILD_END);
 373         chunk_free(&n);
 374         chunk_free(&e);
 375
 376         return public;
 377 }
 378
 379 /**
 380  * Implementation of gmp_rsa_private_key.equals.
 381  */
 382 static bool equals(private_gmp_rsa_private_key_t *this, private_key_t *other)
 383 {
 384         return private_key_equals(&this->public.interface, other);
 385 }
 386
 387 /**
 388  * Implementation of gmp_rsa_private_key.belongs_to.
 389  */
 390 static bool belongs_to(private_gmp_rsa_private_key_t *this, public_key_t *public)
 391 {
 392         return private_key_belongs_to(&this->public.interface, public);
 393 }
 394
 395 /**
 396  * Implementation of private_key_t.get_encoding
 397  */
 398 static bool get_encoding(private_gmp_rsa_private_key_t *this,
 399                                                  key_encoding_type_t type, chunk_t *encoding)
 400 {
 401         chunk_t n, e, d, p, q, exp1, exp2, coeff;
 402         bool success;
 403
 404         n = gmp_mpz_to_chunk(this->n);
 405         e = gmp_mpz_to_chunk(this->e);
 406         d = gmp_mpz_to_chunk(this->d);
 407         p = gmp_mpz_to_chunk(this->p);
 408         q = gmp_mpz_to_chunk(this->q);
 409         exp1 = gmp_mpz_to_chunk(this->exp1);
 410         exp2 = gmp_mpz_to_chunk(this->exp2);
 411         coeff = gmp_mpz_to_chunk(this->coeff);
 412
 413         success = lib->encoding->encode(lib->encoding,
 414                                                         type, NULL, encoding, KEY_PART_RSA_MODULUS, n,
 415                                                         KEY_PART_RSA_PUB_EXP, e, KEY_PART_RSA_PRIV_EXP, d,
 416                                                         KEY_PART_RSA_PRIME1, p, KEY_PART_RSA_PRIME2, q,
 417                                                         KEY_PART_RSA_EXP1, exp1, KEY_PART_RSA_EXP2, exp2,
 418                                                         KEY_PART_RSA_COEFF, coeff, KEY_PART_END);
 419         chunk_free(&n);
 420         chunk_free(&e);
 421         chunk_clear(&d);
 422         chunk_clear(&p);
 423         chunk_clear(&q);
 424         chunk_clear(&exp1);
 425         chunk_clear(&exp2);
 426         chunk_clear(&coeff);
 427
 428         return success;
 429 }
 430
 431 /**
 432  * Implementation of private_key_t.get_fingerprint
 433  */
 434 static bool get_fingerprint(private_gmp_rsa_private_key_t *this,
 435                                                         key_encoding_type_t type, chunk_t *fp)
 436 {
 437         chunk_t n, e;
 438         bool success;
 439
 440         if (lib->encoding->get_cache(lib->encoding, type, this, fp))
 441         {
 442                 return TRUE;
 443         }
 444         n = gmp_mpz_to_chunk(this->n);
 445         e = gmp_mpz_to_chunk(this->e);
 446
 447         success = lib->encoding->encode(lib->encoding, type, this, fp,
 448                                 KEY_PART_RSA_MODULUS, n, KEY_PART_RSA_PUB_EXP, e, KEY_PART_END);
 449         chunk_free(&n);
 450         chunk_free(&e);
 451
 452         return success;
 453 }
 454
 455 /**
 456  * Implementation of gmp_rsa_private_key.get_ref.
 457  */
 458 static private_gmp_rsa_private_key_t* get_ref(private_gmp_rsa_private_key_t *this)
 459 {
 460         ref_get(&this->ref);
 461         return this;
 462 }
 463
 464 /**
 465  * Implementation of gmp_rsa_private_key.destroy.
 466  */
 467 static void destroy(private_gmp_rsa_private_key_t *this)
 468 {
 469         if (ref_put(&this->ref))
 470         {
 471                 mpz_clear_sensitive(this->n);
 472                 mpz_clear_sensitive(this->e);
 473                 mpz_clear_sensitive(this->p);
 474                 mpz_clear_sensitive(this->q);
 475                 mpz_clear_sensitive(this->d);
 476                 mpz_clear_sensitive(this->exp1);
 477                 mpz_clear_sensitive(this->exp2);
 478                 mpz_clear_sensitive(this->coeff);
 479                 lib->encoding->clear_cache(lib->encoding, this);
 480                 free(this);
 481         }
 482 }
 483
 484 /**
 485  * Check the loaded key if it is valid and usable
 486  */
 487 static status_t check(private_gmp_rsa_private_key_t *this)
 488 {
 489         mpz_t t, u, q1;
 490         status_t status = SUCCESS;
 491
 492         /* PKCS#1 1.5 section 6 requires modulus to have at least 12 octets.
 493          * We actually require more (for security).
 494          */
 495         if (this->k < 512 / BITS_PER_BYTE)
 496         {
 497                 DBG1("key shorter than 512 bits");
 498                 return FAILED;
 499         }
 500
 501         /* we picked a max modulus size to simplify buffer allocation */
 502         if (this->k > 8192 / BITS_PER_BYTE)
 503         {
 504                 DBG1("key larger than 8192 bits");
 505                 return FAILED;
 506         }
 507
 508         mpz_init(t);
 509         mpz_init(u);
 510         mpz_init(q1);
 511
 512         /* check that n == p * q */
 513         mpz_mul(u, this->p, this->q);
 514         if (mpz_cmp(u, this->n) != 0)
 515         {
 516                 status = FAILED;
 517         }
 518
 519         /* check that e divides neither p-1 nor q-1 */
 520         mpz_sub_ui(t, this->p, 1);
 521         mpz_mod(t, t, this->e);
 522         if (mpz_cmp_ui(t, 0) == 0)
 523         {
 524                 status = FAILED;
 525         }
 526
 527         mpz_sub_ui(t, this->q, 1);
 528         mpz_mod(t, t, this->e);
 529         if (mpz_cmp_ui(t, 0) == 0)
 530         {
 531                 status = FAILED;
 532         }
 533
 534         /* check that d is e^-1 (mod lcm(p-1, q-1)) */
 535         /* see PKCS#1v2, aka RFC 2437, for the "lcm" */
 536         mpz_sub_ui(q1, this->q, 1);
 537         mpz_sub_ui(u, this->p, 1);
 538         mpz_gcd(t, u, q1);              /* t := gcd(p-1, q-1) */
 539         mpz_mul(u, u, q1);              /* u := (p-1) * (q-1) */
 540         mpz_divexact(u, u, t);  /* u := lcm(p-1, q-1) */
 541
 542         mpz_mul(t, this->d, this->e);
 543         mpz_mod(t, t, u);
 544         if (mpz_cmp_ui(t, 1) != 0)
 545         {
 546                 status = FAILED;
 547         }
 548
 549         /* check that exp1 is d mod (p-1) */
 550         mpz_sub_ui(u, this->p, 1);
 551         mpz_mod(t, this->d, u);
 552         if (mpz_cmp(t, this->exp1) != 0)
 553         {
 554                 status = FAILED;
 555         }
 556
 557         /* check that exp2 is d mod (q-1) */
 558         mpz_sub_ui(u, this->q, 1);
 559         mpz_mod(t, this->d, u);
 560         if (mpz_cmp(t, this->exp2) != 0)
 561         {
 562                 status = FAILED;
 563         }
 564
 565         /* check that coeff is (q^-1) mod p */
 566         mpz_mul(t, this->coeff, this->q);
 567         mpz_mod(t, t, this->p);
 568         if (mpz_cmp_ui(t, 1) != 0)
 569         {
 570                 status = FAILED;
 571         }
 572
 573         mpz_clear_sensitive(t);
 574         mpz_clear_sensitive(u);
 575         mpz_clear_sensitive(q1);
 576         if (status != SUCCESS)
 577         {
 578                 DBG1("key integrity tests failed");
 579         }
 580         return status;
 581 }
 582
 583 /**
 584  * Internal generic constructor
 585  */
 586 static private_gmp_rsa_private_key_t *gmp_rsa_private_key_create_empty(void)
 587 {
 588         private_gmp_rsa_private_key_t *this = malloc_thing(private_gmp_rsa_private_key_t);
 589
 590         this->public.interface.get_type = (key_type_t (*) (private_key_t*))get_type;
 591         this->public.interface.sign = (bool (*) (private_key_t*, signature_scheme_t, chunk_t, chunk_t*))sign;
 592         this->public.interface.decrypt = (bool (*) (private_key_t*, chunk_t, chunk_t*))decrypt;
 593         this->public.interface.get_keysize = (size_t (*) (private_key_t*))get_keysize;
 594         this->public.interface.get_public_key = (public_key_t* (*) (private_key_t*))get_public_key;
 595         this->public.interface.equals = (bool (*) (private_key_t*, private_key_t*))equals;
 596         this->public.interface.belongs_to = (bool (*) (private_key_t*, public_key_t*))belongs_to;
 597         this->public.interface.get_fingerprint = (bool(*)(private_key_t*, key_encoding_type_t type, chunk_t *fp))get_fingerprint;
 598         this->public.interface.get_encoding = (bool(*)(private_key_t*, key_encoding_type_t type, chunk_t *encoding))get_encoding;
 599         this->public.interface.get_ref = (private_key_t* (*) (private_key_t*))get_ref;
 600         this->public.interface.destroy = (void (*) (private_key_t*))destroy;
 601
 602         this->ref = 1;
 603
 604         return this;
 605 }
 606
 607 /**
 608  * Generate an RSA key of specified key size
 609  */
 610 static gmp_rsa_private_key_t *generate(size_t key_size)
 611 {
 612         mpz_t p, q, n, e, d, exp1, exp2, coeff;
 613         mpz_t m, q1, t;
 614         private_gmp_rsa_private_key_t *this = gmp_rsa_private_key_create_empty();
 615
 616         key_size = key_size / BITS_PER_BYTE;
 617
 618         /* Get values of primes p and q  */
 619         if (compute_prime(this, key_size/2, &p) != SUCCESS)
 620         {
 621                 free(this);
 622                 return NULL;
 623         }
 624         if (compute_prime(this, key_size/2, &q) != SUCCESS)
 625         {
 626                 mpz_clear(p);
 627                 free(this);
 628                 return NULL;
 629         }
 630
 631         mpz_init(t);
 632         mpz_init(n);
 633         mpz_init(d);
 634         mpz_init(exp1);
 635         mpz_init(exp2);
 636         mpz_init(coeff);
 637
 638         /* Swapping Primes so p is larger then q */
 639         if (mpz_cmp(p, q) < 0)
 640         {
 641                 mpz_swap(p, q);
 642         }
 643
 644         mpz_mul(n, p, q);                                               /* n = p*q */
 645         mpz_init_set_ui(e, PUBLIC_EXPONENT);    /* assign public exponent */
 646         mpz_init_set(m, p);                                     /* m = p */
 647         mpz_sub_ui(m, m, 1);                                    /* m = m -1 */
 648         mpz_init_set(q1, q);                                    /* q1 = q */
 649         mpz_sub_ui(q1, q1, 1);                                  /* q1 = q1 -1 */
 650         mpz_gcd(t, m, q1);                                              /* t = gcd(p-1, q-1) */
 651         mpz_mul(m, m, q1);                                              /* m = (p-1)*(q-1) */
 652         mpz_divexact(m, m, t);                                  /* m = m / t */
 653         mpz_gcd(t, m, e);                                               /* t = gcd(m, e) */
 654
 655         mpz_invert(d, e, m);                                    /* e has an inverse mod m */
 656         if (mpz_cmp_ui(d, 0) < 0)                               /* make sure d is positive */
 657         {
 658                 mpz_add(d, d, m);
 659         }
 660         mpz_sub_ui(t, p, 1);                                    /* t = p-1 */
 661         mpz_mod(exp1, d, t);                                    /* exp1 = d mod p-1 */
 662         mpz_sub_ui(t, q, 1);                                    /* t = q-1 */
 663         mpz_mod(exp2, d, t);                                    /* exp2 = d mod q-1 */
 664
 665         mpz_invert(coeff, q, p);                                /* coeff = q^-1 mod p */
 666         if (mpz_cmp_ui(coeff, 0) < 0)                   /* make coeff d is positive */
 667         {
 668                 mpz_add(coeff, coeff, p);
 669         }
 670
 671         mpz_clear_sensitive(q1);
 672         mpz_clear_sensitive(m);
 673         mpz_clear_sensitive(t);
 674
 675         /* apply values */
 676         *(this->p) = *p;
 677         *(this->q) = *q;
 678         *(this->n) = *n;
 679         *(this->e) = *e;
 680         *(this->d) = *d;
 681         *(this->exp1) = *exp1;
 682         *(this->exp2) = *exp2;
 683         *(this->coeff) = *coeff;
 684
 685         /* set key size in bytes */
 686         this->k = key_size;
 687
 688         return &this->public;
 689 }
 690
 691 /**
 692  * load private key from a RSA components
 693  */
 694 static gmp_rsa_private_key_t *load(chunk_t n, chunk_t e, chunk_t d,
 695                                 chunk_t p, chunk_t q, chunk_t exp1, chunk_t exp2, chunk_t coeff)
 696 {
 697         private_gmp_rsa_private_key_t *this = gmp_rsa_private_key_create_empty();
 698
 699         mpz_init(this->n);
 700         mpz_init(this->e);
 701         mpz_init(this->p);
 702         mpz_init(this->q);
 703         mpz_init(this->d);
 704         mpz_init(this->exp1);
 705         mpz_init(this->exp2);
 706         mpz_init(this->coeff);
 707
 708         mpz_import(this->n, n.len, 1, 1, 1, 0, n.ptr);
 709         mpz_import(this->e, e.len, 1, 1, 1, 0, e.ptr);
 710         mpz_import(this->d, d.len, 1, 1, 1, 0, d.ptr);
 711         mpz_import(this->p, p.len, 1, 1, 1, 0, p.ptr);
 712         mpz_import(this->q, q.len, 1, 1, 1, 0, q.ptr);
 713         mpz_import(this->coeff, coeff.len, 1, 1, 1, 0, coeff.ptr);
 714         if (!exp1.len)
 715         {       /* exp1 missing in key, recalculate: exp1 = d mod (p-1) */
 716                 mpz_sub_ui(this->exp1, this->p, 1);
 717                 mpz_mod(this->exp1, this->d, this->exp1);
 718         }
 719         else
 720         {
 721                 mpz_import(this->exp1, exp1.len, 1, 1, 1, 0, exp1.ptr);
 722         }
 723         if (!exp2.len)
 724         {       /* exp2 missing in key, recalculate: exp2 = d mod (q-1) */
 725                 mpz_sub_ui(this->exp2, this->q, 1);
 726                 mpz_mod(this->exp2, this->d, this->exp2);
 727         }
 728         else
 729         {
 730                 mpz_import(this->exp2, exp2.len, 1, 1, 1, 0, exp2.ptr);
 731         }
 732         this->k = (mpz_sizeinbase(this->n, 2) + 7) / BITS_PER_BYTE;
 733         if (check(this) != SUCCESS)
 734         {
 735                 destroy(this);
 736                 return NULL;
 737         }
 738         return &this->public;
 739 }
 740
 741 typedef struct private_builder_t private_builder_t;
 742 /**
 743  * Builder implementation for key loading/generation
 744  */
 745 struct private_builder_t {
 746         /** implements the builder interface */
 747         builder_t public;
 748         /** key size, if generating */
 749         u_int key_size;
 750         /** rsa key parameters */
 751         chunk_t n, e, d, p, q, exp1, exp2, coeff;
 752 };
 753
 754 /**
 755  * Implementation of builder_t.build
 756  */
 757 static gmp_rsa_private_key_t *build(private_builder_t *this)
 758 {
 759         gmp_rsa_private_key_t *key = NULL;
 760
 761         if (this->key_size)
 762         {
 763                 key = generate(this->key_size);
 764         }
 765         else
 766         {
 767                 key = load(this->n, this->e, this->d, this->p, this->q,
 768                                    this->exp1, this->exp2, this->coeff);
 769         }
 770         free(this);
 771         return key;
 772 }
 773
 774 /**
 775  * Implementation of builder_t.add
 776  */
 777 static void add(private_builder_t *this, builder_part_t part, ...)
 778 {
 779         va_list args;
 780
 781         va_start(args, part);
 782         switch (part)
 783         {
 784                 case BUILD_KEY_SIZE:
 785                         this->key_size = va_arg(args, u_int);
 786                         return;
 787                 case BUILD_RSA_MODULUS:
 788                         this->n = va_arg(args, chunk_t);
 789                         break;
 790                 case BUILD_RSA_PUB_EXP:
 791                         this->e = va_arg(args, chunk_t);
 792                         break;
 793                 case BUILD_RSA_PRIV_EXP:
 794                         this->d = va_arg(args, chunk_t);
 795                         break;
 796                 case BUILD_RSA_PRIME1:
 797                         this->p = va_arg(args, chunk_t);
 798                         break;
 799                 case BUILD_RSA_PRIME2:
 800                         this->q = va_arg(args, chunk_t);
 801                         break;
 802                 case BUILD_RSA_EXP1:
 803                         this->exp1 = va_arg(args, chunk_t);
 804                         break;
 805                 case BUILD_RSA_EXP2:
 806                         this->exp2 = va_arg(args, chunk_t);
 807                         break;
 808                 case BUILD_RSA_COEFF:
 809                         this->coeff = va_arg(args, chunk_t);
 810                         break;
 811                 default:
 812                         builder_cancel(&this->public);
 813                         break;
 814         }
 815         va_end(args);
 816 }
 817
 818 /**
 819  * Builder construction function
 820  */
 821 builder_t *gmp_rsa_private_key_builder(key_type_t type)
 822 {
 823         private_builder_t *this;
 824
 825         if (type != KEY_RSA)
 826         {
 827                 return NULL;
 828         }
 829
 830         this = malloc_thing(private_builder_t);
 831
 832         this->n = this->e = this->d = this->p = this->q = chunk_empty;
 833         this->exp1 = this->exp2 = this->coeff = chunk_empty;
 834         this->key_size = 0;
 835         this->public.add = (void(*)(builder_t *this, builder_part_t part, ...))add;
 836         this->public.build = (void*(*)(builder_t *this))build;
 837
 838         return &this->public;
 839 }
 840