← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/security/nss/lib/freebl/rsa.c

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

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