/home/XXXX-2/Sources/nssgit/nss/lib/freebl/rsa.c

Source (jump to first uncovered line)
/* 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"

/* The minimal required randomness is 64 bits */
/* EXP_BLINDING_RANDOMNESS_LEN is the length of the randomness in mp_digits */
/* for 32 bits platforts it is 2 mp_digits (= 2 * 32 bits), for 64 bits it is equal to 128 bits */
#define EXP_BLINDING_RANDOMNESS_LEN ((128 + MP_DIGIT_BIT - 1) / MP_DIGIT_BIT)
#define EXP_BLINDING_RANDOMNESS_LEN_BYTES (EXP_BLINDING_RANDOMNESS_LEN * sizeof(mp_digit))

/*
** 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;
}

SECStatus
generate_prime(mp_int *prime, int primeLen)
{
    mp_err err = MP_OKAY;
    SECStatus rv = SECSuccess;
    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_secure(prime, primeLen * 8, PR_FALSE);
        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 = { 0, 0, 0, NULL };
    mp_int q = { 0, 0, 0, NULL };
    mp_int e = { 0, 0, 0, NULL };
    mp_int d = { 0, 0, 0, NULL };
    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.  Set the public exponent and check if it's uneven and greater than 2.*/
    MP_DIGITS(&e) = 0;
    CHECK_MPI_OK(mp_init(&e));
    SECITEM_TO_MPINT(*publicExponent, &e);
    if (mp_iseven(&e) || !(mp_cmp_d(&e, 2) > 0)) {
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
        goto cleanup;
    }
#ifndef NSS_FIPS_DISABLED
    /* Check that the exponent is not smaller than 65537  */
    if (mp_cmp_d(&e, 0x10001) < 0) {
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
        goto cleanup;
    }
#endif

    /* 2. Allocate arena & key */
    arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
    if (!arena) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        goto cleanup;
    }
    key = PORT_ArenaZNew(arena, RSAPrivateKey);
    if (!key) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        goto cleanup;
    }
    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(&d) = 0;
    CHECK_MPI_OK(mp_init(&p));
    CHECK_MPI_OK(mp_init(&q));
    CHECK_MPI_OK(mp_init(&d));
    /* 3.  Set the version number (PKCS1 v1.5 says it should be zero) */
    SECITEM_AllocItem(arena, &key->version, 1);
    key->version.data[0] = 0;

    kiter = 0;
    max_attempts = 5 * (keySizeInBits / 2); /* FIPS 186-4 B.3.3 steps 4.7 and 5.8 */
    do {
        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);

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_secure(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;

    if (order_k <= 1) {
        err = MP_RANGE;
        goto cleanup;
    }

    /* 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)
{
    if (modulus->len == 0) {
        return 0;
    };
    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);

    if (modLen == 0 || expLen == 0) {
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
        rv = SECFailure;
        goto cleanup;
    }

    /* 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;
    /*
            The length of the randomness comes from the papers: 
            https://link.springer.com/chapter/10.1007/978-3-642-29912-4_7
            https://link.springer.com/chapter/10.1007/978-3-642-21554-4_5. 
        */
    mp_int blinding_dp, blinding_dq, r1, r2;
    unsigned char random_block[EXP_BLINDING_RANDOMNESS_LEN_BYTES];
    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;
    MP_DIGITS(&blinding_dp) = 0;
    MP_DIGITS(&blinding_dq) = 0;
    MP_DIGITS(&r1) = 0;
    MP_DIGITS(&r2) = 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));
    CHECK_MPI_OK(mp_init(&blinding_dp));
    CHECK_MPI_OK(mp_init(&blinding_dq));
    CHECK_MPI_OK(mp_init_size(&r1, EXP_BLINDING_RANDOMNESS_LEN));
    CHECK_MPI_OK(mp_init_size(&r2, EXP_BLINDING_RANDOMNESS_LEN));

    /* 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 */

    // blinding_dp = 1
    CHECK_MPI_OK(mp_set_int(&blinding_dp, 1));
    // blinding_dp = p - 1
    CHECK_MPI_OK(mp_sub(&p, &blinding_dp, &blinding_dp));
    // generating a random value
    RNG_GenerateGlobalRandomBytes(random_block, EXP_BLINDING_RANDOMNESS_LEN_BYTES);
    MP_USED(&r1) = EXP_BLINDING_RANDOMNESS_LEN;
    memcpy(MP_DIGITS(&r1), random_block, sizeof(random_block));
    // blinding_dp = random * (p - 1)
    CHECK_MPI_OK(mp_mul(&blinding_dp, &r1, &blinding_dp));
    //d_p = d_p + random * (p - 1)
    CHECK_MPI_OK(mp_add(&d_p, &blinding_dp, &d_p));

    // blinding_dq = 1
    CHECK_MPI_OK(mp_set_int(&blinding_dq, 1));
    // blinding_dq = q - 1
    CHECK_MPI_OK(mp_sub(&q, &blinding_dq, &blinding_dq));
    // generating a random value
    RNG_GenerateGlobalRandomBytes(random_block, EXP_BLINDING_RANDOMNESS_LEN_BYTES);
    memcpy(MP_DIGITS(&r2), random_block, sizeof(random_block));
    MP_USED(&r2) = EXP_BLINDING_RANDOMNESS_LEN;
    // blinding_dq = random * (q - 1)
    CHECK_MPI_OK(mp_mul(&blinding_dq, &r2, &blinding_dq));
    //d_q = d_q + random * (q-1)
    CHECK_MPI_OK(mp_add(&d_q, &blinding_dq, &d_q));

    /* 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);
    mp_clear(&blinding_dp);
    mp_clear(&blinding_dq);
    mp_clear(&r1);
    mp_clear(&r2);
    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)) {
#ifdef UNSAFE_FUZZER_MODE
            /* 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;
#else
            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;
#endif
        }
        /* 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);
    if (modLen == 0 || key->publicExponent.len == 0 || key->privateExponent.len == 0) {
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
        return SECFailure;
    }
    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;
}

SECStatus
RSA_Init(void)
{
    if (PR_CallOnce(&coBPInit, init_blinding_params_list) != PR_SUCCESS) {
        PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
        return SECFailure;
    }
    return SECSuccess;
}

/* 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_ZfreeItem(&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;
}

/home/XXXX-2/Sources/nssgit/nss/lib/freebl/rsapkcs.c

Source (jump to first uncovered line)
/* 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 PKCS#1 v2.1 (RFC 3447) operations
 */

#ifdef FREEBL_NO_DEPEND
#include "stubs.h"
#endif

#include "secerr.h"

#include "blapi.h"
#include "secitem.h"
#include "blapii.h"

#define RSA_BLOCK_MIN_PAD_LEN 8
#define RSA_BLOCK_FIRST_OCTET 0x00
#define RSA_BLOCK_PRIVATE_PAD_OCTET 0xff
#define RSA_BLOCK_AFTER_PAD_OCTET 0x00

/*
 * RSA block types
 *
 * The values of RSA_BlockPrivate and RSA_BlockPublic are fixed.
 * The value of RSA_BlockRaw isn't fixed by definition, but we are keeping
 * the value that NSS has been using in the past.
 */
typedef enum {
    RSA_BlockPrivate = 1, /* pad for a private-key operation */
    RSA_BlockPublic = 2,  /* pad for a public-key operation */
    RSA_BlockRaw = 4      /* simply justify the block appropriately */
} RSA_BlockType;

/* Needed for RSA-PSS functions */
static const unsigned char eightZeros[] = { 0, 0, 0, 0, 0, 0, 0, 0 };

/* Constant time comparison of a single byte.
 * Returns 1 iff a == b, otherwise returns 0.
 * Note: For ranges of bytes, use constantTimeCompare.
 */
static unsigned char
constantTimeEQ8(unsigned char a, unsigned char b)
{
    unsigned char c = ~((a - b) | (b - a));
    c >>= 7;
    return c;
}

/* Constant time comparison of a range of bytes.
 * Returns 1 iff len bytes of a are identical to len bytes of b, otherwise
 * returns 0.
 */
static unsigned char
constantTimeCompare(const unsigned char *a,
                    const unsigned char *b,
                    unsigned int len)
{
    unsigned char tmp = 0;
    unsigned int i;
    for (i = 0; i < len; ++i, ++a, ++b)
        tmp |= *a ^ *b;
    return constantTimeEQ8(0x00, tmp);
}

/* Constant time conditional.
 * Returns a if c is 1, or b if c is 0. The result is undefined if c is
 * not 0 or 1.
 */
static unsigned int
constantTimeCondition(unsigned int c,
                      unsigned int a,
                      unsigned int b)
{
    return (~(c - 1) & a) | ((c - 1) & b);
}

static unsigned int
rsa_modulusLen(SECItem *modulus)
{
    if (modulus->len == 0) {
        return 0;
    }

    unsigned char byteZero = modulus->data[0];
    unsigned int modLen = modulus->len - !byteZero;
    return modLen;
}

static unsigned int
rsa_modulusBits(SECItem *modulus)
{
    if (modulus->len == 0) {
        return 0;
    }

    unsigned char byteZero = modulus->data[0];
    unsigned int numBits = (modulus->len - 1) * 8;

    if (byteZero == 0 && modulus->len == 1) {
        return 0;
    }

    if (byteZero == 0) {
        numBits -= 8;
        byteZero = modulus->data[1];
    }

    while (byteZero > 0) {
        numBits++;
        byteZero >>= 1;
    }

    return numBits;
}

/*
 * Format one block of data for public/private key encryption using
 * the rules defined in PKCS #1.
 */
static unsigned char *
rsa_FormatOneBlock(unsigned modulusLen,
                   RSA_BlockType blockType,
                   SECItem *data)
{
    unsigned char *block;
    unsigned char *bp;
    unsigned int padLen;
    unsigned int i, j;
    SECStatus rv;

    block = (unsigned char *)PORT_Alloc(modulusLen);
    if (block == NULL)
        return NULL;

    bp = block;

    /*
     * All RSA blocks start with two octets:
     *  0x00 || BlockType
     */
    *bp++ = RSA_BLOCK_FIRST_OCTET;
    *bp++ = (unsigned char)blockType;

    switch (blockType) {

        /*
         * Blocks intended for private-key operation.
         */
        case RSA_BlockPrivate: /* preferred method */
            /*
             * 0x00 || BT || Pad || 0x00 || ActualData
             *   1      1   padLen    1      data->len
             * padLen must be at least RSA_BLOCK_MIN_PAD_LEN (8) bytes.
             * Pad is either all 0x00 or all 0xff bytes, depending on blockType.
             */
            padLen = modulusLen - data->len - 3;
            PORT_Assert(padLen >= RSA_BLOCK_MIN_PAD_LEN);
            if (padLen < RSA_BLOCK_MIN_PAD_LEN) {
                PORT_ZFree(block, modulusLen);
                return NULL;
            }
            PORT_Memset(bp, RSA_BLOCK_PRIVATE_PAD_OCTET, padLen);
            bp += padLen;
            *bp++ = RSA_BLOCK_AFTER_PAD_OCTET;
            PORT_Memcpy(bp, data->data, data->len);
            break;

        /*
         * Blocks intended for public-key operation.
         */
        case RSA_BlockPublic:
            /*
             * 0x00 || BT || Pad || 0x00 || ActualData
             *   1      1   padLen    1      data->len
             * Pad is 8 or more non-zero random bytes.
             *
             * Build the block left to right.
             * Fill the entire block from Pad to the end with random bytes.
             * Use the bytes after Pad as a supply of extra random bytes from
             * which to find replacements for the zero bytes in Pad.
             * If we need more than that, refill the bytes after Pad with
             * new random bytes as necessary.
             */

            padLen = modulusLen - (data->len + 3);
            PORT_Assert(padLen >= RSA_BLOCK_MIN_PAD_LEN);
            if (padLen < RSA_BLOCK_MIN_PAD_LEN) {
                PORT_ZFree(block, modulusLen);
                return NULL;
            }
            j = modulusLen - 2;
            rv = RNG_GenerateGlobalRandomBytes(bp, j);
            if (rv == SECSuccess) {
                for (i = 0; i < padLen;) {
                    unsigned char repl;
                    /* Pad with non-zero random data. */
                    if (bp[i] != RSA_BLOCK_AFTER_PAD_OCTET) {
                        ++i;
                        continue;
                    }
                    if (j <= padLen) {
                        rv = RNG_GenerateGlobalRandomBytes(bp + padLen,
                                                           modulusLen - (2 + padLen));
                        if (rv != SECSuccess)
                            break;
                        j = modulusLen - 2;
                    }
                    do {
                        repl = bp[--j];
                    } while (repl == RSA_BLOCK_AFTER_PAD_OCTET && j > padLen);
                    if (repl != RSA_BLOCK_AFTER_PAD_OCTET) {
                        bp[i++] = repl;
                    }
                }
            }
            if (rv != SECSuccess) {
                PORT_ZFree(block, modulusLen);
                PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
                return NULL;
            }
            bp += padLen;
            *bp++ = RSA_BLOCK_AFTER_PAD_OCTET;
            PORT_Memcpy(bp, data->data, data->len);
            break;

        default:
            PORT_Assert(0);
            PORT_ZFree(block, modulusLen);
            return NULL;
    }

    return block;
}

/* modulusLen has to be larger than RSA_BLOCK_MIN_PAD_LEN + 3, and data has to be smaller than modulus - (RSA_BLOCK_MIN_PAD_LEN + 3) */
static SECStatus
rsa_FormatBlock(SECItem *result,
                unsigned modulusLen,
                RSA_BlockType blockType,
                SECItem *data)
{
    switch (blockType) {
        case RSA_BlockPrivate:
        case RSA_BlockPublic:
            /*
             * 0x00 || BT || Pad || 0x00 || ActualData
             *
             * The "3" below is the first octet + the second octet + the 0x00
             * octet that always comes just before the ActualData.
             */
            if (modulusLen < (3 + RSA_BLOCK_MIN_PAD_LEN) || data->len > (modulusLen - (3 + RSA_BLOCK_MIN_PAD_LEN))) {
                return SECFailure;
            }
            result->data = rsa_FormatOneBlock(modulusLen, blockType, data);
            if (result->data == NULL) {
                result->len = 0;
                return SECFailure;
            }
            result->len = modulusLen;

            break;

        case RSA_BlockRaw:
            /*
             * Pad || ActualData
             * Pad is zeros. The application is responsible for recovering
             * the actual data.
             */
            if (data->len > modulusLen) {
                return SECFailure;
            }
            result->data = (unsigned char *)PORT_ZAlloc(modulusLen);
            result->len = modulusLen;
            PORT_Memcpy(result->data + (modulusLen - data->len),
                        data->data, data->len);
            break;

        default:
            PORT_Assert(0);
            result->data = NULL;
            result->len = 0;
            return SECFailure;
    }

    return SECSuccess;
}

/*
 * Mask generation function MGF1 as defined in PKCS #1 v2.1 / RFC 3447.
 */
static SECStatus
MGF1(HASH_HashType hashAlg,
     unsigned char *mask,
     unsigned int maskLen,
     const unsigned char *mgfSeed,
     unsigned int mgfSeedLen)
{
    unsigned int digestLen;
    PRUint32 counter;
    PRUint32 rounds;
    unsigned char *tempHash;
    unsigned char *temp;
    const SECHashObject *hash;
    void *hashContext;
    unsigned char C[4];
    SECStatus rv = SECSuccess;

    hash = HASH_GetRawHashObject(hashAlg);
    if (hash == NULL) {
        return SECFailure;
    }

    hashContext = (*hash->create)();
    rounds = (maskLen + hash->length - 1) / hash->length;
    for (counter = 0; counter < rounds; counter++) {
        C[0] = (unsigned char)((counter >> 24) & 0xff);
        C[1] = (unsigned char)((counter >> 16) & 0xff);
        C[2] = (unsigned char)((counter >> 8) & 0xff);
        C[3] = (unsigned char)(counter & 0xff);

        /* This could be optimized when the clone functions in
         * rawhash.c are implemented. */
        (*hash->begin)(hashContext);
        (*hash->update)(hashContext, mgfSeed, mgfSeedLen);
        (*hash->update)(hashContext, C, sizeof C);

        tempHash = mask + counter * hash->length;
        if (counter != (rounds - 1)) {
            (*hash->end)(hashContext, tempHash, &digestLen, hash->length);
        } else { /* we're in the last round and need to cut the hash */
            temp = (unsigned char *)PORT_Alloc(hash->length);
            if (!temp) {
                rv = SECFailure;
                goto done;
            }
            (*hash->end)(hashContext, temp, &digestLen, hash->length);
            PORT_Memcpy(tempHash, temp, maskLen - counter * hash->length);
            PORT_Free(temp);
        }
    }

done:
    (*hash->destroy)(hashContext, PR_TRUE);
    return rv;
}

/* XXX Doesn't set error code */
SECStatus
RSA_SignRaw(RSAPrivateKey *key,
            unsigned char *output,
            unsigned int *outputLen,
            unsigned int maxOutputLen,
            const unsigned char *data,
            unsigned int dataLen)
{
    SECStatus rv = SECSuccess;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    SECItem formatted;
    SECItem unformatted;

    if (maxOutputLen < modulusLen)
        return SECFailure;

    unformatted.len = dataLen;
    unformatted.data = (unsigned char *)data;
    formatted.data = NULL;
    rv = rsa_FormatBlock(&formatted, modulusLen, RSA_BlockRaw, &unformatted);
    if (rv != SECSuccess)
        goto done;

    rv = RSA_PrivateKeyOpDoubleChecked(key, output, formatted.data);
    *outputLen = modulusLen;

done:
    if (formatted.data != NULL)
        PORT_ZFree(formatted.data, modulusLen);
    return rv;
}

/* XXX Doesn't set error code */
SECStatus
RSA_CheckSignRaw(RSAPublicKey *key,
                 const unsigned char *sig,
                 unsigned int sigLen,
                 const unsigned char *hash,
                 unsigned int hashLen)
{
    SECStatus rv;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned char *buffer;

    if (sigLen != modulusLen)
        goto failure;
    if (hashLen > modulusLen)
        goto failure;

    buffer = (unsigned char *)PORT_Alloc(modulusLen + 1);
    if (!buffer)
        goto failure;

    rv = RSA_PublicKeyOp(key, buffer, sig);
    if (rv != SECSuccess)
        goto loser;

    /*
     * make sure we get the same results
     */
    /* XXX(rsleevi): Constant time */
    /* NOTE: should we verify the leading zeros? */
    if (PORT_Memcmp(buffer + (modulusLen - hashLen), hash, hashLen) != 0)
        goto loser;

    PORT_Free(buffer);
    return SECSuccess;

loser:
    PORT_Free(buffer);
failure:
    return SECFailure;
}

/* XXX Doesn't set error code */
SECStatus
RSA_CheckSignRecoverRaw(RSAPublicKey *key,
                        unsigned char *data,
                        unsigned int *dataLen,
                        unsigned int maxDataLen,
                        const unsigned char *sig,
                        unsigned int sigLen)
{
    SECStatus rv;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);

    if (sigLen != modulusLen)
        goto failure;
    if (maxDataLen < modulusLen)
        goto failure;

    rv = RSA_PublicKeyOp(key, data, sig);
    if (rv != SECSuccess)
        goto failure;

    *dataLen = modulusLen;
    return SECSuccess;

failure:
    return SECFailure;
}

/* XXX Doesn't set error code */
SECStatus
RSA_EncryptRaw(RSAPublicKey *key,
               unsigned char *output,
               unsigned int *outputLen,
               unsigned int maxOutputLen,
               const unsigned char *input,
               unsigned int inputLen)
{
    SECStatus rv;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    SECItem formatted;
    SECItem unformatted;

    formatted.data = NULL;
    if (maxOutputLen < modulusLen)
        goto failure;

    unformatted.len = inputLen;
    unformatted.data = (unsigned char *)input;
    formatted.data = NULL;
    rv = rsa_FormatBlock(&formatted, modulusLen, RSA_BlockRaw, &unformatted);
    if (rv != SECSuccess)
        goto failure;

    rv = RSA_PublicKeyOp(key, output, formatted.data);
    if (rv != SECSuccess)
        goto failure;

    PORT_ZFree(formatted.data, modulusLen);
    *outputLen = modulusLen;
    return SECSuccess;

failure:
    if (formatted.data != NULL)
        PORT_ZFree(formatted.data, modulusLen);
    return SECFailure;
}

/* XXX Doesn't set error code */
SECStatus
RSA_DecryptRaw(RSAPrivateKey *key,
               unsigned char *output,
               unsigned int *outputLen,
               unsigned int maxOutputLen,
               const unsigned char *input,
               unsigned int inputLen)
{
    SECStatus rv;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);

    if (modulusLen > maxOutputLen)
        goto failure;
    if (inputLen != modulusLen)
        goto failure;

    rv = RSA_PrivateKeyOp(key, output, input);
    if (rv != SECSuccess)
        goto failure;

    *outputLen = modulusLen;
    return SECSuccess;

failure:
    return SECFailure;
}

/*
 * Decodes an EME-OAEP encoded block, validating the encoding in constant
 * time.
 * Described in RFC 3447, section 7.1.2.
 * input contains the encoded block, after decryption.
 * label is the optional value L that was associated with the message.
 * On success, the original message and message length will be stored in
 * output and outputLen.
 */
static SECStatus
eme_oaep_decode(unsigned char *output,
                unsigned int *outputLen,
                unsigned int maxOutputLen,
                const unsigned char *input,
                unsigned int inputLen,
                HASH_HashType hashAlg,
                HASH_HashType maskHashAlg,
                const unsigned char *label,
                unsigned int labelLen)
{
    const SECHashObject *hash;
    void *hashContext;
    SECStatus rv = SECFailure;
    unsigned char labelHash[HASH_LENGTH_MAX];
    unsigned int i;
    unsigned int maskLen;
    unsigned int paddingOffset;
    unsigned char *mask = NULL;
    unsigned char *tmpOutput = NULL;
    unsigned char isGood;
    unsigned char foundPaddingEnd;

    hash = HASH_GetRawHashObject(hashAlg);

    /* 1.c */
    if (inputLen < (hash->length * 2) + 2) {
        PORT_SetError(SEC_ERROR_INPUT_LEN);
        return SECFailure;
    }

    /* Step 3.a - Generate lHash */
    hashContext = (*hash->create)();
    if (hashContext == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    (*hash->begin)(hashContext);
    if (labelLen > 0)
        (*hash->update)(hashContext, label, labelLen);
    (*hash->end)(hashContext, labelHash, &i, sizeof(labelHash));
    (*hash->destroy)(hashContext, PR_TRUE);

    tmpOutput = (unsigned char *)PORT_Alloc(inputLen);
    if (tmpOutput == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        goto done;
    }

    maskLen = inputLen - hash->length - 1;
    mask = (unsigned char *)PORT_Alloc(maskLen);
    if (mask == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        goto done;
    }

    PORT_Memcpy(tmpOutput, input, inputLen);

    /* 3.c - Generate seedMask */
    MGF1(maskHashAlg, mask, hash->length, &tmpOutput[1 + hash->length],
         inputLen - hash->length - 1);
    /* 3.d - Unmask seed */
    for (i = 0; i < hash->length; ++i)
        tmpOutput[1 + i] ^= mask[i];

    /* 3.e - Generate dbMask */
    MGF1(maskHashAlg, mask, maskLen, &tmpOutput[1], hash->length);
    /* 3.f - Unmask DB */
    for (i = 0; i < maskLen; ++i)
        tmpOutput[1 + hash->length + i] ^= mask[i];

    /* 3.g - Compare Y, lHash, and PS in constant time
     * Warning: This code is timing dependent and must not disclose which of
     * these were invalid.
     */
    paddingOffset = 0;
    isGood = 1;
    foundPaddingEnd = 0;

    /* Compare Y */
    isGood &= constantTimeEQ8(0x00, tmpOutput[0]);

    /* Compare lHash and lHash' */
    isGood &= constantTimeCompare(&labelHash[0],
                                  &tmpOutput[1 + hash->length],
                                  hash->length);

    /* Compare that the padding is zero or more zero octets, followed by a
     * 0x01 octet */
    for (i = 1 + (hash->length * 2); i < inputLen; ++i) {
        unsigned char isZero = constantTimeEQ8(0x00, tmpOutput[i]);
        unsigned char isOne = constantTimeEQ8(0x01, tmpOutput[i]);
        /* non-constant time equivalent:
         * if (tmpOutput[i] == 0x01 && !foundPaddingEnd)
         *     paddingOffset = i;
         */
        paddingOffset = constantTimeCondition(isOne & ~foundPaddingEnd, i,
                                              paddingOffset);
        /* non-constant time equivalent:
         * if (tmpOutput[i] == 0x01)
         *    foundPaddingEnd = true;
         *
         * Note: This may yield false positives, as it will be set whenever
         * a 0x01 byte is encountered. If there was bad padding (eg:
         * 0x03 0x02 0x01), foundPaddingEnd will still be set to true, and
         * paddingOffset will still be set to 2.
         */
        foundPaddingEnd = constantTimeCondition(isOne, 1, foundPaddingEnd);
        /* non-constant time equivalent:
         * if (tmpOutput[i] != 0x00 && tmpOutput[i] != 0x01 &&
         *     !foundPaddingEnd) {
         *    isGood = false;
         * }
         *
         * Note: This may yield false positives, as a message (and padding)
         * that is entirely zeros will result in isGood still being true. Thus
         * it's necessary to check foundPaddingEnd is positive below.
         */
        isGood = constantTimeCondition(~foundPaddingEnd & ~isZero, 0, isGood);
    }

    /* While both isGood and foundPaddingEnd may have false positives, they
     * cannot BOTH have false positives. If both are not true, then an invalid
     * message was received. Note, this comparison must still be done in constant
     * time so as not to leak either condition.
     */
    if (!(isGood & foundPaddingEnd)) {
        PORT_SetError(SEC_ERROR_BAD_DATA);
        goto done;
    }

    /* End timing dependent code */

    ++paddingOffset; /* Skip the 0x01 following the end of PS */

    *outputLen = inputLen - paddingOffset;
    if (*outputLen > maxOutputLen) {
        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
        goto done;
    }

    if (*outputLen)
        PORT_Memcpy(output, &tmpOutput[paddingOffset], *outputLen);
    rv = SECSuccess;

done:
    if (mask)
        PORT_ZFree(mask, maskLen);
    if (tmpOutput)
        PORT_ZFree(tmpOutput, inputLen);
    return rv;
}

/*
 * Generate an EME-OAEP encoded block for encryption
 * Described in RFC 3447, section 7.1.1
 * We use input instead of M for the message to be encrypted
 * label is the optional value L to be associated with the message.
 */
static SECStatus
eme_oaep_encode(unsigned char *em,
                unsigned int emLen,
                const unsigned char *input,
                unsigned int inputLen,
                HASH_HashType hashAlg,
                HASH_HashType maskHashAlg,
                const unsigned char *label,
                unsigned int labelLen,
                const unsigned char *seed,
                unsigned int seedLen)
{
    const SECHashObject *hash;
    void *hashContext;
    SECStatus rv;
    unsigned char *mask;
    unsigned int reservedLen;
    unsigned int dbMaskLen;
    unsigned int i;

    hash = HASH_GetRawHashObject(hashAlg);
    PORT_Assert(seed == NULL || seedLen == hash->length);

    /* Step 1.b */
    reservedLen = (2 * hash->length) + 2;
    if (emLen < reservedLen || inputLen > (emLen - reservedLen)) {
        PORT_SetError(SEC_ERROR_INPUT_LEN);
        return SECFailure;
    }

    /*
     * From RFC 3447, Section 7.1
     *                      +----------+---------+-------+
     *                 DB = |  lHash   |    PS   |   M   |
     *                      +----------+---------+-------+
     *                                     |
     *           +----------+              V
     *           |   seed   |--> MGF ---> xor
     *           +----------+              |
     *                 |                   |
     *        +--+     V                   |
     *        |00|    xor <----- MGF <-----|
     *        +--+     |                   |
     *          |      |                   |
     *          V      V                   V
     *        +--+----------+----------------------------+
     *  EM =  |00|maskedSeed|          maskedDB          |
     *        +--+----------+----------------------------+
     *
     * We use mask to hold the result of the MGF functions, and all other
     * values are generated in their final resting place.
     */
    *em = 0x00;

    /* Step 2.a - Generate lHash */
    hashContext = (*hash->create)();
    if (hashContext == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    (*hash->begin)(hashContext);
    if (labelLen > 0)
        (*hash->update)(hashContext, label, labelLen);
    (*hash->end)(hashContext, &em[1 + hash->length], &i, hash->length);
    (*hash->destroy)(hashContext, PR_TRUE);

    /* Step 2.b - Generate PS */
    if (emLen - reservedLen - inputLen > 0) {
        PORT_Memset(em + 1 + (hash->length * 2), 0x00,
                    emLen - reservedLen - inputLen);
    }

    /* Step 2.c. - Generate DB
     * DB = lHash || PS || 0x01 || M
     * Note that PS and lHash have already been placed into em at their
     * appropriate offsets. This just copies M into place
     */
    em[emLen - inputLen - 1] = 0x01;
    if (inputLen)
        PORT_Memcpy(em + emLen - inputLen, input, inputLen);

    if (seed == NULL) {
        /* Step 2.d - Generate seed */
        rv = RNG_GenerateGlobalRandomBytes(em + 1, hash->length);
        if (rv != SECSuccess) {
            return rv;
        }
    } else {
        /* For Known Answer Tests, copy the supplied seed. */
        PORT_Memcpy(em + 1, seed, seedLen);
    }

    /* Step 2.e - Generate dbMask*/
    dbMaskLen = emLen - hash->length - 1;
    mask = (unsigned char *)PORT_Alloc(dbMaskLen);
    if (mask == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    MGF1(maskHashAlg, mask, dbMaskLen, em + 1, hash->length);
    /* Step 2.f - Compute maskedDB*/
    for (i = 0; i < dbMaskLen; ++i)
        em[1 + hash->length + i] ^= mask[i];

    /* Step 2.g - Generate seedMask */
    MGF1(maskHashAlg, mask, hash->length, &em[1 + hash->length], dbMaskLen);
    /* Step 2.h - Compute maskedSeed */
    for (i = 0; i < hash->length; ++i)
        em[1 + i] ^= mask[i];

    PORT_ZFree(mask, dbMaskLen);
    return SECSuccess;
}

SECStatus
RSA_EncryptOAEP(RSAPublicKey *key,
                HASH_HashType hashAlg,
                HASH_HashType maskHashAlg,
                const unsigned char *label,
                unsigned int labelLen,
                const unsigned char *seed,
                unsigned int seedLen,
                unsigned char *output,
                unsigned int *outputLen,
                unsigned int maxOutputLen,
                const unsigned char *input,
                unsigned int inputLen)
{
    SECStatus rv = SECFailure;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned char *oaepEncoded = NULL;

    if (maxOutputLen < modulusLen) {
        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
        return SECFailure;
    }

    if ((hashAlg == HASH_AlgNULL) || (maskHashAlg == HASH_AlgNULL)) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return SECFailure;
    }

    if ((labelLen == 0 && label != NULL) ||
        (labelLen > 0 && label == NULL)) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return SECFailure;
    }

    oaepEncoded = (unsigned char *)PORT_Alloc(modulusLen);
    if (oaepEncoded == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    rv = eme_oaep_encode(oaepEncoded, modulusLen, input, inputLen,
                         hashAlg, maskHashAlg, label, labelLen, seed, seedLen);
    if (rv != SECSuccess)
        goto done;

    rv = RSA_PublicKeyOp(key, output, oaepEncoded);
    if (rv != SECSuccess)
        goto done;
    *outputLen = modulusLen;

done:
    PORT_Free(oaepEncoded);
    return rv;
}

SECStatus
RSA_DecryptOAEP(RSAPrivateKey *key,
                HASH_HashType hashAlg,
                HASH_HashType maskHashAlg,
                const unsigned char *label,
                unsigned int labelLen,
                unsigned char *output,
                unsigned int *outputLen,
                unsigned int maxOutputLen,
                const unsigned char *input,
                unsigned int inputLen)
{
    SECStatus rv = SECFailure;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned char *oaepEncoded = NULL;

    if ((hashAlg == HASH_AlgNULL) || (maskHashAlg == HASH_AlgNULL)) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return SECFailure;
    }

    if (inputLen != modulusLen) {
        PORT_SetError(SEC_ERROR_INPUT_LEN);
        return SECFailure;
    }

    if ((labelLen == 0 && label != NULL) ||
        (labelLen > 0 && label == NULL)) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return SECFailure;
    }

    oaepEncoded = (unsigned char *)PORT_Alloc(modulusLen);
    if (oaepEncoded == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }

    rv = RSA_PrivateKeyOpDoubleChecked(key, oaepEncoded, input);
    if (rv != SECSuccess) {
        goto done;
    }
    rv = eme_oaep_decode(output, outputLen, maxOutputLen, oaepEncoded,
                         modulusLen, hashAlg, maskHashAlg, label,
                         labelLen);

done:
    if (oaepEncoded)
        PORT_ZFree(oaepEncoded, modulusLen);
    return rv;
}

/* XXX Doesn't set error code */
SECStatus
RSA_EncryptBlock(RSAPublicKey *key,
                 unsigned char *output,
                 unsigned int *outputLen,
                 unsigned int maxOutputLen,
                 const unsigned char *input,
                 unsigned int inputLen)
{
    SECStatus rv;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    SECItem formatted;
    SECItem unformatted;

    formatted.data = NULL;
    if (maxOutputLen < modulusLen)
        goto failure;

    unformatted.len = inputLen;
    unformatted.data = (unsigned char *)input;
    formatted.data = NULL;
    rv = rsa_FormatBlock(&formatted, modulusLen, RSA_BlockPublic,
                         &unformatted);
    if (rv != SECSuccess)
        goto failure;

    rv = RSA_PublicKeyOp(key, output, formatted.data);
    if (rv != SECSuccess)
        goto failure;

    PORT_ZFree(formatted.data, modulusLen);
    *outputLen = modulusLen;
    return SECSuccess;

failure:
    if (formatted.data != NULL)
        PORT_ZFree(formatted.data, modulusLen);
    return SECFailure;
}

static HMACContext *
rsa_GetHMACContext(const SECHashObject *hash, RSAPrivateKey *key,
                   const unsigned char *input, unsigned int inputLen)
{
    unsigned char keyHash[HASH_LENGTH_MAX];
    void *hashContext;
    HMACContext *hmac = NULL;
    unsigned int privKeyLen = key->privateExponent.len;
    unsigned int keyLen;
    SECStatus rv;

    /* first get the key hash (should store in the key structure) */
    PORT_Memset(keyHash, 0, sizeof(keyHash));
    hashContext = (*hash->create)();
    if (hashContext == NULL) {
        return NULL;
    }
    (*hash->begin)(hashContext);
    if (privKeyLen < inputLen) {
        int padLen = inputLen - privKeyLen;
        while (padLen > sizeof(keyHash)) {
            (*hash->update)(hashContext, keyHash, sizeof(keyHash));
            padLen -= sizeof(keyHash);
        }
        (*hash->update)(hashContext, keyHash, padLen);
    }
    (*hash->update)(hashContext, key->privateExponent.data, privKeyLen);
    (*hash->end)(hashContext, keyHash, &keyLen, sizeof(keyHash));
    (*hash->destroy)(hashContext, PR_TRUE);

    /* now create the hmac key */
    hmac = HMAC_Create(hash, keyHash, keyLen, PR_TRUE);
    if (hmac == NULL) {
        PORT_Memset(keyHash, 0, sizeof(keyHash));
        return NULL;
    }
    HMAC_Begin(hmac);
    HMAC_Update(hmac, input, inputLen);
    rv = HMAC_Finish(hmac, keyHash, &keyLen, sizeof(keyHash));
    if (rv != SECSuccess) {
        PORT_Memset(keyHash, 0, sizeof(keyHash));
        HMAC_Destroy(hmac, PR_TRUE);
        return NULL;
    }
    /* Finally set the new key into the hash context. We
     * reuse the original context allocated above so we don't
     * need to allocate and free another one */
    rv = HMAC_ReInit(hmac, hash, keyHash, keyLen, PR_TRUE);
    PORT_Memset(keyHash, 0, sizeof(keyHash));
    if (rv != SECSuccess) {
        HMAC_Destroy(hmac, PR_TRUE);
        return NULL;
    }

    return hmac;
}

static SECStatus
rsa_HMACPrf(HMACContext *hmac, const char *label, int labelLen,
            int hashLength, unsigned char *output, int length)
{
    unsigned char iterator[2] = { 0, 0 };
    unsigned char encodedLen[2] = { 0, 0 };
    unsigned char hmacLast[HASH_LENGTH_MAX];
    unsigned int left = length;
    unsigned int hashReturn;
    SECStatus rv = SECSuccess;

    /* encodedLen is in bits, length is in bytes, thus the shifts
     * do an implied multiply by 8 */
    encodedLen[0] = (length >> 5) & 0xff;
    encodedLen[1] = (length << 3) & 0xff;

    while (left > hashLength) {
        HMAC_Begin(hmac);
        HMAC_Update(hmac, iterator, 2);
        HMAC_Update(hmac, (const unsigned char *)label, labelLen);
        HMAC_Update(hmac, encodedLen, 2);
        rv = HMAC_Finish(hmac, output, &hashReturn, hashLength);
        if (rv != SECSuccess) {
            return rv;
        }
        iterator[1]++;
        if (iterator[1] == 0)
            iterator[0]++;
        left -= hashLength;
        output += hashLength;
    }
    if (left) {
        HMAC_Begin(hmac);
        HMAC_Update(hmac, iterator, 2);
        HMAC_Update(hmac, (const unsigned char *)label, labelLen);
        HMAC_Update(hmac, encodedLen, 2);
        rv = HMAC_Finish(hmac, hmacLast, &hashReturn, sizeof(hmacLast));
        if (rv != SECSuccess) {
            return rv;
        }
        PORT_Memcpy(output, hmacLast, left);
        PORT_Memset(hmacLast, 0, sizeof(hmacLast));
    }
    return rv;
}

/* This function takes a 16-bit input number and
 * creates the smallest mask which covers
 * the whole number. Examples:
 *     0x81 -> 0xff
 *     0x1af -> 0x1ff
 *     0x4d1 -> 0x7ff
 */
static int
makeMask16(int len)
{
    // or the high bit in each bit location
    len |= (len >> 1);
    len |= (len >> 2);
    len |= (len >> 4);
    len |= (len >> 8);
    return len;
}

#define STRING_AND_LENGTH(s) s, sizeof(s) - 1
static int
rsa_GetErrorLength(HMACContext *hmac, int hashLen, int maxLegalLen)
{
    unsigned char out[128 * 2];
    unsigned char *outp;
    int outLength = 0;
    int lengthMask;
    SECStatus rv;

    lengthMask = makeMask16(maxLegalLen);
    rv = rsa_HMACPrf(hmac, STRING_AND_LENGTH("length"), hashLen,
                     out, sizeof(out));
    if (rv != SECSuccess) {
        return -1;
    }
    for (outp = out; outp < out + sizeof(out); outp += 2) {
        int candidate = outp[0] << 8 | outp[1];
        candidate = candidate & lengthMask;
        outLength = PORT_CT_SEL(PORT_CT_LT(candidate, maxLegalLen),
                                candidate, outLength);
    }
    PORT_Memset(out, 0, sizeof(out));
    return outLength;
}

/*
 * This function can only fail in environmental cases: Programming errors
 * and out of memory situations. It can't fail if the keys are valid and
 * the inputs are the proper size. If the actual RSA decryption fails, a
 * fake value and a fake length, both of which have already been generated
 * based on the key and input, are returned.
 * Applications are expected to detect decryption failures based on the fact
 * that the decrypted value (usually a key) doesn't validate. The prevents
 * Blecheinbaucher style attacks against the key. */
SECStatus
RSA_DecryptBlock(RSAPrivateKey *key,
                 unsigned char *output,
                 unsigned int *outputLen,
                 unsigned int maxOutputLen,
                 const unsigned char *input,
                 unsigned int inputLen)
{
    SECStatus rv;
    PRUint32 fail;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned int i;
    unsigned char *buffer = NULL;
    unsigned char *errorBuffer = NULL;
    unsigned char *bp = NULL;
    unsigned char *ep = NULL;
    unsigned int outLen = modulusLen;
    unsigned int maxLegalLen = modulusLen - 10;
    unsigned int errorLength;
    const SECHashObject *hashObj;
    HMACContext *hmac = NULL;

    /* failures in the top section indicate failures in the environment
     * (memory) or the library. OK to return errors in these cases because
     * it doesn't provide any oracle information to attackers. */
    if (inputLen != modulusLen || modulusLen < 10) {
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
        return SECFailure;
    }

    /* Allocate enough space to decrypt */
    buffer = PORT_ZAlloc(modulusLen);
    if (!buffer) {
        goto loser;
    }
    errorBuffer = PORT_ZAlloc(modulusLen);
    if (!errorBuffer) {
        goto loser;
    }
    hashObj = HASH_GetRawHashObject(HASH_AlgSHA256);
    if (hashObj == NULL) {
        goto loser;
    }

    /* calculate the values to return in the error case rather than
     * the actual returned values. This data is the same for the
     * same input and private key. */
    hmac = rsa_GetHMACContext(hashObj, key, input, inputLen);
    if (hmac == NULL) {
        goto loser;
    }
    errorLength = rsa_GetErrorLength(hmac, hashObj->length, maxLegalLen);
    if (((int)errorLength) < 0) {
        goto loser;
    }
    /* we always have to generate a full moduluslen error string. Otherwise
     * we create a timing dependency on errorLength, which could be used to
     * determine the difference between errorLength and outputLen and tell
     * us that there was a pkcs1 decryption failure */
    rv = rsa_HMACPrf(hmac, STRING_AND_LENGTH("message"),
                     hashObj->length, errorBuffer, modulusLen);
    if (rv != SECSuccess) {
        goto loser;
    }

    HMAC_Destroy(hmac, PR_TRUE);
    hmac = NULL;

    /* From here on out, we will always return success. If there is
     * an error, we will return deterministic output based on the key
     * and the input data. */
    rv = RSA_PrivateKeyOp(key, buffer, input);

    fail = PORT_CT_NE(rv, SECSuccess);
    fail |= PORT_CT_NE(buffer[0], RSA_BLOCK_FIRST_OCTET) | PORT_CT_NE(buffer[1], RSA_BlockPublic);

    /* There have to be at least 8 bytes of padding. */
    for (i = 2; i < 10; i++) {
        fail |= PORT_CT_EQ(buffer[i], RSA_BLOCK_AFTER_PAD_OCTET);
    }

    for (i = 10; i < modulusLen; i++) {
        unsigned int newLen = modulusLen - i - 1;
        PRUint32 condition = PORT_CT_EQ(buffer[i], RSA_BLOCK_AFTER_PAD_OCTET) & PORT_CT_EQ(outLen, modulusLen);
        outLen = PORT_CT_SEL(condition, newLen, outLen);
    }
    // this can only happen if a zero wasn't found above
    fail |= PORT_CT_GE(outLen, modulusLen);

    outLen = PORT_CT_SEL(fail, errorLength, outLen);

    /* index into the correct buffer. Do it before we truncate outLen if the
     * application was asking for less data than we can return */
    bp = buffer + modulusLen - outLen;
    ep = errorBuffer + modulusLen - outLen;

    /* at this point, outLen returns no information about decryption failures,
     * no need to hide its value. maxOutputLen is how much data the
     * application is expecting, which is also not sensitive. */
    if (outLen > maxOutputLen) {
        outLen = maxOutputLen;
    }

    /* we can't use PORT_Memcpy because caching could create a time dependency
     * on the status of fail. */
    for (i = 0; i < outLen; i++) {
        output[i] = PORT_CT_SEL(fail, ep[i], bp[i]);
    }

    *outputLen = outLen;

    PORT_Free(buffer);
    PORT_Free(errorBuffer);

    return SECSuccess;

loser:
    if (hmac) {
        HMAC_Destroy(hmac, PR_TRUE);
    }
    PORT_Free(buffer);
    PORT_Free(errorBuffer);

    return SECFailure;
}

/*
 * Encode a RSA-PSS signature.
 * Described in RFC 3447, section 9.1.1.
 * We use mHash instead of M as input.
 * emBits from the RFC is just modBits - 1, see section 8.1.1.
 * We only support MGF1 as the MGF.
 */
static SECStatus
emsa_pss_encode(unsigned char *em,
                unsigned int emLen,
                unsigned int emBits,
                const unsigned char *mHash,
                HASH_HashType hashAlg,
                HASH_HashType maskHashAlg,
                const unsigned char *salt,
                unsigned int saltLen)
{
    const SECHashObject *hash;
    void *hash_context;
    unsigned char *dbMask;
    unsigned int dbMaskLen;
    unsigned int i;
    SECStatus rv;

    hash = HASH_GetRawHashObject(hashAlg);
    dbMaskLen = emLen - hash->length - 1;

    /* Step 3 */
    if (emLen < hash->length + saltLen + 2) {
        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
        return SECFailure;
    }

    /* Step 4 */
    if (salt == NULL) {
        rv = RNG_GenerateGlobalRandomBytes(&em[dbMaskLen - saltLen], saltLen);
        if (rv != SECSuccess) {
            return rv;
        }
    } else {
        PORT_Memcpy(&em[dbMaskLen - saltLen], salt, saltLen);
    }

    /* Step 5 + 6 */
    /* Compute H and store it at its final location &em[dbMaskLen]. */
    hash_context = (*hash->create)();
    if (hash_context == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    (*hash->begin)(hash_context);
    (*hash->update)(hash_context, eightZeros, 8);
    (*hash->update)(hash_context, mHash, hash->length);
    (*hash->update)(hash_context, &em[dbMaskLen - saltLen], saltLen);
    (*hash->end)(hash_context, &em[dbMaskLen], &i, hash->length);
    (*hash->destroy)(hash_context, PR_TRUE);

    /* Step 7 + 8 */
    PORT_Memset(em, 0, dbMaskLen - saltLen - 1);
    em[dbMaskLen - saltLen - 1] = 0x01;

    /* Step 9 */
    dbMask = (unsigned char *)PORT_Alloc(dbMaskLen);
    if (dbMask == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    MGF1(maskHashAlg, dbMask, dbMaskLen, &em[dbMaskLen], hash->length);

    /* Step 10 */
    for (i = 0; i < dbMaskLen; i++)
        em[i] ^= dbMask[i];
    PORT_Free(dbMask);

    /* Step 11 */
    em[0] &= 0xff >> (8 * emLen - emBits);

    /* Step 12 */
    em[emLen - 1] = 0xbc;

    return SECSuccess;
}

/*
 * Verify a RSA-PSS signature.
 * Described in RFC 3447, section 9.1.2.
 * We use mHash instead of M as input.
 * emBits from the RFC is just modBits - 1, see section 8.1.2.
 * We only support MGF1 as the MGF.
 */
static SECStatus
emsa_pss_verify(const unsigned char *mHash,
                const unsigned char *em,
                unsigned int emLen,
                unsigned int emBits,
                HASH_HashType hashAlg,
                HASH_HashType maskHashAlg,
                unsigned int saltLen)
{
    const SECHashObject *hash;
    void *hash_context;
    unsigned char *db;
    unsigned char *H_; /* H' from the RFC */
    unsigned int i;
    unsigned int dbMaskLen;
    unsigned int zeroBits;
    SECStatus rv;

    hash = HASH_GetRawHashObject(hashAlg);
    dbMaskLen = emLen - hash->length - 1;

    /* Step 3 + 4 */
    if ((emLen < (hash->length + saltLen + 2)) ||
        (em[emLen - 1] != 0xbc)) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        return SECFailure;
    }

    /* Step 6 */
    zeroBits = 8 * emLen - emBits;
    if (em[0] >> (8 - zeroBits)) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        return SECFailure;
    }

    /* Step 7 */
    db = (unsigned char *)PORT_Alloc(dbMaskLen);
    if (db == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    /* &em[dbMaskLen] points to H, used as mgfSeed */
    MGF1(maskHashAlg, db, dbMaskLen, &em[dbMaskLen], hash->length);

    /* Step 8 */
    for (i = 0; i < dbMaskLen; i++) {
        db[i] ^= em[i];
    }

    /* Step 9 */
    db[0] &= 0xff >> zeroBits;

    /* Step 10 */
    for (i = 0; i < (dbMaskLen - saltLen - 1); i++) {
        if (db[i] != 0) {
            PORT_Free(db);
            PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
            return SECFailure;
        }
    }
    if (db[dbMaskLen - saltLen - 1] != 0x01) {
        PORT_Free(db);
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        return SECFailure;
    }

    /* Step 12 + 13 */
    H_ = (unsigned char *)PORT_Alloc(hash->length);
    if (H_ == NULL) {
        PORT_Free(db);
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    hash_context = (*hash->create)();
    if (hash_context == NULL) {
        PORT_Free(db);
        PORT_Free(H_);
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }
    (*hash->begin)(hash_context);
    (*hash->update)(hash_context, eightZeros, 8);
    (*hash->update)(hash_context, mHash, hash->length);
    (*hash->update)(hash_context, &db[dbMaskLen - saltLen], saltLen);
    (*hash->end)(hash_context, H_, &i, hash->length);
    (*hash->destroy)(hash_context, PR_TRUE);

    PORT_Free(db);

    /* Step 14 */
    if (PORT_Memcmp(H_, &em[dbMaskLen], hash->length) != 0) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        rv = SECFailure;
    } else {
        rv = SECSuccess;
    }

    PORT_Free(H_);
    return rv;
}

SECStatus
RSA_SignPSS(RSAPrivateKey *key,
            HASH_HashType hashAlg,
            HASH_HashType maskHashAlg,
            const unsigned char *salt,
            unsigned int saltLength,
            unsigned char *output,
            unsigned int *outputLen,
            unsigned int maxOutputLen,
            const unsigned char *input,
            unsigned int inputLen)
{
    SECStatus rv = SECSuccess;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned int modulusBits = rsa_modulusBits(&key->modulus);
    unsigned int emLen = modulusLen;
    unsigned char *pssEncoded, *em;

    if (maxOutputLen < modulusLen) {
        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
        return SECFailure;
    }

    if ((hashAlg == HASH_AlgNULL) || (maskHashAlg == HASH_AlgNULL)) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return SECFailure;
    }

    pssEncoded = em = (unsigned char *)PORT_Alloc(modulusLen);
    if (pssEncoded == NULL) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }

    /* len(em) == ceil((modulusBits - 1) / 8). */
    if (modulusBits % 8 == 1) {
        em[0] = 0;
        emLen--;
        em++;
    }
    rv = emsa_pss_encode(em, emLen, modulusBits - 1, input, hashAlg,
                         maskHashAlg, salt, saltLength);
    if (rv != SECSuccess)
        goto done;

    // This sets error codes upon failure.
    rv = RSA_PrivateKeyOpDoubleChecked(key, output, pssEncoded);
    *outputLen = modulusLen;

done:
    PORT_Free(pssEncoded);
    return rv;
}

SECStatus
RSA_CheckSignPSS(RSAPublicKey *key,
                 HASH_HashType hashAlg,
                 HASH_HashType maskHashAlg,
                 unsigned int saltLength,
                 const unsigned char *sig,
                 unsigned int sigLen,
                 const unsigned char *hash,
                 unsigned int hashLen)
{
    SECStatus rv;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned int modulusBits = rsa_modulusBits(&key->modulus);
    unsigned int emLen = modulusLen;
    unsigned char *buffer, *em;

    if (sigLen != modulusLen) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        return SECFailure;
    }

    if ((hashAlg == HASH_AlgNULL) || (maskHashAlg == HASH_AlgNULL)) {
        PORT_SetError(SEC_ERROR_INVALID_ALGORITHM);
        return SECFailure;
    }

    buffer = em = (unsigned char *)PORT_Alloc(modulusLen);
    if (!buffer) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        return SECFailure;
    }

    rv = RSA_PublicKeyOp(key, buffer, sig);
    if (rv != SECSuccess) {
        PORT_Free(buffer);
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        return SECFailure;
    }

    /* len(em) == ceil((modulusBits - 1) / 8). */
    if (modulusBits % 8 == 1) {
        emLen--;
        em++;
    }
    rv = emsa_pss_verify(hash, em, emLen, modulusBits - 1, hashAlg,
                         maskHashAlg, saltLength);

    PORT_Free(buffer);
    return rv;
}

SECStatus
RSA_Sign(RSAPrivateKey *key,
         unsigned char *output,
         unsigned int *outputLen,
         unsigned int maxOutputLen,
         const unsigned char *input,
         unsigned int inputLen)
{
    SECStatus rv = SECFailure;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    SECItem formatted = { siBuffer, NULL, 0 };
    SECItem unformatted = { siBuffer, (unsigned char *)input, inputLen };

    if (maxOutputLen < modulusLen) {
        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
        goto done;
    }

    rv = rsa_FormatBlock(&formatted, modulusLen, RSA_BlockPrivate,
                         &unformatted);
    if (rv != SECSuccess) {
        PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
        goto done;
    }

    // This sets error codes upon failure.
    rv = RSA_PrivateKeyOpDoubleChecked(key, output, formatted.data);
    *outputLen = modulusLen;

done:
    if (formatted.data != NULL) {
        PORT_ZFree(formatted.data, modulusLen);
    }
    return rv;
}

SECStatus
RSA_CheckSign(RSAPublicKey *key,
              const unsigned char *sig,
              unsigned int sigLen,
              const unsigned char *data,
              unsigned int dataLen)
{
    SECStatus rv = SECFailure;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned int i;
    unsigned char *buffer = NULL;

    if (sigLen != modulusLen) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }

    /*
     * 0x00 || BT || Pad || 0x00 || ActualData
     *
     * The "3" below is the first octet + the second octet + the 0x00
     * octet that always comes just before the ActualData.
     */
    if (dataLen > modulusLen - (3 + RSA_BLOCK_MIN_PAD_LEN)) {
        PORT_SetError(SEC_ERROR_BAD_DATA);
        goto done;
    }

    buffer = (unsigned char *)PORT_Alloc(modulusLen + 1);
    if (!buffer) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        goto done;
    }

    if (RSA_PublicKeyOp(key, buffer, sig) != SECSuccess) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }

    /*
     * check the padding that was used
     */
    if (buffer[0] != RSA_BLOCK_FIRST_OCTET ||
        buffer[1] != (unsigned char)RSA_BlockPrivate) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }
    for (i = 2; i < modulusLen - dataLen - 1; i++) {
        if (buffer[i] != RSA_BLOCK_PRIVATE_PAD_OCTET) {
            PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
            goto done;
        }
    }
    if (buffer[i] != RSA_BLOCK_AFTER_PAD_OCTET) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }

    /*
     * make sure we get the same results
     */
    if (PORT_Memcmp(buffer + modulusLen - dataLen, data, dataLen) == 0) {
        rv = SECSuccess;
    }

done:
    if (buffer) {
        PORT_Free(buffer);
    }
    return rv;
}

SECStatus
RSA_CheckSignRecover(RSAPublicKey *key,
                     unsigned char *output,
                     unsigned int *outputLen,
                     unsigned int maxOutputLen,
                     const unsigned char *sig,
                     unsigned int sigLen)
{
    SECStatus rv = SECFailure;
    unsigned int modulusLen = rsa_modulusLen(&key->modulus);
    unsigned int i;
    unsigned char *buffer = NULL;
    unsigned int padLen;

    if (sigLen != modulusLen) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }

    buffer = (unsigned char *)PORT_Alloc(modulusLen + 1);
    if (!buffer) {
        PORT_SetError(SEC_ERROR_NO_MEMORY);
        goto done;
    }

    if (RSA_PublicKeyOp(key, buffer, sig) != SECSuccess) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }

    *outputLen = 0;

    /*
     * check the padding that was used
     */
    if (buffer[0] != RSA_BLOCK_FIRST_OCTET ||
        buffer[1] != (unsigned char)RSA_BlockPrivate) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }
    for (i = 2; i < modulusLen; i++) {
        if (buffer[i] == RSA_BLOCK_AFTER_PAD_OCTET) {
            *outputLen = modulusLen - i - 1;
            break;
        }
        if (buffer[i] != RSA_BLOCK_PRIVATE_PAD_OCTET) {
            PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
            goto done;
        }
    }
    padLen = i - 2;
    if (padLen < RSA_BLOCK_MIN_PAD_LEN) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }
    if (*outputLen == 0) {
        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
        goto done;
    }
    if (*outputLen > maxOutputLen) {
        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
        goto done;
    }

    PORT_Memcpy(output, buffer + modulusLen - *outputLen, *outputLen);
    rv = SECSuccess;

done:
    if (buffer) {
        PORT_Free(buffer);
    }
    return rv;
}