879cade2610e58fcd5324ffbd8fd80ea5774e19e
[strongswan.git] / Source / lib / 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 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 #include <sys/stat.h>
25 #include <unistd.h>
26 #include <string.h>
27
28 #include "rsa_private_key.h"
29
30 #include <daemon.h>
31 #include <asn1/der_decoder.h>
32
33
34 /*
35 * Oids for hash algorithms are defined in
36 * rsa_public_key.c.
37 */
38 extern u_int8_t md2_oid[18];
39 extern u_int8_t md5_oid[18];
40 extern u_int8_t sha1_oid[15];
41 extern u_int8_t sha256_oid[19];
42 extern u_int8_t sha384_oid[19];
43 extern u_int8_t sha512_oid[19];
44
45
46 /**
47 * Public exponent to use for key generation.
48 */
49 #define PUBLIC_EXPONENT 0x10001
50
51
52 typedef struct private_rsa_private_key_t private_rsa_private_key_t;
53
54 /**
55 * Private data of a rsa_private_key_t object.
56 */
57 struct private_rsa_private_key_t {
58 /**
59 * Public interface for this signer.
60 */
61 rsa_private_key_t public;
62
63 /**
64 * Version of key, as encoded in PKCS#1
65 */
66 u_int version;
67
68 /**
69 * Public modulus.
70 */
71 mpz_t n;
72
73 /**
74 * Public exponent.
75 */
76 mpz_t e;
77
78 /**
79 * Private prime 1.
80 */
81 mpz_t p;
82
83 /**
84 * Private Prime 2.
85 */
86 mpz_t q;
87
88 /**
89 * Private exponent.
90 */
91 mpz_t d;
92
93 /**
94 * Private exponent 1.
95 */
96 mpz_t exp1;
97
98 /**
99 * Private exponent 2.
100 */
101 mpz_t exp2;
102
103 /**
104 * Private coefficient.
105 */
106 mpz_t coeff;
107
108 /**
109 * Keysize in bytes.
110 */
111 size_t k;
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 /**
142 * Rules for de-/encoding of a private key from/in ASN1
143 */
144 static asn1_rule_t rsa_private_key_rules[] = {
145 {ASN1_SEQUENCE, 0, 0, 0},
146 { ASN1_INTEGER, 0, offsetof(private_rsa_private_key_t, version), 0},
147 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, n), 0},
148 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, e), 0},
149 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, d), 0},
150 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, p), 0},
151 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, q), 0},
152 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, exp1), 0},
153 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, exp2), 0},
154 { ASN1_INTEGER, ASN1_MPZ, offsetof(private_rsa_private_key_t, coeff), 0},
155 {ASN1_END, 0, 0, 0},
156 };
157
158 static private_rsa_private_key_t *rsa_private_key_create_empty();
159
160 /**
161 * Implementation of private_rsa_private_key_t.compute_prime.
162 */
163 static status_t compute_prime(private_rsa_private_key_t *this, size_t prime_size, mpz_t *prime)
164 {
165 randomizer_t *randomizer;
166 chunk_t random_bytes;
167 status_t status;
168
169 randomizer = randomizer_create();
170 mpz_init(*prime);
171
172 do
173 {
174 status = randomizer->allocate_random_bytes(randomizer, prime_size, &random_bytes);
175 if (status != SUCCESS)
176 {
177 randomizer->destroy(randomizer);
178 mpz_clear(*prime);
179 return FAILED;
180 }
181
182 /* make sure most significant bit is set */
183 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
184
185 /* convert chunk to mpz value */
186 mpz_import(*prime, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
187
188 /* get next prime */
189 mpz_nextprime (*prime, *prime);
190
191 free(random_bytes.ptr);
192 }
193 /* check if it isnt too large */
194 while (((mpz_sizeinbase(*prime, 2) + 7) / 8) > prime_size);
195
196 randomizer->destroy(randomizer);
197 return SUCCESS;
198 }
199
200 /**
201 * Implementation of private_rsa_private_key_t.rsadp and private_rsa_private_key_t.rsasp1.
202 */
203 static chunk_t rsadp(private_rsa_private_key_t *this, chunk_t data)
204 {
205 mpz_t t1, t2;
206 chunk_t decrypted;
207
208 mpz_init(t1);
209 mpz_init(t2);
210
211 mpz_import(t1, data.len, 1, 1, 1, 0, data.ptr);
212
213 mpz_powm(t2, t1, this->exp1, this->p); /* m1 = c^dP mod p */
214 mpz_powm(t1, t1, this->exp2, this->q); /* m2 = c^dQ mod Q */
215 mpz_sub(t2, t2, t1); /* h = qInv (m1 - m2) mod p */
216 mpz_mod(t2, t2, this->p);
217 mpz_mul(t2, t2, this->coeff);
218 mpz_mod(t2, t2, this->p);
219
220 mpz_mul(t2, t2, this->q); /* m = m2 + h q */
221 mpz_add(t1, t1, t2);
222
223 decrypted.len = this->k;
224 decrypted.ptr = mpz_export(NULL, NULL, 1, decrypted.len, 1, 0, t1);
225
226 mpz_clear(t1);
227 mpz_clear(t2);
228
229 return decrypted;
230 }
231
232 /**
233 * Implementation of rsa_private_key.build_emsa_signature.
234 */
235 static status_t build_emsa_pkcs1_signature(private_rsa_private_key_t *this, hash_algorithm_t hash_algorithm, chunk_t data, chunk_t *signature)
236 {
237 hasher_t *hasher;
238 chunk_t hash;
239 chunk_t oid;
240 chunk_t em;
241
242 /* get oid string prepended to hash */
243 switch (hash_algorithm)
244 {
245 case HASH_MD2:
246 {
247 oid.ptr = md2_oid;
248 oid.len = sizeof(md2_oid);
249 break;
250 }
251 case HASH_MD5:
252 {
253 oid.ptr = md5_oid;
254 oid.len = sizeof(md5_oid);
255 break;
256 }
257 case HASH_SHA1:
258 {
259 oid.ptr = sha1_oid;
260 oid.len = sizeof(sha1_oid);
261 break;
262 }
263 case HASH_SHA256:
264 {
265 oid.ptr = sha256_oid;
266 oid.len = sizeof(sha256_oid);
267 break;
268 }
269 case HASH_SHA384:
270 {
271 oid.ptr = sha384_oid;
272 oid.len = sizeof(sha384_oid);
273 break;
274 }
275 case HASH_SHA512:
276 {
277 oid.ptr = sha512_oid;
278 oid.len = sizeof(sha512_oid);
279 break;
280 }
281 default:
282 {
283 return NOT_SUPPORTED;
284 }
285 }
286
287 /* get hasher */
288 hasher = hasher_create(hash_algorithm);
289 if (hasher == NULL)
290 {
291 return NOT_SUPPORTED;
292 }
293
294 /* build hash */
295 hasher->allocate_hash(hasher, data, &hash);
296 hasher->destroy(hasher);
297
298 /* build chunk to rsa-decrypt:
299 * EM = 0x00 || 0x01 || PS || 0x00 || T.
300 * PS = 0xFF padding, with length to fill em
301 * T = oid || hash
302 */
303 em.len = this->k;
304 em.ptr = malloc(em.len);
305
306 /* fill em with padding */
307 memset(em.ptr, 0xFF, em.len);
308 /* set magic bytes */
309 *(em.ptr) = 0x00;
310 *(em.ptr+1) = 0x01;
311 *(em.ptr + em.len - hash.len - oid.len - 1) = 0x00;
312 /* set hash */
313 memcpy(em.ptr + em.len - hash.len, hash.ptr, hash.len);
314 /* set oid */
315 memcpy(em.ptr + em.len - hash.len - oid.len, oid.ptr, oid.len);
316
317
318 /* build signature */
319 *signature = this->rsasp1(this, em);
320
321 free(hash.ptr);
322 free(em.ptr);
323
324 return SUCCESS;
325 }
326
327 /**
328 * Implementation of rsa_private_key.get_key.
329 */
330 static status_t get_key(private_rsa_private_key_t *this, chunk_t *key)
331 {
332 chunk_t n, e, p, q, d, exp1, exp2, coeff;
333
334 n.len = this->k;
335 n.ptr = mpz_export(NULL, NULL, 1, n.len, 1, 0, this->n);
336 e.len = this->k;
337 e.ptr = mpz_export(NULL, NULL, 1, e.len, 1, 0, this->e);
338 p.len = this->k;
339 p.ptr = mpz_export(NULL, NULL, 1, p.len, 1, 0, this->p);
340 q.len = this->k;
341 q.ptr = mpz_export(NULL, NULL, 1, q.len, 1, 0, this->q);
342 d.len = this->k;
343 d.ptr = mpz_export(NULL, NULL, 1, d.len, 1, 0, this->d);
344 exp1.len = this->k;
345 exp1.ptr = mpz_export(NULL, NULL, 1, exp1.len, 1, 0, this->exp1);
346 exp2.len = this->k;
347 exp2.ptr = mpz_export(NULL, NULL, 1, exp2.len, 1, 0, this->exp2);
348 coeff.len = this->k;
349 coeff.ptr = mpz_export(NULL, NULL, 1, coeff.len, 1, 0, this->coeff);
350
351 key->len = this->k * 8;
352 key->ptr = malloc(key->len);
353 memcpy(key->ptr + this->k * 0, n.ptr , n.len);
354 memcpy(key->ptr + this->k * 1, e.ptr, e.len);
355 memcpy(key->ptr + this->k * 2, p.ptr, p.len);
356 memcpy(key->ptr + this->k * 3, q.ptr, q.len);
357 memcpy(key->ptr + this->k * 4, d.ptr, d.len);
358 memcpy(key->ptr + this->k * 5, exp1.ptr, exp1.len);
359 memcpy(key->ptr + this->k * 6, exp2.ptr, exp2.len);
360 memcpy(key->ptr + this->k * 7, coeff.ptr, coeff.len);
361
362 free(n.ptr);
363 free(e.ptr);
364 free(p.ptr);
365 free(q.ptr);
366 free(d.ptr);
367 free(exp1.ptr);
368 free(exp2.ptr);
369 free(coeff.ptr);
370
371 return SUCCESS;
372 }
373
374 /**
375 * Implementation of rsa_private_key.save_key.
376 */
377 static status_t save_key(private_rsa_private_key_t *this, char *file)
378 {
379 return NOT_SUPPORTED;
380 }
381
382 /**
383 * Implementation of rsa_private_key.get_public_key.
384 */
385 rsa_public_key_t *get_public_key(private_rsa_private_key_t *this)
386 {
387 return NULL;
388 }
389
390 /**
391 * Implementation of rsa_private_key.belongs_to.
392 */
393 static bool belongs_to(private_rsa_private_key_t *this, rsa_public_key_t *public)
394 {
395 if (mpz_cmp(this->n, *public->get_modulus(public)) == 0)
396 {
397 return TRUE;
398 }
399 return FALSE;
400 }
401
402 /**
403 * Implementation of rsa_private_key.clone.
404 */
405 static rsa_private_key_t* _clone(private_rsa_private_key_t *this)
406 {
407 private_rsa_private_key_t *clone = rsa_private_key_create_empty();
408
409 mpz_init_set(clone->n, this->n);
410 mpz_init_set(clone->e, this->e);
411 mpz_init_set(clone->p, this->p);
412 mpz_init_set(clone->q, this->q);
413 mpz_init_set(clone->d, this->d);
414 mpz_init_set(clone->exp1, this->exp1);
415 mpz_init_set(clone->exp2, this->exp2);
416 mpz_init_set(clone->coeff, this->coeff);
417 clone->k = this->k;
418
419 return &clone->public;
420 }
421
422 /**
423 * Implementation of rsa_private_key.destroy.
424 */
425 static void destroy(private_rsa_private_key_t *this)
426 {
427 mpz_clear(this->n);
428 mpz_clear(this->e);
429 mpz_clear(this->p);
430 mpz_clear(this->q);
431 mpz_clear(this->d);
432 mpz_clear(this->exp1);
433 mpz_clear(this->exp2);
434 mpz_clear(this->coeff);
435 free(this);
436 }
437
438 /**
439 * Internal generic constructor
440 */
441 static private_rsa_private_key_t *rsa_private_key_create_empty()
442 {
443 private_rsa_private_key_t *this = malloc_thing(private_rsa_private_key_t);
444
445 /* public functions */
446 this->public.build_emsa_pkcs1_signature = (status_t (*) (rsa_private_key_t*,hash_algorithm_t,chunk_t,chunk_t*))build_emsa_pkcs1_signature;
447 this->public.get_key = (status_t (*) (rsa_private_key_t*,chunk_t*))get_key;
448 this->public.save_key = (status_t (*) (rsa_private_key_t*,char*))save_key;
449 this->public.get_public_key = (rsa_public_key_t *(*) (rsa_private_key_t*))get_public_key;
450 this->public.belongs_to = (bool (*) (rsa_private_key_t*,rsa_public_key_t*))belongs_to;
451 this->public.clone = (rsa_private_key_t*(*)(rsa_private_key_t*))_clone;
452 this->public.destroy = (void (*) (rsa_private_key_t*))destroy;
453
454 /* private functions */
455 this->rsadp = rsadp;
456 this->rsasp1 = rsadp; /* same algorithm */
457 this->compute_prime = compute_prime;
458
459 return this;
460 }
461
462 /*
463 * See header
464 */
465 rsa_private_key_t *rsa_private_key_create(size_t key_size)
466 {
467 mpz_t p, q, n, e, d, exp1, exp2, coeff;
468 mpz_t m, q1, t;
469 private_rsa_private_key_t *this;
470
471 this = rsa_private_key_create_empty();
472 key_size = key_size / 8;
473
474 /* Get values of primes p and q */
475 if (this->compute_prime(this, key_size/2, &p) != SUCCESS)
476 {
477 free(this);
478 return NULL;
479 }
480 if (this->compute_prime(this, key_size/2, &q) != SUCCESS)
481 {
482 mpz_clear(p);
483 free(this);
484 return NULL;
485 }
486
487
488 mpz_init(t);
489 mpz_init(n);
490 mpz_init(d);
491 mpz_init(exp1);
492 mpz_init(exp2);
493 mpz_init(coeff);
494
495
496 /* Swapping Primes so p is larger then q */
497 if (mpz_cmp(p, q) < 0)
498 {
499 mpz_set(t, p);
500 mpz_set(p, q);
501 mpz_set(q, t);
502 }
503
504 mpz_mul(n, p, q); /* n = p*q */
505 mpz_init_set_ui(e, PUBLIC_EXPONENT); /* assign public exponent */
506 mpz_init_set(m, p); /* m = p */
507 mpz_sub_ui(m, m, 1); /* m = m -1 */
508 mpz_init_set(q1, q); /* q1 = q */
509 mpz_sub_ui(q1, q1, 1); /* q1 = q1 -1 */
510 mpz_gcd(t, m, q1); /* t = gcd(p-1, q-1) */
511 mpz_mul(m, m, q1); /* m = (p-1)*(q-1) */
512 mpz_divexact(m, m, t); /* m = m / t */
513 mpz_gcd(t, m, e); /* t = gcd(m, e) (greatest common divisor) */
514
515 mpz_invert(d, e, m); /* e has an inverse mod m */
516 if (mpz_cmp_ui(d, 0) < 0) /* make sure d is positive */
517 {
518 mpz_add(d, d, m);
519 }
520 mpz_sub_ui(t, p, 1); /* t = p-1 */
521 mpz_mod(exp1, d, t); /* exp1 = d mod p-1 */
522 mpz_sub_ui(t, q, 1); /* t = q-1 */
523 mpz_mod(exp2, d, t); /* exp2 = d mod q-1 */
524
525 mpz_invert(coeff, q, p); /* coeff = q^-1 mod p */
526 if (mpz_cmp_ui(coeff, 0) < 0) /* make coeff d is positive */
527 {
528 mpz_add(coeff, coeff, p);
529 }
530
531 mpz_clear(q1);
532 mpz_clear(m);
533 mpz_clear(t);
534
535 /* apply values */
536 *(this->p) = *p;
537 *(this->q) = *q;
538 *(this->n) = *n;
539 *(this->e) = *e;
540 *(this->d) = *d;
541 *(this->exp1) = *exp1;
542 *(this->exp2) = *exp2;
543 *(this->coeff) = *coeff;
544
545 /* set key size in bytes */
546 this->k = key_size;
547
548 return &this->public;
549 }
550
551 /*
552 * see header
553 */
554 rsa_private_key_t *rsa_private_key_create_from_chunk(chunk_t chunk)
555 {
556 private_rsa_private_key_t *this;
557 der_decoder_t *dd;
558 status_t status;
559
560 this = rsa_private_key_create_empty();
561
562 mpz_init(this->n);
563 mpz_init(this->e);
564 mpz_init(this->p);
565 mpz_init(this->q);
566 mpz_init(this->d);
567 mpz_init(this->exp1);
568 mpz_init(this->exp2);
569 mpz_init(this->coeff);
570
571 dd = der_decoder_create(rsa_private_key_rules);
572 status = dd->decode(dd, chunk, this);
573 dd->destroy(dd);
574 if (status != SUCCESS)
575 {
576 destroy(this);
577 return NULL;
578 }
579 this->k = (mpz_sizeinbase(this->n, 2) + 7) / 8;
580 return &this->public;
581 }
582
583 /*
584 * see header
585 */
586 rsa_private_key_t *rsa_private_key_create_from_file(char *filename, char *passphrase)
587 {
588 chunk_t chunk;
589 struct stat stb;
590 FILE *file;
591 char *buffer;
592
593 if (stat(filename, &stb) == -1)
594 {
595 return NULL;
596 }
597
598 buffer = alloca(stb.st_size);
599
600 file = fopen(filename, "r");
601 if (file == NULL)
602 {
603 return NULL;
604 }
605
606 if (fread(buffer, stb.st_size, 1, file) != 1)
607 {
608 fclose(file);
609 return NULL;
610 }
611 fclose(file);
612
613 chunk.ptr = buffer;
614 chunk.len = stb.st_size;
615
616 return rsa_private_key_create_from_chunk(chunk);
617 }