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: }