Source/charon/transforms/rsa/rsa_private_key.c

   1 /**
   2  * @file rsa_private_key.c
   3  *
   4  * @brief Implementation of rsa_private_key_t.
   5  *
   6  */
   7
   8 /*
   9  * Copyright (C) 2005 Jan Hutter, Martin Willi
  10  * Hochschule fuer Technik Rapperswil
  11  *
  12  * This program is free software; you can redistribute it and/or modify it
  13  * under the terms of the GNU General Public License as published by the
  14  * Free Software Foundation; either version 2 of the License, or (at your
  15  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  16  *
  17  * This program is distributed in the hope that it will be useful, but
  18  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  19  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20  * for more details.
  21  */
  22
  23 #include <gmp.h>
  24
  25 #include "rsa_private_key.h"
  26
  27 #include <daemon.h>
  28 #include <utils/allocator.h>
  29
  30
  31 /* oids for hash algorithms are defined in
  32  * rsa_public_key.c
  33  */
  34 extern u_int8_t md2_oid[18];
  35 extern u_int8_t md5_oid[18];
  36 extern u_int8_t sha1_oid[15];
  37 extern u_int8_t sha256_oid[19];
  38 extern u_int8_t sha384_oid[19];
  39 extern u_int8_t sha512_oid[19];
  40
  41 /**
  42  *  Public exponent to use for key generation
  43  */
  44 #define PUBLIC_EXPONENT 0x10001
  45
  46
  47 typedef struct private_rsa_private_key_t private_rsa_private_key_t;
  48
  49 /**
  50  * private data structure for rsa_private_key.
  51  */
  52 struct private_rsa_private_key_t {
  53         /**
  54          * Public interface for this signer.
  55          */
  56         rsa_private_key_t public;
  57
  58         /**
  59          * is the key already set ?
  60          */
  61         bool is_key_set;
  62
  63         /**
  64          * public modulus
  65          */
  66         mpz_t n;
  67
  68         /**
  69          * public exponent
  70          */
  71         mpz_t e;
  72
  73         /**
  74          * private Prime 1
  75          */
  76         mpz_t p;
  77
  78         /**
  79          * private Prime 2
  80          */
  81         mpz_t q;
  82
  83         /**
  84          * private exponent
  85          */
  86         mpz_t d;
  87
  88         /**
  89          * private exponent 1
  90          */
  91         mpz_t exp1;
  92
  93         /**
  94          * private exponent 2
  95          */
  96         mpz_t exp2;
  97
  98         /**
  99          * private coefficient
 100          */
 101         mpz_t coeff;
 102
 103         /**
 104          * keysize in bytes
 105          */
 106         size_t k;
 107
 108         /**
 109          * @brief Implements the RSADP algorithm specified in PKCS#1.
 110          */
 111         chunk_t (*rsadp) (private_rsa_private_key_t *this, chunk_t data);
 112
 113         /**
 114          * @brief Implements the RSASP1 algorithm specified in PKCS#1.
 115          */
 116         chunk_t (*rsasp1) (private_rsa_private_key_t *this, chunk_t data);
 117
 118 };
 119
 120 /**
 121  * Implements private_rsa_private_key_t.rsadp
 122  * Implements private_rsa_private_key_t.rsasp1
 123  */
 124 static chunk_t rsadp(private_rsa_private_key_t *this, chunk_t data)
 125 {
 126         mpz_t t1, t2;
 127         chunk_t decrypted;
 128
 129     mpz_init(t1);
 130     mpz_init(t2);
 131
 132     mpz_import(t1, data.len, 1, 1, 1, 0, data.ptr);
 133
 134     mpz_powm(t2, t1, this->exp1, this->p);      /* m1 = c^dP mod p */
 135     mpz_powm(t1, t1, this->exp2, this->q);      /* m2 = c^dQ mod Q */
 136     mpz_sub(t2, t2, t1);                                        /* h = qInv (m1 - m2) mod p */
 137     mpz_mod(t2, t2, this->p);
 138     mpz_mul(t2, t2, this->coeff);
 139     mpz_mod(t2, t2, this->p);
 140
 141     mpz_mul(t2, t2, this->q);                           /* m = m2 + h q */
 142     mpz_add(t1, t1, t2);
 143
 144     decrypted.len = this->k;
 145     decrypted.ptr = mpz_export(NULL, NULL, 1, decrypted.len, 1, 0, t1);
 146
 147     mpz_clear(t1);
 148     mpz_clear(t2);
 149
 150     return decrypted;
 151 }
 152
 153 /**
 154  * implementation of rsa_private_key.build_emsa_signature.
 155  */
 156 static status_t build_emsa_pkcs1_signature(private_rsa_private_key_t *this, hash_algorithm_t hash_algorithm, chunk_t data, chunk_t *signature)
 157 {
 158         hasher_t *hasher;
 159         chunk_t hash;
 160         chunk_t oid;
 161         chunk_t em;
 162
 163         /* get oid string prepended to hash */
 164         switch (hash_algorithm)
 165         {
 166                 case HASH_MD2:
 167                 {
 168                         oid.ptr = md2_oid;
 169                         oid.len = sizeof(md2_oid);
 170                         break;
 171                 }
 172                 case HASH_MD5:
 173                 {
 174                         oid.ptr = md5_oid;
 175                         oid.len = sizeof(md5_oid);
 176                         break;
 177                 }
 178                 case HASH_SHA1:
 179                 {
 180                         oid.ptr = sha1_oid;
 181                         oid.len = sizeof(sha1_oid);
 182                         break;
 183                 }
 184                 case HASH_SHA256:
 185                 {
 186                         oid.ptr = sha256_oid;
 187                         oid.len = sizeof(sha256_oid);
 188                         break;
 189                 }
 190                 case HASH_SHA384:
 191                 {
 192                         oid.ptr = sha384_oid;
 193                         oid.len = sizeof(sha384_oid);
 194                         break;
 195                 }
 196                 case HASH_SHA512:
 197                 {
 198                         oid.ptr = sha512_oid;
 199                         oid.len = sizeof(sha512_oid);
 200                         break;
 201                 }
 202                 default:
 203                 {
 204                         return NOT_SUPPORTED;
 205                 }
 206         }
 207
 208         /* get hasher */
 209         hasher = hasher_create(hash_algorithm);
 210         if (hasher == NULL)
 211         {
 212                 return NOT_SUPPORTED;
 213         }
 214
 215         /* build hash */
 216         hasher->allocate_hash(hasher, data, &hash);
 217         hasher->destroy(hasher);
 218
 219         /* build chunk to rsa-decrypt:
 220          * EM = 0x00 || 0x01 || PS || 0x00 || T.
 221          * PS = 0xFF padding, with length to fill em
 222          * T = oid || hash
 223          */
 224         em.len = this->k;
 225         em.ptr = allocator_alloc(em.len);
 226
 227         /* fill em with padding */
 228         memset(em.ptr, 0xFF, em.len);
 229         /* set magic bytes */
 230         *(em.ptr) = 0x00;
 231         *(em.ptr+1) = 0x01;
 232         *(em.ptr + em.len - hash.len - oid.len - 1) = 0x00;
 233         /* set hash */
 234         memcpy(em.ptr + em.len - hash.len, hash.ptr, hash.len);
 235         /* set oid */
 236         memcpy(em.ptr + em.len - hash.len - oid.len, oid.ptr, oid.len);
 237
 238
 239         /* build signature */
 240         *signature = this->rsasp1(this, em);
 241
 242         allocator_free(hash.ptr);
 243         allocator_free(em.ptr);
 244
 245         return SUCCESS;
 246 }
 247
 248
 249 /**
 250  * implementation of rsa_private_key.set_key.
 251  */
 252 static status_t set_key(private_rsa_private_key_t *this, chunk_t key)
 253 {
 254         chunk_t n, e, p, q, d, exp1, exp2, coeff;
 255         this->k = key.len / 8;
 256
 257         n.len = this->k;
 258         e.len = this->k;
 259         p.len = this->k;
 260         q.len = this->k;
 261         d.len = this->k;
 262         exp1.len = this->k;
 263         exp2.len = this->k;
 264         coeff.len = this->k;
 265
 266         n.ptr = key.ptr + this->k * 0;
 267         e.ptr = key.ptr + this->k * 1;
 268         p.ptr = key.ptr + this->k * 2;
 269         q.ptr = key.ptr + this->k * 3;
 270         d.ptr = key.ptr + this->k * 4;
 271         exp1.ptr = key.ptr + this->k * 5;
 272         exp2.ptr = key.ptr + this->k * 6;
 273         coeff.ptr = key.ptr + this->k * 7;
 274
 275         mpz_import(this->n, this->k, 1, 1, 1, 0, n.ptr);
 276         mpz_import(this->e, this->k, 1, 1, 1, 0, e.ptr);
 277         mpz_import(this->p, this->k, 1, 1, 1, 0, p.ptr);
 278         mpz_import(this->q, this->k, 1, 1, 1, 0, q.ptr);
 279         mpz_import(this->d, this->k, 1, 1, 1, 0, d.ptr);
 280         mpz_import(this->exp1, this->k, 1, 1, 1, 0, exp1.ptr);
 281         mpz_import(this->exp2, this->k, 1, 1, 1, 0, exp2.ptr);
 282         mpz_import(this->coeff, this->k, 1, 1, 1, 0, coeff.ptr);
 283
 284         this->is_key_set = TRUE;
 285
 286         return SUCCESS;
 287
 288 }
 289
 290 /**
 291  * implementation of rsa_private_key.get_key.
 292  */
 293 static status_t get_key(private_rsa_private_key_t *this, chunk_t *key)
 294 {
 295         if (!this->is_key_set)
 296         {
 297                 return INVALID_STATE;
 298         }
 299
 300         chunk_t n, e, p, q, d, exp1, exp2, coeff;
 301
 302         n.len = this->k;
 303         n.ptr = mpz_export(NULL, NULL, 1, n.len, 1, 0, this->n);
 304         e.len = this->k;
 305         e.ptr = mpz_export(NULL, NULL, 1, e.len, 1, 0, this->e);
 306         p.len = this->k;
 307         p.ptr = mpz_export(NULL, NULL, 1, p.len, 1, 0, this->p);
 308         q.len = this->k;
 309         q.ptr = mpz_export(NULL, NULL, 1, q.len, 1, 0, this->q);
 310         d.len = this->k;
 311         d.ptr = mpz_export(NULL, NULL, 1, d.len, 1, 0, this->d);
 312         exp1.len = this->k;
 313         exp1.ptr = mpz_export(NULL, NULL, 1, exp1.len, 1, 0, this->exp1);
 314         exp2.len = this->k;
 315         exp2.ptr = mpz_export(NULL, NULL, 1, exp2.len, 1, 0, this->exp2);
 316         coeff.len = this->k;
 317         coeff.ptr = mpz_export(NULL, NULL, 1, coeff.len, 1, 0, this->coeff);
 318
 319         key->len = this->k * 8;
 320         key->ptr = allocator_alloc(key->len);
 321         memcpy(key->ptr + this->k * 0, n.ptr , n.len);
 322         memcpy(key->ptr + this->k * 1, e.ptr, e.len);
 323         memcpy(key->ptr + this->k * 2, p.ptr, p.len);
 324         memcpy(key->ptr + this->k * 3, q.ptr, q.len);
 325         memcpy(key->ptr + this->k * 4, d.ptr, d.len);
 326         memcpy(key->ptr + this->k * 5, exp1.ptr, exp1.len);
 327         memcpy(key->ptr + this->k * 6, exp2.ptr, exp2.len);
 328         memcpy(key->ptr + this->k * 7, coeff.ptr, coeff.len);
 329
 330         allocator_free(n.ptr);
 331         allocator_free(e.ptr);
 332         allocator_free(p.ptr);
 333         allocator_free(q.ptr);
 334         allocator_free(d.ptr);
 335         allocator_free(exp1.ptr);
 336         allocator_free(exp2.ptr);
 337         allocator_free(coeff.ptr);
 338
 339         return SUCCESS;
 340 }
 341
 342 /**
 343  * implementation of rsa_private_key.load_key.
 344  */
 345 static status_t load_key(private_rsa_private_key_t *this, char *file)
 346 {
 347         return NOT_SUPPORTED;
 348 }
 349
 350 /**
 351  * implementation of rsa_private_key.save_key.
 352  */
 353 static status_t save_key(private_rsa_private_key_t *this, char *file)
 354 {
 355         return NOT_SUPPORTED;
 356 }
 357
 358 /**
 359  * implementation of rsa_private_key.generate_key.
 360  */
 361 static status_t generate_key(private_rsa_private_key_t *this, size_t key_size)
 362 {
 363         mpz_t p, q, n, e, d, exp1, exp2, coeff;
 364         mpz_t m, q1, t;
 365
 366         if (key_size <= 0)
 367         {
 368                 return INVALID_ARG;
 369         }
 370
 371         if (this->is_key_set)
 372         {
 373                 mpz_clear(this->n);
 374                 mpz_clear(this->e);
 375                 mpz_clear(this->p);
 376                 mpz_clear(this->q);
 377                 mpz_clear(this->d);
 378                 mpz_clear(this->exp1);
 379                 mpz_clear(this->exp2);
 380                 mpz_clear(this->coeff);
 381         }
 382
 383         key_size = key_size / 8;
 384
 385         mpz_init(t);
 386         mpz_init(n);
 387         mpz_init(d);
 388         mpz_init(exp1);
 389         mpz_init(exp2);
 390         mpz_init(coeff);
 391
 392         /* Get values of primes p and q  */
 393         charon->prime_pool->get_prime(charon->prime_pool, key_size/2, &p);
 394         charon->prime_pool->get_prime(charon->prime_pool, key_size/2, &q);
 395
 396         /* Swapping Primes so p is larger then q */
 397         if (mpz_cmp(p, q) < 0)
 398         {
 399                 mpz_set(t, p);
 400                 mpz_set(p, q);
 401                 mpz_set(q, t);
 402         }
 403
 404         mpz_mul(n, p, q);                                               /* n = p*q */
 405         mpz_init_set_ui(e, PUBLIC_EXPONENT);    /* assign public exponent */
 406         mpz_init_set(m, p);                                     /* m = p */
 407         mpz_sub_ui(m, m, 1);                                    /* m = m -1 */
 408         mpz_init_set(q1, q);                                    /* q1 = q */
 409         mpz_sub_ui(q1, q1, 1);                                  /* q1 = q1 -1 */
 410         mpz_gcd(t, m, q1);                                              /* t = gcd(p-1, q-1) */
 411         mpz_mul(m, m, q1);                                              /* m = (p-1)*(q-1) */
 412         mpz_divexact(m, m, t);                                  /* m = m / t */
 413         mpz_gcd(t, m, e);                                               /* t = gcd(m, e) (greatest common divisor) */
 414
 415         mpz_invert(d, e, m);                                    /* e has an inverse mod m */
 416         if (mpz_cmp_ui(d, 0) < 0)                               /* make sure d is positive */
 417         {
 418                 mpz_add(d, d, m);
 419         }
 420         mpz_sub_ui(t, p, 1);                                    /* t = p-1 */
 421         mpz_mod(exp1, d, t);                                    /* exp1 = d mod p-1 */
 422         mpz_sub_ui(t, q, 1);                                    /* t = q-1 */
 423         mpz_mod(exp2, d, t);                                    /* exp2 = d mod q-1 */
 424
 425         mpz_invert(coeff, q, p);                                /* coeff = q^-1 mod p */
 426         if (mpz_cmp_ui(coeff, 0) < 0)                   /* make coeff d is positive */
 427         {
 428                 mpz_add(coeff, coeff, p);
 429         }
 430
 431         mpz_clear(q1);
 432         mpz_clear(m);
 433         mpz_clear(t);
 434
 435         /* apply values */
 436         *(this->p) = *p;
 437         *(this->q) = *q;
 438         *(this->n) = *n;
 439         *(this->e) = *e;
 440         *(this->d) = *d;
 441         *(this->exp1) = *exp1;
 442         *(this->exp2) = *exp2;
 443         *(this->coeff) = *coeff;
 444
 445         /* set key size in bytes */
 446
 447         this->is_key_set = TRUE;
 448         this->k = key_size;
 449
 450         return SUCCESS;
 451 }
 452
 453
 454 rsa_public_key_t *get_public_key(private_rsa_private_key_t *this)
 455 {
 456         rsa_public_key_t *public_key;
 457         //chunk_t key;
 458
 459         public_key = rsa_public_key_create();
 460
 461         if (this->is_key_set)
 462         {
 463
 464                 chunk_t n, e, key;
 465
 466                 n.len = this->k;
 467                 n.ptr = mpz_export(NULL, NULL, 1, n.len, 1, 0, this->n);
 468                 e.len = this->k;
 469                 e.ptr = mpz_export(NULL, NULL, 1, e.len, 1, 0, this->e);
 470
 471                 key.len = this->k * 2;
 472                 key.ptr = allocator_alloc(key.len);
 473                 memcpy(key.ptr, n.ptr, n.len);
 474                 memcpy(key.ptr + n.len, e.ptr, e.len);
 475                 allocator_free(n.ptr);
 476                 allocator_free(e.ptr);
 477
 478                 public_key->set_key(public_key, key);
 479                 allocator_free(key.ptr);
 480
 481         }
 482
 483         return public_key;
 484 }
 485
 486
 487 /**
 488  * implementation of rsa_private_key.destroy.
 489  */
 490 static void destroy(private_rsa_private_key_t *this)
 491 {
 492         if (this->is_key_set)
 493         {
 494                 mpz_clear(this->n);
 495                 mpz_clear(this->e);
 496                 mpz_clear(this->p);
 497                 mpz_clear(this->q);
 498                 mpz_clear(this->d);
 499                 mpz_clear(this->exp1);
 500                 mpz_clear(this->exp2);
 501                 mpz_clear(this->coeff);
 502         }
 503         allocator_free(this);
 504 }
 505
 506 /*
 507  * Described in header
 508  */
 509 rsa_private_key_t *rsa_private_key_create(hash_algorithm_t hash_algoritm)
 510 {
 511         private_rsa_private_key_t *this = allocator_alloc_thing(private_rsa_private_key_t);
 512
 513         /* public functions */
 514         this->public.build_emsa_pkcs1_signature = (status_t (*) (rsa_private_key_t*,hash_algorithm_t,chunk_t,chunk_t*))build_emsa_pkcs1_signature;
 515         this->public.set_key = (status_t (*) (rsa_private_key_t*,chunk_t))set_key;
 516         this->public.get_key = (status_t (*) (rsa_private_key_t*,chunk_t*))get_key;
 517         this->public.load_key = (status_t (*) (rsa_private_key_t*,char*))load_key;
 518         this->public.save_key = (status_t (*) (rsa_private_key_t*,char*))save_key;
 519         this->public.generate_key = (status_t (*) (rsa_private_key_t*,size_t))generate_key;
 520         this->public.get_public_key = (rsa_public_key_t *(*) (rsa_private_key_t*))get_public_key;
 521         this->public.destroy = (void (*) (rsa_private_key_t*))destroy;
 522
 523         /* private functions */
 524         this->rsadp = rsadp;
 525         this->rsasp1 = rsadp; /* same algorithm */
 526
 527         this->is_key_set = FALSE;
 528
 529         return &(this->public);
 530 }