1 /* Support of PKCS#1 private key data structures
2 * Copyright (C) 2005 Jan Hutter, Martin Willi
3 * Copyright (C) 2002-2005 Andreas Steffen
4 * Hochschule fuer Technik Rapperswil, Switzerland
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2 of the License, or (at your
9 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 * RCSID $Id: pkcs1.c,v 1.17 2006/01/04 21:00:43 as Exp $
25 #include "constants.h"
37 const struct fld RSA_private_field
[] =
39 { "Modulus", offsetof(RSA_private_key_t
, pub
.n
) },
40 { "PublicExponent", offsetof(RSA_private_key_t
, pub
.e
) },
42 { "PrivateExponent", offsetof(RSA_private_key_t
, d
) },
43 { "Prime1", offsetof(RSA_private_key_t
, p
) },
44 { "Prime2", offsetof(RSA_private_key_t
, q
) },
45 { "Exponent1", offsetof(RSA_private_key_t
, dP
) },
46 { "Exponent2", offsetof(RSA_private_key_t
, dQ
) },
47 { "Coefficient", offsetof(RSA_private_key_t
, qInv
) },
50 /* ASN.1 definition of a PKCS#1 RSA private key */
52 static const asn1Object_t privkeyObjects
[] = {
53 { 0, "RSAPrivateKey", ASN1_SEQUENCE
, ASN1_NONE
}, /* 0 */
54 { 1, "version", ASN1_INTEGER
, ASN1_BODY
}, /* 1 */
55 { 1, "modulus", ASN1_INTEGER
, ASN1_BODY
}, /* 2 */
56 { 1, "publicExponent", ASN1_INTEGER
, ASN1_BODY
}, /* 3 */
57 { 1, "privateExponent", ASN1_INTEGER
, ASN1_BODY
}, /* 4 */
58 { 1, "prime1", ASN1_INTEGER
, ASN1_BODY
}, /* 5 */
59 { 1, "prime2", ASN1_INTEGER
, ASN1_BODY
}, /* 6 */
60 { 1, "exponent1", ASN1_INTEGER
, ASN1_BODY
}, /* 7 */
61 { 1, "exponent2", ASN1_INTEGER
, ASN1_BODY
}, /* 8 */
62 { 1, "coefficient", ASN1_INTEGER
, ASN1_BODY
}, /* 9 */
63 { 1, "otherPrimeInfos", ASN1_SEQUENCE
, ASN1_OPT
|
65 { 2, "otherPrimeInfo", ASN1_SEQUENCE
, ASN1_NONE
}, /* 11 */
66 { 3, "prime", ASN1_INTEGER
, ASN1_BODY
}, /* 12 */
67 { 3, "exponent", ASN1_INTEGER
, ASN1_BODY
}, /* 13 */
68 { 3, "coefficient", ASN1_INTEGER
, ASN1_BODY
}, /* 14 */
69 { 1, "end opt or loop", ASN1_EOC
, ASN1_END
} /* 15 */
72 #define PKCS1_PRIV_KEY_VERSION 1
73 #define PKCS1_PRIV_KEY_MODULUS 2
74 #define PKCS1_PRIV_KEY_PUB_EXP 3
75 #define PKCS1_PRIV_KEY_COEFF 9
76 #define PKCS1_PRIV_KEY_ROOF 16
80 * forms the FreeS/WAN keyid from the public exponent e and modulus n
83 form_keyid(chunk_t e
, chunk_t n
, char* keyid
, unsigned *keysize
)
85 /* eliminate leading zero bytes in modulus from ASN.1 coding */
86 while (n
.len
> 1 && *n
.ptr
== 0x00)
91 /* form the FreeS/WAN keyid */
92 keyid
[0] = '\0'; /* in case of splitkeytoid failure */
93 splitkeytoid(e
.ptr
, e
.len
, n
.ptr
, n
.len
, keyid
, KEYID_BUF
);
95 /* return the RSA modulus size in octets */
100 * initialize an RSA_public_key_t object
103 init_RSA_public_key(RSA_public_key_t
*rsa
, chunk_t e
, chunk_t n
)
105 n_to_mpz(&rsa
->e
, e
.ptr
, e
.len
);
106 n_to_mpz(&rsa
->n
, n
.ptr
, n
.len
);
108 form_keyid(e
, n
, rsa
->keyid
, &rsa
->k
);
113 RSA_show_key_fields(RSA_private_key_t
*k
, int fieldcnt
)
117 DBG_log(" keyid: *%s", k
->pub
.keyid
);
119 for (p
= RSA_private_field
; p
< &RSA_private_field
[fieldcnt
]; p
++)
121 MP_INT
*n
= (MP_INT
*) ((char *)k
+ p
->offset
);
122 size_t sz
= mpz_sizeinbase(n
, 16);
123 char buf
[RSA_MAX_OCTETS
* 2 + 2]; /* ought to be big enough */
125 passert(sz
<= sizeof(buf
));
126 mpz_get_str(buf
, 16, n
);
128 DBG_log(" %s: 0x%s", p
->name
, buf
);
132 /* debugging info that compromises security! */
134 RSA_show_private_key(RSA_private_key_t
*k
)
136 RSA_show_key_fields(k
, elemsof(RSA_private_field
));
140 RSA_show_public_key(RSA_public_key_t
*k
)
142 /* Kludge: pretend that it is a private key, but only display the
143 * first two fields (which are the public key).
145 passert(offsetof(RSA_private_key_t
, pub
) == 0);
146 RSA_show_key_fields((RSA_private_key_t
*)k
, 2);
151 RSA_private_key_sanity(RSA_private_key_t
*k
)
153 /* note that the *last* error found is reported */
157 #ifdef DEBUG /* debugging info that compromises security */
158 DBG(DBG_PRIVATE
, RSA_show_private_key(k
));
161 /* PKCS#1 1.5 section 6 requires modulus to have at least 12 octets.
162 * We actually require more (for security).
164 if (k
->pub
.k
< RSA_MIN_OCTETS
)
165 return RSA_MIN_OCTETS_UGH
;
167 /* we picked a max modulus size to simplify buffer allocation */
168 if (k
->pub
.k
> RSA_MAX_OCTETS
)
169 return RSA_MAX_OCTETS_UGH
;
175 /* check that n == p * q */
176 mpz_mul(u
, &k
->p
, &k
->q
);
177 if (mpz_cmp(u
, &k
->pub
.n
) != 0)
180 /* check that e divides neither p-1 nor q-1 */
181 mpz_sub_ui(t
, &k
->p
, 1);
182 mpz_mod(t
, t
, &k
->pub
.e
);
183 if (mpz_cmp_ui(t
, 0) == 0)
184 ugh
= "e divides p-1";
186 mpz_sub_ui(t
, &k
->q
, 1);
187 mpz_mod(t
, t
, &k
->pub
.e
);
188 if (mpz_cmp_ui(t
, 0) == 0)
189 ugh
= "e divides q-1";
191 /* check that d is e^-1 (mod lcm(p-1, q-1)) */
192 /* see PKCS#1v2, aka RFC 2437, for the "lcm" */
193 mpz_sub_ui(q1
, &k
->q
, 1);
194 mpz_sub_ui(u
, &k
->p
, 1);
195 mpz_gcd(t
, u
, q1
); /* t := gcd(p-1, q-1) */
196 mpz_mul(u
, u
, q1
); /* u := (p-1) * (q-1) */
197 mpz_divexact(u
, u
, t
); /* u := lcm(p-1, q-1) */
199 mpz_mul(t
, &k
->d
, &k
->pub
.e
);
201 if (mpz_cmp_ui(t
, 1) != 0)
202 ugh
= "(d * e) mod (lcm(p-1, q-1)) != 1";
204 /* check that dP is d mod (p-1) */
205 mpz_sub_ui(u
, &k
->p
, 1);
206 mpz_mod(t
, &k
->d
, u
);
207 if (mpz_cmp(t
, &k
->dP
) != 0)
208 ugh
= "dP is not congruent to d mod (p-1)";
210 /* check that dQ is d mod (q-1) */
211 mpz_sub_ui(u
, &k
->q
, 1);
212 mpz_mod(t
, &k
->d
, u
);
213 if (mpz_cmp(t
, &k
->dQ
) != 0)
214 ugh
= "dQ is not congruent to d mod (q-1)";
216 /* check that qInv is (q^-1) mod p */
217 mpz_mul(t
, &k
->qInv
, &k
->q
);
218 mpz_mod(t
, t
, &k
->p
);
219 if (mpz_cmp_ui(t
, 1) != 0)
220 ugh
= "qInv is not conguent ot (q^-1) mod p";
229 * Check the equality of two RSA public keys
232 same_RSA_public_key(const RSA_public_key_t
*a
, const RSA_public_key_t
*b
)
235 || (a
->k
== b
->k
&& mpz_cmp(&a
->n
, &b
->n
) == 0 && mpz_cmp(&a
->e
, &b
->e
) == 0);
239 * Parses a PKCS#1 private key
242 pkcs1_parse_private_key(chunk_t blob
, RSA_private_key_t
*key
)
246 chunk_t object
, modulus
, exp
;
250 asn1_init(&ctx
, blob
, 0, FALSE
, DBG_PRIVATE
);
252 while (objectID
< PKCS1_PRIV_KEY_ROOF
) {
254 if (!extract_object(privkeyObjects
, &objectID
, &object
, &level
, &ctx
))
257 if (objectID
== PKCS1_PRIV_KEY_VERSION
)
259 if (object
.len
> 0 && *object
.ptr
!= 0)
261 plog(" wrong PKCS#1 private key version");
265 else if (objectID
>= PKCS1_PRIV_KEY_MODULUS
&&
266 objectID
<= PKCS1_PRIV_KEY_COEFF
)
268 MP_INT
*u
= (MP_INT
*) ((char *)key
269 + RSA_private_field
[objectID
- PKCS1_PRIV_KEY_MODULUS
].offset
);
271 n_to_mpz(u
, object
.ptr
, object
.len
);
273 if (objectID
== PKCS1_PRIV_KEY_MODULUS
)
275 else if (objectID
== PKCS1_PRIV_KEY_PUB_EXP
)
280 form_keyid(exp
, modulus
, key
->pub
.keyid
, &key
->pub
.k
);
281 ugh
= RSA_private_key_sanity(key
);
282 return (ugh
== NULL
);
286 * compute a digest over a binary blob
289 compute_digest(chunk_t tbs
, int alg
, chunk_t
*digest
)
294 case OID_MD2_WITH_RSA
:
298 MD2Update(&context
, tbs
.ptr
, tbs
.len
);
299 MD2Final(digest
->ptr
, &context
);
300 digest
->len
= MD2_DIGEST_SIZE
;
304 case OID_MD5_WITH_RSA
:
308 MD5Update(&context
, tbs
.ptr
, tbs
.len
);
309 MD5Final(digest
->ptr
, &context
);
310 digest
->len
= MD5_DIGEST_SIZE
;
314 case OID_SHA1_WITH_RSA
:
315 case OID_SHA1_WITH_RSA_OIW
:
320 SHA1Update(&context
, tbs
.ptr
, tbs
.len
);
321 SHA1Final(digest
->ptr
, &context
);
322 digest
->len
= SHA1_DIGEST_SIZE
;
332 * compute an RSA signature with PKCS#1 padding
335 sign_hash(const RSA_private_key_t
*k
, const u_char
*hash_val
, size_t hash_len
336 , u_char
*sig_val
, size_t sig_len
)
343 DBG(DBG_CONTROL
| DBG_CRYPT
,
344 DBG_log("signing hash with RSA Key *%s", k
->pub
.keyid
)
346 /* PKCS#1 v1.5 8.1 encryption-block formatting */
348 *p
++ = 0x01; /* BT (block type) 01 */
349 padlen
= sig_len
- 3 - hash_len
;
350 memset(p
, 0xFF, padlen
);
353 memcpy(p
, hash_val
, hash_len
);
354 passert(p
+ hash_len
- sig_val
== (ptrdiff_t)sig_len
);
356 /* PKCS#1 v1.5 8.2 octet-string-to-integer conversion */
357 n_to_mpz(t1
, sig_val
, sig_len
); /* (could skip leading 0x00) */
359 /* PKCS#1 v1.5 8.3 RSA computation y = x^c mod n
360 * Better described in PKCS#1 v2.0 5.1 RSADP.
361 * There are two methods, depending on the form of the private key.
362 * We use the one based on the Chinese Remainder Theorem.
366 mpz_powm(t2
, t1
, &k
->dP
, &k
->p
); /* m1 = c^dP mod p */
368 mpz_powm(t1
, t1
, &k
->dQ
, &k
->q
); /* m2 = c^dQ mod Q */
370 mpz_sub(t2
, t2
, t1
); /* h = qInv (m1 - m2) mod p */
371 mpz_mod(t2
, t2
, &k
->p
);
372 mpz_mul(t2
, t2
, &k
->qInv
);
373 mpz_mod(t2
, t2
, &k
->p
);
375 mpz_mul(t2
, t2
, &k
->q
); /* m = m2 + h q */
378 /* PKCS#1 v1.5 8.4 integer-to-octet-string conversion */
379 ch
= mpz_to_n(t1
, sig_len
);
380 memcpy(sig_val
, ch
.ptr
, sig_len
);
388 * encrypt data with an RSA public key after padding
391 RSA_encrypt(const RSA_public_key_t
*key
, chunk_t in
)
393 u_char padded
[RSA_MAX_OCTETS
];
394 u_char
*pos
= padded
;
395 int padding
= key
->k
- in
.len
- 3;
398 if (padding
< 8 || key
->k
> RSA_MAX_OCTETS
)
401 /* add padding according to PKCS#1 7.2.1 1.+2. */
405 /* pad with pseudo random bytes unequal to zero */
406 get_rnd_bytes(pos
, padding
);
407 for (i
= 0; i
< padding
; i
++)
410 get_rnd_bytes(pos
, 1);
414 /* append the padding terminator */
417 /* now add the data */
418 memcpy(pos
, in
.ptr
, in
.len
);
420 DBG_dump_chunk("data for rsa encryption:\n", in
);
421 DBG_dump("padded data for rsa encryption:\n", padded
, key
->k
)
424 /* convert chunk to integer (PKCS#1 7.2.1 3.a) */
430 n_to_mpz(m
, padded
, key
->k
);
432 /* encrypt(PKCS#1 7.2.1 3.b) */
433 mpz_powm(c
, m
, &key
->e
, &key
->n
);
435 /* convert integer back to a chunk (PKCS#1 7.2.1 3.c) */
436 out
= mpz_to_n(c
, key
->k
);
441 DBG_dump_chunk("rsa encrypted data:\n", out
)
448 * decrypt data with an RSA private key and remove padding
451 RSA_decrypt(const RSA_private_key_t
*key
, chunk_t in
, chunk_t
*out
)
457 n_to_mpz(t1
, in
.ptr
,in
.len
);
459 /* PKCS#1 v1.5 8.3 RSA computation y = x^c mod n
460 * Better described in PKCS#1 v2.0 5.1 RSADP.
461 * There are two methods, depending on the form of the private key.
462 * We use the one based on the Chinese Remainder Theorem.
466 mpz_powm(t2
, t1
, &key
->dP
, &key
->p
); /* m1 = c^dP mod p */
467 mpz_powm(t1
, t1
, &key
->dQ
, &key
->q
); /* m2 = c^dQ mod Q */
469 mpz_sub(t2
, t2
, t1
); /* h = qInv (m1 - m2) mod p */
470 mpz_mod(t2
, t2
, &key
->p
);
471 mpz_mul(t2
, t2
, &key
->qInv
);
472 mpz_mod(t2
, t2
, &key
->p
);
474 mpz_mul(t2
, t2
, &key
->q
); /* m = m2 + h q */
477 padded
= mpz_to_n(t1
, key
->pub
.k
);
482 DBG_dump_chunk("rsa decrypted data with padding:\n", padded
)
486 /* PKCS#1 v1.5 8.1 encryption-block formatting (EB = 00 || 02 || PS || 00 || D) */
488 /* check for hex pattern 00 02 in decrypted message */
489 if ((*pos
++ != 0x00) || (*(pos
++) != 0x02))
491 plog("incorrect padding - probably wrong RSA key");
492 freeanychunk(padded
);
497 /* the plaintext data starts after first 0x00 byte */
498 while (padded
.len
-- > 0 && *pos
++ != 0x00)
502 plog("no plaintext data");
503 freeanychunk(padded
);
507 clonetochunk(*out
, pos
, padded
.len
, "decrypted data");
508 freeanychunk(padded
);
513 * build signatureValue
516 pkcs1_build_signature(chunk_t tbs
, int hash_alg
, const RSA_private_key_t
*key
520 size_t siglen
= key
->pub
.k
;
522 u_char digest_buf
[MAX_DIGEST_LEN
];
523 chunk_t digest
= { digest_buf
, MAX_DIGEST_LEN
};
524 chunk_t digestInfo
, alg_id
, signatureValue
;
530 case OID_MD5_WITH_RSA
:
531 alg_id
= ASN1_md5_id
;
534 case OID_SHA1_WITH_RSA
:
535 alg_id
= ASN1_sha1_id
;
540 compute_digest(tbs
, hash_alg
, &digest
);
542 /* according to PKCS#1 v2.1 digest must be packaged into
543 * an ASN.1 structure for encryption
545 digestInfo
= asn1_wrap(ASN1_SEQUENCE
, "cm"
547 , asn1_simple_object(ASN1_OCTET_STRING
, digest
));
549 /* generate the RSA signature */
552 pos
= build_asn1_object(&signatureValue
, ASN1_BIT_STRING
, 1 + siglen
);
557 pos
= build_asn1_object(&signatureValue
, ASN1_OCTET_STRING
, siglen
);
559 sign_hash(key
, digestInfo
.ptr
, digestInfo
.len
, pos
, siglen
);
560 pfree(digestInfo
.ptr
);
562 return signatureValue
;
566 * build a DER-encoded PKCS#1 private key object
569 pkcs1_build_private_key(const RSA_private_key_t
*key
)
571 chunk_t pkcs1
= asn1_wrap(ASN1_SEQUENCE
, "cmmmmmmmm"
573 , asn1_integer_from_mpz(&key
->pub
.n
)
574 , asn1_integer_from_mpz(&key
->pub
.e
)
575 , asn1_integer_from_mpz(&key
->d
)
576 , asn1_integer_from_mpz(&key
->p
)
577 , asn1_integer_from_mpz(&key
->q
)
578 , asn1_integer_from_mpz(&key
->dP
)
579 , asn1_integer_from_mpz(&key
->dQ
)
580 , asn1_integer_from_mpz(&key
->qInv
));
583 DBG_dump_chunk("PKCS#1 encoded private key:", pkcs1
)
589 * build a DER-encoded PKCS#1 public key object
592 pkcs1_build_public_key(const RSA_public_key_t
*rsa
)
594 return asn1_wrap(ASN1_SEQUENCE
, "mm"
595 , asn1_integer_from_mpz(&rsa
->n
)
596 , asn1_integer_from_mpz(&rsa
->e
));
600 * build a DER-encoded publicKeyInfo object
603 pkcs1_build_publicKeyInfo(const RSA_public_key_t
*rsa
)
606 chunk_t rawKey
= pkcs1_build_public_key(rsa
);
608 u_char
*pos
= build_asn1_object(&publicKey
, ASN1_BIT_STRING
611 mv_chunk(&pos
, rawKey
);
613 return asn1_wrap(ASN1_SEQUENCE
, "cm"
614 , ASN1_rsaEncryption_id
618 free_RSA_public_content(RSA_public_key_t
*rsa
)
625 free_RSA_private_content(RSA_private_key_t
*rsak
)
627 free_RSA_public_content(&rsak
->pub
);
631 mpz_clear(&rsak
->dP
);
632 mpz_clear(&rsak
->dQ
);
633 mpz_clear(&rsak
->qInv
);