![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gmp_rsa_private_key.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / gmp|
Return to gmp_rsa_private_key.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / gmp |
1.1 misho 1: /*
2: * Copyright (C) 2017-2018 Tobias Brunner
3: * Copyright (C) 2005 Jan Hutter
4: * Copyright (C) 2005-2009 Martin Willi
5: * Copyright (C) 2012-2019 Andreas Steffen
6: * HSR Hochschule fuer Technik Rapperswil
7: *
8: * This program is free software; you can redistribute it and/or modify it
9: * under the terms of the GNU General Public License as published by the
10: * Free Software Foundation; either version 2 of the License, or (at your
11: * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
12: *
13: * This program is distributed in the hope that it will be useful, but
14: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16: * for more details.
17: */
18:
19: #include <gmp.h>
20: #include <sys/stat.h>
21: #include <unistd.h>
22: #include <string.h>
23:
24: #include "gmp_rsa_private_key.h"
25: #include "gmp_rsa_public_key.h"
26:
27: #include <utils/debug.h>
28: #include <asn1/oid.h>
29: #include <asn1/asn1.h>
30: #include <asn1/asn1_parser.h>
31: #include <credentials/keys/signature_params.h>
32:
33: #ifdef HAVE_MPZ_POWM_SEC
34: # undef mpz_powm
35: # define mpz_powm mpz_powm_sec
36: #endif
37:
38: /**
39: * Public exponent to use for key generation.
40: */
41: #define PUBLIC_EXPONENT 0x10001
42:
43: typedef struct private_gmp_rsa_private_key_t private_gmp_rsa_private_key_t;
44:
45: /**
46: * Private data of a gmp_rsa_private_key_t object.
47: */
48: struct private_gmp_rsa_private_key_t {
49: /**
50: * Public interface for this signer.
51: */
52: gmp_rsa_private_key_t public;
53:
54: /**
55: * Public modulus.
56: */
57: mpz_t n;
58:
59: /**
60: * Public exponent.
61: */
62: mpz_t e;
63:
64: /**
65: * Private prime 1.
66: */
67: mpz_t p;
68:
69: /**
70: * Private Prime 2.
71: */
72: mpz_t q;
73:
74: /**
75: * Carmichael function m = lambda(n) = lcm(p-1,q-1).
76: */
77: mpz_t m;
78:
79: /**
80: * Private exponent and optional secret sharing polynomial coefficients.
81: */
82: mpz_t *d;
83:
84: /**
85: * Private exponent 1.
86: */
87: mpz_t exp1;
88:
89: /**
90: * Private exponent 2.
91: */
92: mpz_t exp2;
93:
94: /**
95: * Private coefficient.
96: */
97: mpz_t coeff;
98:
99: /**
100: * Total number of private key shares
101: */
102: u_int shares;
103:
104: /**
105: * Secret sharing threshold
106: */
107: u_int threshold;
108:
109: /**
110: * Optional verification key (threshold > 1).
111: */
112: mpz_t v;
113:
114: /**
115: * Keysize in bytes.
116: */
117: size_t k;
118:
119: /**
120: * reference count
121: */
122: refcount_t ref;
123: };
124:
125: /**
126: * Convert a MP integer into a chunk_t
127: */
128: chunk_t gmp_mpz_to_chunk(const mpz_t value)
129: {
130: chunk_t n;
131:
132: n.len = 1 + mpz_sizeinbase(value, 2) / BITS_PER_BYTE;
133: n.ptr = mpz_export(NULL, NULL, 1, n.len, 1, 0, value);
134: if (n.ptr == NULL)
135: { /* if we have zero in "value", gmp returns NULL */
136: n.len = 0;
137: }
138: return n;
139: }
140:
141: /**
142: * Auxiliary function overwriting private key material with zero bytes
143: */
144: static void mpz_clear_sensitive(mpz_t z)
145: {
146: size_t len = mpz_size(z) * GMP_LIMB_BITS / BITS_PER_BYTE;
147: uint8_t *zeros = alloca(len);
148:
149: memset(zeros, 0, len);
150: /* overwrite mpz_t with zero bytes before clearing it */
151: mpz_import(z, len, 1, 1, 1, 0, zeros);
152: mpz_clear(z);
153: }
154:
155: /**
156: * Create a mpz prime of at least prime_size
157: */
158: static status_t compute_prime(drbg_t *drbg, size_t prime_size, bool safe, mpz_t *p, mpz_t *q)
159: {
160: chunk_t random_bytes;
161: int count = 0;
162:
163: mpz_init(*p);
164: mpz_init(*q);
165: random_bytes = chunk_alloc(prime_size);
166:
167: do
168: {
169: if (!drbg->generate(drbg, random_bytes.len, random_bytes.ptr))
170: {
171: DBG1(DBG_LIB, "failed to allocate random prime");
172: mpz_clear(*p);
173: mpz_clear(*q);
174: chunk_free(&random_bytes);
175: return FAILED;
176: }
177:
178: /* make sure the two most significant bits are set */
179: if (safe)
180: {
181: random_bytes.ptr[0] &= 0x7F;
182: random_bytes.ptr[0] |= 0x60;
183: mpz_import(*q, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
184: do
185: {
186: count++;
187: mpz_nextprime (*q, *q);
188: mpz_mul_ui(*p, *q, 2);
189: mpz_add_ui(*p, *p, 1);
190: }
191: while (mpz_probab_prime_p(*p, 10) == 0);
192: DBG2(DBG_LIB, "safe prime found after %d iterations", count);
193: }
194: else
195: {
196: random_bytes.ptr[0] |= 0xC0;
197: mpz_import(*p, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
198: mpz_nextprime (*p, *p);
199: }
200: }
201: /* check if the prime isn't too large */
202: while (((mpz_sizeinbase(*p, 2) + 7) / 8) > prime_size);
203:
204: chunk_clear(&random_bytes);
205:
206: /* additionally return p-1 */
207: mpz_sub_ui(*q, *p, 1);
208:
209: return SUCCESS;
210: }
211:
212: /**
213: * PKCS#1 RSADP function
214: */
215: static chunk_t rsadp(private_gmp_rsa_private_key_t *this, chunk_t data)
216: {
217: mpz_t t1, t2;
218: chunk_t decrypted;
219:
220: mpz_init(t1);
221: mpz_init(t2);
222:
223: mpz_import(t1, data.len, 1, 1, 1, 0, data.ptr);
224:
225: mpz_powm(t2, t1, this->exp1, this->p); /* m1 = c^dP mod p */
226: mpz_powm(t1, t1, this->exp2, this->q); /* m2 = c^dQ mod Q */
227: mpz_sub(t2, t2, t1); /* h = qInv (m1 - m2) mod p */
228: mpz_mod(t2, t2, this->p);
229: mpz_mul(t2, t2, this->coeff);
230: mpz_mod(t2, t2, this->p);
231:
232: mpz_mul(t2, t2, this->q); /* m = m2 + h q */
233: mpz_add(t1, t1, t2);
234:
235: decrypted.len = this->k;
236: decrypted.ptr = mpz_export(NULL, NULL, 1, decrypted.len, 1, 0, t1);
237: if (decrypted.ptr == NULL)
238: {
239: decrypted.len = 0;
240: }
241:
242: mpz_clear_sensitive(t1);
243: mpz_clear_sensitive(t2);
244:
245: return decrypted;
246: }
247:
248: /**
249: * PKCS#1 RSASP1 function
250: */
251: static chunk_t rsasp1(private_gmp_rsa_private_key_t *this, chunk_t data)
252: {
253: return rsadp(this, data);
254: }
255:
256: /**
257: * Hashes the data and builds the plaintext signature value with EMSA
258: * PKCS#1 v1.5 padding.
259: *
260: * Allocates the signature data.
261: */
262: bool gmp_emsa_pkcs1_signature_data(hash_algorithm_t hash_algorithm,
263: chunk_t data, size_t keylen, chunk_t *em)
264: {
265: chunk_t digestInfo = chunk_empty;
266:
267: if (hash_algorithm != HASH_UNKNOWN)
268: {
269: hasher_t *hasher;
270: chunk_t hash;
271: int hash_oid = hasher_algorithm_to_oid(hash_algorithm);
272:
273: if (hash_oid == OID_UNKNOWN)
274: {
275: return FALSE;
276: }
277:
278: hasher = lib->crypto->create_hasher(lib->crypto, hash_algorithm);
279: if (!hasher || !hasher->allocate_hash(hasher, data, &hash))
280: {
281: DESTROY_IF(hasher);
282: return FALSE;
283: }
284: hasher->destroy(hasher);
285:
286: /* build DER-encoded digestInfo */
287: digestInfo = asn1_wrap(ASN1_SEQUENCE, "mm",
288: asn1_algorithmIdentifier(hash_oid),
289: asn1_wrap(ASN1_OCTET_STRING, "m", hash));
290:
291: data = digestInfo;
292: }
293:
294: if (keylen < 11 || data.len > keylen - 11)
295: {
296: chunk_free(&digestInfo);
297: DBG1(DBG_LIB, "signature value of %zu bytes is too long for key of "
298: "%zu bytes", data.len, keylen);
299: return FALSE;
300: }
301:
302: /* EM = 0x00 || 0x01 || PS || 0x00 || T.
303: * PS = 0xFF padding, with length to fill em (at least 8 bytes)
304: * T = encoded_hash
305: */
306: *em = chunk_alloc(keylen);
307:
308: /* fill em with padding */
309: memset(em->ptr, 0xFF, em->len);
310: /* set magic bytes */
311: *(em->ptr) = 0x00;
312: *(em->ptr+1) = 0x01;
313: *(em->ptr + em->len - data.len - 1) = 0x00;
314: /* set encoded hash */
315: memcpy(em->ptr + em->len - data.len, data.ptr, data.len);
316:
317: chunk_clear(&digestInfo);
318: return TRUE;
319: }
320:
321: /**
322: * Build a signature using the PKCS#1 EMSA scheme
323: */
324: static bool build_emsa_pkcs1_signature(private_gmp_rsa_private_key_t *this,
325: hash_algorithm_t hash_algorithm,
326: chunk_t data, chunk_t *signature)
327: {
328: chunk_t em;
329:
330: if (!gmp_emsa_pkcs1_signature_data(hash_algorithm, data, this->k, &em))
331: {
332: return FALSE;
333: }
334:
335: /* build signature */
336: *signature = rsasp1(this, em);
337:
338: chunk_free(&em);
339: return TRUE;
340: }
341:
342: /**
343: * Build a signature using the PKCS#1 EMSA PSS scheme
344: */
345: static bool build_emsa_pss_signature(private_gmp_rsa_private_key_t *this,
346: rsa_pss_params_t *params, chunk_t data,
347: chunk_t *signature)
348: {
349: ext_out_function_t xof;
350: hasher_t *hasher = NULL;
351: rng_t *rng = NULL;
352: xof_t *mgf = NULL;
353: chunk_t hash, salt = chunk_empty, m, ps, db, dbmask, em;
354: size_t embits, emlen, maskbits;
355: bool success = FALSE;
356:
357: if (!params)
358: {
359: return FALSE;
360: }
361: xof = xof_mgf1_from_hash_algorithm(params->mgf1_hash);
362: if (xof == XOF_UNDEFINED)
363: {
364: DBG1(DBG_LIB, "%N is not supported for MGF1", hash_algorithm_names,
365: params->mgf1_hash);
366: return FALSE;
367: }
368: /* emBits = modBits - 1 */
369: embits = mpz_sizeinbase(this->n, 2) - 1;
370: /* emLen = ceil(emBits/8) */
371: emlen = (embits + 7) / BITS_PER_BYTE;
372: /* mHash = Hash(M) */
373: hasher = lib->crypto->create_hasher(lib->crypto, params->hash);
374: if (!hasher)
375: {
376: DBG1(DBG_LIB, "hash algorithm %N not supported",
377: hash_algorithm_names, params->hash);
378: return FALSE;
379: }
380: hash = chunk_alloca(hasher->get_hash_size(hasher));
381: if (!hasher->get_hash(hasher, data, hash.ptr))
382: {
383: goto error;
384: }
385:
386: salt.len = params->salt_len;
387: if (params->salt.len)
388: {
389: salt = params->salt;
390: }
391: if (emlen < (hash.len + salt.len + 2))
392: { /* too long */
393: goto error;
394: }
395: if (salt.len && !params->salt.len)
396: {
397: salt = chunk_alloca(salt.len);
398: rng = lib->crypto->create_rng(lib->crypto, RNG_STRONG);
399: if (!rng || !rng->get_bytes(rng, salt.len, salt.ptr))
400: {
401: goto error;
402: }
403: }
404: /* M' = 0x0000000000000000 | mHash | salt */
405: m = chunk_cata("ccc",
406: chunk_from_chars(0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00),
407: hash, salt);
408: /* H = Hash(M') */
409: if (!hasher->get_hash(hasher, m, hash.ptr))
410: {
411: goto error;
412: }
413: /* PS = 00...<padding depending on hash and salt length> */
414: ps = chunk_alloca(emlen - salt.len - hash.len - 2);
415: memset(ps.ptr, 0, ps.len);
416: /* DB = PS | 0x01 | salt */
417: db = chunk_cata("ccc", ps, chunk_from_chars(0x01), salt);
418: /* dbMask = MGF(H, emLen - hLen - 1) */
419: mgf = lib->crypto->create_xof(lib->crypto, xof);
420: dbmask = chunk_alloca(db.len);
421: if (!mgf)
422: {
423: DBG1(DBG_LIB, "%N not supported", ext_out_function_names, xof);
424: goto error;
425: }
426: if (!mgf->set_seed(mgf, hash) ||
427: !mgf->get_bytes(mgf, dbmask.len, dbmask.ptr))
428: {
429: goto error;
430: }
431: /* maskedDB = DB xor dbMask */
432: memxor(db.ptr, dbmask.ptr, db.len);
433: /* zero out unused bits */
434: maskbits = (8 * emlen) - embits;
435: if (maskbits)
436: {
437: db.ptr[0] &= (0xff >> maskbits);
438: }
439: /* EM = maskedDB | H | 0xbc */
440: em = chunk_cata("ccc", db, hash, chunk_from_chars(0xbc));
441: /* S = RSASP1(K, EM) */
442: *signature = rsasp1(this, em);
443: success = TRUE;
444:
445: error:
446: DESTROY_IF(hasher);
447: DESTROY_IF(rng);
448: DESTROY_IF(mgf);
449: return success;
450: }
451:
452: METHOD(private_key_t, get_type, key_type_t,
453: private_gmp_rsa_private_key_t *this)
454: {
455: return KEY_RSA;
456: }
457:
458: METHOD(private_key_t, sign, bool,
459: private_gmp_rsa_private_key_t *this, signature_scheme_t scheme,
460: void *params, chunk_t data, chunk_t *signature)
461: {
462: switch (scheme)
463: {
464: case SIGN_RSA_EMSA_PKCS1_NULL:
465: return build_emsa_pkcs1_signature(this, HASH_UNKNOWN, data, signature);
466: case SIGN_RSA_EMSA_PKCS1_SHA2_224:
467: return build_emsa_pkcs1_signature(this, HASH_SHA224, data, signature);
468: case SIGN_RSA_EMSA_PKCS1_SHA2_256:
469: return build_emsa_pkcs1_signature(this, HASH_SHA256, data, signature);
470: case SIGN_RSA_EMSA_PKCS1_SHA2_384:
471: return build_emsa_pkcs1_signature(this, HASH_SHA384, data, signature);
472: case SIGN_RSA_EMSA_PKCS1_SHA2_512:
473: return build_emsa_pkcs1_signature(this, HASH_SHA512, data, signature);
474: case SIGN_RSA_EMSA_PKCS1_SHA3_224:
475: return build_emsa_pkcs1_signature(this, HASH_SHA3_224, data, signature);
476: case SIGN_RSA_EMSA_PKCS1_SHA3_256:
477: return build_emsa_pkcs1_signature(this, HASH_SHA3_256, data, signature);
478: case SIGN_RSA_EMSA_PKCS1_SHA3_384:
479: return build_emsa_pkcs1_signature(this, HASH_SHA3_384, data, signature);
480: case SIGN_RSA_EMSA_PKCS1_SHA3_512:
481: return build_emsa_pkcs1_signature(this, HASH_SHA3_512, data, signature);
482: case SIGN_RSA_EMSA_PKCS1_SHA1:
483: return build_emsa_pkcs1_signature(this, HASH_SHA1, data, signature);
484: case SIGN_RSA_EMSA_PKCS1_MD5:
485: return build_emsa_pkcs1_signature(this, HASH_MD5, data, signature);
486: case SIGN_RSA_EMSA_PSS:
487: return build_emsa_pss_signature(this, params, data, signature);
488: default:
489: DBG1(DBG_LIB, "signature scheme %N not supported in RSA",
490: signature_scheme_names, scheme);
491: return FALSE;
492: }
493: }
494:
495: METHOD(private_key_t, decrypt, bool,
496: private_gmp_rsa_private_key_t *this, encryption_scheme_t scheme,
497: chunk_t crypto, chunk_t *plain)
498: {
499: chunk_t em, stripped;
500: bool success = FALSE;
501:
502: if (scheme != ENCRYPT_RSA_PKCS1)
503: {
504: DBG1(DBG_LIB, "encryption scheme %N not supported",
505: encryption_scheme_names, scheme);
506: return FALSE;
507: }
508: /* rsa decryption using PKCS#1 RSADP */
509: stripped = em = rsadp(this, crypto);
510:
511: /* PKCS#1 v1.5 8.1 encryption-block formatting (EB = 00 || 02 || PS || 00 || D) */
512:
513: /* check for hex pattern 00 02 in decrypted message */
514: if ((*stripped.ptr++ != 0x00) || (*(stripped.ptr++) != 0x02))
515: {
516: DBG1(DBG_LIB, "incorrect padding - probably wrong rsa key");
517: goto end;
518: }
519: stripped.len -= 2;
520:
521: /* the plaintext data starts after first 0x00 byte */
522: while (stripped.len-- > 0 && *stripped.ptr++ != 0x00)
523:
524: if (stripped.len == 0)
525: {
526: DBG1(DBG_LIB, "no plaintext data");
527: goto end;
528: }
529:
530: *plain = chunk_clone(stripped);
531: success = TRUE;
532:
533: end:
534: chunk_clear(&em);
535: return success;
536: }
537:
538: METHOD(private_key_t, get_keysize, int,
539: private_gmp_rsa_private_key_t *this)
540: {
541: return mpz_sizeinbase(this->n, 2);
542: }
543:
544: METHOD(private_key_t, get_public_key, public_key_t*,
545: private_gmp_rsa_private_key_t *this)
546: {
547: chunk_t n, e;
548: public_key_t *public;
549:
550: n = gmp_mpz_to_chunk(this->n);
551: e = gmp_mpz_to_chunk(this->e);
552:
553: public = lib->creds->create(lib->creds, CRED_PUBLIC_KEY, KEY_RSA,
554: BUILD_RSA_MODULUS, n, BUILD_RSA_PUB_EXP, e, BUILD_END);
555: chunk_free(&n);
556: chunk_free(&e);
557:
558: return public;
559: }
560:
561: METHOD(private_key_t, get_encoding, bool,
562: private_gmp_rsa_private_key_t *this, cred_encoding_type_t type,
563: chunk_t *encoding)
564: {
565: chunk_t n, e, d, p, q, exp1, exp2, coeff;
566: bool success;
567:
568: n = gmp_mpz_to_chunk(this->n);
569: e = gmp_mpz_to_chunk(this->e);
570: d = gmp_mpz_to_chunk(*this->d);
571: p = gmp_mpz_to_chunk(this->p);
572: q = gmp_mpz_to_chunk(this->q);
573: exp1 = gmp_mpz_to_chunk(this->exp1);
574: exp2 = gmp_mpz_to_chunk(this->exp2);
575: coeff = gmp_mpz_to_chunk(this->coeff);
576:
577: success = lib->encoding->encode(lib->encoding,
578: type, NULL, encoding, CRED_PART_RSA_MODULUS, n,
579: CRED_PART_RSA_PUB_EXP, e, CRED_PART_RSA_PRIV_EXP, d,
580: CRED_PART_RSA_PRIME1, p, CRED_PART_RSA_PRIME2, q,
581: CRED_PART_RSA_EXP1, exp1, CRED_PART_RSA_EXP2, exp2,
582: CRED_PART_RSA_COEFF, coeff, CRED_PART_END);
583: chunk_free(&n);
584: chunk_free(&e);
585: chunk_clear(&d);
586: chunk_clear(&p);
587: chunk_clear(&q);
588: chunk_clear(&exp1);
589: chunk_clear(&exp2);
590: chunk_clear(&coeff);
591:
592: return success;
593: }
594:
595: METHOD(private_key_t, get_fingerprint, bool,
596: private_gmp_rsa_private_key_t *this, cred_encoding_type_t type, chunk_t *fp)
597: {
598: chunk_t n, e;
599: bool success;
600:
601: if (lib->encoding->get_cache(lib->encoding, type, this, fp))
602: {
603: return TRUE;
604: }
605: n = gmp_mpz_to_chunk(this->n);
606: e = gmp_mpz_to_chunk(this->e);
607:
608: success = lib->encoding->encode(lib->encoding, type, this, fp,
609: CRED_PART_RSA_MODULUS, n, CRED_PART_RSA_PUB_EXP, e, CRED_PART_END);
610: chunk_free(&n);
611: chunk_free(&e);
612:
613: return success;
614: }
615:
616: METHOD(private_key_t, get_ref, private_key_t*,
617: private_gmp_rsa_private_key_t *this)
618: {
619: ref_get(&this->ref);
620: return &this->public.key;
621: }
622:
623: METHOD(private_key_t, destroy, void,
624: private_gmp_rsa_private_key_t *this)
625: {
626: if (ref_put(&this->ref))
627: {
628: int i;
629:
630: mpz_clear(this->n);
631: mpz_clear(this->e);
632: mpz_clear(this->v);
633: mpz_clear_sensitive(this->p);
634: mpz_clear_sensitive(this->q);
635: mpz_clear_sensitive(this->m);
636: mpz_clear_sensitive(this->exp1);
637: mpz_clear_sensitive(this->exp2);
638: mpz_clear_sensitive(this->coeff);
639:
640: for (i = 0; i < this->threshold; i++)
641: {
642: mpz_clear_sensitive(*this->d + i);
643: }
644: free(this->d);
645:
646: lib->encoding->clear_cache(lib->encoding, this);
647: free(this);
648: }
649: }
650:
651: /**
652: * Check the loaded key if it is valid and usable
653: */
654: static status_t check(private_gmp_rsa_private_key_t *this)
655: {
656: mpz_t u, p1, q1;
657: status_t status = SUCCESS;
658:
659: /* PKCS#1 1.5 section 6 requires modulus to have at least 12 octets.
660: * We actually require more (for security).
661: */
662: if (this->k < 512 / BITS_PER_BYTE)
663: {
664: DBG1(DBG_LIB, "key shorter than 512 bits");
665: return FAILED;
666: }
667:
668: /* we picked a max modulus size to simplify buffer allocation */
669: if (this->k > 8192 / BITS_PER_BYTE)
670: {
671: DBG1(DBG_LIB, "key larger than 8192 bits");
672: return FAILED;
673: }
674:
675: mpz_init(u);
676: mpz_init(p1);
677: mpz_init(q1);
678:
679: /* precompute p1 = p-1 and q1 = q-1 */
680: mpz_sub_ui(p1, this->p, 1);
681: mpz_sub_ui(q1, this->q, 1);
682:
683: /* check that n == p * q */
684: mpz_mul(u, this->p, this->q);
685: if (mpz_cmp(u, this->n) != 0)
686: {
687: status = FAILED;
688: }
689:
690: /* check that e divides neither p-1 nor q-1 */
691: mpz_mod(u, p1, this->e);
692: if (mpz_cmp_ui(u, 0) == 0)
693: {
694: status = FAILED;
695: }
696:
697: mpz_mod(u, q1, this->e);
698: if (mpz_cmp_ui(u, 0) == 0)
699: {
700: status = FAILED;
701: }
702:
703: /* check that d is e^-1 (mod lcm(p-1, q-1)) */
704: /* see PKCS#1v2, aka RFC 2437, for the "lcm" */
705: mpz_lcm(this->m, p1, q1);
706: mpz_mul(u, *this->d, this->e);
707: mpz_mod(u, u, this->m);
708: if (mpz_cmp_ui(u, 1) != 0)
709: {
710: status = FAILED;
711: }
712:
713: /* check that exp1 is d mod (p-1) */
714: mpz_mod(u, *this->d, p1);
715: if (mpz_cmp(u, this->exp1) != 0)
716: {
717: status = FAILED;
718: }
719:
720: /* check that exp2 is d mod (q-1) */
721: mpz_mod(u, *this->d, q1);
722: if (mpz_cmp(u, this->exp2) != 0)
723: {
724: status = FAILED;
725: }
726:
727: /* check that coeff is (q^-1) mod p */
728: mpz_mul(u, this->coeff, this->q);
729: mpz_mod(u, u, this->p);
730: if (mpz_cmp_ui(u, 1) != 0)
731: {
732: status = FAILED;
733: }
734:
735: mpz_clear_sensitive(u);
736: mpz_clear_sensitive(p1);
737: mpz_clear_sensitive(q1);
738:
739: if (status != SUCCESS)
740: {
741: DBG1(DBG_LIB, "key integrity tests failed");
742: }
743: return status;
744: }
745:
746: /**
747: * Internal generic constructor
748: */
749: static private_gmp_rsa_private_key_t *gmp_rsa_private_key_create_empty(void)
750: {
751: private_gmp_rsa_private_key_t *this;
752:
753: INIT(this,
754: .public = {
755: .key = {
756: .get_type = _get_type,
757: .sign = _sign,
758: .decrypt = _decrypt,
759: .get_keysize = _get_keysize,
760: .get_public_key = _get_public_key,
761: .equals = private_key_equals,
762: .belongs_to = private_key_belongs_to,
763: .get_fingerprint = _get_fingerprint,
764: .has_fingerprint = private_key_has_fingerprint,
765: .get_encoding = _get_encoding,
766: .get_ref = _get_ref,
767: .destroy = _destroy,
768: },
769: },
770: .threshold = 1,
771: .ref = 1,
772: );
773: return this;
774: }
775:
776: /**
777: * See header.
778: */
779: gmp_rsa_private_key_t *gmp_rsa_private_key_gen(key_type_t type, va_list args)
780: {
781: private_gmp_rsa_private_key_t *this;
782: drbg_type_t drbg_type = DRBG_HMAC_SHA512;
783: drbg_t* drbg;
784: rng_t *rng;
785: u_int strength = 256, key_size = 0, shares = 0, threshold = 1;
786: bool safe_prime = FALSE, drbg_failed = FALSE, invert_failed = FALSE;
787: mpz_t p, q, p1, q1;
788: int i;
789:
790:
791: while (TRUE)
792: {
793: switch (va_arg(args, builder_part_t))
794: {
795: case BUILD_KEY_SIZE:
796: key_size = va_arg(args, u_int);
797: continue;
798: case BUILD_SAFE_PRIMES:
799: safe_prime = TRUE;
800: continue;
801: case BUILD_SHARES:
802: shares = va_arg(args, u_int);
803: continue;
804: case BUILD_THRESHOLD:
805: threshold = va_arg(args, u_int);
806: continue;
807: case BUILD_END:
808: break;
809: default:
810: return NULL;
811: }
812: break;
813: }
814: if (!key_size)
815: {
816: return NULL;
817: }
818: key_size = key_size / BITS_PER_BYTE;
819:
820: /* Initiate a NIST SP 800-90A DRBG fed by a true rng owned by the drbg */
821: rng = lib->crypto->create_rng(lib->crypto, RNG_TRUE);
822: if (!rng)
823: {
824: DBG1(DBG_LIB, "no RNG of quality %N found", rng_quality_names, RNG_TRUE);
825: return NULL;
826: }
827: drbg = lib->crypto->create_drbg(lib->crypto, drbg_type, strength, rng,
828: chunk_empty);
829: if (!drbg)
830: {
831: DBG1(DBG_LIB, "instantiation of %N failed", drbg_type_names, drbg_type);
832: rng->destroy(rng);
833: return NULL;
834: }
835:
836: /* Get values of primes p and q */
837: if (compute_prime(drbg, key_size/2, safe_prime, &p, &p1) != SUCCESS)
838: {
839: drbg->destroy(drbg);
840: return NULL;
841: }
842: if (compute_prime(drbg, key_size/2, safe_prime, &q, &q1) != SUCCESS)
843: {
844: mpz_clear(p);
845: mpz_clear(p1);
846: drbg->destroy(drbg);
847: return NULL;
848: }
849:
850: /* Swapping Primes so p is larger then q */
851: if (mpz_cmp(p, q) < 0)
852: {
853: mpz_swap(p, q);
854: mpz_swap(p1, q1);
855: }
856:
857: /* Create and initialize RSA private key object */
858: this = gmp_rsa_private_key_create_empty();
859: *this->p = *p;
860: *this->q = *q;
861:
862: /* allocate space for private exponent d with optional threshold scheme */
863: this->shares = shares;
864: this->threshold = threshold;
865: this->d = malloc(threshold * sizeof(mpz_t));
866: for (i = 0; i < threshold; i++)
867: {
868: mpz_init(this->d[i]);
869: }
870:
871: mpz_init_set_ui(this->e, PUBLIC_EXPONENT);
872: mpz_init(this->n);
873: mpz_init(this->m);
874: mpz_init(this->exp1);
875: mpz_init(this->exp2);
876: mpz_init(this->coeff);
877: mpz_init(this->v);
878:
879: mpz_mul(this->n, p, q); /* n = p*q */
880: mpz_lcm(this->m, p1, q1); /* m = lcm(p-1,q-1) */
881: mpz_invert(this->d[0], this->e, this->m); /* e has an inverse mod m */
882: mpz_mod(this->exp1, this->d[0], p1); /* exp1 = d mod p-1 */
883: mpz_mod(this->exp2, this->d[0], q1); /* exp2 = d mod q-1 */
884: mpz_invert(this->coeff, q, p); /* coeff = q^-1 mod p */
885:
886: invert_failed = mpz_cmp_ui(this->m, 0) == 0 ||
887: mpz_cmp_ui(this->coeff, 0) == 0;
888:
889: /* generate and store random coefficients of secret sharing polynomial */
890: if (threshold > 1)
891: {
892: chunk_t random_bytes;
893: mpz_t u;
894:
895: mpz_init(u);
896: random_bytes = chunk_alloc(key_size);
897:
898: for (i = 1; i < threshold; i++)
899: {
900: if (!drbg->generate(drbg, random_bytes.len, random_bytes.ptr))
901: {
902: drbg_failed = TRUE;
903: continue;
904: }
905: mpz_import(this->d[i], random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
906: mpz_mod(this->d[i], this->d[i], this->m);
907: }
908:
909: /* generate verification key v as a square number */
910: do
911: {
912: if (!drbg->generate(drbg, random_bytes.len, random_bytes.ptr))
913: {
914: drbg_failed = TRUE;
915: break;
916: }
917: mpz_import(this->v, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
918: mpz_mul(this->v, this->v, this->v);
919: mpz_mod(this->v, this->v, this->n);
920: mpz_gcd(u, this->v, this->n);
921: }
922: while (mpz_cmp_ui(u, 1) != 0);
923:
924: mpz_clear(u);
925: chunk_clear(&random_bytes);
926: }
927:
928: mpz_clear_sensitive(p1);
929: mpz_clear_sensitive(q1);
930: drbg->destroy(drbg);
931:
932: if (drbg_failed || invert_failed)
933: {
934: DBG1(DBG_LIB, "rsa key generation failed");
935: destroy(this);
936: return NULL;
937: }
938:
939: /* set key size in bytes */
940: this->k = key_size;
941:
942: return &this->public;
943: }
944:
945: /**
946: * Recover the primes from n, e and d using the algorithm described in
947: * Appendix C of NIST SP 800-56B.
948: */
949: static bool calculate_pq(private_gmp_rsa_private_key_t *this)
950: {
951: gmp_randstate_t rstate;
952: mpz_t k, r, g, y, n1, x;
953: int i, t, j;
954: bool success = FALSE;
955:
956: gmp_randinit_default(rstate);
957: mpz_init(k);
958: mpz_init(r);
959: mpz_init(g);
960: mpz_init(y);
961: mpz_init(n1);
962: mpz_init(x);
963: /* k = (d * e) - 1 */
964: mpz_mul(k, *this->d, this->e);
965: mpz_sub_ui(k, k, 1);
966: if (mpz_odd_p(k))
967: {
968: goto error;
969: }
970: /* k = 2^t * r, where r is the largest odd integer dividing k, and t >= 1 */
971: mpz_set(r, k);
972: for (t = 0; !mpz_odd_p(r); t++)
973: { /* r = r/2 */
974: mpz_divexact_ui(r, r, 2);
975: }
976: /* we need n-1 below */
977: mpz_sub_ui(n1, this->n, 1);
978: for (i = 0; i < 100; i++)
979: { /* generate random integer g in [0, n-1] */
980: mpz_urandomm(g, rstate, this->n);
981: /* y = g^r mod n */
982: mpz_powm(y, g, r, this->n);
983: /* try again if y == 1 or y == n-1 */
984: if (mpz_cmp_ui(y, 1) == 0 || mpz_cmp(y, n1) == 0)
985: {
986: continue;
987: }
988: for (j = 0; j < t; j++)
989: { /* x = y^2 mod n */
990: mpz_powm_ui(x, y, 2, this->n);
991: /* stop if x == 1 */
992: if (mpz_cmp_ui(x, 1) == 0)
993: {
994: goto done;
995: }
996: /* retry with new g if x = n-1 */
997: if (mpz_cmp(x, n1) == 0)
998: {
999: break;
1000: }
1001: /* y = x */
1002: mpz_set(y, x);
1003: }
1004: }
1005: goto error;
1006:
1007: done:
1008: /* p = gcd(y-1, n) */
1009: mpz_sub_ui(y, y, 1);
1010: mpz_gcd(this->p, y, this->n);
1011: /* q = n/p */
1012: mpz_divexact(this->q, this->n, this->p);
1013: success = TRUE;
1014:
1015: error:
1016: mpz_clear_sensitive(k);
1017: mpz_clear_sensitive(r);
1018: mpz_clear_sensitive(g);
1019: mpz_clear_sensitive(y);
1020: mpz_clear_sensitive(x);
1021: mpz_clear(n1);
1022: gmp_randclear(rstate);
1023: return success;
1024: }
1025:
1026: /**
1027: * See header.
1028: */
1029: gmp_rsa_private_key_t *gmp_rsa_private_key_load(key_type_t type, va_list args)
1030: {
1031: private_gmp_rsa_private_key_t *this;
1032: chunk_t n, e, d, p, q, exp1, exp2, coeff;
1033:
1034: n = e = d = p = q = exp1 = exp2 = coeff = chunk_empty;
1035: while (TRUE)
1036: {
1037: switch (va_arg(args, builder_part_t))
1038: {
1039: case BUILD_RSA_MODULUS:
1040: n = va_arg(args, chunk_t);
1041: continue;
1042: case BUILD_RSA_PUB_EXP:
1043: e = va_arg(args, chunk_t);
1044: continue;
1045: case BUILD_RSA_PRIV_EXP:
1046: d = va_arg(args, chunk_t);
1047: continue;
1048: case BUILD_RSA_PRIME1:
1049: p = va_arg(args, chunk_t);
1050: continue;
1051: case BUILD_RSA_PRIME2:
1052: q = va_arg(args, chunk_t);
1053: continue;
1054: case BUILD_RSA_EXP1:
1055: exp1 = va_arg(args, chunk_t);
1056: continue;
1057: case BUILD_RSA_EXP2:
1058: exp2 = va_arg(args, chunk_t);
1059: continue;
1060: case BUILD_RSA_COEFF:
1061: coeff = va_arg(args, chunk_t);
1062: continue;
1063: case BUILD_END:
1064: break;
1065: default:
1066: return NULL;
1067: }
1068: break;
1069: }
1070:
1071: this = gmp_rsa_private_key_create_empty();
1072:
1073: this->d = malloc(sizeof(mpz_t));
1074: mpz_init(this->n);
1075: mpz_init(this->e);
1076: mpz_init(*this->d);
1077: mpz_init(this->p);
1078: mpz_init(this->q);
1079: mpz_init(this->m);
1080: mpz_init(this->exp1);
1081: mpz_init(this->exp2);
1082: mpz_init(this->coeff);
1083: mpz_init(this->v);
1084:
1085: mpz_import(this->n, n.len, 1, 1, 1, 0, n.ptr);
1086: mpz_import(this->e, e.len, 1, 1, 1, 0, e.ptr);
1087: mpz_import(*this->d, d.len, 1, 1, 1, 0, d.ptr);
1088: if (p.len)
1089: {
1090: mpz_import(this->p, p.len, 1, 1, 1, 0, p.ptr);
1091: }
1092: if (q.len)
1093: {
1094: mpz_import(this->q, q.len, 1, 1, 1, 0, q.ptr);
1095: }
1096: if (!p.len && !q.len)
1097: { /* p and q missing in key, recalculate from n, e and d */
1098: if (!calculate_pq(this))
1099: {
1100: destroy(this);
1101: return NULL;
1102: }
1103: }
1104: else if (!p.len)
1105: { /* p missing in key, recalculate: p = n / q */
1106: mpz_divexact(this->p, this->n, this->q);
1107: }
1108: else if (!q.len)
1109: { /* q missing in key, recalculate: q = n / p */
1110: mpz_divexact(this->q, this->n, this->p);
1111: }
1112: if (!exp1.len)
1113: { /* exp1 missing in key, recalculate: exp1 = d mod (p-1) */
1114: mpz_sub_ui(this->exp1, this->p, 1);
1115: mpz_mod(this->exp1, *this->d, this->exp1);
1116: }
1117: else
1118: {
1119: mpz_import(this->exp1, exp1.len, 1, 1, 1, 0, exp1.ptr);
1120: }
1121: if (!exp2.len)
1122: { /* exp2 missing in key, recalculate: exp2 = d mod (q-1) */
1123: mpz_sub_ui(this->exp2, this->q, 1);
1124: mpz_mod(this->exp2, *this->d, this->exp2);
1125: }
1126: else
1127: {
1128: mpz_import(this->exp2, exp2.len, 1, 1, 1, 0, exp2.ptr);
1129: }
1130: if (!coeff.len)
1131: { /* coeff missing in key, recalculate: coeff = q^-1 mod p */
1132: mpz_invert(this->coeff, this->q, this->p);
1133: }
1134: else
1135: {
1136: mpz_import(this->coeff, coeff.len, 1, 1, 1, 0, coeff.ptr);
1137: }
1138: this->k = (mpz_sizeinbase(this->n, 2) + 7) / BITS_PER_BYTE;
1139: if (check(this) != SUCCESS)
1140: {
1141: destroy(this);
1142: return NULL;
1143: }
1144: return &this->public;
1145: }