summaryrefslogtreecommitdiffstats
path: root/security/nss/lib/freebl/rsa.c
diff options
context:
space:
mode:
Diffstat (limited to 'security/nss/lib/freebl/rsa.c')
-rw-r--r--security/nss/lib/freebl/rsa.c1625
1 files changed, 1625 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/rsa.c b/security/nss/lib/freebl/rsa.c
new file mode 100644
index 000000000..ff8c40ed9
--- /dev/null
+++ b/security/nss/lib/freebl/rsa.c
@@ -0,0 +1,1625 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/*
+ * RSA key generation, public key op, private key op.
+ */
+#ifdef FREEBL_NO_DEPEND
+#include "stubs.h"
+#endif
+
+#include "secerr.h"
+
+#include "prclist.h"
+#include "nssilock.h"
+#include "prinit.h"
+#include "blapi.h"
+#include "mpi.h"
+#include "mpprime.h"
+#include "mplogic.h"
+#include "secmpi.h"
+#include "secitem.h"
+#include "blapii.h"
+
+/*
+** Number of times to attempt to generate a prime (p or q) from a random
+** seed (the seed changes for each iteration).
+*/
+#define MAX_PRIME_GEN_ATTEMPTS 10
+/*
+** Number of times to attempt to generate a key. The primes p and q change
+** for each attempt.
+*/
+#define MAX_KEY_GEN_ATTEMPTS 10
+
+/* Blinding Parameters max cache size */
+#define RSA_BLINDING_PARAMS_MAX_CACHE_SIZE 20
+
+/* exponent should not be greater than modulus */
+#define BAD_RSA_KEY_SIZE(modLen, expLen) \
+ ((expLen) > (modLen) || (modLen) > RSA_MAX_MODULUS_BITS / 8 || \
+ (expLen) > RSA_MAX_EXPONENT_BITS / 8)
+
+struct blindingParamsStr;
+typedef struct blindingParamsStr blindingParams;
+
+struct blindingParamsStr {
+ blindingParams *next;
+ mp_int f, g; /* blinding parameter */
+ int counter; /* number of remaining uses of (f, g) */
+};
+
+/*
+** RSABlindingParamsStr
+**
+** For discussion of Paul Kocher's timing attack against an RSA private key
+** operation, see http://www.cryptography.com/timingattack/paper.html. The
+** countermeasure to this attack, known as blinding, is also discussed in
+** the Handbook of Applied Cryptography, 11.118-11.119.
+*/
+struct RSABlindingParamsStr {
+ /* Blinding-specific parameters */
+ PRCList link; /* link to list of structs */
+ SECItem modulus; /* list element "key" */
+ blindingParams *free, *bp; /* Blinding parameters queue */
+ blindingParams array[RSA_BLINDING_PARAMS_MAX_CACHE_SIZE];
+};
+typedef struct RSABlindingParamsStr RSABlindingParams;
+
+/*
+** RSABlindingParamsListStr
+**
+** List of key-specific blinding params. The arena holds the volatile pool
+** of memory for each entry and the list itself. The lock is for list
+** operations, in this case insertions and iterations, as well as control
+** of the counter for each set of blinding parameters.
+*/
+struct RSABlindingParamsListStr {
+ PZLock *lock; /* Lock for the list */
+ PRCondVar *cVar; /* Condidtion Variable */
+ int waitCount; /* Number of threads waiting on cVar */
+ PRCList head; /* Pointer to the list */
+};
+
+/*
+** The master blinding params list.
+*/
+static struct RSABlindingParamsListStr blindingParamsList = { 0 };
+
+/* Number of times to reuse (f, g). Suggested by Paul Kocher */
+#define RSA_BLINDING_PARAMS_MAX_REUSE 50
+
+/* Global, allows optional use of blinding. On by default. */
+/* Cannot be changed at the moment, due to thread-safety issues. */
+static PRBool nssRSAUseBlinding = PR_TRUE;
+
+static SECStatus
+rsa_build_from_primes(const mp_int *p, const mp_int *q,
+ mp_int *e, PRBool needPublicExponent,
+ mp_int *d, PRBool needPrivateExponent,
+ RSAPrivateKey *key, unsigned int keySizeInBits)
+{
+ mp_int n, phi;
+ mp_int psub1, qsub1, tmp;
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ MP_DIGITS(&n) = 0;
+ MP_DIGITS(&phi) = 0;
+ MP_DIGITS(&psub1) = 0;
+ MP_DIGITS(&qsub1) = 0;
+ MP_DIGITS(&tmp) = 0;
+ CHECK_MPI_OK(mp_init(&n));
+ CHECK_MPI_OK(mp_init(&phi));
+ CHECK_MPI_OK(mp_init(&psub1));
+ CHECK_MPI_OK(mp_init(&qsub1));
+ CHECK_MPI_OK(mp_init(&tmp));
+ /* p and q must be distinct. */
+ if (mp_cmp(p, q) == 0) {
+ PORT_SetError(SEC_ERROR_NEED_RANDOM);
+ rv = SECFailure;
+ goto cleanup;
+ }
+ /* 1. Compute n = p*q */
+ CHECK_MPI_OK(mp_mul(p, q, &n));
+ /* verify that the modulus has the desired number of bits */
+ if ((unsigned)mpl_significant_bits(&n) != keySizeInBits) {
+ PORT_SetError(SEC_ERROR_NEED_RANDOM);
+ rv = SECFailure;
+ goto cleanup;
+ }
+
+ /* at least one exponent must be given */
+ PORT_Assert(!(needPublicExponent && needPrivateExponent));
+
+ /* 2. Compute phi = (p-1)*(q-1) */
+ CHECK_MPI_OK(mp_sub_d(p, 1, &psub1));
+ CHECK_MPI_OK(mp_sub_d(q, 1, &qsub1));
+ if (needPublicExponent || needPrivateExponent) {
+ CHECK_MPI_OK(mp_lcm(&psub1, &qsub1, &phi));
+ /* 3. Compute d = e**-1 mod(phi) */
+ /* or e = d**-1 mod(phi) as necessary */
+ if (needPublicExponent) {
+ err = mp_invmod(d, &phi, e);
+ } else {
+ err = mp_invmod(e, &phi, d);
+ }
+ } else {
+ err = MP_OKAY;
+ }
+ /* Verify that phi(n) and e have no common divisors */
+ if (err != MP_OKAY) {
+ if (err == MP_UNDEF) {
+ PORT_SetError(SEC_ERROR_NEED_RANDOM);
+ err = MP_OKAY; /* to keep PORT_SetError from being called again */
+ rv = SECFailure;
+ }
+ goto cleanup;
+ }
+
+ /* 4. Compute exponent1 = d mod (p-1) */
+ CHECK_MPI_OK(mp_mod(d, &psub1, &tmp));
+ MPINT_TO_SECITEM(&tmp, &key->exponent1, key->arena);
+ /* 5. Compute exponent2 = d mod (q-1) */
+ CHECK_MPI_OK(mp_mod(d, &qsub1, &tmp));
+ MPINT_TO_SECITEM(&tmp, &key->exponent2, key->arena);
+ /* 6. Compute coefficient = q**-1 mod p */
+ CHECK_MPI_OK(mp_invmod(q, p, &tmp));
+ MPINT_TO_SECITEM(&tmp, &key->coefficient, key->arena);
+
+ /* copy our calculated results, overwrite what is there */
+ key->modulus.data = NULL;
+ MPINT_TO_SECITEM(&n, &key->modulus, key->arena);
+ key->privateExponent.data = NULL;
+ MPINT_TO_SECITEM(d, &key->privateExponent, key->arena);
+ key->publicExponent.data = NULL;
+ MPINT_TO_SECITEM(e, &key->publicExponent, key->arena);
+ key->prime1.data = NULL;
+ MPINT_TO_SECITEM(p, &key->prime1, key->arena);
+ key->prime2.data = NULL;
+ MPINT_TO_SECITEM(q, &key->prime2, key->arena);
+cleanup:
+ mp_clear(&n);
+ mp_clear(&phi);
+ mp_clear(&psub1);
+ mp_clear(&qsub1);
+ mp_clear(&tmp);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+static SECStatus
+generate_prime(mp_int *prime, int primeLen)
+{
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ unsigned long counter = 0;
+ int piter;
+ unsigned char *pb = NULL;
+ pb = PORT_Alloc(primeLen);
+ if (!pb) {
+ PORT_SetError(SEC_ERROR_NO_MEMORY);
+ goto cleanup;
+ }
+ for (piter = 0; piter < MAX_PRIME_GEN_ATTEMPTS; piter++) {
+ CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(pb, primeLen));
+ pb[0] |= 0xC0; /* set two high-order bits */
+ pb[primeLen - 1] |= 0x01; /* set low-order bit */
+ CHECK_MPI_OK(mp_read_unsigned_octets(prime, pb, primeLen));
+ err = mpp_make_prime(prime, primeLen * 8, PR_FALSE, &counter);
+ if (err != MP_NO)
+ goto cleanup;
+ /* keep going while err == MP_NO */
+ }
+cleanup:
+ if (pb)
+ PORT_ZFree(pb, primeLen);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+/*
+ * make sure the key components meet fips186 requirements.
+ */
+static PRBool
+rsa_fips186_verify(mp_int *p, mp_int *q, mp_int *d, int keySizeInBits)
+{
+ mp_int pq_diff;
+ mp_err err = MP_OKAY;
+ PRBool ret = PR_FALSE;
+
+ if (keySizeInBits < 250) {
+ /* not a valid FIPS length, no point in our other tests */
+ /* if you are here, and in FIPS mode, you are outside the security
+ * policy */
+ return PR_TRUE;
+ }
+
+ /* p & q are already known to be greater then sqrt(2)*2^(keySize/2-1) */
+ /* we also know that gcd(p-1,e) = 1 and gcd(q-1,e) = 1 because the
+ * mp_invmod() function will fail. */
+ /* now check p-q > 2^(keysize/2-100) */
+ MP_DIGITS(&pq_diff) = 0;
+ CHECK_MPI_OK(mp_init(&pq_diff));
+ /* NSS always has p > q, so we know pq_diff is positive */
+ CHECK_MPI_OK(mp_sub(p, q, &pq_diff));
+ if ((unsigned)mpl_significant_bits(&pq_diff) < (keySizeInBits / 2 - 100)) {
+ goto cleanup;
+ }
+ /* now verify d is large enough*/
+ if ((unsigned)mpl_significant_bits(d) < (keySizeInBits / 2)) {
+ goto cleanup;
+ }
+ ret = PR_TRUE;
+
+cleanup:
+ mp_clear(&pq_diff);
+ return ret;
+}
+
+/*
+** Generate and return a new RSA public and private key.
+** Both keys are encoded in a single RSAPrivateKey structure.
+** "cx" is the random number generator context
+** "keySizeInBits" is the size of the key to be generated, in bits.
+** 512, 1024, etc.
+** "publicExponent" when not NULL is a pointer to some data that
+** represents the public exponent to use. The data is a byte
+** encoded integer, in "big endian" order.
+*/
+RSAPrivateKey *
+RSA_NewKey(int keySizeInBits, SECItem *publicExponent)
+{
+ unsigned int primeLen;
+ mp_int p, q, e, d;
+ int kiter;
+ int max_attempts;
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ int prerr = 0;
+ RSAPrivateKey *key = NULL;
+ PLArenaPool *arena = NULL;
+ /* Require key size to be a multiple of 16 bits. */
+ if (!publicExponent || keySizeInBits % 16 != 0 ||
+ BAD_RSA_KEY_SIZE((unsigned int)keySizeInBits / 8, publicExponent->len)) {
+ PORT_SetError(SEC_ERROR_INVALID_ARGS);
+ return NULL;
+ }
+ /* 1. Allocate arena & key */
+ arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
+ if (!arena) {
+ PORT_SetError(SEC_ERROR_NO_MEMORY);
+ return NULL;
+ }
+ key = PORT_ArenaZNew(arena, RSAPrivateKey);
+ if (!key) {
+ PORT_SetError(SEC_ERROR_NO_MEMORY);
+ PORT_FreeArena(arena, PR_TRUE);
+ return NULL;
+ }
+ key->arena = arena;
+ /* length of primes p and q (in bytes) */
+ primeLen = keySizeInBits / (2 * PR_BITS_PER_BYTE);
+ MP_DIGITS(&p) = 0;
+ MP_DIGITS(&q) = 0;
+ MP_DIGITS(&e) = 0;
+ MP_DIGITS(&d) = 0;
+ CHECK_MPI_OK(mp_init(&p));
+ CHECK_MPI_OK(mp_init(&q));
+ CHECK_MPI_OK(mp_init(&e));
+ CHECK_MPI_OK(mp_init(&d));
+ /* 2. Set the version number (PKCS1 v1.5 says it should be zero) */
+ SECITEM_AllocItem(arena, &key->version, 1);
+ key->version.data[0] = 0;
+ /* 3. Set the public exponent */
+ SECITEM_TO_MPINT(*publicExponent, &e);
+ kiter = 0;
+ max_attempts = 5 * (keySizeInBits / 2); /* FIPS 186-4 B.3.3 steps 4.7 and 5.8 */
+ do {
+ prerr = 0;
+ PORT_SetError(0);
+ CHECK_SEC_OK(generate_prime(&p, primeLen));
+ CHECK_SEC_OK(generate_prime(&q, primeLen));
+ /* Assure p > q */
+ /* NOTE: PKCS #1 does not require p > q, and NSS doesn't use any
+ * implementation optimization that requires p > q. We can remove
+ * this code in the future.
+ */
+ if (mp_cmp(&p, &q) < 0)
+ mp_exch(&p, &q);
+ /* Attempt to use these primes to generate a key */
+ rv = rsa_build_from_primes(&p, &q,
+ &e, PR_FALSE, /* needPublicExponent=false */
+ &d, PR_TRUE, /* needPrivateExponent=true */
+ key, keySizeInBits);
+ if (rv == SECSuccess) {
+ if (rsa_fips186_verify(&p, &q, &d, keySizeInBits)) {
+ break;
+ }
+ prerr = SEC_ERROR_NEED_RANDOM; /* retry with different values */
+ } else {
+ prerr = PORT_GetError();
+ }
+ kiter++;
+ /* loop until have primes */
+ } while (prerr == SEC_ERROR_NEED_RANDOM && kiter < max_attempts);
+ if (prerr)
+ goto cleanup;
+cleanup:
+ mp_clear(&p);
+ mp_clear(&q);
+ mp_clear(&e);
+ mp_clear(&d);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ if (rv && arena) {
+ PORT_FreeArena(arena, PR_TRUE);
+ key = NULL;
+ }
+ return key;
+}
+
+mp_err
+rsa_is_prime(mp_int *p)
+{
+ int res;
+
+ /* run a Fermat test */
+ res = mpp_fermat(p, 2);
+ if (res != MP_OKAY) {
+ return res;
+ }
+
+ /* If that passed, run some Miller-Rabin tests */
+ res = mpp_pprime(p, 2);
+ return res;
+}
+
+/*
+ * Factorize a RSA modulus n into p and q by using the exponents e and d.
+ *
+ * In: e, d, n
+ * Out: p, q
+ *
+ * See Handbook of Applied Cryptography, 8.2.2(i).
+ *
+ * The algorithm is probabilistic, it is run 64 times and each run has a 50%
+ * chance of succeeding with a runtime of O(log(e*d)).
+ *
+ * The returned p might be smaller than q.
+ */
+static mp_err
+rsa_factorize_n_from_exponents(mp_int *e, mp_int *d, mp_int *p, mp_int *q,
+ mp_int *n)
+{
+ /* lambda is the private modulus: e*d = 1 mod lambda */
+ /* so: e*d - 1 = k*lambda = t*2^s where t is odd */
+ mp_int klambda;
+ mp_int t, onetwentyeight;
+ unsigned long s = 0;
+ unsigned long i;
+
+ /* cand = a^(t * 2^i) mod n, next_cand = a^(t * 2^(i+1)) mod n */
+ mp_int a;
+ mp_int cand;
+ mp_int next_cand;
+
+ mp_int n_minus_one;
+ mp_err err = MP_OKAY;
+
+ MP_DIGITS(&klambda) = 0;
+ MP_DIGITS(&t) = 0;
+ MP_DIGITS(&a) = 0;
+ MP_DIGITS(&cand) = 0;
+ MP_DIGITS(&n_minus_one) = 0;
+ MP_DIGITS(&next_cand) = 0;
+ MP_DIGITS(&onetwentyeight) = 0;
+ CHECK_MPI_OK(mp_init(&klambda));
+ CHECK_MPI_OK(mp_init(&t));
+ CHECK_MPI_OK(mp_init(&a));
+ CHECK_MPI_OK(mp_init(&cand));
+ CHECK_MPI_OK(mp_init(&n_minus_one));
+ CHECK_MPI_OK(mp_init(&next_cand));
+ CHECK_MPI_OK(mp_init(&onetwentyeight));
+
+ mp_set_int(&onetwentyeight, 128);
+
+ /* calculate k*lambda = e*d - 1 */
+ CHECK_MPI_OK(mp_mul(e, d, &klambda));
+ CHECK_MPI_OK(mp_sub_d(&klambda, 1, &klambda));
+
+ /* factorize klambda into t*2^s */
+ CHECK_MPI_OK(mp_copy(&klambda, &t));
+ while (mpp_divis_d(&t, 2) == MP_YES) {
+ CHECK_MPI_OK(mp_div_2(&t, &t));
+ s += 1;
+ }
+
+ /* precompute n_minus_one = n - 1 */
+ CHECK_MPI_OK(mp_copy(n, &n_minus_one));
+ CHECK_MPI_OK(mp_sub_d(&n_minus_one, 1, &n_minus_one));
+
+ /* pick random bases a, each one has a 50% leading to a factorization */
+ CHECK_MPI_OK(mp_set_int(&a, 2));
+ /* The following is equivalent to for (a=2, a <= 128, a+=2) */
+ while (mp_cmp(&a, &onetwentyeight) <= 0) {
+ /* compute the base cand = a^(t * 2^0) [i = 0] */
+ CHECK_MPI_OK(mp_exptmod(&a, &t, n, &cand));
+
+ for (i = 0; i < s; i++) {
+ /* condition 1: skip the base if we hit a trivial factor of n */
+ if (mp_cmp(&cand, &n_minus_one) == 0 || mp_cmp_d(&cand, 1) == 0) {
+ break;
+ }
+
+ /* increase i in a^(t * 2^i) by squaring the number */
+ CHECK_MPI_OK(mp_exptmod_d(&cand, 2, n, &next_cand));
+
+ /* condition 2: a^(t * 2^(i+1)) = 1 mod n */
+ if (mp_cmp_d(&next_cand, 1) == 0) {
+ /* conditions verified, gcd(a^(t * 2^i) - 1, n) is a factor */
+ CHECK_MPI_OK(mp_sub_d(&cand, 1, &cand));
+ CHECK_MPI_OK(mp_gcd(&cand, n, p));
+ if (mp_cmp_d(p, 1) == 0) {
+ CHECK_MPI_OK(mp_add_d(&cand, 1, &cand));
+ break;
+ }
+ CHECK_MPI_OK(mp_div(n, p, q, NULL));
+ goto cleanup;
+ }
+ CHECK_MPI_OK(mp_copy(&next_cand, &cand));
+ }
+
+ CHECK_MPI_OK(mp_add_d(&a, 2, &a));
+ }
+
+ /* if we reach here it's likely (2^64 - 1 / 2^64) that d is wrong */
+ err = MP_RANGE;
+
+cleanup:
+ mp_clear(&klambda);
+ mp_clear(&t);
+ mp_clear(&a);
+ mp_clear(&cand);
+ mp_clear(&n_minus_one);
+ mp_clear(&next_cand);
+ mp_clear(&onetwentyeight);
+ return err;
+}
+
+/*
+ * Try to find the two primes based on 2 exponents plus a prime.
+ *
+ * In: e, d and p.
+ * Out: p,q.
+ *
+ * Step 1, Since d = e**-1 mod phi, we know that d*e == 1 mod phi, or
+ * d*e = 1+k*phi, or d*e-1 = k*phi. since d is less than phi and e is
+ * usually less than d, then k must be an integer between e-1 and 1
+ * (probably on the order of e).
+ * Step 1a, We can divide k*phi by prime-1 and get k*(q-1). This will reduce
+ * the size of our division through the rest of the loop.
+ * Step 2, Loop through the values k=e-1 to 1 looking for k. k should be on
+ * the order or e, and e is typically small. This may take a while for
+ * a large random e. We are looking for a k that divides kphi
+ * evenly. Once we find a k that divides kphi evenly, we assume it
+ * is the true k. It's possible this k is not the 'true' k but has
+ * swapped factors of p-1 and/or q-1. Because of this, we
+ * tentatively continue Steps 3-6 inside this loop, and may return looking
+ * for another k on failure.
+ * Step 3, Calculate our tentative phi=kphi/k. Note: real phi is (p-1)*(q-1).
+ * Step 4a, kphi is k*(q-1), so phi is our tenative q-1. q = phi+1.
+ * If k is correct, q should be the right length and prime.
+ * Step 4b, It's possible q-1 and k could have swapped factors. We now have a
+ * possible solution that meets our criteria. It may not be the only
+ * solution, however, so we keep looking. If we find more than one,
+ * we will fail since we cannot determine which is the correct
+ * solution, and returning the wrong modulus will compromise both
+ * moduli. If no other solution is found, we return the unique solution.
+ *
+ * This will return p & q. q may be larger than p in the case that p was given
+ * and it was the smaller prime.
+ */
+static mp_err
+rsa_get_prime_from_exponents(mp_int *e, mp_int *d, mp_int *p, mp_int *q,
+ mp_int *n, unsigned int keySizeInBits)
+{
+ mp_int kphi; /* k*phi */
+ mp_int k; /* current guess at 'k' */
+ mp_int phi; /* (p-1)(q-1) */
+ mp_int r; /* remainder */
+ mp_int tmp; /* p-1 if p is given */
+ mp_err err = MP_OKAY;
+ unsigned int order_k;
+
+ MP_DIGITS(&kphi) = 0;
+ MP_DIGITS(&phi) = 0;
+ MP_DIGITS(&k) = 0;
+ MP_DIGITS(&r) = 0;
+ MP_DIGITS(&tmp) = 0;
+ CHECK_MPI_OK(mp_init(&kphi));
+ CHECK_MPI_OK(mp_init(&phi));
+ CHECK_MPI_OK(mp_init(&k));
+ CHECK_MPI_OK(mp_init(&r));
+ CHECK_MPI_OK(mp_init(&tmp));
+
+ /* our algorithm looks for a factor k whose maximum size is dependent
+ * on the size of our smallest exponent, which had better be the public
+ * exponent (if it's the private, the key is vulnerable to a brute force
+ * attack).
+ *
+ * since our factor search is linear, we need to limit the maximum
+ * size of the public key. this should not be a problem normally, since
+ * public keys are usually small.
+ *
+ * if we want to handle larger public key sizes, we should have
+ * a version which tries to 'completely' factor k*phi (where completely
+ * means 'factor into primes, or composites with which are products of
+ * large primes). Once we have all the factors, we can sort them out and
+ * try different combinations to form our phi. The risk is if (p-1)/2,
+ * (q-1)/2, and k are all large primes. In any case if the public key
+ * is small (order of 20 some bits), then a linear search for k is
+ * manageable.
+ */
+ if (mpl_significant_bits(e) > 23) {
+ err = MP_RANGE;
+ goto cleanup;
+ }
+
+ /* calculate k*phi = e*d - 1 */
+ CHECK_MPI_OK(mp_mul(e, d, &kphi));
+ CHECK_MPI_OK(mp_sub_d(&kphi, 1, &kphi));
+
+ /* kphi is (e*d)-1, which is the same as k*(p-1)(q-1)
+ * d < (p-1)(q-1), therefor k must be less than e-1
+ * We can narrow down k even more, though. Since p and q are odd and both
+ * have their high bit set, then we know that phi must be on order of
+ * keySizeBits.
+ */
+ order_k = (unsigned)mpl_significant_bits(&kphi) - keySizeInBits;
+
+ /* for (k=kinit; order(k) >= order_k; k--) { */
+ /* k=kinit: k can't be bigger than kphi/2^(keySizeInBits -1) */
+ CHECK_MPI_OK(mp_2expt(&k, keySizeInBits - 1));
+ CHECK_MPI_OK(mp_div(&kphi, &k, &k, NULL));
+ if (mp_cmp(&k, e) >= 0) {
+ /* also can't be bigger then e-1 */
+ CHECK_MPI_OK(mp_sub_d(e, 1, &k));
+ }
+
+ /* calculate our temp value */
+ /* This saves recalculating this value when the k guess is wrong, which
+ * is reasonably frequent. */
+ /* tmp = p-1 (used to calculate q-1= phi/tmp) */
+ CHECK_MPI_OK(mp_sub_d(p, 1, &tmp));
+ CHECK_MPI_OK(mp_div(&kphi, &tmp, &kphi, &r));
+ if (mp_cmp_z(&r) != 0) {
+ /* p-1 doesn't divide kphi, some parameter wasn't correct */
+ err = MP_RANGE;
+ goto cleanup;
+ }
+ mp_zero(q);
+ /* kphi is now k*(q-1) */
+
+ /* rest of the for loop */
+ for (; (err == MP_OKAY) && (mpl_significant_bits(&k) >= order_k);
+ err = mp_sub_d(&k, 1, &k)) {
+ CHECK_MPI_OK(err);
+ /* looking for k as a factor of kphi */
+ CHECK_MPI_OK(mp_div(&kphi, &k, &phi, &r));
+ if (mp_cmp_z(&r) != 0) {
+ /* not a factor, try the next one */
+ continue;
+ }
+ /* we have a possible phi, see if it works */
+ if ((unsigned)mpl_significant_bits(&phi) != keySizeInBits / 2) {
+ /* phi is not the right size */
+ continue;
+ }
+ /* phi should be divisible by 2, since
+ * q is odd and phi=(q-1). */
+ if (mpp_divis_d(&phi, 2) == MP_NO) {
+ /* phi is not divisible by 4 */
+ continue;
+ }
+ /* we now have a candidate for the second prime */
+ CHECK_MPI_OK(mp_add_d(&phi, 1, &tmp));
+
+ /* check to make sure it is prime */
+ err = rsa_is_prime(&tmp);
+ if (err != MP_OKAY) {
+ if (err == MP_NO) {
+ /* No, then we still have the wrong phi */
+ continue;
+ }
+ goto cleanup;
+ }
+ /*
+ * It is possible that we have the wrong phi if
+ * k_guess*(q_guess-1) = k*(q-1) (k and q-1 have swapped factors).
+ * since our q_quess is prime, however. We have found a valid
+ * rsa key because:
+ * q is the correct order of magnitude.
+ * phi = (p-1)(q-1) where p and q are both primes.
+ * e*d mod phi = 1.
+ * There is no way to know from the info given if this is the
+ * original key. We never want to return the wrong key because if
+ * two moduli with the same factor is known, then euclid's gcd
+ * algorithm can be used to find that factor. Even though the
+ * caller didn't pass the original modulus, it doesn't mean the
+ * modulus wasn't known or isn't available somewhere. So to be safe
+ * if we can't be sure we have the right q, we don't return any.
+ *
+ * So to make sure we continue looking for other valid q's. If none
+ * are found, then we can safely return this one, otherwise we just
+ * fail */
+ if (mp_cmp_z(q) != 0) {
+ /* this is the second valid q, don't return either,
+ * just fail */
+ err = MP_RANGE;
+ break;
+ }
+ /* we only have one q so far, save it and if no others are found,
+ * it's safe to return it */
+ CHECK_MPI_OK(mp_copy(&tmp, q));
+ continue;
+ }
+ if ((unsigned)mpl_significant_bits(&k) < order_k) {
+ if (mp_cmp_z(q) == 0) {
+ /* If we get here, something was wrong with the parameters we
+ * were given */
+ err = MP_RANGE;
+ }
+ }
+cleanup:
+ mp_clear(&kphi);
+ mp_clear(&phi);
+ mp_clear(&k);
+ mp_clear(&r);
+ mp_clear(&tmp);
+ return err;
+}
+
+/*
+ * take a private key with only a few elements and fill out the missing pieces.
+ *
+ * All the entries will be overwritten with data allocated out of the arena
+ * If no arena is supplied, one will be created.
+ *
+ * The following fields must be supplied in order for this function
+ * to succeed:
+ * one of either publicExponent or privateExponent
+ * two more of the following 5 parameters.
+ * modulus (n)
+ * prime1 (p)
+ * prime2 (q)
+ * publicExponent (e)
+ * privateExponent (d)
+ *
+ * NOTE: if only the publicExponent, privateExponent, and one prime is given,
+ * then there may be more than one RSA key that matches that combination.
+ *
+ * All parameters will be replaced in the key structure with new parameters
+ * Allocated out of the arena. There is no attempt to free the old structures.
+ * Prime1 will always be greater than prime2 (even if the caller supplies the
+ * smaller prime as prime1 or the larger prime as prime2). The parameters are
+ * not overwritten on failure.
+ *
+ * How it works:
+ * We can generate all the parameters from one of the exponents, plus the
+ * two primes. (rsa_build_key_from_primes)
+ * If we are given one of the exponents and both primes, we are done.
+ * If we are given one of the exponents, the modulus and one prime, we
+ * caclulate the second prime by dividing the modulus by the given
+ * prime, giving us an exponent and 2 primes.
+ * If we are given 2 exponents and one of the primes we calculate
+ * k*phi = d*e-1, where k is an integer less than d which
+ * divides d*e-1. We find factor k so we can isolate phi.
+ * phi = (p-1)(q-1)
+ * We can use phi to find the other prime as follows:
+ * q = (phi/(p-1)) + 1. We now have 2 primes and an exponent.
+ * (NOTE: if more then one prime meets this condition, the operation
+ * will fail. See comments elsewhere in this file about this).
+ * (rsa_get_prime_from_exponents)
+ * If we are given 2 exponents and the modulus we factor the modulus to
+ * get the 2 missing primes (rsa_factorize_n_from_exponents)
+ *
+ */
+SECStatus
+RSA_PopulatePrivateKey(RSAPrivateKey *key)
+{
+ PLArenaPool *arena = NULL;
+ PRBool needPublicExponent = PR_TRUE;
+ PRBool needPrivateExponent = PR_TRUE;
+ PRBool hasModulus = PR_FALSE;
+ unsigned int keySizeInBits = 0;
+ int prime_count = 0;
+ /* standard RSA nominclature */
+ mp_int p, q, e, d, n;
+ /* remainder */
+ mp_int r;
+ mp_err err = 0;
+ SECStatus rv = SECFailure;
+
+ MP_DIGITS(&p) = 0;
+ MP_DIGITS(&q) = 0;
+ MP_DIGITS(&e) = 0;
+ MP_DIGITS(&d) = 0;
+ MP_DIGITS(&n) = 0;
+ MP_DIGITS(&r) = 0;
+ CHECK_MPI_OK(mp_init(&p));
+ CHECK_MPI_OK(mp_init(&q));
+ CHECK_MPI_OK(mp_init(&e));
+ CHECK_MPI_OK(mp_init(&d));
+ CHECK_MPI_OK(mp_init(&n));
+ CHECK_MPI_OK(mp_init(&r));
+
+ /* if the key didn't already have an arena, create one. */
+ if (key->arena == NULL) {
+ arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
+ if (!arena) {
+ goto cleanup;
+ }
+ key->arena = arena;
+ }
+
+ /* load up the known exponents */
+ if (key->publicExponent.data) {
+ SECITEM_TO_MPINT(key->publicExponent, &e);
+ needPublicExponent = PR_FALSE;
+ }
+ if (key->privateExponent.data) {
+ SECITEM_TO_MPINT(key->privateExponent, &d);
+ needPrivateExponent = PR_FALSE;
+ }
+ if (needPrivateExponent && needPublicExponent) {
+ /* Not enough information, we need at least one exponent */
+ err = MP_BADARG;
+ goto cleanup;
+ }
+
+ /* load up the known primes. If only one prime is given, it will be
+ * assigned 'p'. Once we have both primes, well make sure p is the larger.
+ * The value prime_count tells us howe many we have acquired.
+ */
+ if (key->prime1.data) {
+ int primeLen = key->prime1.len;
+ if (key->prime1.data[0] == 0) {
+ primeLen--;
+ }
+ keySizeInBits = primeLen * 2 * PR_BITS_PER_BYTE;
+ SECITEM_TO_MPINT(key->prime1, &p);
+ prime_count++;
+ }
+ if (key->prime2.data) {
+ int primeLen = key->prime2.len;
+ if (key->prime2.data[0] == 0) {
+ primeLen--;
+ }
+ keySizeInBits = primeLen * 2 * PR_BITS_PER_BYTE;
+ SECITEM_TO_MPINT(key->prime2, prime_count ? &q : &p);
+ prime_count++;
+ }
+ /* load up the modulus */
+ if (key->modulus.data) {
+ int modLen = key->modulus.len;
+ if (key->modulus.data[0] == 0) {
+ modLen--;
+ }
+ keySizeInBits = modLen * PR_BITS_PER_BYTE;
+ SECITEM_TO_MPINT(key->modulus, &n);
+ hasModulus = PR_TRUE;
+ }
+ /* if we have the modulus and one prime, calculate the second. */
+ if ((prime_count == 1) && (hasModulus)) {
+ if (mp_div(&n, &p, &q, &r) != MP_OKAY || mp_cmp_z(&r) != 0) {
+ /* p is not a factor or n, fail */
+ err = MP_BADARG;
+ goto cleanup;
+ }
+ prime_count++;
+ }
+
+ /* If we didn't have enough primes try to calculate the primes from
+ * the exponents */
+ if (prime_count < 2) {
+ /* if we don't have at least 2 primes at this point, then we need both
+ * exponents and one prime or a modulus*/
+ if (!needPublicExponent && !needPrivateExponent &&
+ (prime_count > 0)) {
+ CHECK_MPI_OK(rsa_get_prime_from_exponents(&e, &d, &p, &q, &n,
+ keySizeInBits));
+ } else if (!needPublicExponent && !needPrivateExponent && hasModulus) {
+ CHECK_MPI_OK(rsa_factorize_n_from_exponents(&e, &d, &p, &q, &n));
+ } else {
+ /* not enough given parameters to get both primes */
+ err = MP_BADARG;
+ goto cleanup;
+ }
+ }
+
+ /* Assure p > q */
+ /* NOTE: PKCS #1 does not require p > q, and NSS doesn't use any
+ * implementation optimization that requires p > q. We can remove
+ * this code in the future.
+ */
+ if (mp_cmp(&p, &q) < 0)
+ mp_exch(&p, &q);
+
+ /* we now have our 2 primes and at least one exponent, we can fill
+ * in the key */
+ rv = rsa_build_from_primes(&p, &q,
+ &e, needPublicExponent,
+ &d, needPrivateExponent,
+ key, keySizeInBits);
+cleanup:
+ mp_clear(&p);
+ mp_clear(&q);
+ mp_clear(&e);
+ mp_clear(&d);
+ mp_clear(&n);
+ mp_clear(&r);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ if (rv && arena) {
+ PORT_FreeArena(arena, PR_TRUE);
+ key->arena = NULL;
+ }
+ return rv;
+}
+
+static unsigned int
+rsa_modulusLen(SECItem *modulus)
+{
+ unsigned char byteZero = modulus->data[0];
+ unsigned int modLen = modulus->len - !byteZero;
+ return modLen;
+}
+
+/*
+** Perform a raw public-key operation
+** Length of input and output buffers are equal to key's modulus len.
+*/
+SECStatus
+RSA_PublicKeyOp(RSAPublicKey *key,
+ unsigned char *output,
+ const unsigned char *input)
+{
+ unsigned int modLen, expLen, offset;
+ mp_int n, e, m, c;
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ if (!key || !output || !input) {
+ PORT_SetError(SEC_ERROR_INVALID_ARGS);
+ return SECFailure;
+ }
+ MP_DIGITS(&n) = 0;
+ MP_DIGITS(&e) = 0;
+ MP_DIGITS(&m) = 0;
+ MP_DIGITS(&c) = 0;
+ CHECK_MPI_OK(mp_init(&n));
+ CHECK_MPI_OK(mp_init(&e));
+ CHECK_MPI_OK(mp_init(&m));
+ CHECK_MPI_OK(mp_init(&c));
+ modLen = rsa_modulusLen(&key->modulus);
+ expLen = rsa_modulusLen(&key->publicExponent);
+ /* 1. Obtain public key (n, e) */
+ if (BAD_RSA_KEY_SIZE(modLen, expLen)) {
+ PORT_SetError(SEC_ERROR_INVALID_KEY);
+ rv = SECFailure;
+ goto cleanup;
+ }
+ SECITEM_TO_MPINT(key->modulus, &n);
+ SECITEM_TO_MPINT(key->publicExponent, &e);
+ if (e.used > n.used) {
+ /* exponent should not be greater than modulus */
+ PORT_SetError(SEC_ERROR_INVALID_KEY);
+ rv = SECFailure;
+ goto cleanup;
+ }
+ /* 2. check input out of range (needs to be in range [0..n-1]) */
+ offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
+ if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
+ PORT_SetError(SEC_ERROR_INPUT_LEN);
+ rv = SECFailure;
+ goto cleanup;
+ }
+ /* 2 bis. Represent message as integer in range [0..n-1] */
+ CHECK_MPI_OK(mp_read_unsigned_octets(&m, input, modLen));
+/* 3. Compute c = m**e mod n */
+#ifdef USE_MPI_EXPT_D
+ /* XXX see which is faster */
+ if (MP_USED(&e) == 1) {
+ CHECK_MPI_OK(mp_exptmod_d(&m, MP_DIGIT(&e, 0), &n, &c));
+ } else
+#endif
+ CHECK_MPI_OK(mp_exptmod(&m, &e, &n, &c));
+ /* 4. result c is ciphertext */
+ err = mp_to_fixlen_octets(&c, output, modLen);
+ if (err >= 0)
+ err = MP_OKAY;
+cleanup:
+ mp_clear(&n);
+ mp_clear(&e);
+ mp_clear(&m);
+ mp_clear(&c);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+/*
+** RSA Private key operation (no CRT).
+*/
+static SECStatus
+rsa_PrivateKeyOpNoCRT(RSAPrivateKey *key, mp_int *m, mp_int *c, mp_int *n,
+ unsigned int modLen)
+{
+ mp_int d;
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ MP_DIGITS(&d) = 0;
+ CHECK_MPI_OK(mp_init(&d));
+ SECITEM_TO_MPINT(key->privateExponent, &d);
+ /* 1. m = c**d mod n */
+ CHECK_MPI_OK(mp_exptmod(c, &d, n, m));
+cleanup:
+ mp_clear(&d);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+/*
+** RSA Private key operation using CRT.
+*/
+static SECStatus
+rsa_PrivateKeyOpCRTNoCheck(RSAPrivateKey *key, mp_int *m, mp_int *c)
+{
+ mp_int p, q, d_p, d_q, qInv;
+ mp_int m1, m2, h, ctmp;
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ MP_DIGITS(&p) = 0;
+ MP_DIGITS(&q) = 0;
+ MP_DIGITS(&d_p) = 0;
+ MP_DIGITS(&d_q) = 0;
+ MP_DIGITS(&qInv) = 0;
+ MP_DIGITS(&m1) = 0;
+ MP_DIGITS(&m2) = 0;
+ MP_DIGITS(&h) = 0;
+ MP_DIGITS(&ctmp) = 0;
+ CHECK_MPI_OK(mp_init(&p));
+ CHECK_MPI_OK(mp_init(&q));
+ CHECK_MPI_OK(mp_init(&d_p));
+ CHECK_MPI_OK(mp_init(&d_q));
+ CHECK_MPI_OK(mp_init(&qInv));
+ CHECK_MPI_OK(mp_init(&m1));
+ CHECK_MPI_OK(mp_init(&m2));
+ CHECK_MPI_OK(mp_init(&h));
+ CHECK_MPI_OK(mp_init(&ctmp));
+ /* copy private key parameters into mp integers */
+ SECITEM_TO_MPINT(key->prime1, &p); /* p */
+ SECITEM_TO_MPINT(key->prime2, &q); /* q */
+ SECITEM_TO_MPINT(key->exponent1, &d_p); /* d_p = d mod (p-1) */
+ SECITEM_TO_MPINT(key->exponent2, &d_q); /* d_q = d mod (q-1) */
+ SECITEM_TO_MPINT(key->coefficient, &qInv); /* qInv = q**-1 mod p */
+ /* 1. m1 = c**d_p mod p */
+ CHECK_MPI_OK(mp_mod(c, &p, &ctmp));
+ CHECK_MPI_OK(mp_exptmod(&ctmp, &d_p, &p, &m1));
+ /* 2. m2 = c**d_q mod q */
+ CHECK_MPI_OK(mp_mod(c, &q, &ctmp));
+ CHECK_MPI_OK(mp_exptmod(&ctmp, &d_q, &q, &m2));
+ /* 3. h = (m1 - m2) * qInv mod p */
+ CHECK_MPI_OK(mp_submod(&m1, &m2, &p, &h));
+ CHECK_MPI_OK(mp_mulmod(&h, &qInv, &p, &h));
+ /* 4. m = m2 + h * q */
+ CHECK_MPI_OK(mp_mul(&h, &q, m));
+ CHECK_MPI_OK(mp_add(m, &m2, m));
+cleanup:
+ mp_clear(&p);
+ mp_clear(&q);
+ mp_clear(&d_p);
+ mp_clear(&d_q);
+ mp_clear(&qInv);
+ mp_clear(&m1);
+ mp_clear(&m2);
+ mp_clear(&h);
+ mp_clear(&ctmp);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+/*
+** An attack against RSA CRT was described by Boneh, DeMillo, and Lipton in:
+** "On the Importance of Eliminating Errors in Cryptographic Computations",
+** http://theory.stanford.edu/~dabo/papers/faults.ps.gz
+**
+** As a defense against the attack, carry out the private key operation,
+** followed up with a public key operation to invert the result.
+** Verify that result against the input.
+*/
+static SECStatus
+rsa_PrivateKeyOpCRTCheckedPubKey(RSAPrivateKey *key, mp_int *m, mp_int *c)
+{
+ mp_int n, e, v;
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ MP_DIGITS(&n) = 0;
+ MP_DIGITS(&e) = 0;
+ MP_DIGITS(&v) = 0;
+ CHECK_MPI_OK(mp_init(&n));
+ CHECK_MPI_OK(mp_init(&e));
+ CHECK_MPI_OK(mp_init(&v));
+ CHECK_SEC_OK(rsa_PrivateKeyOpCRTNoCheck(key, m, c));
+ SECITEM_TO_MPINT(key->modulus, &n);
+ SECITEM_TO_MPINT(key->publicExponent, &e);
+ /* Perform a public key operation v = m ** e mod n */
+ CHECK_MPI_OK(mp_exptmod(m, &e, &n, &v));
+ if (mp_cmp(&v, c) != 0) {
+ rv = SECFailure;
+ }
+cleanup:
+ mp_clear(&n);
+ mp_clear(&e);
+ mp_clear(&v);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+static PRCallOnceType coBPInit = { 0, 0, 0 };
+static PRStatus
+init_blinding_params_list(void)
+{
+ blindingParamsList.lock = PZ_NewLock(nssILockOther);
+ if (!blindingParamsList.lock) {
+ PORT_SetError(SEC_ERROR_NO_MEMORY);
+ return PR_FAILURE;
+ }
+ blindingParamsList.cVar = PR_NewCondVar(blindingParamsList.lock);
+ if (!blindingParamsList.cVar) {
+ PORT_SetError(SEC_ERROR_NO_MEMORY);
+ return PR_FAILURE;
+ }
+ blindingParamsList.waitCount = 0;
+ PR_INIT_CLIST(&blindingParamsList.head);
+ return PR_SUCCESS;
+}
+
+static SECStatus
+generate_blinding_params(RSAPrivateKey *key, mp_int *f, mp_int *g, mp_int *n,
+ unsigned int modLen)
+{
+ SECStatus rv = SECSuccess;
+ mp_int e, k;
+ mp_err err = MP_OKAY;
+ unsigned char *kb = NULL;
+
+ MP_DIGITS(&e) = 0;
+ MP_DIGITS(&k) = 0;
+ CHECK_MPI_OK(mp_init(&e));
+ CHECK_MPI_OK(mp_init(&k));
+ SECITEM_TO_MPINT(key->publicExponent, &e);
+ /* generate random k < n */
+ kb = PORT_Alloc(modLen);
+ if (!kb) {
+ PORT_SetError(SEC_ERROR_NO_MEMORY);
+ goto cleanup;
+ }
+ CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(kb, modLen));
+ CHECK_MPI_OK(mp_read_unsigned_octets(&k, kb, modLen));
+ /* k < n */
+ CHECK_MPI_OK(mp_mod(&k, n, &k));
+ /* f = k**e mod n */
+ CHECK_MPI_OK(mp_exptmod(&k, &e, n, f));
+ /* g = k**-1 mod n */
+ CHECK_MPI_OK(mp_invmod(&k, n, g));
+cleanup:
+ if (kb)
+ PORT_ZFree(kb, modLen);
+ mp_clear(&k);
+ mp_clear(&e);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+static SECStatus
+init_blinding_params(RSABlindingParams *rsabp, RSAPrivateKey *key,
+ mp_int *n, unsigned int modLen)
+{
+ blindingParams *bp = rsabp->array;
+ int i = 0;
+
+ /* Initialize the list pointer for the element */
+ PR_INIT_CLIST(&rsabp->link);
+ for (i = 0; i < RSA_BLINDING_PARAMS_MAX_CACHE_SIZE; ++i, ++bp) {
+ bp->next = bp + 1;
+ MP_DIGITS(&bp->f) = 0;
+ MP_DIGITS(&bp->g) = 0;
+ bp->counter = 0;
+ }
+ /* The last bp->next value was initialized with out
+ * of rsabp->array pointer and must be set to NULL
+ */
+ rsabp->array[RSA_BLINDING_PARAMS_MAX_CACHE_SIZE - 1].next = NULL;
+
+ bp = rsabp->array;
+ rsabp->bp = NULL;
+ rsabp->free = bp;
+
+ /* List elements are keyed using the modulus */
+ return SECITEM_CopyItem(NULL, &rsabp->modulus, &key->modulus);
+}
+
+static SECStatus
+get_blinding_params(RSAPrivateKey *key, mp_int *n, unsigned int modLen,
+ mp_int *f, mp_int *g)
+{
+ RSABlindingParams *rsabp = NULL;
+ blindingParams *bpUnlinked = NULL;
+ blindingParams *bp;
+ PRCList *el;
+ SECStatus rv = SECSuccess;
+ mp_err err = MP_OKAY;
+ int cmp = -1;
+ PRBool holdingLock = PR_FALSE;
+
+ do {
+ if (blindingParamsList.lock == NULL) {
+ PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
+ return SECFailure;
+ }
+ /* Acquire the list lock */
+ PZ_Lock(blindingParamsList.lock);
+ holdingLock = PR_TRUE;
+
+ /* Walk the list looking for the private key */
+ for (el = PR_NEXT_LINK(&blindingParamsList.head);
+ el != &blindingParamsList.head;
+ el = PR_NEXT_LINK(el)) {
+ rsabp = (RSABlindingParams *)el;
+ cmp = SECITEM_CompareItem(&rsabp->modulus, &key->modulus);
+ if (cmp >= 0) {
+ /* The key is found or not in the list. */
+ break;
+ }
+ }
+
+ if (cmp) {
+ /* At this point, the key is not in the list. el should point to
+ ** the list element before which this key should be inserted.
+ */
+ rsabp = PORT_ZNew(RSABlindingParams);
+ if (!rsabp) {
+ PORT_SetError(SEC_ERROR_NO_MEMORY);
+ goto cleanup;
+ }
+
+ rv = init_blinding_params(rsabp, key, n, modLen);
+ if (rv != SECSuccess) {
+ PORT_ZFree(rsabp, sizeof(RSABlindingParams));
+ goto cleanup;
+ }
+
+ /* Insert the new element into the list
+ ** If inserting in the middle of the list, el points to the link
+ ** to insert before. Otherwise, the link needs to be appended to
+ ** the end of the list, which is the same as inserting before the
+ ** head (since el would have looped back to the head).
+ */
+ PR_INSERT_BEFORE(&rsabp->link, el);
+ }
+
+ /* We've found (or created) the RSAblindingParams struct for this key.
+ * Now, search its list of ready blinding params for a usable one.
+ */
+ while (0 != (bp = rsabp->bp)) {
+ if (--(bp->counter) > 0) {
+ /* Found a match and there are still remaining uses left */
+ /* Return the parameters */
+ CHECK_MPI_OK(mp_copy(&bp->f, f));
+ CHECK_MPI_OK(mp_copy(&bp->g, g));
+
+ PZ_Unlock(blindingParamsList.lock);
+ return SECSuccess;
+ }
+ /* exhausted this one, give its values to caller, and
+ * then retire it.
+ */
+ mp_exch(&bp->f, f);
+ mp_exch(&bp->g, g);
+ mp_clear(&bp->f);
+ mp_clear(&bp->g);
+ bp->counter = 0;
+ /* Move to free list */
+ rsabp->bp = bp->next;
+ bp->next = rsabp->free;
+ rsabp->free = bp;
+ /* In case there're threads waiting for new blinding
+ * value - notify 1 thread the value is ready
+ */
+ if (blindingParamsList.waitCount > 0) {
+ PR_NotifyCondVar(blindingParamsList.cVar);
+ blindingParamsList.waitCount--;
+ }
+ PZ_Unlock(blindingParamsList.lock);
+ return SECSuccess;
+ }
+ /* We did not find a usable set of blinding params. Can we make one? */
+ /* Find a free bp struct. */
+ if ((bp = rsabp->free) != NULL) {
+ /* unlink this bp */
+ rsabp->free = bp->next;
+ bp->next = NULL;
+ bpUnlinked = bp; /* In case we fail */
+
+ PZ_Unlock(blindingParamsList.lock);
+ holdingLock = PR_FALSE;
+ /* generate blinding parameter values for the current thread */
+ CHECK_SEC_OK(generate_blinding_params(key, f, g, n, modLen));
+
+ /* put the blinding parameter values into cache */
+ CHECK_MPI_OK(mp_init(&bp->f));
+ CHECK_MPI_OK(mp_init(&bp->g));
+ CHECK_MPI_OK(mp_copy(f, &bp->f));
+ CHECK_MPI_OK(mp_copy(g, &bp->g));
+
+ /* Put this at head of queue of usable params. */
+ PZ_Lock(blindingParamsList.lock);
+ holdingLock = PR_TRUE;
+ (void)holdingLock;
+ /* initialize RSABlindingParamsStr */
+ bp->counter = RSA_BLINDING_PARAMS_MAX_REUSE;
+ bp->next = rsabp->bp;
+ rsabp->bp = bp;
+ bpUnlinked = NULL;
+ /* In case there're threads waiting for new blinding value
+ * just notify them the value is ready
+ */
+ if (blindingParamsList.waitCount > 0) {
+ PR_NotifyAllCondVar(blindingParamsList.cVar);
+ blindingParamsList.waitCount = 0;
+ }
+ PZ_Unlock(blindingParamsList.lock);
+ return SECSuccess;
+ }
+ /* Here, there are no usable blinding parameters available,
+ * and no free bp blocks, presumably because they're all
+ * actively having parameters generated for them.
+ * So, we need to wait here and not eat up CPU until some
+ * change happens.
+ */
+ blindingParamsList.waitCount++;
+ PR_WaitCondVar(blindingParamsList.cVar, PR_INTERVAL_NO_TIMEOUT);
+ PZ_Unlock(blindingParamsList.lock);
+ holdingLock = PR_FALSE;
+ (void)holdingLock;
+ } while (1);
+
+cleanup:
+ /* It is possible to reach this after the lock is already released. */
+ if (bpUnlinked) {
+ if (!holdingLock) {
+ PZ_Lock(blindingParamsList.lock);
+ holdingLock = PR_TRUE;
+ }
+ bp = bpUnlinked;
+ mp_clear(&bp->f);
+ mp_clear(&bp->g);
+ bp->counter = 0;
+ /* Must put the unlinked bp back on the free list */
+ bp->next = rsabp->free;
+ rsabp->free = bp;
+ }
+ if (holdingLock) {
+ PZ_Unlock(blindingParamsList.lock);
+ }
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ }
+ return SECFailure;
+}
+
+/*
+** Perform a raw private-key operation
+** Length of input and output buffers are equal to key's modulus len.
+*/
+static SECStatus
+rsa_PrivateKeyOp(RSAPrivateKey *key,
+ unsigned char *output,
+ const unsigned char *input,
+ PRBool check)
+{
+ unsigned int modLen;
+ unsigned int offset;
+ SECStatus rv = SECSuccess;
+ mp_err err;
+ mp_int n, c, m;
+ mp_int f, g;
+ if (!key || !output || !input) {
+ PORT_SetError(SEC_ERROR_INVALID_ARGS);
+ return SECFailure;
+ }
+ /* check input out of range (needs to be in range [0..n-1]) */
+ modLen = rsa_modulusLen(&key->modulus);
+ offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
+ if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
+ PORT_SetError(SEC_ERROR_INVALID_ARGS);
+ return SECFailure;
+ }
+ MP_DIGITS(&n) = 0;
+ MP_DIGITS(&c) = 0;
+ MP_DIGITS(&m) = 0;
+ MP_DIGITS(&f) = 0;
+ MP_DIGITS(&g) = 0;
+ CHECK_MPI_OK(mp_init(&n));
+ CHECK_MPI_OK(mp_init(&c));
+ CHECK_MPI_OK(mp_init(&m));
+ CHECK_MPI_OK(mp_init(&f));
+ CHECK_MPI_OK(mp_init(&g));
+ SECITEM_TO_MPINT(key->modulus, &n);
+ OCTETS_TO_MPINT(input, &c, modLen);
+ /* If blinding, compute pre-image of ciphertext by multiplying by
+ ** blinding factor
+ */
+ if (nssRSAUseBlinding) {
+ CHECK_SEC_OK(get_blinding_params(key, &n, modLen, &f, &g));
+ /* c' = c*f mod n */
+ CHECK_MPI_OK(mp_mulmod(&c, &f, &n, &c));
+ }
+ /* Do the private key operation m = c**d mod n */
+ if (key->prime1.len == 0 ||
+ key->prime2.len == 0 ||
+ key->exponent1.len == 0 ||
+ key->exponent2.len == 0 ||
+ key->coefficient.len == 0) {
+ CHECK_SEC_OK(rsa_PrivateKeyOpNoCRT(key, &m, &c, &n, modLen));
+ } else if (check) {
+ CHECK_SEC_OK(rsa_PrivateKeyOpCRTCheckedPubKey(key, &m, &c));
+ } else {
+ CHECK_SEC_OK(rsa_PrivateKeyOpCRTNoCheck(key, &m, &c));
+ }
+ /* If blinding, compute post-image of plaintext by multiplying by
+ ** blinding factor
+ */
+ if (nssRSAUseBlinding) {
+ /* m = m'*g mod n */
+ CHECK_MPI_OK(mp_mulmod(&m, &g, &n, &m));
+ }
+ err = mp_to_fixlen_octets(&m, output, modLen);
+ if (err >= 0)
+ err = MP_OKAY;
+cleanup:
+ mp_clear(&n);
+ mp_clear(&c);
+ mp_clear(&m);
+ mp_clear(&f);
+ mp_clear(&g);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+SECStatus
+RSA_PrivateKeyOp(RSAPrivateKey *key,
+ unsigned char *output,
+ const unsigned char *input)
+{
+ return rsa_PrivateKeyOp(key, output, input, PR_FALSE);
+}
+
+SECStatus
+RSA_PrivateKeyOpDoubleChecked(RSAPrivateKey *key,
+ unsigned char *output,
+ const unsigned char *input)
+{
+ return rsa_PrivateKeyOp(key, output, input, PR_TRUE);
+}
+
+SECStatus
+RSA_PrivateKeyCheck(const RSAPrivateKey *key)
+{
+ mp_int p, q, n, psub1, qsub1, e, d, d_p, d_q, qInv, res;
+ mp_err err = MP_OKAY;
+ SECStatus rv = SECSuccess;
+ MP_DIGITS(&p) = 0;
+ MP_DIGITS(&q) = 0;
+ MP_DIGITS(&n) = 0;
+ MP_DIGITS(&psub1) = 0;
+ MP_DIGITS(&qsub1) = 0;
+ MP_DIGITS(&e) = 0;
+ MP_DIGITS(&d) = 0;
+ MP_DIGITS(&d_p) = 0;
+ MP_DIGITS(&d_q) = 0;
+ MP_DIGITS(&qInv) = 0;
+ MP_DIGITS(&res) = 0;
+ CHECK_MPI_OK(mp_init(&p));
+ CHECK_MPI_OK(mp_init(&q));
+ CHECK_MPI_OK(mp_init(&n));
+ CHECK_MPI_OK(mp_init(&psub1));
+ CHECK_MPI_OK(mp_init(&qsub1));
+ CHECK_MPI_OK(mp_init(&e));
+ CHECK_MPI_OK(mp_init(&d));
+ CHECK_MPI_OK(mp_init(&d_p));
+ CHECK_MPI_OK(mp_init(&d_q));
+ CHECK_MPI_OK(mp_init(&qInv));
+ CHECK_MPI_OK(mp_init(&res));
+
+ if (!key->modulus.data || !key->prime1.data || !key->prime2.data ||
+ !key->publicExponent.data || !key->privateExponent.data ||
+ !key->exponent1.data || !key->exponent2.data ||
+ !key->coefficient.data) {
+ /* call RSA_PopulatePrivateKey first, if the application wishes to
+ * recover these parameters */
+ err = MP_BADARG;
+ goto cleanup;
+ }
+
+ SECITEM_TO_MPINT(key->modulus, &n);
+ SECITEM_TO_MPINT(key->prime1, &p);
+ SECITEM_TO_MPINT(key->prime2, &q);
+ SECITEM_TO_MPINT(key->publicExponent, &e);
+ SECITEM_TO_MPINT(key->privateExponent, &d);
+ SECITEM_TO_MPINT(key->exponent1, &d_p);
+ SECITEM_TO_MPINT(key->exponent2, &d_q);
+ SECITEM_TO_MPINT(key->coefficient, &qInv);
+ /* p and q must be distinct. */
+ if (mp_cmp(&p, &q) == 0) {
+ rv = SECFailure;
+ goto cleanup;
+ }
+#define VERIFY_MPI_EQUAL(m1, m2) \
+ if (mp_cmp(m1, m2) != 0) { \
+ rv = SECFailure; \
+ goto cleanup; \
+ }
+#define VERIFY_MPI_EQUAL_1(m) \
+ if (mp_cmp_d(m, 1) != 0) { \
+ rv = SECFailure; \
+ goto cleanup; \
+ }
+ /* n == p * q */
+ CHECK_MPI_OK(mp_mul(&p, &q, &res));
+ VERIFY_MPI_EQUAL(&res, &n);
+ /* gcd(e, p-1) == 1 */
+ CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1));
+ CHECK_MPI_OK(mp_gcd(&e, &psub1, &res));
+ VERIFY_MPI_EQUAL_1(&res);
+ /* gcd(e, q-1) == 1 */
+ CHECK_MPI_OK(mp_sub_d(&q, 1, &qsub1));
+ CHECK_MPI_OK(mp_gcd(&e, &qsub1, &res));
+ VERIFY_MPI_EQUAL_1(&res);
+ /* d*e == 1 mod p-1 */
+ CHECK_MPI_OK(mp_mulmod(&d, &e, &psub1, &res));
+ VERIFY_MPI_EQUAL_1(&res);
+ /* d*e == 1 mod q-1 */
+ CHECK_MPI_OK(mp_mulmod(&d, &e, &qsub1, &res));
+ VERIFY_MPI_EQUAL_1(&res);
+ /* d_p == d mod p-1 */
+ CHECK_MPI_OK(mp_mod(&d, &psub1, &res));
+ VERIFY_MPI_EQUAL(&res, &d_p);
+ /* d_q == d mod q-1 */
+ CHECK_MPI_OK(mp_mod(&d, &qsub1, &res));
+ VERIFY_MPI_EQUAL(&res, &d_q);
+ /* q * q**-1 == 1 mod p */
+ CHECK_MPI_OK(mp_mulmod(&q, &qInv, &p, &res));
+ VERIFY_MPI_EQUAL_1(&res);
+
+cleanup:
+ mp_clear(&n);
+ mp_clear(&p);
+ mp_clear(&q);
+ mp_clear(&psub1);
+ mp_clear(&qsub1);
+ mp_clear(&e);
+ mp_clear(&d);
+ mp_clear(&d_p);
+ mp_clear(&d_q);
+ mp_clear(&qInv);
+ mp_clear(&res);
+ if (err) {
+ MP_TO_SEC_ERROR(err);
+ rv = SECFailure;
+ }
+ return rv;
+}
+
+static SECStatus
+RSA_Init(void)
+{
+ if (PR_CallOnce(&coBPInit, init_blinding_params_list) != PR_SUCCESS) {
+ PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
+ return SECFailure;
+ }
+ return SECSuccess;
+}
+
+SECStatus
+BL_Init(void)
+{
+ return RSA_Init();
+}
+
+/* cleanup at shutdown */
+void
+RSA_Cleanup(void)
+{
+ blindingParams *bp = NULL;
+ if (!coBPInit.initialized)
+ return;
+
+ while (!PR_CLIST_IS_EMPTY(&blindingParamsList.head)) {
+ RSABlindingParams *rsabp =
+ (RSABlindingParams *)PR_LIST_HEAD(&blindingParamsList.head);
+ PR_REMOVE_LINK(&rsabp->link);
+ /* clear parameters cache */
+ while (rsabp->bp != NULL) {
+ bp = rsabp->bp;
+ rsabp->bp = rsabp->bp->next;
+ mp_clear(&bp->f);
+ mp_clear(&bp->g);
+ }
+ SECITEM_FreeItem(&rsabp->modulus, PR_FALSE);
+ PORT_Free(rsabp);
+ }
+
+ if (blindingParamsList.cVar) {
+ PR_DestroyCondVar(blindingParamsList.cVar);
+ blindingParamsList.cVar = NULL;
+ }
+
+ if (blindingParamsList.lock) {
+ SKIP_AFTER_FORK(PZ_DestroyLock(blindingParamsList.lock));
+ blindingParamsList.lock = NULL;
+ }
+
+ coBPInit.initialized = 0;
+ coBPInit.inProgress = 0;
+ coBPInit.status = 0;
+}
+
+/*
+ * need a central place for this function to free up all the memory that
+ * free_bl may have allocated along the way. Currently only RSA does this,
+ * so I've put it here for now.
+ */
+void
+BL_Cleanup(void)
+{
+ RSA_Cleanup();
+}
+
+PRBool bl_parentForkedAfterC_Initialize;
+
+/*
+ * Set fork flag so it can be tested in SKIP_AFTER_FORK on relevant platforms.
+ */
+void
+BL_SetForkState(PRBool forked)
+{
+ bl_parentForkedAfterC_Initialize = forked;
+}