]> git.ipfire.org Git - people/ms/strongswan.git/blob - Source/charon/transforms/rsa/rsa_private_key.c
projects / people / ms / strongswan.git / blob
? search:


4da3baf7caf49008a567871f63075b10e5486a30
[people/ms/strongswan.git] / 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 #include <sys/stat.h>
25 #include <unistd.h>
26
27 #include "rsa_private_key.h"
28
29 #include <daemon.h>
30 #include <utils/allocator.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 void (*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 /**
159 * Implementation of private_rsa_private_key_t.compute_prime.
160 */
161 static void compute_prime(private_rsa_private_key_t *this, size_t prime_size, mpz_t *prime)
162 {
163 randomizer_t *randomizer;
164 chunk_t random_bytes;
165
166 randomizer = randomizer_create();
167 mpz_init(*prime);
168
169 do
170 {
171 randomizer->allocate_random_bytes(randomizer, prime_size, &random_bytes);
172
173 /* make sure most significant bit is set */
174 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
175
176 /* convert chunk to mpz value */
177 mpz_import(*prime, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
178
179 /* get next prime */
180 mpz_nextprime (*prime, *prime);
181
182 allocator_free(random_bytes.ptr);
183 }
184 /* check if it isnt too large */
185 while (((mpz_sizeinbase(*prime, 2) + 7) / 8) > prime_size);
186
187 randomizer->destroy(randomizer);
188 }
189
190 /**
191 * Implementation of private_rsa_private_key_t.rsadp and private_rsa_private_key_t.rsasp1.
192 */
193 static chunk_t rsadp(private_rsa_private_key_t *this, chunk_t data)
194 {
195 mpz_t t1, t2;
196 chunk_t decrypted;
197
198 mpz_init(t1);
199 mpz_init(t2);
200
201 mpz_import(t1, data.len, 1, 1, 1, 0, data.ptr);
202
203 mpz_powm(t2, t1, this->exp1, this->p); /* m1 = c^dP mod p */
204 mpz_powm(t1, t1, this->exp2, this->q); /* m2 = c^dQ mod Q */
205 mpz_sub(t2, t2, t1); /* h = qInv (m1 - m2) mod p */
206 mpz_mod(t2, t2, this->p);
207 mpz_mul(t2, t2, this->coeff);
208 mpz_mod(t2, t2, this->p);
209
210 mpz_mul(t2, t2, this->q); /* m = m2 + h q */
211 mpz_add(t1, t1, t2);
212
213 decrypted.len = this->k;
214 decrypted.ptr = mpz_export(NULL, NULL, 1, decrypted.len, 1, 0, t1);
215
216 mpz_clear(t1);
217 mpz_clear(t2);
218
219 return decrypted;
220 }
221
222 /**
223 * Implementation of rsa_private_key.build_emsa_signature.
224 */
225 static status_t build_emsa_pkcs1_signature(private_rsa_private_key_t *this, hash_algorithm_t hash_algorithm, chunk_t data, chunk_t *signature)
226 {
227 hasher_t *hasher;
228 chunk_t hash;
229 chunk_t oid;
230 chunk_t em;
231
232 /* get oid string prepended to hash */
233 switch (hash_algorithm)
234 {
235 case HASH_MD2:
236 {
237 oid.ptr = md2_oid;
238 oid.len = sizeof(md2_oid);
239 break;
240 }
241 case HASH_MD5:
242 {
243 oid.ptr = md5_oid;
244 oid.len = sizeof(md5_oid);
245 break;
246 }
247 case HASH_SHA1:
248 {
249 oid.ptr = sha1_oid;
250 oid.len = sizeof(sha1_oid);
251 break;
252 }
253 case HASH_SHA256:
254 {
255 oid.ptr = sha256_oid;
256 oid.len = sizeof(sha256_oid);
257 break;
258 }
259 case HASH_SHA384:
260 {
261 oid.ptr = sha384_oid;
262 oid.len = sizeof(sha384_oid);
263 break;
264 }
265 case HASH_SHA512:
266 {
267 oid.ptr = sha512_oid;
268 oid.len = sizeof(sha512_oid);
269 break;
270 }
271 default:
272 {
273 return NOT_SUPPORTED;
274 }
275 }
276
277 /* get hasher */
278 hasher = hasher_create(hash_algorithm);
279 if (hasher == NULL)
280 {
281 return NOT_SUPPORTED;
282 }
283
284 /* build hash */
285 hasher->allocate_hash(hasher, data, &hash);
286 hasher->destroy(hasher);
287
288 /* build chunk to rsa-decrypt:
289 * EM = 0x00 || 0x01 || PS || 0x00 || T.
290 * PS = 0xFF padding, with length to fill em
291 * T = oid || hash
292 */
293 em.len = this->k;
294 em.ptr = allocator_alloc(em.len);
295
296 /* fill em with padding */
297 memset(em.ptr, 0xFF, em.len);
298 /* set magic bytes */
299 *(em.ptr) = 0x00;
300 *(em.ptr+1) = 0x01;
301 *(em.ptr + em.len - hash.len - oid.len - 1) = 0x00;
302 /* set hash */
303 memcpy(em.ptr + em.len - hash.len, hash.ptr, hash.len);
304 /* set oid */
305 memcpy(em.ptr + em.len - hash.len - oid.len, oid.ptr, oid.len);
306
307
308 /* build signature */
309 *signature = this->rsasp1(this, em);
310
311 allocator_free(hash.ptr);
312 allocator_free(em.ptr);
313
314 return SUCCESS;
315 }
316
317 /**
318 * Implementation of rsa_private_key.get_key.
319 */
320 static status_t get_key(private_rsa_private_key_t *this, chunk_t *key)
321 {
322 chunk_t n, e, p, q, d, exp1, exp2, coeff;
323
324 n.len = this->k;
325 n.ptr = mpz_export(NULL, NULL, 1, n.len, 1, 0, this->n);
326 e.len = this->k;
327 e.ptr = mpz_export(NULL, NULL, 1, e.len, 1, 0, this->e);
328 p.len = this->k;
329 p.ptr = mpz_export(NULL, NULL, 1, p.len, 1, 0, this->p);
330 q.len = this->k;
331 q.ptr = mpz_export(NULL, NULL, 1, q.len, 1, 0, this->q);
332 d.len = this->k;
333 d.ptr = mpz_export(NULL, NULL, 1, d.len, 1, 0, this->d);
334 exp1.len = this->k;
335 exp1.ptr = mpz_export(NULL, NULL, 1, exp1.len, 1, 0, this->exp1);
336 exp2.len = this->k;
337 exp2.ptr = mpz_export(NULL, NULL, 1, exp2.len, 1, 0, this->exp2);
338 coeff.len = this->k;
339 coeff.ptr = mpz_export(NULL, NULL, 1, coeff.len, 1, 0, this->coeff);
340
341 key->len = this->k * 8;
342 key->ptr = allocator_alloc(key->len);
343 memcpy(key->ptr + this->k * 0, n.ptr , n.len);
344 memcpy(key->ptr + this->k * 1, e.ptr, e.len);
345 memcpy(key->ptr + this->k * 2, p.ptr, p.len);
346 memcpy(key->ptr + this->k * 3, q.ptr, q.len);
347 memcpy(key->ptr + this->k * 4, d.ptr, d.len);
348 memcpy(key->ptr + this->k * 5, exp1.ptr, exp1.len);
349 memcpy(key->ptr + this->k * 6, exp2.ptr, exp2.len);
350 memcpy(key->ptr + this->k * 7, coeff.ptr, coeff.len);
351
352 allocator_free(n.ptr);
353 allocator_free(e.ptr);
354 allocator_free(p.ptr);
355 allocator_free(q.ptr);
356 allocator_free(d.ptr);
357 allocator_free(exp1.ptr);
358 allocator_free(exp2.ptr);
359 allocator_free(coeff.ptr);
360
361 return SUCCESS;
362 }
363
364 /**
365 * Implementation of rsa_private_key.save_key.
366 */
367 static status_t save_key(private_rsa_private_key_t *this, char *file)
368 {
369 return NOT_SUPPORTED;
370 }
371
372 /**
373 * Implementation of rsa_private_key.get_public_key.
374 */
375 rsa_public_key_t *get_public_key(private_rsa_private_key_t *this)
376 {
377 return NULL;
378 }
379
380 /**
381 * Implementation of rsa_private_key.belongs_to.
382 */
383 bool belongs_to(private_rsa_private_key_t *this, rsa_public_key_t *public)
384 {
385 if (mpz_cmp(this->n, *public->get_modulus(public)) == 0)
386 {
387 return TRUE;
388 }
389 return FALSE;
390 }
391
392
393 /**
394 * Implementation of rsa_private_key.destroy.
395 */
396 static void destroy(private_rsa_private_key_t *this)
397 {
398 mpz_clear(this->n);
399 mpz_clear(this->e);
400 mpz_clear(this->p);
401 mpz_clear(this->q);
402 mpz_clear(this->d);
403 mpz_clear(this->exp1);
404 mpz_clear(this->exp2);
405 mpz_clear(this->coeff);
406 allocator_free(this);
407 }
408
409 /**
410 * Internal generic constructor
411 */
412 static private_rsa_private_key_t *rsa_private_key_create_empty()
413 {
414 private_rsa_private_key_t *this = allocator_alloc_thing(private_rsa_private_key_t);
415
416 /* public functions */
417 this->public.build_emsa_pkcs1_signature = (status_t (*) (rsa_private_key_t*,hash_algorithm_t,chunk_t,chunk_t*))build_emsa_pkcs1_signature;
418 this->public.get_key = (status_t (*) (rsa_private_key_t*,chunk_t*))get_key;
419 this->public.save_key = (status_t (*) (rsa_private_key_t*,char*))save_key;
420 this->public.get_public_key = (rsa_public_key_t *(*) (rsa_private_key_t*))get_public_key;
421 this->public.belongs_to = (bool (*) (rsa_private_key_t*,rsa_public_key_t*))belongs_to;
422 this->public.destroy = (void (*) (rsa_private_key_t*))destroy;
423
424 /* private functions */
425 this->rsadp = rsadp;
426 this->rsasp1 = rsadp; /* same algorithm */
427 this->compute_prime = compute_prime;
428
429 return this;
430 }
431
432 /*
433 * See header
434 */
435 rsa_private_key_t *rsa_private_key_create(size_t key_size)
436 {
437 mpz_t p, q, n, e, d, exp1, exp2, coeff;
438 mpz_t m, q1, t;
439 private_rsa_private_key_t *this;
440
441 this = rsa_private_key_create_empty();
442
443 key_size = key_size / 8;
444
445 mpz_init(t);
446 mpz_init(n);
447 mpz_init(d);
448 mpz_init(exp1);
449 mpz_init(exp2);
450 mpz_init(coeff);
451
452 /* Get values of primes p and q */
453 this->compute_prime(this, key_size/2, &p);
454 this->compute_prime(this, key_size/2, &q);
455
456 /* Swapping Primes so p is larger then q */
457 if (mpz_cmp(p, q) < 0)
458 {
459 mpz_set(t, p);
460 mpz_set(p, q);
461 mpz_set(q, t);
462 }
463
464 mpz_mul(n, p, q); /* n = p*q */
465 mpz_init_set_ui(e, PUBLIC_EXPONENT); /* assign public exponent */
466 mpz_init_set(m, p); /* m = p */
467 mpz_sub_ui(m, m, 1); /* m = m -1 */
468 mpz_init_set(q1, q); /* q1 = q */
469 mpz_sub_ui(q1, q1, 1); /* q1 = q1 -1 */
470 mpz_gcd(t, m, q1); /* t = gcd(p-1, q-1) */
471 mpz_mul(m, m, q1); /* m = (p-1)*(q-1) */
472 mpz_divexact(m, m, t); /* m = m / t */
473 mpz_gcd(t, m, e); /* t = gcd(m, e) (greatest common divisor) */
474
475 mpz_invert(d, e, m); /* e has an inverse mod m */
476 if (mpz_cmp_ui(d, 0) < 0) /* make sure d is positive */
477 {
478 mpz_add(d, d, m);
479 }
480 mpz_sub_ui(t, p, 1); /* t = p-1 */
481 mpz_mod(exp1, d, t); /* exp1 = d mod p-1 */
482 mpz_sub_ui(t, q, 1); /* t = q-1 */
483 mpz_mod(exp2, d, t); /* exp2 = d mod q-1 */
484
485 mpz_invert(coeff, q, p); /* coeff = q^-1 mod p */
486 if (mpz_cmp_ui(coeff, 0) < 0) /* make coeff d is positive */
487 {
488 mpz_add(coeff, coeff, p);
489 }
490
491 mpz_clear(q1);
492 mpz_clear(m);
493 mpz_clear(t);
494
495 /* apply values */
496 *(this->p) = *p;
497 *(this->q) = *q;
498 *(this->n) = *n;
499 *(this->e) = *e;
500 *(this->d) = *d;
501 *(this->exp1) = *exp1;
502 *(this->exp2) = *exp2;
503 *(this->coeff) = *coeff;
504
505 /* set key size in bytes */
506 this->k = key_size;
507
508 return &this->public;
509 }
510
511 /*
512 * see header
513 */
514 rsa_private_key_t *rsa_private_key_create_from_chunk(chunk_t chunk)
515 {
516 private_rsa_private_key_t *this;
517 der_decoder_t *dd;
518 status_t status;
519
520 this = rsa_private_key_create_empty();
521
522 mpz_init(this->n);
523 mpz_init(this->e);
524 mpz_init(this->p);
525 mpz_init(this->q);
526 mpz_init(this->d);
527 mpz_init(this->exp1);
528 mpz_init(this->exp2);
529 mpz_init(this->coeff);
530
531 dd = der_decoder_create(rsa_private_key_rules);
532 status = dd->decode(dd, chunk, this);
533 dd->destroy(dd);
534 if (status != SUCCESS)
535 {
536 destroy(this);
537 return NULL;
538 }
539 this->k = (mpz_sizeinbase(this->n, 2) + 7) / 8;
540 return &this->public;
541 }
542
543 /*
544 * see header
545 */
546 rsa_private_key_t *rsa_private_key_create_from_file(char *filename, char *passphrase)
547 {
548 chunk_t chunk;
549 struct stat stb;
550 FILE *file;
551 char *buffer;
552
553 if (stat(filename, &stb) == -1)
554 {
555 return NULL;
556 }
557
558 buffer = alloca(stb.st_size);
559
560 file = fopen(filename, "r");
561 if (file == NULL)
562 {
563 return NULL;
564 }
565
566 if (fread(buffer, stb.st_size, 1, file) != 1)
567 {
568 return NULL;
569 }
570
571 chunk.ptr = buffer;
572 chunk.len = stb.st_size;
573
574 return rsa_private_key_create_from_chunk(chunk);
575 }
Michael's strongswan development tree