Annotation of embedaddon/strongswan/src/libstrongswan/plugins/gmp/gmp_rsa_private_key.c, revision 1.1
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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[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