src/libstrongswan/plugins/gmp/gmp_rsa_private_key.c

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