fixed warnings and memory leak
[strongswan.git] / src / libstrongswan / crypto / 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-2006 Martin Willi
10 * Copyright (C) 2005 Jan Hutter
11 * Hochschule fuer Technik Rapperswil
12 *
13 * This program is free software; you can redistribute it and/or modify it
14 * under the terms of the GNU General Public License as published by the
15 * Free Software Foundation; either version 2 of the License, or (at your
16 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
17 *
18 * This program is distributed in the hope that it will be useful, but
19 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
20 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 * for more details.
22 */
23
24 #include <gmp.h>
25 #include <sys/stat.h>
26 #include <unistd.h>
27 #include <string.h>
28
29 #include "rsa_public_key.h"
30 #include "rsa_private_key.h"
31
32 #include <asn1/asn1.h>
33 #include <asn1/pem.h>
34 #include <utils/randomizer.h>
35
36 /**
37 * defined in rsa_public_key.c
38 */
39 extern chunk_t rsa_public_key_info_to_asn1(const mpz_t n, const mpz_t e);
40
41 /**
42 * Public exponent to use for key generation.
43 */
44 #define PUBLIC_EXPONENT 0x10001
45
46 typedef struct private_rsa_private_key_t private_rsa_private_key_t;
47
48 /**
49 * Private data of a rsa_private_key_t object.
50 */
51 struct private_rsa_private_key_t {
52 /**
53 * Public interface for this signer.
54 */
55 rsa_private_key_t public;
56
57 /**
58 * Version of key, as encoded in PKCS#1
59 */
60 u_int version;
61
62 /**
63 * Public modulus.
64 */
65 mpz_t n;
66
67 /**
68 * Public exponent.
69 */
70 mpz_t e;
71
72 /**
73 * Private prime 1.
74 */
75 mpz_t p;
76
77 /**
78 * Private Prime 2.
79 */
80 mpz_t q;
81
82 /**
83 * Private exponent.
84 */
85 mpz_t d;
86
87 /**
88 * Private exponent 1.
89 */
90 mpz_t exp1;
91
92 /**
93 * Private exponent 2.
94 */
95 mpz_t exp2;
96
97 /**
98 * Private coefficient.
99 */
100 mpz_t coeff;
101
102 /**
103 * Keysize in bytes.
104 */
105 size_t k;
106
107 /**
108 * Keyid formed as a SHA-1 hash of a publicKeyInfo object
109 */
110 chunk_t keyid;
111
112
113 /**
114 * @brief Implements the RSADP algorithm specified in PKCS#1.
115 *
116 * @param this calling object
117 * @param data data to process
118 * @return processed data
119 */
120 chunk_t (*rsadp) (private_rsa_private_key_t *this, chunk_t data);
121
122 /**
123 * @brief Implements the RSASP1 algorithm specified in PKCS#1.
124 * @param this calling object
125 * @param data data to process
126 * @return processed data
127 */
128 chunk_t (*rsasp1) (private_rsa_private_key_t *this, chunk_t data);
129
130 /**
131 * @brief Generate a prime value.
132 *
133 * @param this calling object
134 * @param prime_size size of the prime, in bytes
135 * @param[out] prime uninitialized mpz
136 */
137 status_t (*compute_prime) (private_rsa_private_key_t *this, size_t prime_size, mpz_t *prime);
138
139 };
140
141 /* ASN.1 definition of a PKCS#1 RSA private key */
142 static const asn1Object_t privkey_objects[] = {
143 { 0, "RSAPrivateKey", ASN1_SEQUENCE, ASN1_NONE }, /* 0 */
144 { 1, "version", ASN1_INTEGER, ASN1_BODY }, /* 1 */
145 { 1, "modulus", ASN1_INTEGER, ASN1_BODY }, /* 2 */
146 { 1, "publicExponent", ASN1_INTEGER, ASN1_BODY }, /* 3 */
147 { 1, "privateExponent", ASN1_INTEGER, ASN1_BODY }, /* 4 */
148 { 1, "prime1", ASN1_INTEGER, ASN1_BODY }, /* 5 */
149 { 1, "prime2", ASN1_INTEGER, ASN1_BODY }, /* 6 */
150 { 1, "exponent1", ASN1_INTEGER, ASN1_BODY }, /* 7 */
151 { 1, "exponent2", ASN1_INTEGER, ASN1_BODY }, /* 8 */
152 { 1, "coefficient", ASN1_INTEGER, ASN1_BODY }, /* 9 */
153 { 1, "otherPrimeInfos", ASN1_SEQUENCE, ASN1_OPT |
154 ASN1_LOOP }, /* 10 */
155 { 2, "otherPrimeInfo", ASN1_SEQUENCE, ASN1_NONE }, /* 11 */
156 { 3, "prime", ASN1_INTEGER, ASN1_BODY }, /* 12 */
157 { 3, "exponent", ASN1_INTEGER, ASN1_BODY }, /* 13 */
158 { 3, "coefficient", ASN1_INTEGER, ASN1_BODY }, /* 14 */
159 { 1, "end opt or loop", ASN1_EOC, ASN1_END } /* 15 */
160 };
161
162 #define PRIV_KEY_VERSION 1
163 #define PRIV_KEY_MODULUS 2
164 #define PRIV_KEY_PUB_EXP 3
165 #define PRIV_KEY_PRIV_EXP 4
166 #define PRIV_KEY_PRIME1 5
167 #define PRIV_KEY_PRIME2 6
168 #define PRIV_KEY_EXP1 7
169 #define PRIV_KEY_EXP2 8
170 #define PRIV_KEY_COEFF 9
171 #define PRIV_KEY_ROOF 16
172
173 static private_rsa_private_key_t *rsa_private_key_create_empty(void);
174
175 /**
176 * Auxiliary function overwriting private key material with
177 * pseudo-random bytes before releasing it
178 */
179 static void mpz_clear_randomized(mpz_t z)
180 {
181 size_t len = mpz_size(z) * GMP_LIMB_BITS / BITS_PER_BYTE;
182 u_int8_t *random_bytes = alloca(len);
183
184 randomizer_t *randomizer = randomizer_create();
185
186 randomizer->get_pseudo_random_bytes(randomizer, len, random_bytes);
187
188 /* overwrite mpz_t with pseudo-random bytes before clearing it */
189 mpz_import(z, len, 1, 1, 1, 0, random_bytes);
190 mpz_clear(z);
191
192 randomizer->destroy(randomizer);
193 }
194
195 /**
196 * Implementation of private_rsa_private_key_t.compute_prime.
197 */
198 static status_t compute_prime(private_rsa_private_key_t *this, size_t prime_size, mpz_t *prime)
199 {
200 randomizer_t *randomizer;
201 chunk_t random_bytes;
202 status_t status;
203
204 randomizer = randomizer_create();
205 mpz_init(*prime);
206
207 do
208 {
209 status = randomizer->allocate_random_bytes(randomizer, prime_size, &random_bytes);
210 if (status != SUCCESS)
211 {
212 randomizer->destroy(randomizer);
213 mpz_clear(*prime);
214 return FAILED;
215 }
216
217 /* make sure most significant bit is set */
218 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
219
220 /* convert chunk to mpz value */
221 mpz_import(*prime, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
222
223 /* get next prime */
224 mpz_nextprime (*prime, *prime);
225
226 /* free the random_bytes after overwriting them with a pseudo-random sequence */
227 chunk_free_randomized(&random_bytes);
228 }
229 /* check if it isnt too large */
230 while (((mpz_sizeinbase(*prime, 2) + 7) / 8) > prime_size);
231
232 randomizer->destroy(randomizer);
233 return SUCCESS;
234 }
235
236 /**
237 * Implementation of private_rsa_private_key_t.rsadp and private_rsa_private_key_t.rsasp1.
238 */
239 static chunk_t rsadp(private_rsa_private_key_t *this, chunk_t data)
240 {
241 mpz_t t1, t2;
242 chunk_t decrypted;
243
244 mpz_init(t1);
245 mpz_init(t2);
246
247 mpz_import(t1, data.len, 1, 1, 1, 0, data.ptr);
248
249 mpz_powm(t2, t1, this->exp1, this->p); /* m1 = c^dP mod p */
250 mpz_powm(t1, t1, this->exp2, this->q); /* m2 = c^dQ mod Q */
251 mpz_sub(t2, t2, t1); /* h = qInv (m1 - m2) mod p */
252 mpz_mod(t2, t2, this->p);
253 mpz_mul(t2, t2, this->coeff);
254 mpz_mod(t2, t2, this->p);
255
256 mpz_mul(t2, t2, this->q); /* m = m2 + h q */
257 mpz_add(t1, t1, t2);
258
259 decrypted.len = this->k;
260 decrypted.ptr = mpz_export(NULL, NULL, 1, decrypted.len, 1, 0, t1);
261
262 mpz_clear_randomized(t1);
263 mpz_clear_randomized(t2);
264
265 return decrypted;
266 }
267
268 /**
269 * Implementation of rsa_private_key.build_emsa_signature.
270 */
271 static status_t build_emsa_pkcs1_signature(private_rsa_private_key_t *this,
272 hash_algorithm_t hash_algorithm,
273 chunk_t data, chunk_t *signature)
274 {
275 hasher_t *hasher;
276 chunk_t em, encoded_hash, hash_id, hash;
277
278 /* get oid string prepended to hash */
279 switch (hash_algorithm)
280 {
281 case HASH_MD2:
282 {
283 hash_id =ASN1_md2_id;
284 break;
285 }
286 case HASH_MD5:
287 {
288 hash_id = ASN1_md5_id;
289 break;
290 }
291 case HASH_SHA1:
292 {
293 hash_id = ASN1_sha1_id;
294 break;
295 }
296 case HASH_SHA256:
297 {
298 hash_id = ASN1_sha256_id;
299 break;
300 }
301 case HASH_SHA384:
302 {
303 hash_id = ASN1_sha384_id;
304 break;
305 }
306 case HASH_SHA512:
307 {
308 hash_id = ASN1_sha512_id;
309 break;
310 }
311 default:
312 {
313 return NOT_SUPPORTED;
314 }
315 }
316
317 /* get hasher */
318 hasher = hasher_create(hash_algorithm);
319 if (hasher == NULL)
320 {
321 return NOT_SUPPORTED;
322 }
323
324 /* build hash */
325 hasher->allocate_hash(hasher, data, &hash);
326 hasher->destroy(hasher);
327
328 /* build DER-encoded hash */
329 encoded_hash = asn1_wrap(ASN1_SEQUENCE, "cm",
330 hash_id,
331 asn1_simple_object(ASN1_OCTET_STRING, hash)
332 );
333 chunk_free(&hash);
334
335 /* build chunk to rsa-decrypt:
336 * EM = 0x00 || 0x01 || PS || 0x00 || T.
337 * PS = 0xFF padding, with length to fill em
338 * T = encoded_hash
339 */
340 em.len = this->k;
341 em.ptr = malloc(em.len);
342
343 /* fill em with padding */
344 memset(em.ptr, 0xFF, em.len);
345 /* set magic bytes */
346 *(em.ptr) = 0x00;
347 *(em.ptr+1) = 0x01;
348 *(em.ptr + em.len - encoded_hash.len - 1) = 0x00;
349 /* set DER-encoded hash */
350 memcpy(em.ptr + em.len - encoded_hash.len, encoded_hash.ptr, encoded_hash.len);
351
352 /* build signature */
353 *signature = this->rsasp1(this, em);
354
355 free(encoded_hash.ptr);
356 free(em.ptr);
357
358 return SUCCESS;
359 }
360
361 /**
362 * Implementation of rsa_private_key.save_key.
363 */
364 static status_t save_key(private_rsa_private_key_t *this, char *file)
365 {
366 return NOT_SUPPORTED;
367 }
368
369 /**
370 * Implementation of rsa_private_key.get_public_key.
371 */
372 rsa_public_key_t *get_public_key(private_rsa_private_key_t *this)
373 {
374 return NULL;
375 }
376
377 /**
378 * Implementation of rsa_private_key.belongs_to.
379 */
380 static bool belongs_to(private_rsa_private_key_t *this, rsa_public_key_t *public)
381 {
382 return chunk_equals(this->keyid, public->get_keyid(public));
383 }
384
385 /**
386 * Check the loaded key if it is valid and usable
387 * TODO: Log errors
388 */
389 static status_t check(private_rsa_private_key_t *this)
390 {
391 mpz_t t, u, q1;
392 status_t status = SUCCESS;
393
394 /* PKCS#1 1.5 section 6 requires modulus to have at least 12 octets.
395 * We actually require more (for security).
396 */
397 if (this->k < 512/8)
398 {
399 return FAILED;
400 }
401
402 /* we picked a max modulus size to simplify buffer allocation */
403 if (this->k > 8192/8)
404 {
405 return FAILED;
406 }
407
408 mpz_init(t);
409 mpz_init(u);
410 mpz_init(q1);
411
412 /* check that n == p * q */
413 mpz_mul(u, this->p, this->q);
414 if (mpz_cmp(u, this->n) != 0)
415 {
416 status = FAILED;
417 }
418
419 /* check that e divides neither p-1 nor q-1 */
420 mpz_sub_ui(t, this->p, 1);
421 mpz_mod(t, t, this->e);
422 if (mpz_cmp_ui(t, 0) == 0)
423 {
424 status = FAILED;
425 }
426
427 mpz_sub_ui(t, this->q, 1);
428 mpz_mod(t, t, this->e);
429 if (mpz_cmp_ui(t, 0) == 0)
430 {
431 status = FAILED;
432 }
433
434 /* check that d is e^-1 (mod lcm(p-1, q-1)) */
435 /* see PKCS#1v2, aka RFC 2437, for the "lcm" */
436 mpz_sub_ui(q1, this->q, 1);
437 mpz_sub_ui(u, this->p, 1);
438 mpz_gcd(t, u, q1); /* t := gcd(p-1, q-1) */
439 mpz_mul(u, u, q1); /* u := (p-1) * (q-1) */
440 mpz_divexact(u, u, t); /* u := lcm(p-1, q-1) */
441
442 mpz_mul(t, this->d, this->e);
443 mpz_mod(t, t, u);
444 if (mpz_cmp_ui(t, 1) != 0)
445 {
446 status = FAILED;
447 }
448
449 /* check that exp1 is d mod (p-1) */
450 mpz_sub_ui(u, this->p, 1);
451 mpz_mod(t, this->d, u);
452 if (mpz_cmp(t, this->exp1) != 0)
453 {
454 status = FAILED;
455 }
456
457 /* check that exp2 is d mod (q-1) */
458 mpz_sub_ui(u, this->q, 1);
459 mpz_mod(t, this->d, u);
460 if (mpz_cmp(t, this->exp2) != 0)
461 {
462 status = FAILED;
463 }
464
465 /* check that coeff is (q^-1) mod p */
466 mpz_mul(t, this->coeff, this->q);
467 mpz_mod(t, t, this->p);
468 if (mpz_cmp_ui(t, 1) != 0)
469 {
470 status = FAILED;
471 }
472
473 mpz_clear_randomized(t);
474 mpz_clear_randomized(u);
475 mpz_clear_randomized(q1);
476 return status;
477 }
478
479 /**
480 * Implementation of rsa_private_key.destroy.
481 */
482 static void destroy(private_rsa_private_key_t *this)
483 {
484 mpz_clear_randomized(this->n);
485 mpz_clear_randomized(this->e);
486 mpz_clear_randomized(this->p);
487 mpz_clear_randomized(this->q);
488 mpz_clear_randomized(this->d);
489 mpz_clear_randomized(this->exp1);
490 mpz_clear_randomized(this->exp2);
491 mpz_clear_randomized(this->coeff);
492 chunk_free_randomized(&this->keyid);
493 free(this);
494 }
495
496 /**
497 * Internal generic constructor
498 */
499 static private_rsa_private_key_t *rsa_private_key_create_empty(void)
500 {
501 private_rsa_private_key_t *this = malloc_thing(private_rsa_private_key_t);
502
503 /* public functions */
504 this->public.build_emsa_pkcs1_signature = (status_t (*) (rsa_private_key_t*,hash_algorithm_t,chunk_t,chunk_t*))build_emsa_pkcs1_signature;
505 this->public.save_key = (status_t (*) (rsa_private_key_t*,char*))save_key;
506 this->public.get_public_key = (rsa_public_key_t *(*) (rsa_private_key_t*))get_public_key;
507 this->public.belongs_to = (bool (*) (rsa_private_key_t*,rsa_public_key_t*))belongs_to;
508 this->public.destroy = (void (*) (rsa_private_key_t*))destroy;
509
510 /* private functions */
511 this->rsadp = rsadp;
512 this->rsasp1 = rsadp; /* same algorithm */
513 this->compute_prime = compute_prime;
514
515 this->keyid = chunk_empty;
516
517 return this;
518 }
519
520 /*
521 * See header
522 */
523 rsa_private_key_t *rsa_private_key_create(size_t key_size)
524 {
525 mpz_t p, q, n, e, d, exp1, exp2, coeff;
526 mpz_t m, q1, t;
527 private_rsa_private_key_t *this;
528
529 this = rsa_private_key_create_empty();
530 key_size = key_size / 8;
531
532 /* Get values of primes p and q */
533 if (this->compute_prime(this, key_size/2, &p) != SUCCESS)
534 {
535 free(this);
536 return NULL;
537 }
538 if (this->compute_prime(this, key_size/2, &q) != SUCCESS)
539 {
540 mpz_clear(p);
541 free(this);
542 return NULL;
543 }
544
545 mpz_init(t);
546 mpz_init(n);
547 mpz_init(d);
548 mpz_init(exp1);
549 mpz_init(exp2);
550 mpz_init(coeff);
551
552 /* Swapping Primes so p is larger then q */
553 if (mpz_cmp(p, q) < 0)
554 {
555 mpz_swap(p, q);
556 }
557
558 mpz_mul(n, p, q); /* n = p*q */
559 mpz_init_set_ui(e, PUBLIC_EXPONENT); /* assign public exponent */
560 mpz_init_set(m, p); /* m = p */
561 mpz_sub_ui(m, m, 1); /* m = m -1 */
562 mpz_init_set(q1, q); /* q1 = q */
563 mpz_sub_ui(q1, q1, 1); /* q1 = q1 -1 */
564 mpz_gcd(t, m, q1); /* t = gcd(p-1, q-1) */
565 mpz_mul(m, m, q1); /* m = (p-1)*(q-1) */
566 mpz_divexact(m, m, t); /* m = m / t */
567 mpz_gcd(t, m, e); /* t = gcd(m, e) (greatest common divisor) */
568
569 mpz_invert(d, e, m); /* e has an inverse mod m */
570 if (mpz_cmp_ui(d, 0) < 0) /* make sure d is positive */
571 {
572 mpz_add(d, d, m);
573 }
574 mpz_sub_ui(t, p, 1); /* t = p-1 */
575 mpz_mod(exp1, d, t); /* exp1 = d mod p-1 */
576 mpz_sub_ui(t, q, 1); /* t = q-1 */
577 mpz_mod(exp2, d, t); /* exp2 = d mod q-1 */
578
579 mpz_invert(coeff, q, p); /* coeff = q^-1 mod p */
580 if (mpz_cmp_ui(coeff, 0) < 0) /* make coeff d is positive */
581 {
582 mpz_add(coeff, coeff, p);
583 }
584
585 mpz_clear_randomized(q1);
586 mpz_clear_randomized(m);
587 mpz_clear_randomized(t);
588
589 /* apply values */
590 *(this->p) = *p;
591 *(this->q) = *q;
592 *(this->n) = *n;
593 *(this->e) = *e;
594 *(this->d) = *d;
595 *(this->exp1) = *exp1;
596 *(this->exp2) = *exp2;
597 *(this->coeff) = *coeff;
598
599 /* set key size in bytes */
600 this->k = key_size;
601
602 return &this->public;
603 }
604
605 /*
606 * see header
607 */
608 rsa_private_key_t *rsa_private_key_create_from_chunk(chunk_t blob)
609 {
610 asn1_ctx_t ctx;
611 chunk_t object;
612 u_int level;
613 int objectID = 0;
614 private_rsa_private_key_t *this;
615
616 this = rsa_private_key_create_empty();
617
618 mpz_init(this->n);
619 mpz_init(this->e);
620 mpz_init(this->p);
621 mpz_init(this->q);
622 mpz_init(this->d);
623 mpz_init(this->exp1);
624 mpz_init(this->exp2);
625 mpz_init(this->coeff);
626
627 asn1_init(&ctx, blob, 0, FALSE, TRUE);
628
629 while (objectID < PRIV_KEY_ROOF)
630 {
631 if (!extract_object(privkey_objects, &objectID, &object, &level, &ctx))
632 {
633 destroy(this);
634 return FALSE;
635 }
636 switch (objectID)
637 {
638 case PRIV_KEY_VERSION:
639 if (object.len > 0 && *object.ptr != 0)
640 {
641 destroy(this);
642 return NULL;
643 }
644 break;
645 case PRIV_KEY_MODULUS:
646 mpz_import(this->n, object.len, 1, 1, 1, 0, object.ptr);
647 break;
648 case PRIV_KEY_PUB_EXP:
649 mpz_import(this->e, object.len, 1, 1, 1, 0, object.ptr);
650 break;
651 case PRIV_KEY_PRIV_EXP:
652 mpz_import(this->d, object.len, 1, 1, 1, 0, object.ptr);
653 break;
654 case PRIV_KEY_PRIME1:
655 mpz_import(this->p, object.len, 1, 1, 1, 0, object.ptr);
656 break;
657 case PRIV_KEY_PRIME2:
658 mpz_import(this->q, object.len, 1, 1, 1, 0, object.ptr);
659 break;
660 case PRIV_KEY_EXP1:
661 mpz_import(this->exp1, object.len, 1, 1, 1, 0, object.ptr);
662 break;
663 case PRIV_KEY_EXP2:
664 mpz_import(this->exp2, object.len, 1, 1, 1, 0, object.ptr);
665 break;
666 case PRIV_KEY_COEFF:
667 mpz_import(this->coeff, object.len, 1, 1, 1, 0, object.ptr);
668 break;
669 }
670 objectID++;
671 }
672
673 this->k = (mpz_sizeinbase(this->n, 2) + 7) / 8;
674
675 /* form the keyid as a SHA-1 hash of a publicKeyInfo object */
676 {
677 chunk_t publicKeyInfo = rsa_public_key_info_to_asn1(this->n, this->e);
678 hasher_t *hasher = hasher_create(HASH_SHA1);
679
680 hasher->allocate_hash(hasher, publicKeyInfo, &this->keyid);
681 hasher->destroy(hasher);
682 free(publicKeyInfo.ptr);
683 }
684
685 if (check(this) != SUCCESS)
686 {
687 destroy(this);
688 return NULL;
689 }
690 else
691 {
692 return &this->public;
693 }
694 }
695
696 /*
697 * see header
698 */
699 rsa_private_key_t *rsa_private_key_create_from_file(char *filename, chunk_t *passphrase)
700 {
701 bool pgp = FALSE;
702 chunk_t chunk = chunk_empty;
703 rsa_private_key_t *key = NULL;
704
705 if (!pem_asn1_load_file(filename, passphrase, "private key", &chunk, &pgp))
706 return NULL;
707
708 key = rsa_private_key_create_from_chunk(chunk);
709 chunk_free_randomized(&chunk);
710 return key;
711 }