cc153f7949621ab7400ee0f8d4fbaec52c239664
[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
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 }