projects / strongswan.git / blob
? search:


a50acaeceaaa6edb57185fd3fe0af0384a4437a2
[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 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
334 /* build chunk to rsa-decrypt:
335 * EM = 0x00 || 0x01 || PS || 0x00 || T.
336 * PS = 0xFF padding, with length to fill em
337 * T = encoded_hash
338 */
339 em.len = this->k;
340 em.ptr = malloc(em.len);
341
342 /* fill em with padding */
343 memset(em.ptr, 0xFF, em.len);
344 /* set magic bytes */
345 *(em.ptr) = 0x00;
346 *(em.ptr+1) = 0x01;
347 *(em.ptr + em.len - encoded_hash.len - 1) = 0x00;
348 /* set DER-encoded hash */
349 memcpy(em.ptr + em.len - encoded_hash.len, encoded_hash.ptr, encoded_hash.len);
350
351 /* build signature */
352 *signature = this->rsasp1(this, em);
353
354 free(encoded_hash.ptr);
355 free(em.ptr);
356
357 return SUCCESS;
358 }
359
360 /**
361 * Implementation of rsa_private_key.save_key.
362 */
363 static status_t save_key(private_rsa_private_key_t *this, char *file)
364 {
365 return NOT_SUPPORTED;
366 }
367
368 /**
369 * Implementation of rsa_private_key.get_public_key.
370 */
371 rsa_public_key_t *get_public_key(private_rsa_private_key_t *this)
372 {
373 return NULL;
374 }
375
376 /**
377 * Implementation of rsa_private_key.belongs_to.
378 */
379 static bool belongs_to(private_rsa_private_key_t *this, rsa_public_key_t *public)
380 {
381 return chunk_equals(this->keyid, public->get_keyid(public));
382 }
383
384 /**
385 * Check the loaded key if it is valid and usable
386 * TODO: Log errors
387 */
388 static status_t check(private_rsa_private_key_t *this)
389 {
390 mpz_t t, u, q1;
391 status_t status = SUCCESS;
392
393 /* PKCS#1 1.5 section 6 requires modulus to have at least 12 octets.
394 * We actually require more (for security).
395 */
396 if (this->k < 512/8)
397 {
398 return FAILED;
399 }
400
401 /* we picked a max modulus size to simplify buffer allocation */
402 if (this->k > 8192/8)
403 {
404 return FAILED;
405 }
406
407 mpz_init(t);
408 mpz_init(u);
409 mpz_init(q1);
410
411 /* check that n == p * q */
412 mpz_mul(u, this->p, this->q);
413 if (mpz_cmp(u, this->n) != 0)
414 {
415 status = FAILED;
416 }
417
418 /* check that e divides neither p-1 nor q-1 */
419 mpz_sub_ui(t, this->p, 1);
420 mpz_mod(t, t, this->e);
421 if (mpz_cmp_ui(t, 0) == 0)
422 {
423 status = FAILED;
424 }
425
426 mpz_sub_ui(t, this->q, 1);
427 mpz_mod(t, t, this->e);
428 if (mpz_cmp_ui(t, 0) == 0)
429 {
430 status = FAILED;
431 }
432
433 /* check that d is e^-1 (mod lcm(p-1, q-1)) */
434 /* see PKCS#1v2, aka RFC 2437, for the "lcm" */
435 mpz_sub_ui(q1, this->q, 1);
436 mpz_sub_ui(u, this->p, 1);
437 mpz_gcd(t, u, q1); /* t := gcd(p-1, q-1) */
438 mpz_mul(u, u, q1); /* u := (p-1) * (q-1) */
439 mpz_divexact(u, u, t); /* u := lcm(p-1, q-1) */
440
441 mpz_mul(t, this->d, this->e);
442 mpz_mod(t, t, u);
443 if (mpz_cmp_ui(t, 1) != 0)
444 {
445 status = FAILED;
446 }
447
448 /* check that exp1 is d mod (p-1) */
449 mpz_sub_ui(u, this->p, 1);
450 mpz_mod(t, this->d, u);
451 if (mpz_cmp(t, this->exp1) != 0)
452 {
453 status = FAILED;
454 }
455
456 /* check that exp2 is d mod (q-1) */
457 mpz_sub_ui(u, this->q, 1);
458 mpz_mod(t, this->d, u);
459 if (mpz_cmp(t, this->exp2) != 0)
460 {
461 status = FAILED;
462 }
463
464 /* check that coeff is (q^-1) mod p */
465 mpz_mul(t, this->coeff, this->q);
466 mpz_mod(t, t, this->p);
467 if (mpz_cmp_ui(t, 1) != 0)
468 {
469 status = FAILED;
470 }
471
472 mpz_clear_randomized(t);
473 mpz_clear_randomized(u);
474 mpz_clear_randomized(q1);
475 return status;
476 }
477
478 /**
479 * Implementation of rsa_private_key.destroy.
480 */
481 static void destroy(private_rsa_private_key_t *this)
482 {
483 mpz_clear_randomized(this->n);
484 mpz_clear_randomized(this->e);
485 mpz_clear_randomized(this->p);
486 mpz_clear_randomized(this->q);
487 mpz_clear_randomized(this->d);
488 mpz_clear_randomized(this->exp1);
489 mpz_clear_randomized(this->exp2);
490 mpz_clear_randomized(this->coeff);
491 chunk_free_randomized(&this->keyid);
492 free(this);
493 }
494
495 /**
496 * Internal generic constructor
497 */
498 static private_rsa_private_key_t *rsa_private_key_create_empty(void)
499 {
500 private_rsa_private_key_t *this = malloc_thing(private_rsa_private_key_t);
501
502 /* public functions */
503 this->public.build_emsa_pkcs1_signature = (status_t (*) (rsa_private_key_t*,hash_algorithm_t,chunk_t,chunk_t*))build_emsa_pkcs1_signature;
504 this->public.save_key = (status_t (*) (rsa_private_key_t*,char*))save_key;
505 this->public.get_public_key = (rsa_public_key_t *(*) (rsa_private_key_t*))get_public_key;
506 this->public.belongs_to = (bool (*) (rsa_private_key_t*,rsa_public_key_t*))belongs_to;
507 this->public.destroy = (void (*) (rsa_private_key_t*))destroy;
508
509 /* private functions */
510 this->rsadp = rsadp;
511 this->rsasp1 = rsadp; /* same algorithm */
512 this->compute_prime = compute_prime;
513
514 this->keyid = chunk_empty;
515
516 return this;
517 }
518
519 /*
520 * See header
521 */
522 rsa_private_key_t *rsa_private_key_create(size_t key_size)
523 {
524 mpz_t p, q, n, e, d, exp1, exp2, coeff;
525 mpz_t m, q1, t;
526 private_rsa_private_key_t *this;
527
528 this = rsa_private_key_create_empty();
529 key_size = key_size / 8;
530
531 /* Get values of primes p and q */
532 if (this->compute_prime(this, key_size/2, &p) != SUCCESS)
533 {
534 free(this);
535 return NULL;
536 }
537 if (this->compute_prime(this, key_size/2, &q) != SUCCESS)
538 {
539 mpz_clear(p);
540 free(this);
541 return NULL;
542 }
543
544 mpz_init(t);
545 mpz_init(n);
546 mpz_init(d);
547 mpz_init(exp1);
548 mpz_init(exp2);
549 mpz_init(coeff);
550
551 /* Swapping Primes so p is larger then q */
552 if (mpz_cmp(p, q) < 0)
553 {
554 mpz_swap(p, q);
555 }
556
557 mpz_mul(n, p, q); /* n = p*q */
558 mpz_init_set_ui(e, PUBLIC_EXPONENT); /* assign public exponent */
559 mpz_init_set(m, p); /* m = p */
560 mpz_sub_ui(m, m, 1); /* m = m -1 */
561 mpz_init_set(q1, q); /* q1 = q */
562 mpz_sub_ui(q1, q1, 1); /* q1 = q1 -1 */
563 mpz_gcd(t, m, q1); /* t = gcd(p-1, q-1) */
564 mpz_mul(m, m, q1); /* m = (p-1)*(q-1) */
565 mpz_divexact(m, m, t); /* m = m / t */
566 mpz_gcd(t, m, e); /* t = gcd(m, e) (greatest common divisor) */
567
568 mpz_invert(d, e, m); /* e has an inverse mod m */
569 if (mpz_cmp_ui(d, 0) < 0) /* make sure d is positive */
570 {
571 mpz_add(d, d, m);
572 }
573 mpz_sub_ui(t, p, 1); /* t = p-1 */
574 mpz_mod(exp1, d, t); /* exp1 = d mod p-1 */
575 mpz_sub_ui(t, q, 1); /* t = q-1 */
576 mpz_mod(exp2, d, t); /* exp2 = d mod q-1 */
577
578 mpz_invert(coeff, q, p); /* coeff = q^-1 mod p */
579 if (mpz_cmp_ui(coeff, 0) < 0) /* make coeff d is positive */
580 {
581 mpz_add(coeff, coeff, p);
582 }
583
584 mpz_clear_randomized(q1);
585 mpz_clear_randomized(m);
586 mpz_clear_randomized(t);
587
588 /* apply values */
589 *(this->p) = *p;
590 *(this->q) = *q;
591 *(this->n) = *n;
592 *(this->e) = *e;
593 *(this->d) = *d;
594 *(this->exp1) = *exp1;
595 *(this->exp2) = *exp2;
596 *(this->coeff) = *coeff;
597
598 /* set key size in bytes */
599 this->k = key_size;
600
601 return &this->public;
602 }
603
604 /*
605 * see header
606 */
607 rsa_private_key_t *rsa_private_key_create_from_chunk(chunk_t blob)
608 {
609 asn1_ctx_t ctx;
610 chunk_t object;
611 u_int level;
612 int objectID = 0;
613 private_rsa_private_key_t *this;
614
615 this = rsa_private_key_create_empty();
616
617 mpz_init(this->n);
618 mpz_init(this->e);
619 mpz_init(this->p);
620 mpz_init(this->q);
621 mpz_init(this->d);
622 mpz_init(this->exp1);
623 mpz_init(this->exp2);
624 mpz_init(this->coeff);
625
626 asn1_init(&ctx, blob, 0, FALSE, TRUE);
627
628 while (objectID < PRIV_KEY_ROOF)
629 {
630 if (!extract_object(privkey_objects, &objectID, &object, &level, &ctx))
631 {
632 destroy(this);
633 return FALSE;
634 }
635 switch (objectID)
636 {
637 case PRIV_KEY_VERSION:
638 if (object.len > 0 && *object.ptr != 0)
639 {
640 destroy(this);
641 return NULL;
642 }
643 break;
644 case PRIV_KEY_MODULUS:
645 mpz_import(this->n, object.len, 1, 1, 1, 0, object.ptr);
646 break;
647 case PRIV_KEY_PUB_EXP:
648 mpz_import(this->e, object.len, 1, 1, 1, 0, object.ptr);
649 break;
650 case PRIV_KEY_PRIV_EXP:
651 mpz_import(this->d, object.len, 1, 1, 1, 0, object.ptr);
652 break;
653 case PRIV_KEY_PRIME1:
654 mpz_import(this->p, object.len, 1, 1, 1, 0, object.ptr);
655 break;
656 case PRIV_KEY_PRIME2:
657 mpz_import(this->q, object.len, 1, 1, 1, 0, object.ptr);
658 break;
659 case PRIV_KEY_EXP1:
660 mpz_import(this->exp1, object.len, 1, 1, 1, 0, object.ptr);
661 break;
662 case PRIV_KEY_EXP2:
663 mpz_import(this->exp2, object.len, 1, 1, 1, 0, object.ptr);
664 break;
665 case PRIV_KEY_COEFF:
666 mpz_import(this->coeff, object.len, 1, 1, 1, 0, object.ptr);
667 break;
668 }
669 objectID++;
670 }
671
672 this->k = (mpz_sizeinbase(this->n, 2) + 7) / 8;
673
674 /* form the keyid as a SHA-1 hash of a publicKeyInfo object */
675 {
676 chunk_t publicKeyInfo = rsa_public_key_info_to_asn1(this->n, this->e);
677 hasher_t *hasher = hasher_create(HASH_SHA1);
678
679 hasher->allocate_hash(hasher, publicKeyInfo, &this->keyid);
680 hasher->destroy(hasher);
681 free(publicKeyInfo.ptr);
682 }
683
684 if (check(this) != SUCCESS)
685 {
686 destroy(this);
687 return NULL;
688 }
689 else
690 {
691 return &this->public;
692 }
693 }
694
695 /*
696 * see header
697 */
698 rsa_private_key_t *rsa_private_key_create_from_file(char *filename, chunk_t *passphrase)
699 {
700 bool pgp = FALSE;
701 chunk_t chunk = chunk_empty;
702 rsa_private_key_t *key = NULL;
703
704 if (!pem_asn1_load_file(filename, passphrase, "private key", &chunk, &pgp))
705 return NULL;
706
707 key = rsa_private_key_create_from_chunk(chunk);
708 chunk_free_randomized(&chunk);
709 return key;
710 }
strongSwan - IPsec VPN