Back to index

lightning-sunbird  0.9+nobinonly
rsa.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is the Netscape security libraries.
00015  *
00016  * The Initial Developer of the Original Code is
00017  * Netscape Communications Corporation.
00018  * Portions created by the Initial Developer are Copyright (C) 1994-2000
00019  * the Initial Developer. All Rights Reserved.
00020  *
00021  * Contributor(s):
00022  *
00023  * Alternatively, the contents of this file may be used under the terms of
00024  * either the GNU General Public License Version 2 or later (the "GPL"), or
00025  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00026  * in which case the provisions of the GPL or the LGPL are applicable instead
00027  * of those above. If you wish to allow use of your version of this file only
00028  * under the terms of either the GPL or the LGPL, and not to allow others to
00029  * use your version of this file under the terms of the MPL, indicate your
00030  * decision by deleting the provisions above and replace them with the notice
00031  * and other provisions required by the GPL or the LGPL. If you do not delete
00032  * the provisions above, a recipient may use your version of this file under
00033  * the terms of any one of the MPL, the GPL or the LGPL.
00034  *
00035  * ***** END LICENSE BLOCK ***** */
00036 
00037 /*
00038  * RSA key generation, public key op, private key op.
00039  *
00040  * $Id: rsa.c,v 1.36 2005/05/27 23:53:19 wtchang%redhat.com Exp $
00041  */
00042 
00043 #include "secerr.h"
00044 
00045 #include "prclist.h"
00046 #include "nssilock.h"
00047 #include "prinit.h"
00048 #include "blapi.h"
00049 #include "mpi.h"
00050 #include "mpprime.h"
00051 #include "mplogic.h"
00052 #include "secmpi.h"
00053 #include "secitem.h"
00054 
00055 /*
00056 ** Number of times to attempt to generate a prime (p or q) from a random
00057 ** seed (the seed changes for each iteration).
00058 */
00059 #define MAX_PRIME_GEN_ATTEMPTS 10
00060 /*
00061 ** Number of times to attempt to generate a key.  The primes p and q change
00062 ** for each attempt.
00063 */
00064 #define MAX_KEY_GEN_ATTEMPTS 10
00065 
00066 #define MAX_RSA_MODULUS  1024 /* bytes, 8k bits */
00067 #define MAX_RSA_EXPONENT    8 /* bytes, 64 bits */
00068 
00069 /* exponent should not be greater than modulus */
00070 #define BAD_RSA_KEY_SIZE(modLen, expLen) \
00071     ((expLen) > (modLen) || (modLen) > MAX_RSA_MODULUS || \
00072     (expLen) > MAX_RSA_EXPONENT)
00073 
00074 /*
00075 ** RSABlindingParamsStr
00076 **
00077 ** For discussion of Paul Kocher's timing attack against an RSA private key
00078 ** operation, see http://www.cryptography.com/timingattack/paper.html.  The 
00079 ** countermeasure to this attack, known as blinding, is also discussed in 
00080 ** the Handbook of Applied Cryptography, 11.118-11.119.
00081 */
00082 struct RSABlindingParamsStr
00083 {
00084     /* Blinding-specific parameters */
00085     PRCList   link;                  /* link to list of structs            */
00086     SECItem   modulus;               /* list element "key"                 */
00087     mp_int    f, g;                  /* Blinding parameters                */
00088     int       counter;               /* number of remaining uses of (f, g) */
00089 };
00090 
00091 /*
00092 ** RSABlindingParamsListStr
00093 **
00094 ** List of key-specific blinding params.  The arena holds the volatile pool
00095 ** of memory for each entry and the list itself.  The lock is for list
00096 ** operations, in this case insertions and iterations, as well as control
00097 ** of the counter for each set of blinding parameters.
00098 */
00099 struct RSABlindingParamsListStr
00100 {
00101     PZLock  *lock;   /* Lock for the list   */
00102     PRCList  head;   /* Pointer to the list */
00103 };
00104 
00105 /*
00106 ** The master blinding params list.
00107 */
00108 static struct RSABlindingParamsListStr blindingParamsList = { 0 };
00109 
00110 /* Number of times to reuse (f, g).  Suggested by Paul Kocher */
00111 #define RSA_BLINDING_PARAMS_MAX_REUSE 50
00112 
00113 /* Global, allows optional use of blinding.  On by default. */
00114 /* Cannot be changed at the moment, due to thread-safety issues. */
00115 static PRBool nssRSAUseBlinding = PR_TRUE;
00116 
00117 static SECStatus
00118 rsa_keygen_from_primes(mp_int *p, mp_int *q, mp_int *e, RSAPrivateKey *key,
00119                        unsigned int keySizeInBits)
00120 {
00121     mp_int n, d, phi;
00122     mp_int psub1, qsub1, tmp;
00123     mp_err   err = MP_OKAY;
00124     SECStatus rv = SECSuccess;
00125     MP_DIGITS(&n)     = 0;
00126     MP_DIGITS(&d)     = 0;
00127     MP_DIGITS(&phi)   = 0;
00128     MP_DIGITS(&psub1) = 0;
00129     MP_DIGITS(&qsub1) = 0;
00130     MP_DIGITS(&tmp)   = 0;
00131     CHECK_MPI_OK( mp_init(&n)     );
00132     CHECK_MPI_OK( mp_init(&d)     );
00133     CHECK_MPI_OK( mp_init(&phi)   );
00134     CHECK_MPI_OK( mp_init(&psub1) );
00135     CHECK_MPI_OK( mp_init(&qsub1) );
00136     CHECK_MPI_OK( mp_init(&tmp)   );
00137     /* 1.  Compute n = p*q */
00138     CHECK_MPI_OK( mp_mul(p, q, &n) );
00139     /*     verify that the modulus has the desired number of bits */
00140     if ((unsigned)mpl_significant_bits(&n) != keySizeInBits) {
00141        PORT_SetError(SEC_ERROR_NEED_RANDOM);
00142        rv = SECFailure;
00143        goto cleanup;
00144     }
00145     /* 2.  Compute phi = (p-1)*(q-1) */
00146     CHECK_MPI_OK( mp_sub_d(p, 1, &psub1) );
00147     CHECK_MPI_OK( mp_sub_d(q, 1, &qsub1) );
00148     CHECK_MPI_OK( mp_mul(&psub1, &qsub1, &phi) );
00149     /* 3.  Compute d = e**-1 mod(phi) */
00150     err = mp_invmod(e, &phi, &d);
00151     /*     Verify that phi(n) and e have no common divisors */
00152     if (err != MP_OKAY) {
00153        if (err == MP_UNDEF) {
00154            PORT_SetError(SEC_ERROR_NEED_RANDOM);
00155            err = MP_OKAY; /* to keep PORT_SetError from being called again */
00156            rv = SECFailure;
00157        }
00158        goto cleanup;
00159     }
00160     MPINT_TO_SECITEM(&n, &key->modulus, key->arena);
00161     MPINT_TO_SECITEM(&d, &key->privateExponent, key->arena);
00162     /* 4.  Compute exponent1 = d mod (p-1) */
00163     CHECK_MPI_OK( mp_mod(&d, &psub1, &tmp) );
00164     MPINT_TO_SECITEM(&tmp, &key->exponent1, key->arena);
00165     /* 5.  Compute exponent2 = d mod (q-1) */
00166     CHECK_MPI_OK( mp_mod(&d, &qsub1, &tmp) );
00167     MPINT_TO_SECITEM(&tmp, &key->exponent2, key->arena);
00168     /* 6.  Compute coefficient = q**-1 mod p */
00169     CHECK_MPI_OK( mp_invmod(q, p, &tmp) );
00170     MPINT_TO_SECITEM(&tmp, &key->coefficient, key->arena);
00171 cleanup:
00172     mp_clear(&n);
00173     mp_clear(&d);
00174     mp_clear(&phi);
00175     mp_clear(&psub1);
00176     mp_clear(&qsub1);
00177     mp_clear(&tmp);
00178     if (err) {
00179        MP_TO_SEC_ERROR(err);
00180        rv = SECFailure;
00181     }
00182     return rv;
00183 }
00184 static SECStatus
00185 generate_prime(mp_int *prime, int primeLen)
00186 {
00187     mp_err   err = MP_OKAY;
00188     SECStatus rv = SECSuccess;
00189     unsigned long counter = 0;
00190     int piter;
00191     unsigned char *pb = NULL;
00192     pb = PORT_Alloc(primeLen);
00193     if (!pb) {
00194        PORT_SetError(SEC_ERROR_NO_MEMORY);
00195        goto cleanup;
00196     }
00197     for (piter = 0; piter < MAX_PRIME_GEN_ATTEMPTS; piter++) {
00198        CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(pb, primeLen) );
00199        pb[0]          |= 0xC0; /* set two high-order bits */
00200        pb[primeLen-1] |= 0x01; /* set low-order bit       */
00201        CHECK_MPI_OK( mp_read_unsigned_octets(prime, pb, primeLen) );
00202        err = mpp_make_prime(prime, primeLen * 8, PR_FALSE, &counter);
00203        if (err != MP_NO)
00204            goto cleanup;
00205        /* keep going while err == MP_NO */
00206     }
00207 cleanup:
00208     if (pb)
00209        PORT_ZFree(pb, primeLen);
00210     if (err) {
00211        MP_TO_SEC_ERROR(err);
00212        rv = SECFailure;
00213     }
00214     return rv;
00215 }
00216 
00217 /*
00218 ** Generate and return a new RSA public and private key.
00219 **     Both keys are encoded in a single RSAPrivateKey structure.
00220 **     "cx" is the random number generator context
00221 **     "keySizeInBits" is the size of the key to be generated, in bits.
00222 **        512, 1024, etc.
00223 **     "publicExponent" when not NULL is a pointer to some data that
00224 **        represents the public exponent to use. The data is a byte
00225 **        encoded integer, in "big endian" order.
00226 */
00227 RSAPrivateKey *
00228 RSA_NewKey(int keySizeInBits, SECItem *publicExponent)
00229 {
00230     unsigned int primeLen;
00231     mp_int p, q, e;
00232     int kiter;
00233     mp_err   err = MP_OKAY;
00234     SECStatus rv = SECSuccess;
00235     int prerr = 0;
00236     RSAPrivateKey *key = NULL;
00237     PRArenaPool *arena = NULL;
00238     /* Require key size to be a multiple of 16 bits. */
00239     if (!publicExponent || keySizeInBits % 16 != 0 ||
00240            BAD_RSA_KEY_SIZE(keySizeInBits/8, publicExponent->len)) {
00241        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00242        return NULL;
00243     }
00244     /* 1. Allocate arena & key */
00245     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
00246     if (!arena) {
00247        PORT_SetError(SEC_ERROR_NO_MEMORY);
00248        return NULL;
00249     }
00250     key = (RSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(RSAPrivateKey));
00251     if (!key) {
00252        PORT_SetError(SEC_ERROR_NO_MEMORY);
00253        PORT_FreeArena(arena, PR_TRUE);
00254        return NULL;
00255     }
00256     key->arena = arena;
00257     /* length of primes p and q (in bytes) */
00258     primeLen = keySizeInBits / (2 * BITS_PER_BYTE);
00259     MP_DIGITS(&p) = 0;
00260     MP_DIGITS(&q) = 0;
00261     MP_DIGITS(&e) = 0;
00262     CHECK_MPI_OK( mp_init(&p) );
00263     CHECK_MPI_OK( mp_init(&q) );
00264     CHECK_MPI_OK( mp_init(&e) );
00265     /* 2.  Set the version number (PKCS1 v1.5 says it should be zero) */
00266     SECITEM_AllocItem(arena, &key->version, 1);
00267     key->version.data[0] = 0;
00268     /* 3.  Set the public exponent */
00269     SECITEM_CopyItem(arena, &key->publicExponent, publicExponent);
00270     SECITEM_TO_MPINT(*publicExponent, &e);
00271     kiter = 0;
00272     do {
00273        prerr = 0;
00274        PORT_SetError(0);
00275        CHECK_SEC_OK( generate_prime(&p, primeLen) );
00276        CHECK_SEC_OK( generate_prime(&q, primeLen) );
00277        /* Assure q < p */
00278        if (mp_cmp(&p, &q) < 0)
00279            mp_exch(&p, &q);
00280        /* Attempt to use these primes to generate a key */
00281        rv = rsa_keygen_from_primes(&p, &q, &e, key, keySizeInBits);
00282        if (rv == SECSuccess)
00283            break; /* generated two good primes */
00284        prerr = PORT_GetError();
00285        kiter++;
00286        /* loop until have primes */
00287     } while (prerr == SEC_ERROR_NEED_RANDOM && kiter < MAX_KEY_GEN_ATTEMPTS);
00288     if (prerr)
00289        goto cleanup;
00290     MPINT_TO_SECITEM(&p, &key->prime1, arena);
00291     MPINT_TO_SECITEM(&q, &key->prime2, arena);
00292 cleanup:
00293     mp_clear(&p);
00294     mp_clear(&q);
00295     mp_clear(&e);
00296     if (err) {
00297        MP_TO_SEC_ERROR(err);
00298        rv = SECFailure;
00299     }
00300     if (rv && arena) {
00301        PORT_FreeArena(arena, PR_TRUE);
00302        key = NULL;
00303     }
00304     return key;
00305 }
00306 
00307 static unsigned int
00308 rsa_modulusLen(SECItem *modulus)
00309 {
00310     unsigned char byteZero = modulus->data[0];
00311     unsigned int modLen = modulus->len - !byteZero;
00312     return modLen;
00313 }
00314 
00315 /*
00316 ** Perform a raw public-key operation 
00317 **     Length of input and output buffers are equal to key's modulus len.
00318 */
00319 SECStatus 
00320 RSA_PublicKeyOp(RSAPublicKey  *key, 
00321                 unsigned char *output, 
00322                 const unsigned char *input)
00323 {
00324     unsigned int modLen, expLen, offset;
00325     mp_int n, e, m, c;
00326     mp_err err   = MP_OKAY;
00327     SECStatus rv = SECSuccess;
00328     if (!key || !output || !input) {
00329        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00330        return SECFailure;
00331     }
00332     MP_DIGITS(&n) = 0;
00333     MP_DIGITS(&e) = 0;
00334     MP_DIGITS(&m) = 0;
00335     MP_DIGITS(&c) = 0;
00336     CHECK_MPI_OK( mp_init(&n) );
00337     CHECK_MPI_OK( mp_init(&e) );
00338     CHECK_MPI_OK( mp_init(&m) );
00339     CHECK_MPI_OK( mp_init(&c) );
00340     modLen = rsa_modulusLen(&key->modulus);
00341     expLen = rsa_modulusLen(&key->publicExponent);
00342     /* 1.  Obtain public key (n, e) */
00343     if (BAD_RSA_KEY_SIZE(modLen, expLen)) {
00344        PORT_SetError(SEC_ERROR_INVALID_KEY);
00345        rv = SECFailure;
00346        goto cleanup;
00347     }
00348     SECITEM_TO_MPINT(key->modulus, &n);
00349     SECITEM_TO_MPINT(key->publicExponent, &e);
00350     if (e.used > n.used) {
00351        /* exponent should not be greater than modulus */
00352        PORT_SetError(SEC_ERROR_INVALID_KEY);
00353        rv = SECFailure;
00354        goto cleanup;
00355     }
00356     /* 2. check input out of range (needs to be in range [0..n-1]) */
00357     offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
00358     if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
00359         PORT_SetError(SEC_ERROR_INPUT_LEN);
00360         rv = SECFailure;
00361         goto cleanup;
00362     }
00363     /* 2 bis.  Represent message as integer in range [0..n-1] */
00364     CHECK_MPI_OK( mp_read_unsigned_octets(&m, input, modLen) );
00365     /* 3.  Compute c = m**e mod n */
00366 #ifdef USE_MPI_EXPT_D
00367     /* XXX see which is faster */
00368     if (MP_USED(&e) == 1) {
00369        CHECK_MPI_OK( mp_exptmod_d(&m, MP_DIGIT(&e, 0), &n, &c) );
00370     } else
00371 #endif
00372     CHECK_MPI_OK( mp_exptmod(&m, &e, &n, &c) );
00373     /* 4.  result c is ciphertext */
00374     err = mp_to_fixlen_octets(&c, output, modLen);
00375     if (err >= 0) err = MP_OKAY;
00376 cleanup:
00377     mp_clear(&n);
00378     mp_clear(&e);
00379     mp_clear(&m);
00380     mp_clear(&c);
00381     if (err) {
00382        MP_TO_SEC_ERROR(err);
00383        rv = SECFailure;
00384     }
00385     return rv;
00386 }
00387 
00388 /*
00389 **  RSA Private key operation (no CRT).
00390 */
00391 static SECStatus 
00392 rsa_PrivateKeyOpNoCRT(RSAPrivateKey *key, mp_int *m, mp_int *c, mp_int *n,
00393                       unsigned int modLen)
00394 {
00395     mp_int d;
00396     mp_err   err = MP_OKAY;
00397     SECStatus rv = SECSuccess;
00398     MP_DIGITS(&d) = 0;
00399     CHECK_MPI_OK( mp_init(&d) );
00400     SECITEM_TO_MPINT(key->privateExponent, &d);
00401     /* 1. m = c**d mod n */
00402     CHECK_MPI_OK( mp_exptmod(c, &d, n, m) );
00403 cleanup:
00404     mp_clear(&d);
00405     if (err) {
00406        MP_TO_SEC_ERROR(err);
00407        rv = SECFailure;
00408     }
00409     return rv;
00410 }
00411 
00412 /*
00413 **  RSA Private key operation using CRT.
00414 */
00415 static SECStatus 
00416 rsa_PrivateKeyOpCRTNoCheck(RSAPrivateKey *key, mp_int *m, mp_int *c)
00417 {
00418     mp_int p, q, d_p, d_q, qInv;
00419     mp_int m1, m2, h, ctmp;
00420     mp_err   err = MP_OKAY;
00421     SECStatus rv = SECSuccess;
00422     MP_DIGITS(&p)    = 0;
00423     MP_DIGITS(&q)    = 0;
00424     MP_DIGITS(&d_p)  = 0;
00425     MP_DIGITS(&d_q)  = 0;
00426     MP_DIGITS(&qInv) = 0;
00427     MP_DIGITS(&m1)   = 0;
00428     MP_DIGITS(&m2)   = 0;
00429     MP_DIGITS(&h)    = 0;
00430     MP_DIGITS(&ctmp) = 0;
00431     CHECK_MPI_OK( mp_init(&p)    );
00432     CHECK_MPI_OK( mp_init(&q)    );
00433     CHECK_MPI_OK( mp_init(&d_p)  );
00434     CHECK_MPI_OK( mp_init(&d_q)  );
00435     CHECK_MPI_OK( mp_init(&qInv) );
00436     CHECK_MPI_OK( mp_init(&m1)   );
00437     CHECK_MPI_OK( mp_init(&m2)   );
00438     CHECK_MPI_OK( mp_init(&h)    );
00439     CHECK_MPI_OK( mp_init(&ctmp) );
00440     /* copy private key parameters into mp integers */
00441     SECITEM_TO_MPINT(key->prime1,      &p);    /* p */
00442     SECITEM_TO_MPINT(key->prime2,      &q);    /* q */
00443     SECITEM_TO_MPINT(key->exponent1,   &d_p);  /* d_p  = d mod (p-1) */
00444     SECITEM_TO_MPINT(key->exponent2,   &d_q);  /* d_q  = d mod (q-1) */
00445     SECITEM_TO_MPINT(key->coefficient, &qInv); /* qInv = q**-1 mod p */
00446     /* 1. m1 = c**d_p mod p */
00447     CHECK_MPI_OK( mp_mod(c, &p, &ctmp) );
00448     CHECK_MPI_OK( mp_exptmod(&ctmp, &d_p, &p, &m1) );
00449     /* 2. m2 = c**d_q mod q */
00450     CHECK_MPI_OK( mp_mod(c, &q, &ctmp) );
00451     CHECK_MPI_OK( mp_exptmod(&ctmp, &d_q, &q, &m2) );
00452     /* 3.  h = (m1 - m2) * qInv mod p */
00453     CHECK_MPI_OK( mp_submod(&m1, &m2, &p, &h) );
00454     CHECK_MPI_OK( mp_mulmod(&h, &qInv, &p, &h)  );
00455     /* 4.  m = m2 + h * q */
00456     CHECK_MPI_OK( mp_mul(&h, &q, m) );
00457     CHECK_MPI_OK( mp_add(m, &m2, m) );
00458 cleanup:
00459     mp_clear(&p);
00460     mp_clear(&q);
00461     mp_clear(&d_p);
00462     mp_clear(&d_q);
00463     mp_clear(&qInv);
00464     mp_clear(&m1);
00465     mp_clear(&m2);
00466     mp_clear(&h);
00467     mp_clear(&ctmp);
00468     if (err) {
00469        MP_TO_SEC_ERROR(err);
00470        rv = SECFailure;
00471     }
00472     return rv;
00473 }
00474 
00475 /*
00476 ** An attack against RSA CRT was described by Boneh, DeMillo, and Lipton in:
00477 ** "On the Importance of Eliminating Errors in Cryptographic Computations",
00478 ** http://theory.stanford.edu/~dabo/papers/faults.ps.gz
00479 **
00480 ** As a defense against the attack, carry out the private key operation, 
00481 ** followed up with a public key operation to invert the result.  
00482 ** Verify that result against the input.
00483 */
00484 static SECStatus 
00485 rsa_PrivateKeyOpCRTCheckedPubKey(RSAPrivateKey *key, mp_int *m, mp_int *c)
00486 {
00487     mp_int n, e, v;
00488     mp_err   err = MP_OKAY;
00489     SECStatus rv = SECSuccess;
00490     MP_DIGITS(&n) = 0;
00491     MP_DIGITS(&e) = 0;
00492     MP_DIGITS(&v) = 0;
00493     CHECK_MPI_OK( mp_init(&n) );
00494     CHECK_MPI_OK( mp_init(&e) );
00495     CHECK_MPI_OK( mp_init(&v) );
00496     CHECK_SEC_OK( rsa_PrivateKeyOpCRTNoCheck(key, m, c) );
00497     SECITEM_TO_MPINT(key->modulus,        &n);
00498     SECITEM_TO_MPINT(key->publicExponent, &e);
00499     /* Perform a public key operation v = m ** e mod n */
00500     CHECK_MPI_OK( mp_exptmod(m, &e, &n, &v) );
00501     if (mp_cmp(&v, c) != 0) {
00502        rv = SECFailure;
00503     }
00504 cleanup:
00505     mp_clear(&n);
00506     mp_clear(&e);
00507     mp_clear(&v);
00508     if (err) {
00509        MP_TO_SEC_ERROR(err);
00510        rv = SECFailure;
00511     }
00512     return rv;
00513 }
00514 
00515 static PRCallOnceType coBPInit = { 0, 0, 0 };
00516 static PRStatus 
00517 init_blinding_params_list(void)
00518 {
00519     blindingParamsList.lock = PZ_NewLock(nssILockOther);
00520     if (!blindingParamsList.lock) {
00521        PORT_SetError(SEC_ERROR_NO_MEMORY);
00522        return PR_FAILURE;
00523     }
00524     PR_INIT_CLIST(&blindingParamsList.head);
00525     return PR_SUCCESS;
00526 }
00527 
00528 static SECStatus
00529 generate_blinding_params(struct RSABlindingParamsStr *rsabp, 
00530                          RSAPrivateKey *key, mp_int *n, unsigned int modLen)
00531 {
00532     SECStatus rv = SECSuccess;
00533     mp_int e, k;
00534     mp_err err = MP_OKAY;
00535     unsigned char *kb = NULL;
00536     MP_DIGITS(&e) = 0;
00537     MP_DIGITS(&k) = 0;
00538     CHECK_MPI_OK( mp_init(&e) );
00539     CHECK_MPI_OK( mp_init(&k) );
00540     SECITEM_TO_MPINT(key->publicExponent, &e);
00541     /* generate random k < n */
00542     kb = PORT_Alloc(modLen);
00543     if (!kb) {
00544        PORT_SetError(SEC_ERROR_NO_MEMORY);
00545        goto cleanup;
00546     }
00547     CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(kb, modLen) );
00548     CHECK_MPI_OK( mp_read_unsigned_octets(&k, kb, modLen) );
00549     /* k < n */
00550     CHECK_MPI_OK( mp_mod(&k, n, &k) );
00551     /* f = k**e mod n */
00552     CHECK_MPI_OK( mp_exptmod(&k, &e, n, &rsabp->f) );
00553     /* g = k**-1 mod n */
00554     CHECK_MPI_OK( mp_invmod(&k, n, &rsabp->g) );
00555     /* Initialize the counter for this (f, g) */
00556     rsabp->counter = RSA_BLINDING_PARAMS_MAX_REUSE;
00557 cleanup:
00558     if (kb)
00559        PORT_ZFree(kb, modLen);
00560     mp_clear(&k);
00561     mp_clear(&e);
00562     if (err) {
00563        MP_TO_SEC_ERROR(err);
00564        rv = SECFailure;
00565     }
00566     return rv;
00567 }
00568 
00569 static SECStatus
00570 init_blinding_params(struct RSABlindingParamsStr *rsabp, RSAPrivateKey *key,
00571                      mp_int *n, unsigned int modLen)
00572 {
00573     SECStatus rv = SECSuccess;
00574     mp_err err = MP_OKAY;
00575     MP_DIGITS(&rsabp->f) = 0;
00576     MP_DIGITS(&rsabp->g) = 0;
00577     /* initialize blinding parameters */
00578     CHECK_MPI_OK( mp_init(&rsabp->f) );
00579     CHECK_MPI_OK( mp_init(&rsabp->g) );
00580     /* List elements are keyed using the modulus */
00581     SECITEM_CopyItem(NULL, &rsabp->modulus, &key->modulus);
00582     CHECK_SEC_OK( generate_blinding_params(rsabp, key, n, modLen) );
00583     return SECSuccess;
00584 cleanup:
00585     mp_clear(&rsabp->f);
00586     mp_clear(&rsabp->g);
00587     if (err) {
00588        MP_TO_SEC_ERROR(err);
00589        rv = SECFailure;
00590     }
00591     return rv;
00592 }
00593 
00594 static SECStatus
00595 get_blinding_params(RSAPrivateKey *key, mp_int *n, unsigned int modLen,
00596                     mp_int *f, mp_int *g)
00597 {
00598     SECStatus rv = SECSuccess;
00599     mp_err err = MP_OKAY;
00600     int cmp;
00601     PRCList *el;
00602     struct RSABlindingParamsStr *rsabp = NULL;
00603     /* Init the list if neccessary (the init function is only called once!) */
00604     if (blindingParamsList.lock == NULL) {
00605        if (PR_CallOnce(&coBPInit, init_blinding_params_list) != PR_SUCCESS) {
00606            PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
00607            return SECFailure;
00608        }
00609     }
00610     /* Acquire the list lock */
00611     PZ_Lock(blindingParamsList.lock);
00612     /* Walk the list looking for the private key */
00613     for (el = PR_NEXT_LINK(&blindingParamsList.head);
00614          el != &blindingParamsList.head;
00615          el = PR_NEXT_LINK(el)) {
00616        rsabp = (struct RSABlindingParamsStr *)el;
00617        cmp = SECITEM_CompareItem(&rsabp->modulus, &key->modulus);
00618        if (cmp == 0) {
00619            /* Check the usage counter for the parameters */
00620            if (--rsabp->counter <= 0) {
00621               /* Regenerate the blinding parameters */
00622               CHECK_SEC_OK( generate_blinding_params(rsabp, key, n, modLen) );
00623            }
00624            /* Return the parameters */
00625            CHECK_MPI_OK( mp_copy(&rsabp->f, f) );
00626            CHECK_MPI_OK( mp_copy(&rsabp->g, g) );
00627            /* Now that the params are located, release the list lock. */
00628            PZ_Unlock(blindingParamsList.lock); /* XXX when fails? */
00629            return SECSuccess;
00630        } else if (cmp > 0) {
00631            /* The key is not in the list.  Break to param creation. */
00632            break;
00633        }
00634     }
00635     /* At this point, the key is not in the list.  el should point to the
00636     ** list element that this key should be inserted before.  NOTE: the list
00637     ** lock is still held, so there cannot be a race condition here.
00638     */
00639     rsabp = (struct RSABlindingParamsStr *)
00640               PORT_ZAlloc(sizeof(struct RSABlindingParamsStr));
00641     if (!rsabp) {
00642        PORT_SetError(SEC_ERROR_NO_MEMORY);
00643        goto cleanup;
00644     }
00645     /* Initialize the list pointer for the element */
00646     PR_INIT_CLIST(&rsabp->link);
00647     /* Initialize the blinding parameters 
00648     ** This ties up the list lock while doing some heavy, element-specific
00649     ** operations, but we don't want to insert the element until it is valid,
00650     ** which requires computing the blinding params.  If this proves costly,
00651     ** it could be done after the list lock is released, and then if it fails
00652     ** the lock would have to be reobtained and the invalid element removed.
00653     */
00654     rv = init_blinding_params(rsabp, key, n, modLen);
00655     if (rv != SECSuccess) {
00656        PORT_ZFree(rsabp, sizeof(struct RSABlindingParamsStr));
00657        goto cleanup;
00658     }
00659     /* Insert the new element into the list
00660     ** If inserting in the middle of the list, el points to the link
00661     ** to insert before.  Otherwise, the link needs to be appended to
00662     ** the end of the list, which is the same as inserting before the
00663     ** head (since el would have looped back to the head).
00664     */
00665     PR_INSERT_BEFORE(&rsabp->link, el);
00666     /* Return the parameters */
00667     CHECK_MPI_OK( mp_copy(&rsabp->f, f) );
00668     CHECK_MPI_OK( mp_copy(&rsabp->g, g) );
00669     /* Release the list lock */
00670     PZ_Unlock(blindingParamsList.lock); /* XXX when fails? */
00671     return SECSuccess;
00672 cleanup:
00673     /* It is possible to reach this after the lock is already released.
00674     ** Ignore the error in that case.
00675     */
00676     PZ_Unlock(blindingParamsList.lock);
00677     if (err) {
00678        MP_TO_SEC_ERROR(err);
00679        rv = SECFailure;
00680     }
00681     return SECFailure;
00682 }
00683 
00684 /*
00685 ** Perform a raw private-key operation 
00686 **     Length of input and output buffers are equal to key's modulus len.
00687 */
00688 static SECStatus 
00689 rsa_PrivateKeyOp(RSAPrivateKey *key, 
00690                  unsigned char *output, 
00691                  const unsigned char *input,
00692                  PRBool check)
00693 {
00694     unsigned int modLen;
00695     unsigned int offset;
00696     SECStatus rv = SECSuccess;
00697     mp_err err;
00698     mp_int n, c, m;
00699     mp_int f, g;
00700     if (!key || !output || !input) {
00701        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00702        return SECFailure;
00703     }
00704     /* check input out of range (needs to be in range [0..n-1]) */
00705     modLen = rsa_modulusLen(&key->modulus);
00706     offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
00707     if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
00708        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00709        return SECFailure;
00710     }
00711     MP_DIGITS(&n) = 0;
00712     MP_DIGITS(&c) = 0;
00713     MP_DIGITS(&m) = 0;
00714     MP_DIGITS(&f) = 0;
00715     MP_DIGITS(&g) = 0;
00716     CHECK_MPI_OK( mp_init(&n) );
00717     CHECK_MPI_OK( mp_init(&c) );
00718     CHECK_MPI_OK( mp_init(&m) );
00719     CHECK_MPI_OK( mp_init(&f) );
00720     CHECK_MPI_OK( mp_init(&g) );
00721     SECITEM_TO_MPINT(key->modulus, &n);
00722     OCTETS_TO_MPINT(input, &c, modLen);
00723     /* If blinding, compute pre-image of ciphertext by multiplying by
00724     ** blinding factor
00725     */
00726     if (nssRSAUseBlinding) {
00727        CHECK_SEC_OK( get_blinding_params(key, &n, modLen, &f, &g) );
00728        /* c' = c*f mod n */
00729        CHECK_MPI_OK( mp_mulmod(&c, &f, &n, &c) );
00730     }
00731     /* Do the private key operation m = c**d mod n */
00732     if ( key->prime1.len      == 0 ||
00733          key->prime2.len      == 0 ||
00734          key->exponent1.len   == 0 ||
00735          key->exponent2.len   == 0 ||
00736          key->coefficient.len == 0) {
00737        CHECK_SEC_OK( rsa_PrivateKeyOpNoCRT(key, &m, &c, &n, modLen) );
00738     } else if (check) {
00739        CHECK_SEC_OK( rsa_PrivateKeyOpCRTCheckedPubKey(key, &m, &c) );
00740     } else {
00741        CHECK_SEC_OK( rsa_PrivateKeyOpCRTNoCheck(key, &m, &c) );
00742     }
00743     /* If blinding, compute post-image of plaintext by multiplying by
00744     ** blinding factor
00745     */
00746     if (nssRSAUseBlinding) {
00747        /* m = m'*g mod n */
00748        CHECK_MPI_OK( mp_mulmod(&m, &g, &n, &m) );
00749     }
00750     err = mp_to_fixlen_octets(&m, output, modLen);
00751     if (err >= 0) err = MP_OKAY;
00752 cleanup:
00753     mp_clear(&n);
00754     mp_clear(&c);
00755     mp_clear(&m);
00756     mp_clear(&f);
00757     mp_clear(&g);
00758     if (err) {
00759        MP_TO_SEC_ERROR(err);
00760        rv = SECFailure;
00761     }
00762     return rv;
00763 }
00764 
00765 SECStatus 
00766 RSA_PrivateKeyOp(RSAPrivateKey *key, 
00767                  unsigned char *output, 
00768                  const unsigned char *input)
00769 {
00770     return rsa_PrivateKeyOp(key, output, input, PR_FALSE);
00771 }
00772 
00773 SECStatus 
00774 RSA_PrivateKeyOpDoubleChecked(RSAPrivateKey *key, 
00775                               unsigned char *output, 
00776                               const unsigned char *input)
00777 {
00778     return rsa_PrivateKeyOp(key, output, input, PR_TRUE);
00779 }
00780 
00781 static SECStatus
00782 swap_in_key_value(PRArenaPool *arena, mp_int *mpval, SECItem *buffer)
00783 {
00784     int len;
00785     mp_err err = MP_OKAY;
00786     memset(buffer->data, 0, buffer->len);
00787     len = mp_unsigned_octet_size(mpval);
00788     if (len <= 0) return SECFailure;
00789     if ((unsigned int)len <= buffer->len) {
00790        /* The new value is no longer than the old buffer, so use it */
00791        err = mp_to_unsigned_octets(mpval, buffer->data, len);
00792        if (err >= 0) err = MP_OKAY;
00793        buffer->len = len;
00794     } else if (arena) {
00795        /* The new value is longer, but working within an arena */
00796        (void)SECITEM_AllocItem(arena, buffer, len);
00797        err = mp_to_unsigned_octets(mpval, buffer->data, len);
00798        if (err >= 0) err = MP_OKAY;
00799     } else {
00800        /* The new value is longer, no arena, can't handle this key */
00801        return SECFailure;
00802     }
00803     return (err == MP_OKAY) ? SECSuccess : SECFailure;
00804 }
00805 
00806 SECStatus
00807 RSA_PrivateKeyCheck(RSAPrivateKey *key)
00808 {
00809     mp_int p, q, n, psub1, qsub1, e, d, d_p, d_q, qInv, res;
00810     mp_err   err = MP_OKAY;
00811     SECStatus rv = SECSuccess;
00812     MP_DIGITS(&n)    = 0;
00813     MP_DIGITS(&psub1)= 0;
00814     MP_DIGITS(&qsub1)= 0;
00815     MP_DIGITS(&e)    = 0;
00816     MP_DIGITS(&d)    = 0;
00817     MP_DIGITS(&d_p)  = 0;
00818     MP_DIGITS(&d_q)  = 0;
00819     MP_DIGITS(&qInv) = 0;
00820     MP_DIGITS(&res)  = 0;
00821     CHECK_MPI_OK( mp_init(&n)    );
00822     CHECK_MPI_OK( mp_init(&p)    );
00823     CHECK_MPI_OK( mp_init(&q)    );
00824     CHECK_MPI_OK( mp_init(&psub1));
00825     CHECK_MPI_OK( mp_init(&qsub1));
00826     CHECK_MPI_OK( mp_init(&e)    );
00827     CHECK_MPI_OK( mp_init(&d)    );
00828     CHECK_MPI_OK( mp_init(&d_p)  );
00829     CHECK_MPI_OK( mp_init(&d_q)  );
00830     CHECK_MPI_OK( mp_init(&qInv) );
00831     CHECK_MPI_OK( mp_init(&res)  );
00832     SECITEM_TO_MPINT(key->modulus,         &n);
00833     SECITEM_TO_MPINT(key->prime1,          &p);
00834     SECITEM_TO_MPINT(key->prime2,          &q);
00835     SECITEM_TO_MPINT(key->publicExponent,  &e);
00836     SECITEM_TO_MPINT(key->privateExponent, &d);
00837     SECITEM_TO_MPINT(key->exponent1,       &d_p);
00838     SECITEM_TO_MPINT(key->exponent2,       &d_q);
00839     SECITEM_TO_MPINT(key->coefficient,     &qInv);
00840     /* p > q  */
00841     if (mp_cmp(&p, &q) <= 0) {
00842        /* mind the p's and q's (and d_p's and d_q's) */
00843        SECItem tmp;
00844        mp_exch(&p, &q);
00845        mp_exch(&d_p,&d_q);
00846        tmp = key->prime1;
00847        key->prime1 = key->prime2;
00848        key->prime2 = tmp;
00849        tmp = key->exponent1;
00850        key->exponent1 = key->exponent2;
00851        key->exponent2 = tmp;
00852     }
00853 #define VERIFY_MPI_EQUAL(m1, m2) \
00854     if (mp_cmp(m1, m2) != 0) {   \
00855        rv = SECFailure;         \
00856        goto cleanup;            \
00857     }
00858 #define VERIFY_MPI_EQUAL_1(m)    \
00859     if (mp_cmp_d(m, 1) != 0) {   \
00860        rv = SECFailure;         \
00861        goto cleanup;            \
00862     }
00863     /*
00864      * The following errors cannot be recovered from.
00865      */
00866     /* n == p * q */
00867     CHECK_MPI_OK( mp_mul(&p, &q, &res) );
00868     VERIFY_MPI_EQUAL(&res, &n);
00869     /* gcd(e, p-1) == 1 */
00870     CHECK_MPI_OK( mp_sub_d(&p, 1, &psub1) );
00871     CHECK_MPI_OK( mp_gcd(&e, &psub1, &res) );
00872     VERIFY_MPI_EQUAL_1(&res);
00873     /* gcd(e, q-1) == 1 */
00874     CHECK_MPI_OK( mp_sub_d(&q, 1, &qsub1) );
00875     CHECK_MPI_OK( mp_gcd(&e, &qsub1, &res) );
00876     VERIFY_MPI_EQUAL_1(&res);
00877     /* d*e == 1 mod p-1 */
00878     CHECK_MPI_OK( mp_mulmod(&d, &e, &psub1, &res) );
00879     VERIFY_MPI_EQUAL_1(&res);
00880     /* d*e == 1 mod q-1 */
00881     CHECK_MPI_OK( mp_mulmod(&d, &e, &qsub1, &res) );
00882     VERIFY_MPI_EQUAL_1(&res);
00883     /*
00884      * The following errors can be recovered from.
00885      */
00886     /* d_p == d mod p-1 */
00887     CHECK_MPI_OK( mp_mod(&d, &psub1, &res) );
00888     if (mp_cmp(&d_p, &res) != 0) {
00889        /* swap in the correct value */
00890        CHECK_SEC_OK( swap_in_key_value(key->arena, &res, &key->exponent1) );
00891     }
00892     /* d_q == d mod q-1 */
00893     CHECK_MPI_OK( mp_mod(&d, &qsub1, &res) );
00894     if (mp_cmp(&d_q, &res) != 0) {
00895        /* swap in the correct value */
00896        CHECK_SEC_OK( swap_in_key_value(key->arena, &res, &key->exponent2) );
00897     }
00898     /* q * q**-1 == 1 mod p */
00899     CHECK_MPI_OK( mp_mulmod(&q, &qInv, &p, &res) );
00900     if (mp_cmp_d(&res, 1) != 0) {
00901        /* compute the correct value */
00902        CHECK_MPI_OK( mp_invmod(&q, &p, &qInv) );
00903        CHECK_SEC_OK( swap_in_key_value(key->arena, &qInv, &key->coefficient) );
00904     }
00905 cleanup:
00906     mp_clear(&n);
00907     mp_clear(&p);
00908     mp_clear(&q);
00909     mp_clear(&psub1);
00910     mp_clear(&qsub1);
00911     mp_clear(&e);
00912     mp_clear(&d);
00913     mp_clear(&d_p);
00914     mp_clear(&d_q);
00915     mp_clear(&qInv);
00916     mp_clear(&res);
00917     if (err) {
00918        MP_TO_SEC_ERROR(err);
00919        rv = SECFailure;
00920     }
00921     return rv;
00922 }
00923 
00924 /* cleanup at shutdown */
00925 void RSA_Cleanup(void)
00926 {
00927     if (!coBPInit.initialized)
00928        return;
00929 
00930     while (!PR_CLIST_IS_EMPTY(&blindingParamsList.head))
00931     {
00932        struct RSABlindingParamsStr * rsabp = (struct RSABlindingParamsStr *)
00933            PR_LIST_HEAD(&blindingParamsList.head);
00934        PR_REMOVE_LINK(&rsabp->link);
00935        mp_clear(&rsabp->f);
00936        mp_clear(&rsabp->g);
00937        SECITEM_FreeItem(&rsabp->modulus,PR_FALSE);
00938        PORT_Free(rsabp);
00939     }
00940 
00941     if (blindingParamsList.lock)
00942     {
00943        PZ_DestroyLock(blindingParamsList.lock);
00944        blindingParamsList.lock = NULL;
00945     }
00946 
00947     coBPInit.initialized = 0;
00948     coBPInit.inProgress = 0;
00949     coBPInit.status = 0;
00950 }
00951 
00952 /*
00953  * need a central place for this function to free up all the memory that
00954  * free_bl may have allocated along the way. Currently only RSA does this,
00955  * so I've put it here for now.
00956  */
00957 void BL_Cleanup(void)
00958 {
00959     RSA_Cleanup();
00960 }