2 * @file rsa_private_key.c
4 * @brief Implementation of rsa_private_key_t.
9 * Copyright (C) 2005 Jan Hutter, Martin Willi
10 * Hochschule fuer Technik Rapperswil
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>.
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
28 #include "rsa_private_key.h"
31 #include <asn1/asn1.h>
35 * Oids for hash algorithms are defined in
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];
47 * Public exponent to use for key generation.
49 #define PUBLIC_EXPONENT 0x10001
52 typedef struct private_rsa_private_key_t private_rsa_private_key_t
;
55 * Private data of a rsa_private_key_t object.
57 struct private_rsa_private_key_t
{
59 * Public interface for this signer.
61 rsa_private_key_t
public;
64 * Version of key, as encoded in PKCS#1
104 * Private coefficient.
114 * @brief Implements the RSADP algorithm specified in PKCS#1.
116 * @param this calling object
117 * @param data data to process
118 * @return processed data
120 chunk_t (*rsadp
) (private_rsa_private_key_t
*this, chunk_t data
);
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
128 chunk_t (*rsasp1
) (private_rsa_private_key_t
*this, chunk_t data
);
131 * @brief Generate a prime value.
133 * @param this calling object
134 * @param prime_size size of the prime, in bytes
135 * @param[out] prime uninitialized mpz
137 status_t (*compute_prime
) (private_rsa_private_key_t
*this, size_t prime_size
, mpz_t
*prime
);
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 */
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
173 static private_rsa_private_key_t
*rsa_private_key_create_empty(void);
176 * Implementation of private_rsa_private_key_t.compute_prime.
178 static status_t
compute_prime(private_rsa_private_key_t
*this, size_t prime_size
, mpz_t
*prime
)
180 randomizer_t
*randomizer
;
181 chunk_t random_bytes
;
184 randomizer
= randomizer_create();
189 status
= randomizer
->allocate_random_bytes(randomizer
, prime_size
, &random_bytes
);
190 if (status
!= SUCCESS
)
192 randomizer
->destroy(randomizer
);
197 /* make sure most significant bit is set */
198 random_bytes
.ptr
[0] = random_bytes
.ptr
[0] | 0x80;
200 /* convert chunk to mpz value */
201 mpz_import(*prime
, random_bytes
.len
, 1, 1, 1, 0, random_bytes
.ptr
);
204 mpz_nextprime (*prime
, *prime
);
206 free(random_bytes
.ptr
);
208 /* check if it isnt too large */
209 while (((mpz_sizeinbase(*prime
, 2) + 7) / 8) > prime_size
);
211 randomizer
->destroy(randomizer
);
216 * Implementation of private_rsa_private_key_t.rsadp and private_rsa_private_key_t.rsasp1.
218 static chunk_t
rsadp(private_rsa_private_key_t
*this, chunk_t data
)
226 mpz_import(t1
, data
.len
, 1, 1, 1, 0, data
.ptr
);
228 mpz_powm(t2
, t1
, this->exp1
, this->p
); /* m1 = c^dP mod p */
229 mpz_powm(t1
, t1
, this->exp2
, this->q
); /* m2 = c^dQ mod Q */
230 mpz_sub(t2
, t2
, t1
); /* h = qInv (m1 - m2) mod p */
231 mpz_mod(t2
, t2
, this->p
);
232 mpz_mul(t2
, t2
, this->coeff
);
233 mpz_mod(t2
, t2
, this->p
);
235 mpz_mul(t2
, t2
, this->q
); /* m = m2 + h q */
238 decrypted
.len
= this->k
;
239 decrypted
.ptr
= mpz_export(NULL
, NULL
, 1, decrypted
.len
, 1, 0, t1
);
248 * Implementation of rsa_private_key.build_emsa_signature.
250 static status_t
build_emsa_pkcs1_signature(private_rsa_private_key_t
*this, hash_algorithm_t hash_algorithm
, chunk_t data
, chunk_t
*signature
)
257 /* get oid string prepended to hash */
258 switch (hash_algorithm
)
263 oid
.len
= sizeof(md2_oid
);
269 oid
.len
= sizeof(md5_oid
);
275 oid
.len
= sizeof(sha1_oid
);
280 oid
.ptr
= sha256_oid
;
281 oid
.len
= sizeof(sha256_oid
);
286 oid
.ptr
= sha384_oid
;
287 oid
.len
= sizeof(sha384_oid
);
292 oid
.ptr
= sha512_oid
;
293 oid
.len
= sizeof(sha512_oid
);
298 return NOT_SUPPORTED
;
303 hasher
= hasher_create(hash_algorithm
);
306 return NOT_SUPPORTED
;
310 hasher
->allocate_hash(hasher
, data
, &hash
);
311 hasher
->destroy(hasher
);
313 /* build chunk to rsa-decrypt:
314 * EM = 0x00 || 0x01 || PS || 0x00 || T.
315 * PS = 0xFF padding, with length to fill em
319 em
.ptr
= malloc(em
.len
);
321 /* fill em with padding */
322 memset(em
.ptr
, 0xFF, em
.len
);
323 /* set magic bytes */
326 *(em
.ptr
+ em
.len
- hash
.len
- oid
.len
- 1) = 0x00;
328 memcpy(em
.ptr
+ em
.len
- hash
.len
, hash
.ptr
, hash
.len
);
330 memcpy(em
.ptr
+ em
.len
- hash
.len
- oid
.len
, oid
.ptr
, oid
.len
);
332 /* build signature */
333 *signature
= this->rsasp1(this, em
);
342 * Implementation of rsa_private_key.get_key.
344 static status_t
get_key(private_rsa_private_key_t
*this, chunk_t
*key
)
346 chunk_t n
, e
, p
, q
, d
, exp1
, exp2
, coeff
;
349 n
.ptr
= mpz_export(NULL
, NULL
, 1, n
.len
, 1, 0, this->n
);
351 e
.ptr
= mpz_export(NULL
, NULL
, 1, e
.len
, 1, 0, this->e
);
353 p
.ptr
= mpz_export(NULL
, NULL
, 1, p
.len
, 1, 0, this->p
);
355 q
.ptr
= mpz_export(NULL
, NULL
, 1, q
.len
, 1, 0, this->q
);
357 d
.ptr
= mpz_export(NULL
, NULL
, 1, d
.len
, 1, 0, this->d
);
359 exp1
.ptr
= mpz_export(NULL
, NULL
, 1, exp1
.len
, 1, 0, this->exp1
);
361 exp2
.ptr
= mpz_export(NULL
, NULL
, 1, exp2
.len
, 1, 0, this->exp2
);
363 coeff
.ptr
= mpz_export(NULL
, NULL
, 1, coeff
.len
, 1, 0, this->coeff
);
365 key
->len
= this->k
* 8;
366 key
->ptr
= malloc(key
->len
);
367 memcpy(key
->ptr
+ this->k
* 0, n
.ptr
, n
.len
);
368 memcpy(key
->ptr
+ this->k
* 1, e
.ptr
, e
.len
);
369 memcpy(key
->ptr
+ this->k
* 2, p
.ptr
, p
.len
);
370 memcpy(key
->ptr
+ this->k
* 3, q
.ptr
, q
.len
);
371 memcpy(key
->ptr
+ this->k
* 4, d
.ptr
, d
.len
);
372 memcpy(key
->ptr
+ this->k
* 5, exp1
.ptr
, exp1
.len
);
373 memcpy(key
->ptr
+ this->k
* 6, exp2
.ptr
, exp2
.len
);
374 memcpy(key
->ptr
+ this->k
* 7, coeff
.ptr
, coeff
.len
);
389 * Implementation of rsa_private_key.save_key.
391 static status_t
save_key(private_rsa_private_key_t
*this, char *file
)
393 return NOT_SUPPORTED
;
397 * Implementation of rsa_private_key.get_public_key.
399 rsa_public_key_t
*get_public_key(private_rsa_private_key_t
*this)
405 * Implementation of rsa_private_key.belongs_to.
407 static bool belongs_to(private_rsa_private_key_t
*this, rsa_public_key_t
*public)
409 if (mpz_cmp(this->n
, *public->get_modulus(public)) == 0)
417 * Check the loaded key if it is valid and usable
420 static status_t
check(private_rsa_private_key_t
*this)
423 status_t status
= SUCCESS
;
425 /* PKCS#1 1.5 section 6 requires modulus to have at least 12 octets.
426 * We actually require more (for security).
433 /* we picked a max modulus size to simplify buffer allocation */
434 if (this->k
> 8192/8)
443 /* check that n == p * q */
444 mpz_mul(u
, this->p
, this->q
);
445 if (mpz_cmp(u
, this->n
) != 0)
450 /* check that e divides neither p-1 nor q-1 */
451 mpz_sub_ui(t
, this->p
, 1);
452 mpz_mod(t
, t
, this->e
);
453 if (mpz_cmp_ui(t
, 0) == 0)
458 mpz_sub_ui(t
, this->q
, 1);
459 mpz_mod(t
, t
, this->e
);
460 if (mpz_cmp_ui(t
, 0) == 0)
465 /* check that d is e^-1 (mod lcm(p-1, q-1)) */
466 /* see PKCS#1v2, aka RFC 2437, for the "lcm" */
467 mpz_sub_ui(q1
, this->q
, 1);
468 mpz_sub_ui(u
, this->p
, 1);
469 mpz_gcd(t
, u
, q1
); /* t := gcd(p-1, q-1) */
470 mpz_mul(u
, u
, q1
); /* u := (p-1) * (q-1) */
471 mpz_divexact(u
, u
, t
); /* u := lcm(p-1, q-1) */
473 mpz_mul(t
, this->d
, this->e
);
475 if (mpz_cmp_ui(t
, 1) != 0)
480 /* check that exp1 is d mod (p-1) */
481 mpz_sub_ui(u
, this->p
, 1);
482 mpz_mod(t
, this->d
, u
);
483 if (mpz_cmp(t
, this->exp1
) != 0)
488 /* check that exp2 is d mod (q-1) */
489 mpz_sub_ui(u
, this->q
, 1);
490 mpz_mod(t
, this->d
, u
);
491 if (mpz_cmp(t
, this->exp2
) != 0)
496 /* check that coeff is (q^-1) mod p */
497 mpz_mul(t
, this->coeff
, this->q
);
498 mpz_mod(t
, t
, this->p
);
499 if (mpz_cmp_ui(t
, 1) != 0)
511 * Implementation of rsa_private_key.clone.
513 static rsa_private_key_t
* _clone(private_rsa_private_key_t
*this)
515 private_rsa_private_key_t
*clone
= rsa_private_key_create_empty();
517 mpz_init_set(clone
->n
, this->n
);
518 mpz_init_set(clone
->e
, this->e
);
519 mpz_init_set(clone
->p
, this->p
);
520 mpz_init_set(clone
->q
, this->q
);
521 mpz_init_set(clone
->d
, this->d
);
522 mpz_init_set(clone
->exp1
, this->exp1
);
523 mpz_init_set(clone
->exp2
, this->exp2
);
524 mpz_init_set(clone
->coeff
, this->coeff
);
527 return &clone
->public;
531 * Implementation of rsa_private_key.destroy.
533 static void destroy(private_rsa_private_key_t
*this)
540 mpz_clear(this->exp1
);
541 mpz_clear(this->exp2
);
542 mpz_clear(this->coeff
);
547 * Internal generic constructor
549 static private_rsa_private_key_t
*rsa_private_key_create_empty(void)
551 private_rsa_private_key_t
*this = malloc_thing(private_rsa_private_key_t
);
553 /* public functions */
554 this->public.build_emsa_pkcs1_signature
= (status_t (*) (rsa_private_key_t
*,hash_algorithm_t
,chunk_t
,chunk_t
*))build_emsa_pkcs1_signature
;
555 this->public.get_key
= (status_t (*) (rsa_private_key_t
*,chunk_t
*))get_key
;
556 this->public.save_key
= (status_t (*) (rsa_private_key_t
*,char*))save_key
;
557 this->public.get_public_key
= (rsa_public_key_t
*(*) (rsa_private_key_t
*))get_public_key
;
558 this->public.belongs_to
= (bool (*) (rsa_private_key_t
*,rsa_public_key_t
*))belongs_to
;
559 this->public.clone
= (rsa_private_key_t
*(*)(rsa_private_key_t
*))_clone
;
560 this->public.destroy
= (void (*) (rsa_private_key_t
*))destroy
;
562 /* private functions */
564 this->rsasp1
= rsadp
; /* same algorithm */
565 this->compute_prime
= compute_prime
;
573 rsa_private_key_t
*rsa_private_key_create(size_t key_size
)
575 mpz_t p
, q
, n
, e
, d
, exp1
, exp2
, coeff
;
577 private_rsa_private_key_t
*this;
579 this = rsa_private_key_create_empty();
580 key_size
= key_size
/ 8;
582 /* Get values of primes p and q */
583 if (this->compute_prime(this, key_size
/2, &p
) != SUCCESS
)
588 if (this->compute_prime(this, key_size
/2, &q
) != SUCCESS
)
602 /* Swapping Primes so p is larger then q */
603 if (mpz_cmp(p
, q
) < 0)
610 mpz_mul(n
, p
, q
); /* n = p*q */
611 mpz_init_set_ui(e
, PUBLIC_EXPONENT
); /* assign public exponent */
612 mpz_init_set(m
, p
); /* m = p */
613 mpz_sub_ui(m
, m
, 1); /* m = m -1 */
614 mpz_init_set(q1
, q
); /* q1 = q */
615 mpz_sub_ui(q1
, q1
, 1); /* q1 = q1 -1 */
616 mpz_gcd(t
, m
, q1
); /* t = gcd(p-1, q-1) */
617 mpz_mul(m
, m
, q1
); /* m = (p-1)*(q-1) */
618 mpz_divexact(m
, m
, t
); /* m = m / t */
619 mpz_gcd(t
, m
, e
); /* t = gcd(m, e) (greatest common divisor) */
621 mpz_invert(d
, e
, m
); /* e has an inverse mod m */
622 if (mpz_cmp_ui(d
, 0) < 0) /* make sure d is positive */
626 mpz_sub_ui(t
, p
, 1); /* t = p-1 */
627 mpz_mod(exp1
, d
, t
); /* exp1 = d mod p-1 */
628 mpz_sub_ui(t
, q
, 1); /* t = q-1 */
629 mpz_mod(exp2
, d
, t
); /* exp2 = d mod q-1 */
631 mpz_invert(coeff
, q
, p
); /* coeff = q^-1 mod p */
632 if (mpz_cmp_ui(coeff
, 0) < 0) /* make coeff d is positive */
634 mpz_add(coeff
, coeff
, p
);
647 *(this->exp1
) = *exp1
;
648 *(this->exp2
) = *exp2
;
649 *(this->coeff
) = *coeff
;
651 /* set key size in bytes */
654 return &this->public;
660 rsa_private_key_t
*rsa_private_key_create_from_chunk(chunk_t blob
)
666 private_rsa_private_key_t
*this;
668 this = rsa_private_key_create_empty();
675 mpz_init(this->exp1
);
676 mpz_init(this->exp2
);
677 mpz_init(this->coeff
);
679 asn1_init(&ctx
, blob
, 0, FALSE
);
681 while (objectID
< PRIV_KEY_ROOF
)
683 if (!extract_object(privkey_objects
, &objectID
, &object
, &level
, &ctx
))
690 case PRIV_KEY_VERSION
:
691 if (object
.len
> 0 && *object
.ptr
!= 0)
697 case PRIV_KEY_MODULUS
:
698 mpz_import(this->n
, object
.len
, 1, 1, 1, 0, object
.ptr
);
700 case PRIV_KEY_PUB_EXP
:
701 mpz_import(this->e
, object
.len
, 1, 1, 1, 0, object
.ptr
);
703 case PRIV_KEY_PRIV_EXP
:
704 mpz_import(this->d
, object
.len
, 1, 1, 1, 0, object
.ptr
);
706 case PRIV_KEY_PRIME1
:
707 mpz_import(this->p
, object
.len
, 1, 1, 1, 0, object
.ptr
);
709 case PRIV_KEY_PRIME2
:
710 mpz_import(this->q
, object
.len
, 1, 1, 1, 0, object
.ptr
);
713 mpz_import(this->exp1
, object
.len
, 1, 1, 1, 0, object
.ptr
);
716 mpz_import(this->exp2
, object
.len
, 1, 1, 1, 0, object
.ptr
);
719 mpz_import(this->coeff
, object
.len
, 1, 1, 1, 0, object
.ptr
);
725 this->k
= (mpz_sizeinbase(this->n
, 2) + 7) / 8;
727 if (check(this) != SUCCESS
)
734 return &this->public;
741 rsa_private_key_t
*rsa_private_key_create_from_file(char *filename
, char *passphrase
)
744 chunk_t chunk
= CHUNK_INITIALIZER
;
745 rsa_private_key_t
*key
= NULL
;
747 if (!pem_asn1_load_file(filename
, passphrase
, "private key", &chunk
, &pgp
))
750 key
= rsa_private_key_create_from_chunk(chunk
);