security/nss/lib/freebl/rsa.c

   1 /* ***** BEGIN LICENSE BLOCK *****
   2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   3  *
   4  * The contents of this file are subject to the Mozilla Public License Version
   5  * 1.1 (the "License"); you may not use this file except in compliance with
   6  * the License. You may obtain a copy of the License at
   7  * http://www.mozilla.org/MPL/
   8  *
   9  * Software distributed under the License is distributed on an "AS IS" basis,
  10  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  11  * for the specific language governing rights and limitations under the
  12  * License.
  13  *
  14  * The Original Code is the Netscape security libraries.
  15  *
  16  * The Initial Developer of the Original Code is
  17  * Netscape Communications Corporation.
  18  * Portions created by the Initial Developer are Copyright (C) 1994-2000
  19  * the Initial Developer. All Rights Reserved.
  20  *
  21  * Contributor(s):
  22  *
  23  * Alternatively, the contents of this file may be used under the terms of
  24  * either the GNU General Public License Version 2 or later (the "GPL"), or
  25  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  26  * in which case the provisions of the GPL or the LGPL are applicable instead
  27  * of those above. If you wish to allow use of your version of this file only
  28  * under the terms of either the GPL or the LGPL, and not to allow others to
  29  * use your version of this file under the terms of the MPL, indicate your
  30  * decision by deleting the provisions above and replace them with the notice
  31  * and other provisions required by the GPL or the LGPL. If you do not delete
  32  * the provisions above, a recipient may use your version of this file under
  33  * the terms of any one of the MPL, the GPL or the LGPL.
  34  *
  35  * ***** END LICENSE BLOCK ***** */
  36
  37 /*
  38  * RSA key generation, public key op, private key op.
  39  *
  40  * $Id: rsa.c,v 1.37 2006/05/22 22:10:40 wtchang%redhat.com Exp $
  41  */
  42
  43 #include "secerr.h"
  44
  45 #include "prclist.h"
  46 #include "nssilock.h"
  47 #include "prinit.h"
  48 #include "blapi.h"
  49 #include "mpi.h"
  50 #include "mpprime.h"
  51 #include "mplogic.h"
  52 #include "secmpi.h"
  53 #include "secitem.h"
  54
  55 /*
  56 ** Number of times to attempt to generate a prime (p or q) from a random
  57 ** seed (the seed changes for each iteration).
  58 */
  59 #define MAX_PRIME_GEN_ATTEMPTS 10
  60 /*
  61 ** Number of times to attempt to generate a key.  The primes p and q change
  62 ** for each attempt.
  63 */
  64 #define MAX_KEY_GEN_ATTEMPTS 10
  65
  66 /* exponent should not be greater than modulus */
  67 #define BAD_RSA_KEY_SIZE(modLen, expLen) \
  68     ((expLen) > (modLen) || (modLen) > RSA_MAX_MODULUS_BITS/8 || \
  69     (expLen) > RSA_MAX_EXPONENT_BITS/8)
  70
  71 /*
  72 ** RSABlindingParamsStr
  73 **
  74 ** For discussion of Paul Kocher's timing attack against an RSA private key
  75 ** operation, see http://www.cryptography.com/timingattack/paper.html.  The
  76 ** countermeasure to this attack, known as blinding, is also discussed in
  77 ** the Handbook of Applied Cryptography, 11.118-11.119.
  78 */
  79 struct RSABlindingParamsStr
  80 {
  81     /* Blinding-specific parameters */
  82     PRCList   link;                  /* link to list of structs            */
  83     SECItem   modulus;               /* list element "key"                 */
  84     mp_int    f, g;                  /* Blinding parameters                */
  85     int       counter;               /* number of remaining uses of (f, g) */
  86 };
  87
  88 /*
  89 ** RSABlindingParamsListStr
  90 **
  91 ** List of key-specific blinding params.  The arena holds the volatile pool
  92 ** of memory for each entry and the list itself.  The lock is for list
  93 ** operations, in this case insertions and iterations, as well as control
  94 ** of the counter for each set of blinding parameters.
  95 */
  96 struct RSABlindingParamsListStr
  97 {
  98     PZLock  *lock;   /* Lock for the list   */
  99     PRCList  head;   /* Pointer to the list */
 100 };
 101
 102 /*
 103 ** The master blinding params list.
 104 */
 105 static struct RSABlindingParamsListStr blindingParamsList = { 0 };
 106
 107 /* Number of times to reuse (f, g).  Suggested by Paul Kocher */
 108 #define RSA_BLINDING_PARAMS_MAX_REUSE 50
 109
 110 /* Global, allows optional use of blinding.  On by default. */
 111 /* Cannot be changed at the moment, due to thread-safety issues. */
 112 static PRBool nssRSAUseBlinding = PR_TRUE;
 113
 114 static SECStatus
 115 rsa_keygen_from_primes(mp_int *p, mp_int *q, mp_int *e, RSAPrivateKey *key,
 116                        unsigned int keySizeInBits)
 117 {
 118     mp_int n, d, phi;
 119     mp_int psub1, qsub1, tmp;
 120     mp_err   err = MP_OKAY;
 121     SECStatus rv = SECSuccess;
 122     MP_DIGITS(&n)     = 0;
 123     MP_DIGITS(&d)     = 0;
 124     MP_DIGITS(&phi)   = 0;
 125     MP_DIGITS(&psub1) = 0;
 126     MP_DIGITS(&qsub1) = 0;
 127     MP_DIGITS(&tmp)   = 0;
 128     CHECK_MPI_OK( mp_init(&n)     );
 129     CHECK_MPI_OK( mp_init(&d)     );
 130     CHECK_MPI_OK( mp_init(&phi)   );
 131     CHECK_MPI_OK( mp_init(&psub1) );
 132     CHECK_MPI_OK( mp_init(&qsub1) );
 133     CHECK_MPI_OK( mp_init(&tmp)   );
 134     /* 1.  Compute n = p*q */
 135     CHECK_MPI_OK( mp_mul(p, q, &n) );
 136     /*     verify that the modulus has the desired number of bits */
 137     if ((unsigned)mpl_significant_bits(&n) != keySizeInBits) {
 138         PORT_SetError(SEC_ERROR_NEED_RANDOM);
 139         rv = SECFailure;
 140         goto cleanup;
 141     }
 142     /* 2.  Compute phi = (p-1)*(q-1) */
 143     CHECK_MPI_OK( mp_sub_d(p, 1, &psub1) );
 144     CHECK_MPI_OK( mp_sub_d(q, 1, &qsub1) );
 145     CHECK_MPI_OK( mp_mul(&psub1, &qsub1, &phi) );
 146     /* 3.  Compute d = e**-1 mod(phi) */
 147     err = mp_invmod(e, &phi, &d);
 148     /*     Verify that phi(n) and e have no common divisors */
 149     if (err != MP_OKAY) {
 150         if (err == MP_UNDEF) {
 151             PORT_SetError(SEC_ERROR_NEED_RANDOM);
 152             err = MP_OKAY; /* to keep PORT_SetError from being called again */
 153             rv = SECFailure;
 154         }
 155         goto cleanup;
 156     }
 157     MPINT_TO_SECITEM(&n, &key->modulus, key->arena);
 158     MPINT_TO_SECITEM(&d, &key->privateExponent, key->arena);
 159     /* 4.  Compute exponent1 = d mod (p-1) */
 160     CHECK_MPI_OK( mp_mod(&d, &psub1, &tmp) );
 161     MPINT_TO_SECITEM(&tmp, &key->exponent1, key->arena);
 162     /* 5.  Compute exponent2 = d mod (q-1) */
 163     CHECK_MPI_OK( mp_mod(&d, &qsub1, &tmp) );
 164     MPINT_TO_SECITEM(&tmp, &key->exponent2, key->arena);
 165     /* 6.  Compute coefficient = q**-1 mod p */
 166     CHECK_MPI_OK( mp_invmod(q, p, &tmp) );
 167     MPINT_TO_SECITEM(&tmp, &key->coefficient, key->arena);
 168 cleanup:
 169     mp_clear(&n);
 170     mp_clear(&d);
 171     mp_clear(&phi);
 172     mp_clear(&psub1);
 173     mp_clear(&qsub1);
 174     mp_clear(&tmp);
 175     if (err) {
 176         MP_TO_SEC_ERROR(err);
 177         rv = SECFailure;
 178     }
 179     return rv;
 180 }
 181 static SECStatus
 182 generate_prime(mp_int *prime, int primeLen)
 183 {
 184     mp_err   err = MP_OKAY;
 185     SECStatus rv = SECSuccess;
 186     unsigned long counter = 0;
 187     int piter;
 188     unsigned char *pb = NULL;
 189     pb = PORT_Alloc(primeLen);
 190     if (!pb) {
 191         PORT_SetError(SEC_ERROR_NO_MEMORY);
 192         goto cleanup;
 193     }
 194     for (piter = 0; piter < MAX_PRIME_GEN_ATTEMPTS; piter++) {
 195         CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(pb, primeLen) );
 196         pb[0]          |= 0xC0; /* set two high-order bits */
 197         pb[primeLen-1] |= 0x01; /* set low-order bit       */
 198         CHECK_MPI_OK( mp_read_unsigned_octets(prime, pb, primeLen) );
 199         err = mpp_make_prime(prime, primeLen * 8, PR_FALSE, &counter);
 200         if (err != MP_NO)
 201             goto cleanup;
 202         /* keep going while err == MP_NO */
 203     }
 204 cleanup:
 205     if (pb)
 206         PORT_ZFree(pb, primeLen);
 207     if (err) {
 208         MP_TO_SEC_ERROR(err);
 209         rv = SECFailure;
 210     }
 211     return rv;
 212 }
 213
 214 /*
 215 ** Generate and return a new RSA public and private key.
 216 **      Both keys are encoded in a single RSAPrivateKey structure.
 217 **      "cx" is the random number generator context
 218 **      "keySizeInBits" is the size of the key to be generated, in bits.
 219 **         512, 1024, etc.
 220 **      "publicExponent" when not NULL is a pointer to some data that
 221 **         represents the public exponent to use. The data is a byte
 222 **         encoded integer, in "big endian" order.
 223 */
 224 RSAPrivateKey *
 225 RSA_NewKey(int keySizeInBits, SECItem *publicExponent)
 226 {
 227     unsigned int primeLen;
 228     mp_int p, q, e;
 229     int kiter;
 230     mp_err   err = MP_OKAY;
 231     SECStatus rv = SECSuccess;
 232     int prerr = 0;
 233     RSAPrivateKey *key = NULL;
 234     PRArenaPool *arena = NULL;
 235     /* Require key size to be a multiple of 16 bits. */
 236     if (!publicExponent || keySizeInBits % 16 != 0 ||
 237             BAD_RSA_KEY_SIZE(keySizeInBits/8, publicExponent->len)) {
 238         PORT_SetError(SEC_ERROR_INVALID_ARGS);
 239         return NULL;
 240     }
 241     /* 1. Allocate arena & key */
 242     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
 243     if (!arena) {
 244         PORT_SetError(SEC_ERROR_NO_MEMORY);
 245         return NULL;
 246     }
 247     key = (RSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(RSAPrivateKey));
 248     if (!key) {
 249         PORT_SetError(SEC_ERROR_NO_MEMORY);
 250         PORT_FreeArena(arena, PR_TRUE);
 251         return NULL;
 252     }
 253     key->arena = arena;
 254     /* length of primes p and q (in bytes) */
 255     primeLen = keySizeInBits / (2 * BITS_PER_BYTE);
 256     MP_DIGITS(&p) = 0;
 257     MP_DIGITS(&q) = 0;
 258     MP_DIGITS(&e) = 0;
 259     CHECK_MPI_OK( mp_init(&p) );
 260     CHECK_MPI_OK( mp_init(&q) );
 261     CHECK_MPI_OK( mp_init(&e) );
 262     /* 2.  Set the version number (PKCS1 v1.5 says it should be zero) */
 263     SECITEM_AllocItem(arena, &key->version, 1);
 264     key->version.data[0] = 0;
 265     /* 3.  Set the public exponent */
 266     SECITEM_CopyItem(arena, &key->publicExponent, publicExponent);
 267     SECITEM_TO_MPINT(*publicExponent, &e);
 268     kiter = 0;
 269     do {
 270         prerr = 0;
 271         PORT_SetError(0);
 272         CHECK_SEC_OK( generate_prime(&p, primeLen) );
 273         CHECK_SEC_OK( generate_prime(&q, primeLen) );
 274         /* Assure q < p */
 275         if (mp_cmp(&p, &q) < 0)
 276             mp_exch(&p, &q);
 277         /* Attempt to use these primes to generate a key */
 278         rv = rsa_keygen_from_primes(&p, &q, &e, key, keySizeInBits);
 279         if (rv == SECSuccess)
 280             break; /* generated two good primes */
 281         prerr = PORT_GetError();
 282         kiter++;
 283         /* loop until have primes */
 284     } while (prerr == SEC_ERROR_NEED_RANDOM && kiter < MAX_KEY_GEN_ATTEMPTS);
 285     if (prerr)
 286         goto cleanup;
 287     MPINT_TO_SECITEM(&p, &key->prime1, arena);
 288     MPINT_TO_SECITEM(&q, &key->prime2, arena);
 289 cleanup:
 290     mp_clear(&p);
 291     mp_clear(&q);
 292     mp_clear(&e);
 293     if (err) {
 294         MP_TO_SEC_ERROR(err);
 295         rv = SECFailure;
 296     }
 297     if (rv && arena) {
 298         PORT_FreeArena(arena, PR_TRUE);
 299         key = NULL;
 300     }
 301     return key;
 302 }
 303
 304 static unsigned int
 305 rsa_modulusLen(SECItem *modulus)
 306 {
 307     unsigned char byteZero = modulus->data[0];
 308     unsigned int modLen = modulus->len - !byteZero;
 309     return modLen;
 310 }
 311
 312 /*
 313 ** Perform a raw public-key operation
 314 **      Length of input and output buffers are equal to key's modulus len.
 315 */
 316 SECStatus
 317 RSA_PublicKeyOp(RSAPublicKey  *key,
 318                 unsigned char *output,
 319                 const unsigned char *input)
 320 {
 321     unsigned int modLen, expLen, offset;
 322     mp_int n, e, m, c;
 323     mp_err err   = MP_OKAY;
 324     SECStatus rv = SECSuccess;
 325     if (!key || !output || !input) {
 326         PORT_SetError(SEC_ERROR_INVALID_ARGS);
 327         return SECFailure;
 328     }
 329     MP_DIGITS(&n) = 0;
 330     MP_DIGITS(&e) = 0;
 331     MP_DIGITS(&m) = 0;
 332     MP_DIGITS(&c) = 0;
 333     CHECK_MPI_OK( mp_init(&n) );
 334     CHECK_MPI_OK( mp_init(&e) );
 335     CHECK_MPI_OK( mp_init(&m) );
 336     CHECK_MPI_OK( mp_init(&c) );
 337     modLen = rsa_modulusLen(&key->modulus);
 338     expLen = rsa_modulusLen(&key->publicExponent);
 339     /* 1.  Obtain public key (n, e) */
 340     if (BAD_RSA_KEY_SIZE(modLen, expLen)) {
 341         PORT_SetError(SEC_ERROR_INVALID_KEY);
 342         rv = SECFailure;
 343         goto cleanup;
 344     }
 345     SECITEM_TO_MPINT(key->modulus, &n);
 346     SECITEM_TO_MPINT(key->publicExponent, &e);
 347     if (e.used > n.used) {
 348         /* exponent should not be greater than modulus */
 349         PORT_SetError(SEC_ERROR_INVALID_KEY);
 350         rv = SECFailure;
 351         goto cleanup;
 352     }
 353     /* 2. check input out of range (needs to be in range [0..n-1]) */
 354     offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
 355     if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
 356         PORT_SetError(SEC_ERROR_INPUT_LEN);
 357         rv = SECFailure;
 358         goto cleanup;
 359     }
 360     /* 2 bis.  Represent message as integer in range [0..n-1] */
 361     CHECK_MPI_OK( mp_read_unsigned_octets(&m, input, modLen) );
 362     /* 3.  Compute c = m**e mod n */
 363 #ifdef USE_MPI_EXPT_D
 364     /* XXX see which is faster */
 365     if (MP_USED(&e) == 1) {
 366         CHECK_MPI_OK( mp_exptmod_d(&m, MP_DIGIT(&e, 0), &n, &c) );
 367     } else
 368 #endif
 369     CHECK_MPI_OK( mp_exptmod(&m, &e, &n, &c) );
 370     /* 4.  result c is ciphertext */
 371     err = mp_to_fixlen_octets(&c, output, modLen);
 372     if (err >= 0) err = MP_OKAY;
 373 cleanup:
 374     mp_clear(&n);
 375     mp_clear(&e);
 376     mp_clear(&m);
 377     mp_clear(&c);
 378     if (err) {
 379         MP_TO_SEC_ERROR(err);
 380         rv = SECFailure;
 381     }
 382     return rv;
 383 }
 384
 385 /*
 386 **  RSA Private key operation (no CRT).
 387 */
 388 static SECStatus
 389 rsa_PrivateKeyOpNoCRT(RSAPrivateKey *key, mp_int *m, mp_int *c, mp_int *n,
 390                       unsigned int modLen)
 391 {
 392     mp_int d;
 393     mp_err   err = MP_OKAY;
 394     SECStatus rv = SECSuccess;
 395     MP_DIGITS(&d) = 0;
 396     CHECK_MPI_OK( mp_init(&d) );
 397     SECITEM_TO_MPINT(key->privateExponent, &d);
 398     /* 1. m = c**d mod n */
 399     CHECK_MPI_OK( mp_exptmod(c, &d, n, m) );
 400 cleanup:
 401     mp_clear(&d);
 402     if (err) {
 403         MP_TO_SEC_ERROR(err);
 404         rv = SECFailure;
 405     }
 406     return rv;
 407 }
 408
 409 /*
 410 **  RSA Private key operation using CRT.
 411 */
 412 static SECStatus
 413 rsa_PrivateKeyOpCRTNoCheck(RSAPrivateKey *key, mp_int *m, mp_int *c)
 414 {
 415     mp_int p, q, d_p, d_q, qInv;
 416     mp_int m1, m2, h, ctmp;
 417     mp_err   err = MP_OKAY;
 418     SECStatus rv = SECSuccess;
 419     MP_DIGITS(&p)    = 0;
 420     MP_DIGITS(&q)    = 0;
 421     MP_DIGITS(&d_p)  = 0;
 422     MP_DIGITS(&d_q)  = 0;
 423     MP_DIGITS(&qInv) = 0;
 424     MP_DIGITS(&m1)   = 0;
 425     MP_DIGITS(&m2)   = 0;
 426     MP_DIGITS(&h)    = 0;
 427     MP_DIGITS(&ctmp) = 0;
 428     CHECK_MPI_OK( mp_init(&p)    );
 429     CHECK_MPI_OK( mp_init(&q)    );
 430     CHECK_MPI_OK( mp_init(&d_p)  );
 431     CHECK_MPI_OK( mp_init(&d_q)  );
 432     CHECK_MPI_OK( mp_init(&qInv) );
 433     CHECK_MPI_OK( mp_init(&m1)   );
 434     CHECK_MPI_OK( mp_init(&m2)   );
 435     CHECK_MPI_OK( mp_init(&h)    );
 436     CHECK_MPI_OK( mp_init(&ctmp) );
 437     /* copy private key parameters into mp integers */
 438     SECITEM_TO_MPINT(key->prime1,      &p);    /* p */
 439     SECITEM_TO_MPINT(key->prime2,      &q);    /* q */
 440     SECITEM_TO_MPINT(key->exponent1,   &d_p);  /* d_p  = d mod (p-1) */
 441     SECITEM_TO_MPINT(key->exponent2,   &d_q);  /* d_q  = d mod (q-1) */
 442     SECITEM_TO_MPINT(key->coefficient, &qInv); /* qInv = q**-1 mod p */
 443     /* 1. m1 = c**d_p mod p */
 444     CHECK_MPI_OK( mp_mod(c, &p, &ctmp) );
 445     CHECK_MPI_OK( mp_exptmod(&ctmp, &d_p, &p, &m1) );
 446     /* 2. m2 = c**d_q mod q */
 447     CHECK_MPI_OK( mp_mod(c, &q, &ctmp) );
 448     CHECK_MPI_OK( mp_exptmod(&ctmp, &d_q, &q, &m2) );
 449     /* 3.  h = (m1 - m2) * qInv mod p */
 450     CHECK_MPI_OK( mp_submod(&m1, &m2, &p, &h) );
 451     CHECK_MPI_OK( mp_mulmod(&h, &qInv, &p, &h)  );
 452     /* 4.  m = m2 + h * q */
 453     CHECK_MPI_OK( mp_mul(&h, &q, m) );
 454     CHECK_MPI_OK( mp_add(m, &m2, m) );
 455 cleanup:
 456     mp_clear(&p);
 457     mp_clear(&q);
 458     mp_clear(&d_p);
 459     mp_clear(&d_q);
 460     mp_clear(&qInv);
 461     mp_clear(&m1);
 462     mp_clear(&m2);
 463     mp_clear(&h);
 464     mp_clear(&ctmp);
 465     if (err) {
 466         MP_TO_SEC_ERROR(err);
 467         rv = SECFailure;
 468     }
 469     return rv;
 470 }
 471
 472 /*
 473 ** An attack against RSA CRT was described by Boneh, DeMillo, and Lipton in:
 474 ** "On the Importance of Eliminating Errors in Cryptographic Computations",
 475 ** http://theory.stanford.edu/~dabo/papers/faults.ps.gz
 476 **
 477 ** As a defense against the attack, carry out the private key operation,
 478 ** followed up with a public key operation to invert the result.
 479 ** Verify that result against the input.
 480 */
 481 static SECStatus
 482 rsa_PrivateKeyOpCRTCheckedPubKey(RSAPrivateKey *key, mp_int *m, mp_int *c)
 483 {
 484     mp_int n, e, v;
 485     mp_err   err = MP_OKAY;
 486     SECStatus rv = SECSuccess;
 487     MP_DIGITS(&n) = 0;
 488     MP_DIGITS(&e) = 0;
 489     MP_DIGITS(&v) = 0;
 490     CHECK_MPI_OK( mp_init(&n) );
 491     CHECK_MPI_OK( mp_init(&e) );
 492     CHECK_MPI_OK( mp_init(&v) );
 493     CHECK_SEC_OK( rsa_PrivateKeyOpCRTNoCheck(key, m, c) );
 494     SECITEM_TO_MPINT(key->modulus,        &n);
 495     SECITEM_TO_MPINT(key->publicExponent, &e);
 496     /* Perform a public key operation v = m ** e mod n */
 497     CHECK_MPI_OK( mp_exptmod(m, &e, &n, &v) );
 498     if (mp_cmp(&v, c) != 0) {
 499         rv = SECFailure;
 500     }
 501 cleanup:
 502     mp_clear(&n);
 503     mp_clear(&e);
 504     mp_clear(&v);
 505     if (err) {
 506         MP_TO_SEC_ERROR(err);
 507         rv = SECFailure;
 508     }
 509     return rv;
 510 }
 511
 512 static PRCallOnceType coBPInit = { 0, 0, 0 };
 513 static PRStatus
 514 init_blinding_params_list(void)
 515 {
 516     blindingParamsList.lock = PZ_NewLock(nssILockOther);
 517     if (!blindingParamsList.lock) {
 518         PORT_SetError(SEC_ERROR_NO_MEMORY);
 519         return PR_FAILURE;
 520     }
 521     PR_INIT_CLIST(&blindingParamsList.head);
 522     return PR_SUCCESS;
 523 }
 524
 525 static SECStatus
 526 generate_blinding_params(struct RSABlindingParamsStr *rsabp,
 527                          RSAPrivateKey *key, mp_int *n, unsigned int modLen)
 528 {
 529     SECStatus rv = SECSuccess;
 530     mp_int e, k;
 531     mp_err err = MP_OKAY;
 532     unsigned char *kb = NULL;
 533     MP_DIGITS(&e) = 0;
 534     MP_DIGITS(&k) = 0;
 535     CHECK_MPI_OK( mp_init(&e) );
 536     CHECK_MPI_OK( mp_init(&k) );
 537     SECITEM_TO_MPINT(key->publicExponent, &e);
 538     /* generate random k < n */
 539     kb = PORT_Alloc(modLen);
 540     if (!kb) {
 541         PORT_SetError(SEC_ERROR_NO_MEMORY);
 542         goto cleanup;
 543     }
 544     CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(kb, modLen) );
 545     CHECK_MPI_OK( mp_read_unsigned_octets(&k, kb, modLen) );
 546     /* k < n */
 547     CHECK_MPI_OK( mp_mod(&k, n, &k) );
 548     /* f = k**e mod n */
 549     CHECK_MPI_OK( mp_exptmod(&k, &e, n, &rsabp->f) );
 550     /* g = k**-1 mod n */
 551     CHECK_MPI_OK( mp_invmod(&k, n, &rsabp->g) );
 552     /* Initialize the counter for this (f, g) */
 553     rsabp->counter = RSA_BLINDING_PARAMS_MAX_REUSE;
 554 cleanup:
 555     if (kb)
 556         PORT_ZFree(kb, modLen);
 557     mp_clear(&k);
 558     mp_clear(&e);
 559     if (err) {
 560         MP_TO_SEC_ERROR(err);
 561         rv = SECFailure;
 562     }
 563     return rv;
 564 }
 565
 566 static SECStatus
 567 init_blinding_params(struct RSABlindingParamsStr *rsabp, RSAPrivateKey *key,
 568                      mp_int *n, unsigned int modLen)
 569 {
 570     SECStatus rv = SECSuccess;
 571     mp_err err = MP_OKAY;
 572     MP_DIGITS(&rsabp->f) = 0;
 573     MP_DIGITS(&rsabp->g) = 0;
 574     /* initialize blinding parameters */
 575     CHECK_MPI_OK( mp_init(&rsabp->f) );
 576     CHECK_MPI_OK( mp_init(&rsabp->g) );
 577     /* List elements are keyed using the modulus */
 578     SECITEM_CopyItem(NULL, &rsabp->modulus, &key->modulus);
 579     CHECK_SEC_OK( generate_blinding_params(rsabp, key, n, modLen) );
 580     return SECSuccess;
 581 cleanup:
 582     mp_clear(&rsabp->f);
 583     mp_clear(&rsabp->g);
 584     if (err) {
 585         MP_TO_SEC_ERROR(err);
 586         rv = SECFailure;
 587     }
 588     return rv;
 589 }
 590
 591 static SECStatus
 592 get_blinding_params(RSAPrivateKey *key, mp_int *n, unsigned int modLen,
 593                     mp_int *f, mp_int *g)
 594 {
 595     SECStatus rv = SECSuccess;
 596     mp_err err = MP_OKAY;
 597     int cmp;
 598     PRCList *el;
 599     struct RSABlindingParamsStr *rsabp = NULL;
 600     /* Init the list if neccessary (the init function is only called once!) */
 601     if (blindingParamsList.lock == NULL) {
 602         if (PR_CallOnce(&coBPInit, init_blinding_params_list) != PR_SUCCESS) {
 603             PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
 604             return SECFailure;
 605         }
 606     }
 607     /* Acquire the list lock */
 608     PZ_Lock(blindingParamsList.lock);
 609     /* Walk the list looking for the private key */
 610     for (el = PR_NEXT_LINK(&blindingParamsList.head);
 611          el != &blindingParamsList.head;
 612          el = PR_NEXT_LINK(el)) {
 613         rsabp = (struct RSABlindingParamsStr *)el;
 614         cmp = SECITEM_CompareItem(&rsabp->modulus, &key->modulus);
 615         if (cmp == 0) {
 616             /* Check the usage counter for the parameters */
 617             if (--rsabp->counter <= 0) {
 618                 /* Regenerate the blinding parameters */
 619                 CHECK_SEC_OK( generate_blinding_params(rsabp, key, n, modLen) );
 620             }
 621             /* Return the parameters */
 622             CHECK_MPI_OK( mp_copy(&rsabp->f, f) );
 623             CHECK_MPI_OK( mp_copy(&rsabp->g, g) );
 624             /* Now that the params are located, release the list lock. */
 625             PZ_Unlock(blindingParamsList.lock); /* XXX when fails? */
 626             return SECSuccess;
 627         } else if (cmp > 0) {
 628             /* The key is not in the list.  Break to param creation. */
 629             break;
 630         }
 631     }
 632     /* At this point, the key is not in the list.  el should point to the
 633     ** list element that this key should be inserted before.  NOTE: the list
 634     ** lock is still held, so there cannot be a race condition here.
 635     */
 636     rsabp = (struct RSABlindingParamsStr *)
 637               PORT_ZAlloc(sizeof(struct RSABlindingParamsStr));
 638     if (!rsabp) {
 639         PORT_SetError(SEC_ERROR_NO_MEMORY);
 640         goto cleanup;
 641     }
 642     /* Initialize the list pointer for the element */
 643     PR_INIT_CLIST(&rsabp->link);
 644     /* Initialize the blinding parameters
 645     ** This ties up the list lock while doing some heavy, element-specific
 646     ** operations, but we don't want to insert the element until it is valid,
 647     ** which requires computing the blinding params.  If this proves costly,
 648     ** it could be done after the list lock is released, and then if it fails
 649     ** the lock would have to be reobtained and the invalid element removed.
 650     */
 651     rv = init_blinding_params(rsabp, key, n, modLen);
 652     if (rv != SECSuccess) {
 653         PORT_ZFree(rsabp, sizeof(struct RSABlindingParamsStr));
 654         goto cleanup;
 655     }
 656     /* Insert the new element into the list
 657     ** If inserting in the middle of the list, el points to the link
 658     ** to insert before.  Otherwise, the link needs to be appended to
 659     ** the end of the list, which is the same as inserting before the
 660     ** head (since el would have looped back to the head).
 661     */
 662     PR_INSERT_BEFORE(&rsabp->link, el);
 663     /* Return the parameters */
 664     CHECK_MPI_OK( mp_copy(&rsabp->f, f) );
 665     CHECK_MPI_OK( mp_copy(&rsabp->g, g) );
 666     /* Release the list lock */
 667     PZ_Unlock(blindingParamsList.lock); /* XXX when fails? */
 668     return SECSuccess;
 669 cleanup:
 670     /* It is possible to reach this after the lock is already released.
 671     ** Ignore the error in that case.
 672     */
 673     PZ_Unlock(blindingParamsList.lock);
 674     if (err) {
 675         MP_TO_SEC_ERROR(err);
 676         rv = SECFailure;
 677     }
 678     return SECFailure;
 679 }
 680
 681 /*
 682 ** Perform a raw private-key operation
 683 **      Length of input and output buffers are equal to key's modulus len.
 684 */
 685 static SECStatus
 686 rsa_PrivateKeyOp(RSAPrivateKey *key,
 687                  unsigned char *output,
 688                  const unsigned char *input,
 689                  PRBool check)
 690 {
 691     unsigned int modLen;
 692     unsigned int offset;
 693     SECStatus rv = SECSuccess;
 694     mp_err err;
 695     mp_int n, c, m;
 696     mp_int f, g;
 697     if (!key || !output || !input) {
 698         PORT_SetError(SEC_ERROR_INVALID_ARGS);
 699         return SECFailure;
 700     }
 701     /* check input out of range (needs to be in range [0..n-1]) */
 702     modLen = rsa_modulusLen(&key->modulus);
 703     offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
 704     if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
 705         PORT_SetError(SEC_ERROR_INVALID_ARGS);
 706         return SECFailure;
 707     }
 708     MP_DIGITS(&n) = 0;
 709     MP_DIGITS(&c) = 0;
 710     MP_DIGITS(&m) = 0;
 711     MP_DIGITS(&f) = 0;
 712     MP_DIGITS(&g) = 0;
 713     CHECK_MPI_OK( mp_init(&n) );
 714     CHECK_MPI_OK( mp_init(&c) );
 715     CHECK_MPI_OK( mp_init(&m) );
 716     CHECK_MPI_OK( mp_init(&f) );
 717     CHECK_MPI_OK( mp_init(&g) );
 718     SECITEM_TO_MPINT(key->modulus, &n);
 719     OCTETS_TO_MPINT(input, &c, modLen);
 720     /* If blinding, compute pre-image of ciphertext by multiplying by
 721     ** blinding factor
 722     */
 723     if (nssRSAUseBlinding) {
 724         CHECK_SEC_OK( get_blinding_params(key, &n, modLen, &f, &g) );
 725         /* c' = c*f mod n */
 726         CHECK_MPI_OK( mp_mulmod(&c, &f, &n, &c) );
 727     }
 728     /* Do the private key operation m = c**d mod n */
 729     if ( key->prime1.len      == 0 ||
 730          key->prime2.len      == 0 ||
 731          key->exponent1.len   == 0 ||
 732          key->exponent2.len   == 0 ||
 733          key->coefficient.len == 0) {
 734         CHECK_SEC_OK( rsa_PrivateKeyOpNoCRT(key, &m, &c, &n, modLen) );
 735     } else if (check) {
 736         CHECK_SEC_OK( rsa_PrivateKeyOpCRTCheckedPubKey(key, &m, &c) );
 737     } else {
 738         CHECK_SEC_OK( rsa_PrivateKeyOpCRTNoCheck(key, &m, &c) );
 739     }
 740     /* If blinding, compute post-image of plaintext by multiplying by
 741     ** blinding factor
 742     */
 743     if (nssRSAUseBlinding) {
 744         /* m = m'*g mod n */
 745         CHECK_MPI_OK( mp_mulmod(&m, &g, &n, &m) );
 746     }
 747     err = mp_to_fixlen_octets(&m, output, modLen);
 748     if (err >= 0) err = MP_OKAY;
 749 cleanup:
 750     mp_clear(&n);
 751     mp_clear(&c);
 752     mp_clear(&m);
 753     mp_clear(&f);
 754     mp_clear(&g);
 755     if (err) {
 756         MP_TO_SEC_ERROR(err);
 757         rv = SECFailure;
 758     }
 759     return rv;
 760 }
 761
 762 SECStatus
 763 RSA_PrivateKeyOp(RSAPrivateKey *key,
 764                  unsigned char *output,
 765                  const unsigned char *input)
 766 {
 767     return rsa_PrivateKeyOp(key, output, input, PR_FALSE);
 768 }
 769
 770 SECStatus
 771 RSA_PrivateKeyOpDoubleChecked(RSAPrivateKey *key,
 772                               unsigned char *output,
 773                               const unsigned char *input)
 774 {
 775     return rsa_PrivateKeyOp(key, output, input, PR_TRUE);
 776 }
 777
 778 static SECStatus
 779 swap_in_key_value(PRArenaPool *arena, mp_int *mpval, SECItem *buffer)
 780 {
 781     int len;
 782     mp_err err = MP_OKAY;
 783     memset(buffer->data, 0, buffer->len);
 784     len = mp_unsigned_octet_size(mpval);
 785     if (len <= 0) return SECFailure;
 786     if ((unsigned int)len <= buffer->len) {
 787         /* The new value is no longer than the old buffer, so use it */
 788         err = mp_to_unsigned_octets(mpval, buffer->data, len);
 789         if (err >= 0) err = MP_OKAY;
 790         buffer->len = len;
 791     } else if (arena) {
 792         /* The new value is longer, but working within an arena */
 793         (void)SECITEM_AllocItem(arena, buffer, len);
 794         err = mp_to_unsigned_octets(mpval, buffer->data, len);
 795         if (err >= 0) err = MP_OKAY;
 796     } else {
 797         /* The new value is longer, no arena, can't handle this key */
 798         return SECFailure;
 799     }
 800     return (err == MP_OKAY) ? SECSuccess : SECFailure;
 801 }
 802
 803 SECStatus
 804 RSA_PrivateKeyCheck(RSAPrivateKey *key)
 805 {
 806     mp_int p, q, n, psub1, qsub1, e, d, d_p, d_q, qInv, res;
 807     mp_err   err = MP_OKAY;
 808     SECStatus rv = SECSuccess;
 809     MP_DIGITS(&n)    = 0;
 810     MP_DIGITS(&psub1)= 0;
 811     MP_DIGITS(&qsub1)= 0;
 812     MP_DIGITS(&e)    = 0;
 813     MP_DIGITS(&d)    = 0;
 814     MP_DIGITS(&d_p)  = 0;
 815     MP_DIGITS(&d_q)  = 0;
 816     MP_DIGITS(&qInv) = 0;
 817     MP_DIGITS(&res)  = 0;
 818     CHECK_MPI_OK( mp_init(&n)    );
 819     CHECK_MPI_OK( mp_init(&p)    );
 820     CHECK_MPI_OK( mp_init(&q)    );
 821     CHECK_MPI_OK( mp_init(&psub1));
 822     CHECK_MPI_OK( mp_init(&qsub1));
 823     CHECK_MPI_OK( mp_init(&e)    );
 824     CHECK_MPI_OK( mp_init(&d)    );
 825     CHECK_MPI_OK( mp_init(&d_p)  );
 826     CHECK_MPI_OK( mp_init(&d_q)  );
 827     CHECK_MPI_OK( mp_init(&qInv) );
 828     CHECK_MPI_OK( mp_init(&res)  );
 829     SECITEM_TO_MPINT(key->modulus,         &n);
 830     SECITEM_TO_MPINT(key->prime1,          &p);
 831     SECITEM_TO_MPINT(key->prime2,          &q);
 832     SECITEM_TO_MPINT(key->publicExponent,  &e);
 833     SECITEM_TO_MPINT(key->privateExponent, &d);
 834     SECITEM_TO_MPINT(key->exponent1,       &d_p);
 835     SECITEM_TO_MPINT(key->exponent2,       &d_q);
 836     SECITEM_TO_MPINT(key->coefficient,     &qInv);
 837     /* p > q  */
 838     if (mp_cmp(&p, &q) <= 0) {
 839         /* mind the p's and q's (and d_p's and d_q's) */
 840         SECItem tmp;
 841         mp_exch(&p, &q);
 842         mp_exch(&d_p,&d_q);
 843         tmp = key->prime1;
 844         key->prime1 = key->prime2;
 845         key->prime2 = tmp;
 846         tmp = key->exponent1;
 847         key->exponent1 = key->exponent2;
 848         key->exponent2 = tmp;
 849     }
 850 #define VERIFY_MPI_EQUAL(m1, m2) \
 851     if (mp_cmp(m1, m2) != 0) {   \
 852         rv = SECFailure;         \
 853         goto cleanup;            \
 854     }
 855 #define VERIFY_MPI_EQUAL_1(m)    \
 856     if (mp_cmp_d(m, 1) != 0) {   \
 857         rv = SECFailure;         \
 858         goto cleanup;            \
 859     }
 860     /*
 861      * The following errors cannot be recovered from.
 862      */
 863     /* n == p * q */
 864     CHECK_MPI_OK( mp_mul(&p, &q, &res) );
 865     VERIFY_MPI_EQUAL(&res, &n);
 866     /* gcd(e, p-1) == 1 */
 867     CHECK_MPI_OK( mp_sub_d(&p, 1, &psub1) );
 868     CHECK_MPI_OK( mp_gcd(&e, &psub1, &res) );
 869     VERIFY_MPI_EQUAL_1(&res);
 870     /* gcd(e, q-1) == 1 */
 871     CHECK_MPI_OK( mp_sub_d(&q, 1, &qsub1) );
 872     CHECK_MPI_OK( mp_gcd(&e, &qsub1, &res) );
 873     VERIFY_MPI_EQUAL_1(&res);
 874     /* d*e == 1 mod p-1 */
 875     CHECK_MPI_OK( mp_mulmod(&d, &e, &psub1, &res) );
 876     VERIFY_MPI_EQUAL_1(&res);
 877     /* d*e == 1 mod q-1 */
 878     CHECK_MPI_OK( mp_mulmod(&d, &e, &qsub1, &res) );
 879     VERIFY_MPI_EQUAL_1(&res);
 880     /*
 881      * The following errors can be recovered from.
 882      */
 883     /* d_p == d mod p-1 */
 884     CHECK_MPI_OK( mp_mod(&d, &psub1, &res) );
 885     if (mp_cmp(&d_p, &res) != 0) {
 886         /* swap in the correct value */
 887         CHECK_SEC_OK( swap_in_key_value(key->arena, &res, &key->exponent1) );
 888     }
 889     /* d_q == d mod q-1 */
 890     CHECK_MPI_OK( mp_mod(&d, &qsub1, &res) );
 891     if (mp_cmp(&d_q, &res) != 0) {
 892         /* swap in the correct value */
 893         CHECK_SEC_OK( swap_in_key_value(key->arena, &res, &key->exponent2) );
 894     }
 895     /* q * q**-1 == 1 mod p */
 896     CHECK_MPI_OK( mp_mulmod(&q, &qInv, &p, &res) );
 897     if (mp_cmp_d(&res, 1) != 0) {
 898         /* compute the correct value */
 899         CHECK_MPI_OK( mp_invmod(&q, &p, &qInv) );
 900         CHECK_SEC_OK( swap_in_key_value(key->arena, &qInv, &key->coefficient) );
 901     }
 902 cleanup:
 903     mp_clear(&n);
 904     mp_clear(&p);
 905     mp_clear(&q);
 906     mp_clear(&psub1);
 907     mp_clear(&qsub1);
 908     mp_clear(&e);
 909     mp_clear(&d);
 910     mp_clear(&d_p);
 911     mp_clear(&d_q);
 912     mp_clear(&qInv);
 913     mp_clear(&res);
 914     if (err) {
 915         MP_TO_SEC_ERROR(err);
 916         rv = SECFailure;
 917     }
 918     return rv;
 919 }
 920
 921 /* cleanup at shutdown */
 922 void RSA_Cleanup(void)
 923 {
 924     if (!coBPInit.initialized)
 925         return;
 926
 927     while (!PR_CLIST_IS_EMPTY(&blindingParamsList.head))
 928     {
 929         struct RSABlindingParamsStr * rsabp = (struct RSABlindingParamsStr *)
 930             PR_LIST_HEAD(&blindingParamsList.head);
 931         PR_REMOVE_LINK(&rsabp->link);
 932         mp_clear(&rsabp->f);
 933         mp_clear(&rsabp->g);
 934         SECITEM_FreeItem(&rsabp->modulus,PR_FALSE);
 935         PORT_Free(rsabp);
 936     }
 937
 938     if (blindingParamsList.lock)
 939     {
 940         PZ_DestroyLock(blindingParamsList.lock);
 941         blindingParamsList.lock = NULL;
 942     }
 943
 944     coBPInit.initialized = 0;
 945     coBPInit.inProgress = 0;
 946     coBPInit.status = 0;
 947 }
 948
 949 /*
 950  * need a central place for this function to free up all the memory that
 951  * free_bl may have allocated along the way. Currently only RSA does this,
 952  * so I've put it here for now.
 953  */
 954 void BL_Cleanup(void)
 955 {
 956     RSA_Cleanup();
 957 }