Coverage Report

Created: 2024-11-21 07:03

/src/nss-nspr/nss/lib/freebl/rsa.c
Line
Count
Source (jump to first uncovered line)
1
/* This Source Code Form is subject to the terms of the Mozilla Public
2
 * License, v. 2.0. If a copy of the MPL was not distributed with this
3
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5
/*
6
 * RSA key generation, public key op, private key op.
7
 */
8
#ifdef FREEBL_NO_DEPEND
9
#include "stubs.h"
10
#endif
11
12
#include "secerr.h"
13
14
#include "prclist.h"
15
#include "nssilock.h"
16
#include "prinit.h"
17
#include "blapi.h"
18
#include "mpi.h"
19
#include "mpprime.h"
20
#include "mplogic.h"
21
#include "secmpi.h"
22
#include "secitem.h"
23
#include "blapii.h"
24
25
/* The minimal required randomness is 64 bits */
26
/* EXP_BLINDING_RANDOMNESS_LEN is the length of the randomness in mp_digits */
27
/* for 32 bits platforts it is 2 mp_digits (= 2 * 32 bits), for 64 bits it is equal to 128 bits */
28
24
#define EXP_BLINDING_RANDOMNESS_LEN ((128 + MP_DIGIT_BIT - 1) / MP_DIGIT_BIT)
29
12
#define EXP_BLINDING_RANDOMNESS_LEN_BYTES (EXP_BLINDING_RANDOMNESS_LEN * sizeof(mp_digit))
30
31
/*
32
** Number of times to attempt to generate a prime (p or q) from a random
33
** seed (the seed changes for each iteration).
34
*/
35
0
#define MAX_PRIME_GEN_ATTEMPTS 10
36
/*
37
** Number of times to attempt to generate a key.  The primes p and q change
38
** for each attempt.
39
*/
40
#define MAX_KEY_GEN_ATTEMPTS 10
41
42
/* Blinding Parameters max cache size  */
43
44
#define RSA_BLINDING_PARAMS_MAX_CACHE_SIZE 20
44
45
/* exponent should not be greater than modulus */
46
#define BAD_RSA_KEY_SIZE(modLen, expLen)                           \
47
6
    ((expLen) > (modLen) || (modLen) > RSA_MAX_MODULUS_BITS / 8 || \
48
6
     (expLen) > RSA_MAX_EXPONENT_BITS / 8)
49
50
struct blindingParamsStr;
51
typedef struct blindingParamsStr blindingParams;
52
53
struct blindingParamsStr {
54
    blindingParams *next;
55
    mp_int f, g; /* blinding parameter                 */
56
    int counter; /* number of remaining uses of (f, g) */
57
};
58
59
/*
60
** RSABlindingParamsStr
61
**
62
** For discussion of Paul Kocher's timing attack against an RSA private key
63
** operation, see http://www.cryptography.com/timingattack/paper.html.  The
64
** countermeasure to this attack, known as blinding, is also discussed in
65
** the Handbook of Applied Cryptography, 11.118-11.119.
66
*/
67
struct RSABlindingParamsStr {
68
    /* Blinding-specific parameters */
69
    PRCList link;              /* link to list of structs            */
70
    SECItem modulus;           /* list element "key"                 */
71
    blindingParams *free, *bp; /* Blinding parameters queue          */
72
    blindingParams array[RSA_BLINDING_PARAMS_MAX_CACHE_SIZE];
73
    /* precalculate montegomery reduction value */
74
    mp_digit n0i; /* n0i = -( n & MP_DIGIT) ** -1 mod mp_RADIX */
75
};
76
typedef struct RSABlindingParamsStr RSABlindingParams;
77
78
/*
79
** RSABlindingParamsListStr
80
**
81
** List of key-specific blinding params.  The arena holds the volatile pool
82
** of memory for each entry and the list itself.  The lock is for list
83
** operations, in this case insertions and iterations, as well as control
84
** of the counter for each set of blinding parameters.
85
*/
86
struct RSABlindingParamsListStr {
87
    PZLock *lock;    /* Lock for the list   */
88
    PRCondVar *cVar; /* Condidtion Variable */
89
    int waitCount;   /* Number of threads waiting on cVar */
90
    PRCList head;    /* Pointer to the list */
91
};
92
93
/*
94
** The master blinding params list.
95
*/
96
static struct RSABlindingParamsListStr blindingParamsList = { 0 };
97
98
/* Number of times to reuse (f, g).  Suggested by Paul Kocher */
99
2
#define RSA_BLINDING_PARAMS_MAX_REUSE 50
100
101
/* Global, allows optional use of blinding.  On by default. */
102
/* Cannot be changed at the moment, due to thread-safety issues. */
103
static const PRBool nssRSAUseBlinding = PR_TRUE;
104
105
static SECStatus
106
rsa_build_from_primes(const mp_int *p, const mp_int *q,
107
                      mp_int *e, PRBool needPublicExponent,
108
                      mp_int *d, PRBool needPrivateExponent,
109
                      RSAPrivateKey *key, unsigned int keySizeInBits)
110
0
{
111
0
    mp_int n, phi;
112
0
    mp_int psub1, qsub1, tmp;
113
0
    mp_err err = MP_OKAY;
114
0
    SECStatus rv = SECSuccess;
115
0
    MP_DIGITS(&n) = 0;
116
0
    MP_DIGITS(&phi) = 0;
117
0
    MP_DIGITS(&psub1) = 0;
118
0
    MP_DIGITS(&qsub1) = 0;
119
0
    MP_DIGITS(&tmp) = 0;
120
0
    CHECK_MPI_OK(mp_init(&n));
121
0
    CHECK_MPI_OK(mp_init(&phi));
122
0
    CHECK_MPI_OK(mp_init(&psub1));
123
0
    CHECK_MPI_OK(mp_init(&qsub1));
124
0
    CHECK_MPI_OK(mp_init(&tmp));
125
    /* p and q must be distinct. */
126
0
    if (mp_cmp(p, q) == 0) {
127
0
        PORT_SetError(SEC_ERROR_NEED_RANDOM);
128
0
        rv = SECFailure;
129
0
        goto cleanup;
130
0
    }
131
    /* 1.  Compute n = p*q */
132
0
    CHECK_MPI_OK(mp_mul(p, q, &n));
133
    /*     verify that the modulus has the desired number of bits */
134
0
    if ((unsigned)mpl_significant_bits(&n) != keySizeInBits) {
135
0
        PORT_SetError(SEC_ERROR_NEED_RANDOM);
136
0
        rv = SECFailure;
137
0
        goto cleanup;
138
0
    }
139
140
    /* at least one exponent must be given */
141
0
    PORT_Assert(!(needPublicExponent && needPrivateExponent));
142
143
    /* 2.  Compute phi = (p-1)*(q-1) */
144
0
    CHECK_MPI_OK(mp_sub_d(p, 1, &psub1));
145
0
    CHECK_MPI_OK(mp_sub_d(q, 1, &qsub1));
146
0
    if (needPublicExponent || needPrivateExponent) {
147
0
        CHECK_MPI_OK(mp_lcm(&psub1, &qsub1, &phi));
148
        /* 3.  Compute d = e**-1 mod(phi) */
149
        /*     or      e = d**-1 mod(phi) as necessary */
150
0
        if (needPublicExponent) {
151
0
            err = mp_invmod(d, &phi, e);
152
0
        } else {
153
0
            err = mp_invmod(e, &phi, d);
154
0
        }
155
0
    } else {
156
0
        err = MP_OKAY;
157
0
    }
158
    /*     Verify that phi(n) and e have no common divisors */
159
0
    if (err != MP_OKAY) {
160
0
        if (err == MP_UNDEF) {
161
0
            PORT_SetError(SEC_ERROR_NEED_RANDOM);
162
0
            err = MP_OKAY; /* to keep PORT_SetError from being called again */
163
0
            rv = SECFailure;
164
0
        }
165
0
        goto cleanup;
166
0
    }
167
168
    /* 4.  Compute exponent1 = d mod (p-1) */
169
0
    CHECK_MPI_OK(mp_mod(d, &psub1, &tmp));
170
0
    MPINT_TO_SECITEM(&tmp, &key->exponent1, key->arena);
171
    /* 5.  Compute exponent2 = d mod (q-1) */
172
0
    CHECK_MPI_OK(mp_mod(d, &qsub1, &tmp));
173
0
    MPINT_TO_SECITEM(&tmp, &key->exponent2, key->arena);
174
    /* 6.  Compute coefficient = q**-1 mod p */
175
0
    CHECK_MPI_OK(mp_invmod(q, p, &tmp));
176
0
    MPINT_TO_SECITEM(&tmp, &key->coefficient, key->arena);
177
178
    /* copy our calculated results, overwrite what is there */
179
0
    key->modulus.data = NULL;
180
0
    MPINT_TO_SECITEM(&n, &key->modulus, key->arena);
181
0
    key->privateExponent.data = NULL;
182
0
    MPINT_TO_SECITEM(d, &key->privateExponent, key->arena);
183
0
    key->publicExponent.data = NULL;
184
0
    MPINT_TO_SECITEM(e, &key->publicExponent, key->arena);
185
0
    key->prime1.data = NULL;
186
0
    MPINT_TO_SECITEM(p, &key->prime1, key->arena);
187
0
    key->prime2.data = NULL;
188
0
    MPINT_TO_SECITEM(q, &key->prime2, key->arena);
189
0
cleanup:
190
0
    mp_clear(&n);
191
0
    mp_clear(&phi);
192
0
    mp_clear(&psub1);
193
0
    mp_clear(&qsub1);
194
0
    mp_clear(&tmp);
195
0
    if (err) {
196
0
        MP_TO_SEC_ERROR(err);
197
0
        rv = SECFailure;
198
0
    }
199
0
    return rv;
200
0
}
201
202
SECStatus
203
generate_prime(mp_int *prime, int primeLen)
204
0
{
205
0
    mp_err err = MP_OKAY;
206
0
    SECStatus rv = SECSuccess;
207
0
    int piter;
208
0
    unsigned char *pb = NULL;
209
0
    pb = PORT_Alloc(primeLen);
210
0
    if (!pb) {
211
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
212
0
        goto cleanup;
213
0
    }
214
0
    for (piter = 0; piter < MAX_PRIME_GEN_ATTEMPTS; piter++) {
215
0
        CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(pb, primeLen));
216
0
        pb[0] |= 0xC0;            /* set two high-order bits */
217
0
        pb[primeLen - 1] |= 0x01; /* set low-order bit       */
218
0
        CHECK_MPI_OK(mp_read_unsigned_octets(prime, pb, primeLen));
219
0
        err = mpp_make_prime_secure(prime, primeLen * 8, PR_FALSE);
220
0
        if (err != MP_NO)
221
0
            goto cleanup;
222
        /* keep going while err == MP_NO */
223
0
    }
224
0
cleanup:
225
0
    if (pb)
226
0
        PORT_ZFree(pb, primeLen);
227
0
    if (err) {
228
0
        MP_TO_SEC_ERROR(err);
229
0
        rv = SECFailure;
230
0
    }
231
0
    return rv;
232
0
}
233
234
/*
235
 *  make sure the key components meet fips186 requirements.
236
 */
237
static PRBool
238
rsa_fips186_verify(mp_int *p, mp_int *q, mp_int *d, int keySizeInBits)
239
0
{
240
0
    mp_int pq_diff;
241
0
    mp_err err = MP_OKAY;
242
0
    PRBool ret = PR_FALSE;
243
244
0
    if (keySizeInBits < 250) {
245
        /* not a valid FIPS length, no point in our other tests */
246
        /* if you are here, and in FIPS mode, you are outside the security
247
         * policy */
248
0
        return PR_TRUE;
249
0
    }
250
251
    /* p & q are already known to be greater then sqrt(2)*2^(keySize/2-1) */
252
    /* we also know that gcd(p-1,e) = 1 and gcd(q-1,e) = 1 because the
253
     * mp_invmod() function will fail. */
254
    /* now check p-q > 2^(keysize/2-100) */
255
0
    MP_DIGITS(&pq_diff) = 0;
256
0
    CHECK_MPI_OK(mp_init(&pq_diff));
257
    /* NSS always has p > q, so we know pq_diff is positive */
258
0
    CHECK_MPI_OK(mp_sub(p, q, &pq_diff));
259
0
    if ((unsigned)mpl_significant_bits(&pq_diff) < (keySizeInBits / 2 - 100)) {
260
0
        goto cleanup;
261
0
    }
262
    /* now verify d is large enough*/
263
0
    if ((unsigned)mpl_significant_bits(d) < (keySizeInBits / 2)) {
264
0
        goto cleanup;
265
0
    }
266
0
    ret = PR_TRUE;
267
268
0
cleanup:
269
0
    mp_clear(&pq_diff);
270
0
    return ret;
271
0
}
272
273
/*
274
** Generate and return a new RSA public and private key.
275
**  Both keys are encoded in a single RSAPrivateKey structure.
276
**  "cx" is the random number generator context
277
**  "keySizeInBits" is the size of the key to be generated, in bits.
278
**     512, 1024, etc.
279
**  "publicExponent" when not NULL is a pointer to some data that
280
**     represents the public exponent to use. The data is a byte
281
**     encoded integer, in "big endian" order.
282
*/
283
RSAPrivateKey *
284
RSA_NewKey(int keySizeInBits, SECItem *publicExponent)
285
0
{
286
0
    unsigned int primeLen;
287
0
    mp_int p = { 0, 0, 0, NULL };
288
0
    mp_int q = { 0, 0, 0, NULL };
289
0
    mp_int e = { 0, 0, 0, NULL };
290
0
    mp_int d = { 0, 0, 0, NULL };
291
0
    int kiter;
292
0
    int max_attempts;
293
0
    mp_err err = MP_OKAY;
294
0
    SECStatus rv = SECSuccess;
295
0
    int prerr = 0;
296
0
    RSAPrivateKey *key = NULL;
297
0
    PLArenaPool *arena = NULL;
298
    /* Require key size to be a multiple of 16 bits. */
299
0
    if (!publicExponent || keySizeInBits % 16 != 0 ||
300
0
        BAD_RSA_KEY_SIZE((unsigned int)keySizeInBits / 8, publicExponent->len)) {
301
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
302
0
        return NULL;
303
0
    }
304
    /* 1.  Set the public exponent and check if it's uneven and greater than 2.*/
305
0
    MP_DIGITS(&e) = 0;
306
0
    CHECK_MPI_OK(mp_init(&e));
307
0
    SECITEM_TO_MPINT(*publicExponent, &e);
308
0
    if (mp_iseven(&e) || !(mp_cmp_d(&e, 2) > 0)) {
309
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
310
0
        goto cleanup;
311
0
    }
312
0
#ifndef NSS_FIPS_DISABLED
313
    /* Check that the exponent is not smaller than 65537  */
314
0
    if (mp_cmp_d(&e, 0x10001) < 0) {
315
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
316
0
        goto cleanup;
317
0
    }
318
0
#endif
319
320
    /* 2. Allocate arena & key */
321
0
    arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
322
0
    if (!arena) {
323
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
324
0
        goto cleanup;
325
0
    }
326
0
    key = PORT_ArenaZNew(arena, RSAPrivateKey);
327
0
    if (!key) {
328
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
329
0
        goto cleanup;
330
0
    }
331
0
    key->arena = arena;
332
    /* length of primes p and q (in bytes) */
333
0
    primeLen = keySizeInBits / (2 * PR_BITS_PER_BYTE);
334
0
    MP_DIGITS(&p) = 0;
335
0
    MP_DIGITS(&q) = 0;
336
0
    MP_DIGITS(&d) = 0;
337
0
    CHECK_MPI_OK(mp_init(&p));
338
0
    CHECK_MPI_OK(mp_init(&q));
339
0
    CHECK_MPI_OK(mp_init(&d));
340
    /* 3.  Set the version number (PKCS1 v1.5 says it should be zero) */
341
0
    SECITEM_AllocItem(arena, &key->version, 1);
342
0
    key->version.data[0] = 0;
343
344
0
    kiter = 0;
345
0
    max_attempts = 5 * (keySizeInBits / 2); /* FIPS 186-4 B.3.3 steps 4.7 and 5.8 */
346
0
    do {
347
0
        PORT_SetError(0);
348
0
        CHECK_SEC_OK(generate_prime(&p, primeLen));
349
0
        CHECK_SEC_OK(generate_prime(&q, primeLen));
350
        /* Assure p > q */
351
        /* NOTE: PKCS #1 does not require p > q, and NSS doesn't use any
352
         * implementation optimization that requires p > q. We can remove
353
         * this code in the future.
354
         */
355
0
        if (mp_cmp(&p, &q) < 0)
356
0
            mp_exch(&p, &q);
357
        /* Attempt to use these primes to generate a key */
358
0
        rv = rsa_build_from_primes(&p, &q,
359
0
                                   &e, PR_FALSE, /* needPublicExponent=false */
360
0
                                   &d, PR_TRUE,  /* needPrivateExponent=true */
361
0
                                   key, keySizeInBits);
362
0
        if (rv == SECSuccess) {
363
0
            if (rsa_fips186_verify(&p, &q, &d, keySizeInBits)) {
364
0
                break;
365
0
            }
366
0
            prerr = SEC_ERROR_NEED_RANDOM; /* retry with different values */
367
0
        } else {
368
0
            prerr = PORT_GetError();
369
0
        }
370
0
        kiter++;
371
        /* loop until have primes */
372
0
    } while (prerr == SEC_ERROR_NEED_RANDOM && kiter < max_attempts);
373
374
0
cleanup:
375
0
    mp_clear(&p);
376
0
    mp_clear(&q);
377
0
    mp_clear(&e);
378
0
    mp_clear(&d);
379
0
    if (err) {
380
0
        MP_TO_SEC_ERROR(err);
381
0
        rv = SECFailure;
382
0
    }
383
0
    if (rv && arena) {
384
0
        PORT_FreeArena(arena, PR_TRUE);
385
0
        key = NULL;
386
0
    }
387
0
    return key;
388
0
}
389
390
mp_err
391
rsa_is_prime(mp_int *p)
392
0
{
393
0
    int res;
394
395
    /* run a Fermat test */
396
0
    res = mpp_fermat(p, 2);
397
0
    if (res != MP_OKAY) {
398
0
        return res;
399
0
    }
400
401
    /* If that passed, run some Miller-Rabin tests */
402
0
    res = mpp_pprime_secure(p, 2);
403
0
    return res;
404
0
}
405
406
/*
407
 * Factorize a RSA modulus n into p and q by using the exponents e and d.
408
 *
409
 * In: e, d, n
410
 * Out: p, q
411
 *
412
 * See Handbook of Applied Cryptography, 8.2.2(i).
413
 *
414
 * The algorithm is probabilistic, it is run 64 times and each run has a 50%
415
 * chance of succeeding with a runtime of O(log(e*d)).
416
 *
417
 * The returned p might be smaller than q.
418
 */
419
static mp_err
420
rsa_factorize_n_from_exponents(mp_int *e, mp_int *d, mp_int *p, mp_int *q,
421
                               mp_int *n)
422
0
{
423
    /* lambda is the private modulus: e*d = 1 mod lambda */
424
    /* so: e*d - 1 = k*lambda = t*2^s where t is odd */
425
0
    mp_int klambda;
426
0
    mp_int t, onetwentyeight;
427
0
    unsigned long s = 0;
428
0
    unsigned long i;
429
430
    /* cand = a^(t * 2^i) mod n, next_cand = a^(t * 2^(i+1)) mod n */
431
0
    mp_int a;
432
0
    mp_int cand;
433
0
    mp_int next_cand;
434
435
0
    mp_int n_minus_one;
436
0
    mp_err err = MP_OKAY;
437
438
0
    MP_DIGITS(&klambda) = 0;
439
0
    MP_DIGITS(&t) = 0;
440
0
    MP_DIGITS(&a) = 0;
441
0
    MP_DIGITS(&cand) = 0;
442
0
    MP_DIGITS(&n_minus_one) = 0;
443
0
    MP_DIGITS(&next_cand) = 0;
444
0
    MP_DIGITS(&onetwentyeight) = 0;
445
0
    CHECK_MPI_OK(mp_init(&klambda));
446
0
    CHECK_MPI_OK(mp_init(&t));
447
0
    CHECK_MPI_OK(mp_init(&a));
448
0
    CHECK_MPI_OK(mp_init(&cand));
449
0
    CHECK_MPI_OK(mp_init(&n_minus_one));
450
0
    CHECK_MPI_OK(mp_init(&next_cand));
451
0
    CHECK_MPI_OK(mp_init(&onetwentyeight));
452
453
0
    mp_set_int(&onetwentyeight, 128);
454
455
    /* calculate k*lambda = e*d - 1 */
456
0
    CHECK_MPI_OK(mp_mul(e, d, &klambda));
457
0
    CHECK_MPI_OK(mp_sub_d(&klambda, 1, &klambda));
458
459
    /* factorize klambda into t*2^s */
460
0
    CHECK_MPI_OK(mp_copy(&klambda, &t));
461
0
    while (mpp_divis_d(&t, 2) == MP_YES) {
462
0
        CHECK_MPI_OK(mp_div_2(&t, &t));
463
0
        s += 1;
464
0
    }
465
466
    /* precompute n_minus_one = n - 1 */
467
0
    CHECK_MPI_OK(mp_copy(n, &n_minus_one));
468
0
    CHECK_MPI_OK(mp_sub_d(&n_minus_one, 1, &n_minus_one));
469
470
    /* pick random bases a, each one has a 50% leading to a factorization */
471
0
    CHECK_MPI_OK(mp_set_int(&a, 2));
472
    /* The following is equivalent to for (a=2, a <= 128, a+=2) */
473
0
    while (mp_cmp(&a, &onetwentyeight) <= 0) {
474
        /* compute the base cand = a^(t * 2^0) [i = 0] */
475
0
        CHECK_MPI_OK(mp_exptmod(&a, &t, n, &cand));
476
477
0
        for (i = 0; i < s; i++) {
478
            /* condition 1: skip the base if we hit a trivial factor of n */
479
0
            if (mp_cmp(&cand, &n_minus_one) == 0 || mp_cmp_d(&cand, 1) == 0) {
480
0
                break;
481
0
            }
482
483
            /* increase i in a^(t * 2^i) by squaring the number */
484
0
            CHECK_MPI_OK(mp_exptmod_d(&cand, 2, n, &next_cand));
485
486
            /* condition 2: a^(t * 2^(i+1)) = 1 mod n */
487
0
            if (mp_cmp_d(&next_cand, 1) == 0) {
488
                /* conditions verified, gcd(a^(t * 2^i) - 1, n) is a factor */
489
0
                CHECK_MPI_OK(mp_sub_d(&cand, 1, &cand));
490
0
                CHECK_MPI_OK(mp_gcd(&cand, n, p));
491
0
                if (mp_cmp_d(p, 1) == 0) {
492
0
                    CHECK_MPI_OK(mp_add_d(&cand, 1, &cand));
493
0
                    break;
494
0
                }
495
0
                CHECK_MPI_OK(mp_div(n, p, q, NULL));
496
0
                goto cleanup;
497
0
            }
498
0
            CHECK_MPI_OK(mp_copy(&next_cand, &cand));
499
0
        }
500
501
0
        CHECK_MPI_OK(mp_add_d(&a, 2, &a));
502
0
    }
503
504
    /* if we reach here it's likely (2^64 - 1 / 2^64) that d is wrong */
505
0
    err = MP_RANGE;
506
507
0
cleanup:
508
0
    mp_clear(&klambda);
509
0
    mp_clear(&t);
510
0
    mp_clear(&a);
511
0
    mp_clear(&cand);
512
0
    mp_clear(&n_minus_one);
513
0
    mp_clear(&next_cand);
514
0
    mp_clear(&onetwentyeight);
515
0
    return err;
516
0
}
517
518
/*
519
 * Try to find the two primes based on 2 exponents plus a prime.
520
 *
521
 * In: e, d and p.
522
 * Out: p,q.
523
 *
524
 * Step 1, Since d = e**-1 mod phi, we know that d*e == 1 mod phi, or
525
 *  d*e = 1+k*phi, or d*e-1 = k*phi. since d is less than phi and e is
526
 *  usually less than d, then k must be an integer between e-1 and 1
527
 *  (probably on the order of e).
528
 * Step 1a, We can divide k*phi by prime-1 and get k*(q-1). This will reduce
529
 *      the size of our division through the rest of the loop.
530
 * Step 2, Loop through the values k=e-1 to 1 looking for k. k should be on
531
 *  the order or e, and e is typically small. This may take a while for
532
 *  a large random e. We are looking for a k that divides kphi
533
 *  evenly. Once we find a k that divides kphi evenly, we assume it
534
 *  is the true k. It's possible this k is not the 'true' k but has
535
 *  swapped factors of p-1 and/or q-1. Because of this, we
536
 *  tentatively continue Steps 3-6 inside this loop, and may return looking
537
 *  for another k on failure.
538
 * Step 3, Calculate our tentative phi=kphi/k. Note: real phi is (p-1)*(q-1).
539
 * Step 4a, kphi is k*(q-1), so phi is our tenative q-1. q = phi+1.
540
 *      If k is correct, q should be the right length and prime.
541
 * Step 4b, It's possible q-1 and k could have swapped factors. We now have a
542
 *  possible solution that meets our criteria. It may not be the only
543
 *      solution, however, so we keep looking. If we find more than one,
544
 *      we will fail since we cannot determine which is the correct
545
 *      solution, and returning the wrong modulus will compromise both
546
 *      moduli. If no other solution is found, we return the unique solution.
547
 *
548
 * This will return p & q. q may be larger than p in the case that p was given
549
 * and it was the smaller prime.
550
 */
551
static mp_err
552
rsa_get_prime_from_exponents(mp_int *e, mp_int *d, mp_int *p, mp_int *q,
553
                             mp_int *n, unsigned int keySizeInBits)
554
0
{
555
0
    mp_int kphi; /* k*phi */
556
0
    mp_int k;    /* current guess at 'k' */
557
0
    mp_int phi;  /* (p-1)(q-1) */
558
0
    mp_int r;    /* remainder */
559
0
    mp_int tmp;  /* p-1 if p is given */
560
0
    mp_err err = MP_OKAY;
561
0
    unsigned int order_k;
562
563
0
    MP_DIGITS(&kphi) = 0;
564
0
    MP_DIGITS(&phi) = 0;
565
0
    MP_DIGITS(&k) = 0;
566
0
    MP_DIGITS(&r) = 0;
567
0
    MP_DIGITS(&tmp) = 0;
568
0
    CHECK_MPI_OK(mp_init(&kphi));
569
0
    CHECK_MPI_OK(mp_init(&phi));
570
0
    CHECK_MPI_OK(mp_init(&k));
571
0
    CHECK_MPI_OK(mp_init(&r));
572
0
    CHECK_MPI_OK(mp_init(&tmp));
573
574
    /* our algorithm looks for a factor k whose maximum size is dependent
575
     * on the size of our smallest exponent, which had better be the public
576
     * exponent (if it's the private, the key is vulnerable to a brute force
577
     * attack).
578
     *
579
     * since our factor search is linear, we need to limit the maximum
580
     * size of the public key. this should not be a problem normally, since
581
     * public keys are usually small.
582
     *
583
     * if we want to handle larger public key sizes, we should have
584
     * a version which tries to 'completely' factor k*phi (where completely
585
     * means 'factor into primes, or composites with which are products of
586
     * large primes). Once we have all the factors, we can sort them out and
587
     * try different combinations to form our phi. The risk is if (p-1)/2,
588
     * (q-1)/2, and k are all large primes. In any case if the public key
589
     * is small (order of 20 some bits), then a linear search for k is
590
     * manageable.
591
     */
592
0
    if (mpl_significant_bits(e) > 23) {
593
0
        err = MP_RANGE;
594
0
        goto cleanup;
595
0
    }
596
597
    /* calculate k*phi = e*d - 1 */
598
0
    CHECK_MPI_OK(mp_mul(e, d, &kphi));
599
0
    CHECK_MPI_OK(mp_sub_d(&kphi, 1, &kphi));
600
601
    /* kphi is (e*d)-1, which is the same as k*(p-1)(q-1)
602
     * d < (p-1)(q-1), therefor k must be less than e-1
603
     * We can narrow down k even more, though. Since p and q are odd and both
604
     * have their high bit set, then we know that phi must be on order of
605
     * keySizeBits.
606
     */
607
0
    order_k = (unsigned)mpl_significant_bits(&kphi) - keySizeInBits;
608
609
0
    if (order_k <= 1) {
610
0
        err = MP_RANGE;
611
0
        goto cleanup;
612
0
    }
613
614
    /* for (k=kinit; order(k) >= order_k; k--) { */
615
    /* k=kinit: k can't be bigger than  kphi/2^(keySizeInBits -1) */
616
0
    CHECK_MPI_OK(mp_2expt(&k, keySizeInBits - 1));
617
0
    CHECK_MPI_OK(mp_div(&kphi, &k, &k, NULL));
618
0
    if (mp_cmp(&k, e) >= 0) {
619
        /* also can't be bigger then e-1 */
620
0
        CHECK_MPI_OK(mp_sub_d(e, 1, &k));
621
0
    }
622
623
    /* calculate our temp value */
624
    /* This saves recalculating this value when the k guess is wrong, which
625
     * is reasonably frequent. */
626
    /* tmp = p-1 (used to calculate q-1= phi/tmp) */
627
0
    CHECK_MPI_OK(mp_sub_d(p, 1, &tmp));
628
0
    CHECK_MPI_OK(mp_div(&kphi, &tmp, &kphi, &r));
629
0
    if (mp_cmp_z(&r) != 0) {
630
        /* p-1 doesn't divide kphi, some parameter wasn't correct */
631
0
        err = MP_RANGE;
632
0
        goto cleanup;
633
0
    }
634
0
    mp_zero(q);
635
    /* kphi is now k*(q-1) */
636
637
    /* rest of the for loop */
638
0
    for (; (err == MP_OKAY) && (mpl_significant_bits(&k) >= order_k);
639
0
         err = mp_sub_d(&k, 1, &k)) {
640
0
        CHECK_MPI_OK(err);
641
        /* looking for k as a factor of kphi */
642
0
        CHECK_MPI_OK(mp_div(&kphi, &k, &phi, &r));
643
0
        if (mp_cmp_z(&r) != 0) {
644
            /* not a factor, try the next one */
645
0
            continue;
646
0
        }
647
        /* we have a possible phi, see if it works */
648
0
        if ((unsigned)mpl_significant_bits(&phi) != keySizeInBits / 2) {
649
            /* phi is not the right size */
650
0
            continue;
651
0
        }
652
        /* phi should be divisible by 2, since
653
         * q is odd and phi=(q-1). */
654
0
        if (mpp_divis_d(&phi, 2) == MP_NO) {
655
            /* phi is not divisible by 4 */
656
0
            continue;
657
0
        }
658
        /* we now have a candidate for the second prime */
659
0
        CHECK_MPI_OK(mp_add_d(&phi, 1, &tmp));
660
661
        /* check to make sure it is prime */
662
0
        err = rsa_is_prime(&tmp);
663
0
        if (err != MP_OKAY) {
664
0
            if (err == MP_NO) {
665
                /* No, then we still have the wrong phi */
666
0
                continue;
667
0
            }
668
0
            goto cleanup;
669
0
        }
670
        /*
671
         * It is possible that we have the wrong phi if
672
         * k_guess*(q_guess-1) = k*(q-1) (k and q-1 have swapped factors).
673
         * since our q_quess is prime, however. We have found a valid
674
         * rsa key because:
675
         *   q is the correct order of magnitude.
676
         *   phi = (p-1)(q-1) where p and q are both primes.
677
         *   e*d mod phi = 1.
678
         * There is no way to know from the info given if this is the
679
         * original key. We never want to return the wrong key because if
680
         * two moduli with the same factor is known, then euclid's gcd
681
         * algorithm can be used to find that factor. Even though the
682
         * caller didn't pass the original modulus, it doesn't mean the
683
         * modulus wasn't known or isn't available somewhere. So to be safe
684
         * if we can't be sure we have the right q, we don't return any.
685
         *
686
         * So to make sure we continue looking for other valid q's. If none
687
         * are found, then we can safely return this one, otherwise we just
688
         * fail */
689
0
        if (mp_cmp_z(q) != 0) {
690
            /* this is the second valid q, don't return either,
691
             * just fail */
692
0
            err = MP_RANGE;
693
0
            break;
694
0
        }
695
        /* we only have one q so far, save it and if no others are found,
696
         * it's safe to return it */
697
0
        CHECK_MPI_OK(mp_copy(&tmp, q));
698
0
        continue;
699
0
    }
700
0
    if ((unsigned)mpl_significant_bits(&k) < order_k) {
701
0
        if (mp_cmp_z(q) == 0) {
702
            /* If we get here, something was wrong with the parameters we
703
             * were given */
704
0
            err = MP_RANGE;
705
0
        }
706
0
    }
707
0
cleanup:
708
0
    mp_clear(&kphi);
709
0
    mp_clear(&phi);
710
0
    mp_clear(&k);
711
0
    mp_clear(&r);
712
0
    mp_clear(&tmp);
713
0
    return err;
714
0
}
715
716
/*
717
 * take a private key with only a few elements and fill out the missing pieces.
718
 *
719
 * All the entries will be overwritten with data allocated out of the arena
720
 * If no arena is supplied, one will be created.
721
 *
722
 * The following fields must be supplied in order for this function
723
 * to succeed:
724
 *   one of either publicExponent or privateExponent
725
 *   two more of the following 5 parameters.
726
 *      modulus (n)
727
 *      prime1  (p)
728
 *      prime2  (q)
729
 *      publicExponent (e)
730
 *      privateExponent (d)
731
 *
732
 * NOTE: if only the publicExponent, privateExponent, and one prime is given,
733
 * then there may be more than one RSA key that matches that combination.
734
 *
735
 * All parameters will be replaced in the key structure with new parameters
736
 * Allocated out of the arena. There is no attempt to free the old structures.
737
 * Prime1 will always be greater than prime2 (even if the caller supplies the
738
 * smaller prime as prime1 or the larger prime as prime2). The parameters are
739
 * not overwritten on failure.
740
 *
741
 *  How it works:
742
 *     We can generate all the parameters from one of the exponents, plus the
743
 *        two primes. (rsa_build_key_from_primes)
744
 *     If we are given one of the exponents and both primes, we are done.
745
 *     If we are given one of the exponents, the modulus and one prime, we
746
 *        caclulate the second prime by dividing the modulus by the given
747
 *        prime, giving us an exponent and 2 primes.
748
 *     If we are given 2 exponents and one of the primes we calculate
749
 *        k*phi = d*e-1, where k is an integer less than d which
750
 *        divides d*e-1. We find factor k so we can isolate phi.
751
 *            phi = (p-1)(q-1)
752
 *        We can use phi to find the other prime as follows:
753
 *        q = (phi/(p-1)) + 1. We now have 2 primes and an exponent.
754
 *        (NOTE: if more then one prime meets this condition, the operation
755
 *        will fail. See comments elsewhere in this file about this).
756
 *        (rsa_get_prime_from_exponents)
757
 *     If we are given 2 exponents and the modulus we factor the modulus to
758
 *        get the 2 missing primes (rsa_factorize_n_from_exponents)
759
 *
760
 */
761
SECStatus
762
RSA_PopulatePrivateKey(RSAPrivateKey *key)
763
0
{
764
0
    PLArenaPool *arena = NULL;
765
0
    PRBool needPublicExponent = PR_TRUE;
766
0
    PRBool needPrivateExponent = PR_TRUE;
767
0
    PRBool hasModulus = PR_FALSE;
768
0
    unsigned int keySizeInBits = 0;
769
0
    int prime_count = 0;
770
    /* standard RSA nominclature */
771
0
    mp_int p, q, e, d, n;
772
    /* remainder */
773
0
    mp_int r;
774
0
    mp_err err = 0;
775
0
    SECStatus rv = SECFailure;
776
777
0
    MP_DIGITS(&p) = 0;
778
0
    MP_DIGITS(&q) = 0;
779
0
    MP_DIGITS(&e) = 0;
780
0
    MP_DIGITS(&d) = 0;
781
0
    MP_DIGITS(&n) = 0;
782
0
    MP_DIGITS(&r) = 0;
783
0
    CHECK_MPI_OK(mp_init(&p));
784
0
    CHECK_MPI_OK(mp_init(&q));
785
0
    CHECK_MPI_OK(mp_init(&e));
786
0
    CHECK_MPI_OK(mp_init(&d));
787
0
    CHECK_MPI_OK(mp_init(&n));
788
0
    CHECK_MPI_OK(mp_init(&r));
789
790
    /* if the key didn't already have an arena, create one. */
791
0
    if (key->arena == NULL) {
792
0
        arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
793
0
        if (!arena) {
794
0
            goto cleanup;
795
0
        }
796
0
        key->arena = arena;
797
0
    }
798
799
    /* load up the known exponents */
800
0
    if (key->publicExponent.data) {
801
0
        SECITEM_TO_MPINT(key->publicExponent, &e);
802
0
        needPublicExponent = PR_FALSE;
803
0
    }
804
0
    if (key->privateExponent.data) {
805
0
        SECITEM_TO_MPINT(key->privateExponent, &d);
806
0
        needPrivateExponent = PR_FALSE;
807
0
    }
808
0
    if (needPrivateExponent && needPublicExponent) {
809
        /* Not enough information, we need at least one exponent */
810
0
        err = MP_BADARG;
811
0
        goto cleanup;
812
0
    }
813
814
    /* load up the known primes. If only one prime is given, it will be
815
     * assigned 'p'. Once we have both primes, well make sure p is the larger.
816
     * The value prime_count tells us howe many we have acquired.
817
     */
818
0
    if (key->prime1.data) {
819
0
        int primeLen = key->prime1.len;
820
0
        if (key->prime1.data[0] == 0) {
821
0
            primeLen--;
822
0
        }
823
0
        keySizeInBits = primeLen * 2 * PR_BITS_PER_BYTE;
824
0
        SECITEM_TO_MPINT(key->prime1, &p);
825
0
        prime_count++;
826
0
    }
827
0
    if (key->prime2.data) {
828
0
        int primeLen = key->prime2.len;
829
0
        if (key->prime2.data[0] == 0) {
830
0
            primeLen--;
831
0
        }
832
0
        keySizeInBits = primeLen * 2 * PR_BITS_PER_BYTE;
833
0
        SECITEM_TO_MPINT(key->prime2, prime_count ? &q : &p);
834
0
        prime_count++;
835
0
    }
836
    /* load up the modulus */
837
0
    if (key->modulus.data) {
838
0
        int modLen = key->modulus.len;
839
0
        if (key->modulus.data[0] == 0) {
840
0
            modLen--;
841
0
        }
842
0
        keySizeInBits = modLen * PR_BITS_PER_BYTE;
843
0
        SECITEM_TO_MPINT(key->modulus, &n);
844
0
        hasModulus = PR_TRUE;
845
0
    }
846
    /* if we have the modulus and one prime, calculate the second. */
847
0
    if ((prime_count == 1) && (hasModulus)) {
848
0
        if (mp_div(&n, &p, &q, &r) != MP_OKAY || mp_cmp_z(&r) != 0) {
849
            /* p is not a factor or n, fail */
850
0
            err = MP_BADARG;
851
0
            goto cleanup;
852
0
        }
853
0
        prime_count++;
854
0
    }
855
856
    /* If we didn't have enough primes try to calculate the primes from
857
     * the exponents */
858
0
    if (prime_count < 2) {
859
        /* if we don't have at least 2 primes at this point, then we need both
860
         * exponents and one prime or a modulus*/
861
0
        if (!needPublicExponent && !needPrivateExponent &&
862
0
            (prime_count > 0)) {
863
0
            CHECK_MPI_OK(rsa_get_prime_from_exponents(&e, &d, &p, &q, &n,
864
0
                                                      keySizeInBits));
865
0
        } else if (!needPublicExponent && !needPrivateExponent && hasModulus) {
866
0
            CHECK_MPI_OK(rsa_factorize_n_from_exponents(&e, &d, &p, &q, &n));
867
0
        } else {
868
            /* not enough given parameters to get both primes */
869
0
            err = MP_BADARG;
870
0
            goto cleanup;
871
0
        }
872
0
    }
873
874
    /* Assure p > q */
875
    /* NOTE: PKCS #1 does not require p > q, and NSS doesn't use any
876
     * implementation optimization that requires p > q. We can remove
877
     * this code in the future.
878
     */
879
0
    if (mp_cmp(&p, &q) < 0)
880
0
        mp_exch(&p, &q);
881
882
    /* we now have our 2 primes and at least one exponent, we can fill
883
     * in the key */
884
0
    rv = rsa_build_from_primes(&p, &q,
885
0
                               &e, needPublicExponent,
886
0
                               &d, needPrivateExponent,
887
0
                               key, keySizeInBits);
888
0
cleanup:
889
0
    mp_clear(&p);
890
0
    mp_clear(&q);
891
0
    mp_clear(&e);
892
0
    mp_clear(&d);
893
0
    mp_clear(&n);
894
0
    mp_clear(&r);
895
0
    if (err) {
896
0
        MP_TO_SEC_ERROR(err);
897
0
        rv = SECFailure;
898
0
    }
899
0
    if (rv && arena) {
900
0
        PORT_FreeArena(arena, PR_TRUE);
901
0
        key->arena = NULL;
902
0
    }
903
0
    return rv;
904
0
}
905
906
static unsigned int
907
rsa_modulusLen(SECItem *modulus)
908
18
{
909
18
    if (modulus->len == 0) {
910
0
        return 0;
911
18
    };
912
18
    unsigned char byteZero = modulus->data[0];
913
18
    unsigned int modLen = modulus->len - !byteZero;
914
18
    return modLen;
915
18
}
916
917
/*
918
** Perform a raw public-key operation
919
**  Length of input and output buffers are equal to key's modulus len.
920
*/
921
SECStatus
922
RSA_PublicKeyOp(RSAPublicKey *key,
923
                unsigned char *output,
924
                const unsigned char *input)
925
6
{
926
6
    unsigned int modLen, expLen, offset;
927
6
    mp_int n, e, m, c;
928
6
    mp_err err = MP_OKAY;
929
6
    SECStatus rv = SECSuccess;
930
6
    if (!key || !output || !input) {
931
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
932
0
        return SECFailure;
933
0
    }
934
6
    MP_DIGITS(&n) = 0;
935
6
    MP_DIGITS(&e) = 0;
936
6
    MP_DIGITS(&m) = 0;
937
6
    MP_DIGITS(&c) = 0;
938
6
    CHECK_MPI_OK(mp_init(&n));
939
6
    CHECK_MPI_OK(mp_init(&e));
940
6
    CHECK_MPI_OK(mp_init(&m));
941
6
    CHECK_MPI_OK(mp_init(&c));
942
6
    modLen = rsa_modulusLen(&key->modulus);
943
6
    expLen = rsa_modulusLen(&key->publicExponent);
944
945
6
    if (modLen == 0) {
946
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
947
0
        rv = SECFailure;
948
0
        goto cleanup;
949
0
    }
950
951
    /* 1.  Obtain public key (n, e) */
952
6
    if (BAD_RSA_KEY_SIZE(modLen, expLen)) {
953
0
        PORT_SetError(SEC_ERROR_INVALID_KEY);
954
0
        rv = SECFailure;
955
0
        goto cleanup;
956
0
    }
957
6
    SECITEM_TO_MPINT(key->modulus, &n);
958
6
    SECITEM_TO_MPINT(key->publicExponent, &e);
959
6
    if (e.used > n.used) {
960
        /* exponent should not be greater than modulus */
961
0
        PORT_SetError(SEC_ERROR_INVALID_KEY);
962
0
        rv = SECFailure;
963
0
        goto cleanup;
964
0
    }
965
    /* 2. check input out of range (needs to be in range [0..n-1]) */
966
6
    offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
967
6
    if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
968
0
        PORT_SetError(SEC_ERROR_INPUT_LEN);
969
0
        rv = SECFailure;
970
0
        goto cleanup;
971
0
    }
972
    /* 2 bis.  Represent message as integer in range [0..n-1] */
973
6
    CHECK_MPI_OK(mp_read_unsigned_octets(&m, input, modLen));
974
/* 3.  Compute c = m**e mod n */
975
#ifdef USE_MPI_EXPT_D
976
    /* XXX see which is faster */
977
    if (MP_USED(&e) == 1) {
978
        CHECK_MPI_OK(mp_exptmod_d(&m, MP_DIGIT(&e, 0), &n, &c));
979
    } else
980
#endif
981
6
        CHECK_MPI_OK(mp_exptmod(&m, &e, &n, &c));
982
    /* 4.  result c is ciphertext */
983
6
    err = mp_to_fixlen_octets(&c, output, modLen);
984
6
    if (err >= 0)
985
6
        err = MP_OKAY;
986
6
cleanup:
987
6
    mp_clear(&n);
988
6
    mp_clear(&e);
989
6
    mp_clear(&m);
990
6
    mp_clear(&c);
991
6
    if (err) {
992
0
        MP_TO_SEC_ERROR(err);
993
0
        rv = SECFailure;
994
0
    }
995
6
    return rv;
996
6
}
997
998
/*
999
**  RSA Private key operation (no CRT).
1000
*/
1001
static SECStatus
1002
rsa_PrivateKeyOpNoCRT(RSAPrivateKey *key, mp_int *m, mp_int *c, mp_int *n,
1003
                      unsigned int modLen)
1004
0
{
1005
0
    mp_int d;
1006
0
    mp_err err = MP_OKAY;
1007
0
    SECStatus rv = SECSuccess;
1008
0
    MP_DIGITS(&d) = 0;
1009
0
    CHECK_MPI_OK(mp_init(&d));
1010
0
    SECITEM_TO_MPINT(key->privateExponent, &d);
1011
    /* 1. m = c**d mod n */
1012
0
    CHECK_MPI_OK(mp_exptmod(c, &d, n, m));
1013
0
cleanup:
1014
0
    mp_clear(&d);
1015
0
    if (err) {
1016
0
        MP_TO_SEC_ERROR(err);
1017
0
        rv = SECFailure;
1018
0
    }
1019
0
    return rv;
1020
0
}
1021
1022
/*
1023
**  RSA Private key operation using CRT.
1024
*/
1025
static SECStatus
1026
rsa_PrivateKeyOpCRTNoCheck(RSAPrivateKey *key, mp_int *m, mp_int *c)
1027
6
{
1028
6
    mp_int p, q, d_p, d_q, qInv;
1029
    /*
1030
            The length of the randomness comes from the papers:
1031
            https://link.springer.com/chapter/10.1007/978-3-642-29912-4_7
1032
            https://link.springer.com/chapter/10.1007/978-3-642-21554-4_5.
1033
        */
1034
6
    mp_int blinding_dp, blinding_dq, r1, r2;
1035
6
    unsigned char random_block[EXP_BLINDING_RANDOMNESS_LEN_BYTES];
1036
6
    mp_int m1, m2, h, ctmp;
1037
6
    mp_err err = MP_OKAY;
1038
6
    SECStatus rv = SECSuccess;
1039
6
    MP_DIGITS(&p) = 0;
1040
6
    MP_DIGITS(&q) = 0;
1041
6
    MP_DIGITS(&d_p) = 0;
1042
6
    MP_DIGITS(&d_q) = 0;
1043
6
    MP_DIGITS(&qInv) = 0;
1044
6
    MP_DIGITS(&m1) = 0;
1045
6
    MP_DIGITS(&m2) = 0;
1046
6
    MP_DIGITS(&h) = 0;
1047
6
    MP_DIGITS(&ctmp) = 0;
1048
6
    MP_DIGITS(&blinding_dp) = 0;
1049
6
    MP_DIGITS(&blinding_dq) = 0;
1050
6
    MP_DIGITS(&r1) = 0;
1051
6
    MP_DIGITS(&r2) = 0;
1052
1053
6
    CHECK_MPI_OK(mp_init(&p));
1054
6
    CHECK_MPI_OK(mp_init(&q));
1055
6
    CHECK_MPI_OK(mp_init(&d_p));
1056
6
    CHECK_MPI_OK(mp_init(&d_q));
1057
6
    CHECK_MPI_OK(mp_init(&qInv));
1058
6
    CHECK_MPI_OK(mp_init(&m1));
1059
6
    CHECK_MPI_OK(mp_init(&m2));
1060
6
    CHECK_MPI_OK(mp_init(&h));
1061
6
    CHECK_MPI_OK(mp_init(&ctmp));
1062
6
    CHECK_MPI_OK(mp_init(&blinding_dp));
1063
6
    CHECK_MPI_OK(mp_init(&blinding_dq));
1064
6
    CHECK_MPI_OK(mp_init_size(&r1, EXP_BLINDING_RANDOMNESS_LEN));
1065
6
    CHECK_MPI_OK(mp_init_size(&r2, EXP_BLINDING_RANDOMNESS_LEN));
1066
1067
    /* copy private key parameters into mp integers */
1068
6
    SECITEM_TO_MPINT(key->prime1, &p);         /* p */
1069
6
    SECITEM_TO_MPINT(key->prime2, &q);         /* q */
1070
6
    SECITEM_TO_MPINT(key->exponent1, &d_p);    /* d_p  = d mod (p-1) */
1071
6
    SECITEM_TO_MPINT(key->exponent2, &d_q);    /* d_q  = d mod (q-1) */
1072
6
    SECITEM_TO_MPINT(key->coefficient, &qInv); /* qInv = q**-1 mod p */
1073
1074
    // blinding_dp = 1
1075
6
    CHECK_MPI_OK(mp_set_int(&blinding_dp, 1));
1076
    // blinding_dp = p - 1
1077
6
    CHECK_MPI_OK(mp_sub(&p, &blinding_dp, &blinding_dp));
1078
    // generating a random value
1079
6
    RNG_GenerateGlobalRandomBytes(random_block, EXP_BLINDING_RANDOMNESS_LEN_BYTES);
1080
6
    MP_USED(&r1) = EXP_BLINDING_RANDOMNESS_LEN;
1081
6
    memcpy(MP_DIGITS(&r1), random_block, sizeof(random_block));
1082
    // blinding_dp = random * (p - 1)
1083
6
    CHECK_MPI_OK(mp_mul(&blinding_dp, &r1, &blinding_dp));
1084
    // d_p = d_p + random * (p - 1)
1085
6
    CHECK_MPI_OK(mp_add(&d_p, &blinding_dp, &d_p));
1086
1087
    // blinding_dq = 1
1088
6
    CHECK_MPI_OK(mp_set_int(&blinding_dq, 1));
1089
    // blinding_dq = q - 1
1090
6
    CHECK_MPI_OK(mp_sub(&q, &blinding_dq, &blinding_dq));
1091
    // generating a random value
1092
6
    RNG_GenerateGlobalRandomBytes(random_block, EXP_BLINDING_RANDOMNESS_LEN_BYTES);
1093
6
    memcpy(MP_DIGITS(&r2), random_block, sizeof(random_block));
1094
6
    MP_USED(&r2) = EXP_BLINDING_RANDOMNESS_LEN;
1095
    // blinding_dq = random * (q - 1)
1096
6
    CHECK_MPI_OK(mp_mul(&blinding_dq, &r2, &blinding_dq));
1097
    // d_q = d_q + random * (q-1)
1098
6
    CHECK_MPI_OK(mp_add(&d_q, &blinding_dq, &d_q));
1099
1100
    /* 1. m1 = c**d_p mod p */
1101
6
    CHECK_MPI_OK(mp_mod(c, &p, &ctmp));
1102
6
    CHECK_MPI_OK(mp_exptmod(&ctmp, &d_p, &p, &m1));
1103
    /* 2. m2 = c**d_q mod q */
1104
6
    CHECK_MPI_OK(mp_mod(c, &q, &ctmp));
1105
6
    CHECK_MPI_OK(mp_exptmod(&ctmp, &d_q, &q, &m2));
1106
    /* 3.  h = (m1 - m2) * qInv mod p */
1107
6
    CHECK_MPI_OK(mp_submod(&m1, &m2, &p, &h));
1108
6
    CHECK_MPI_OK(mp_mulmod(&h, &qInv, &p, &h));
1109
    /* 4.  m = m2 + h * q */
1110
6
    CHECK_MPI_OK(mp_mul(&h, &q, m));
1111
6
    CHECK_MPI_OK(mp_add(m, &m2, m));
1112
6
cleanup:
1113
6
    mp_clear(&p);
1114
6
    mp_clear(&q);
1115
6
    mp_clear(&d_p);
1116
6
    mp_clear(&d_q);
1117
6
    mp_clear(&qInv);
1118
6
    mp_clear(&m1);
1119
6
    mp_clear(&m2);
1120
6
    mp_clear(&h);
1121
6
    mp_clear(&ctmp);
1122
6
    mp_clear(&blinding_dp);
1123
6
    mp_clear(&blinding_dq);
1124
6
    mp_clear(&r1);
1125
6
    mp_clear(&r2);
1126
6
    if (err) {
1127
0
        MP_TO_SEC_ERROR(err);
1128
0
        rv = SECFailure;
1129
0
    }
1130
6
    return rv;
1131
6
}
1132
1133
/*
1134
** An attack against RSA CRT was described by Boneh, DeMillo, and Lipton in:
1135
** "On the Importance of Eliminating Errors in Cryptographic Computations",
1136
** http://theory.stanford.edu/~dabo/papers/faults.ps.gz
1137
**
1138
** As a defense against the attack, carry out the private key operation,
1139
** followed up with a public key operation to invert the result.
1140
** Verify that result against the input.
1141
*/
1142
static SECStatus
1143
rsa_PrivateKeyOpCRTCheckedPubKey(RSAPrivateKey *key, mp_int *m, mp_int *c)
1144
6
{
1145
6
    mp_int n, e, v;
1146
6
    mp_err err = MP_OKAY;
1147
6
    SECStatus rv = SECSuccess;
1148
6
    MP_DIGITS(&n) = 0;
1149
6
    MP_DIGITS(&e) = 0;
1150
6
    MP_DIGITS(&v) = 0;
1151
6
    CHECK_MPI_OK(mp_init(&n));
1152
6
    CHECK_MPI_OK(mp_init(&e));
1153
6
    CHECK_MPI_OK(mp_init(&v));
1154
6
    CHECK_SEC_OK(rsa_PrivateKeyOpCRTNoCheck(key, m, c));
1155
6
    SECITEM_TO_MPINT(key->modulus, &n);
1156
6
    SECITEM_TO_MPINT(key->publicExponent, &e);
1157
    /* Perform a public key operation v = m ** e mod n */
1158
6
    CHECK_MPI_OK(mp_exptmod(m, &e, &n, &v));
1159
6
    if (mp_cmp(&v, c) != 0) {
1160
0
        rv = SECFailure;
1161
0
    }
1162
6
cleanup:
1163
6
    mp_clear(&n);
1164
6
    mp_clear(&e);
1165
6
    mp_clear(&v);
1166
6
    if (err) {
1167
0
        MP_TO_SEC_ERROR(err);
1168
0
        rv = SECFailure;
1169
0
    }
1170
6
    return rv;
1171
6
}
1172
1173
static PRCallOnceType coBPInit = { 0, 0, 0 };
1174
static PRStatus
1175
init_blinding_params_list(void)
1176
2
{
1177
2
    blindingParamsList.lock = PZ_NewLock(nssILockOther);
1178
2
    if (!blindingParamsList.lock) {
1179
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
1180
0
        return PR_FAILURE;
1181
0
    }
1182
2
    blindingParamsList.cVar = PR_NewCondVar(blindingParamsList.lock);
1183
2
    if (!blindingParamsList.cVar) {
1184
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
1185
0
        return PR_FAILURE;
1186
0
    }
1187
2
    blindingParamsList.waitCount = 0;
1188
2
    PR_INIT_CLIST(&blindingParamsList.head);
1189
2
    return PR_SUCCESS;
1190
2
}
1191
1192
static SECStatus
1193
generate_blinding_params(RSAPrivateKey *key, mp_int *f, mp_int *g, mp_int *n,
1194
                         unsigned int modLen)
1195
2
{
1196
2
    SECStatus rv = SECSuccess;
1197
2
    mp_int e, k;
1198
2
    mp_err err = MP_OKAY;
1199
2
    unsigned char *kb = NULL;
1200
1201
2
    MP_DIGITS(&e) = 0;
1202
2
    MP_DIGITS(&k) = 0;
1203
2
    CHECK_MPI_OK(mp_init(&e));
1204
2
    CHECK_MPI_OK(mp_init(&k));
1205
2
    SECITEM_TO_MPINT(key->publicExponent, &e);
1206
    /* generate random k < n */
1207
2
    kb = PORT_Alloc(modLen);
1208
2
    if (!kb) {
1209
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
1210
0
        goto cleanup;
1211
0
    }
1212
2
    CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(kb, modLen));
1213
2
    CHECK_MPI_OK(mp_read_unsigned_octets(&k, kb, modLen));
1214
    /* k < n */
1215
2
    CHECK_MPI_OK(mp_mod(&k, n, &k));
1216
    /* f = k**e mod n */
1217
2
    CHECK_MPI_OK(mp_exptmod(&k, &e, n, f));
1218
    /* g = k**-1 mod n */
1219
2
    CHECK_MPI_OK(mp_invmod(&k, n, g));
1220
    /* g in montgomery form.. */
1221
2
    CHECK_MPI_OK(mp_to_mont(g, n, g));
1222
2
cleanup:
1223
2
    if (kb)
1224
2
        PORT_ZFree(kb, modLen);
1225
2
    mp_clear(&k);
1226
2
    mp_clear(&e);
1227
2
    if (err) {
1228
0
        MP_TO_SEC_ERROR(err);
1229
0
        rv = SECFailure;
1230
0
    }
1231
2
    return rv;
1232
2
}
1233
1234
static SECStatus
1235
init_blinding_params(RSABlindingParams *rsabp, RSAPrivateKey *key,
1236
                     mp_int *n, unsigned int modLen)
1237
2
{
1238
2
    blindingParams *bp = rsabp->array;
1239
2
    int i = 0;
1240
1241
    /* Initialize the list pointer for the element */
1242
2
    PR_INIT_CLIST(&rsabp->link);
1243
42
    for (i = 0; i < RSA_BLINDING_PARAMS_MAX_CACHE_SIZE; ++i, ++bp) {
1244
40
        bp->next = bp + 1;
1245
40
        MP_DIGITS(&bp->f) = 0;
1246
40
        MP_DIGITS(&bp->g) = 0;
1247
40
        bp->counter = 0;
1248
40
    }
1249
    /* The last bp->next value was initialized with out
1250
     * of rsabp->array pointer and must be set to NULL
1251
     */
1252
2
    rsabp->array[RSA_BLINDING_PARAMS_MAX_CACHE_SIZE - 1].next = NULL;
1253
1254
2
    bp = rsabp->array;
1255
2
    rsabp->bp = NULL;
1256
2
    rsabp->free = bp;
1257
1258
    /* precalculate montgomery reduction parameter */
1259
2
    rsabp->n0i = mp_calculate_mont_n0i(n);
1260
1261
    /* List elements are keyed using the modulus */
1262
2
    return SECITEM_CopyItem(NULL, &rsabp->modulus, &key->modulus);
1263
2
}
1264
1265
static SECStatus
1266
get_blinding_params(RSAPrivateKey *key, mp_int *n, unsigned int modLen,
1267
                    mp_int *f, mp_int *g, mp_digit *n0i)
1268
6
{
1269
6
    RSABlindingParams *rsabp = NULL;
1270
6
    blindingParams *bpUnlinked = NULL;
1271
6
    blindingParams *bp;
1272
6
    PRCList *el;
1273
6
    SECStatus rv = SECSuccess;
1274
6
    mp_err err = MP_OKAY;
1275
6
    int cmp = -1;
1276
6
    PRBool holdingLock = PR_FALSE;
1277
1278
6
    do {
1279
6
        if (blindingParamsList.lock == NULL) {
1280
0
            PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
1281
0
            return SECFailure;
1282
0
        }
1283
        /* Acquire the list lock */
1284
6
        PZ_Lock(blindingParamsList.lock);
1285
6
        holdingLock = PR_TRUE;
1286
1287
        /* Walk the list looking for the private key */
1288
6
        for (el = PR_NEXT_LINK(&blindingParamsList.head);
1289
6
             el != &blindingParamsList.head;
1290
6
             el = PR_NEXT_LINK(el)) {
1291
4
            rsabp = (RSABlindingParams *)el;
1292
4
            cmp = SECITEM_CompareItem(&rsabp->modulus, &key->modulus);
1293
4
            if (cmp >= 0) {
1294
                /* The key is found or not in the list. */
1295
4
                break;
1296
4
            }
1297
4
        }
1298
1299
6
        if (cmp) {
1300
            /* At this point, the key is not in the list.  el should point to
1301
            ** the list element before which this key should be inserted.
1302
            */
1303
2
            rsabp = PORT_ZNew(RSABlindingParams);
1304
2
            if (!rsabp) {
1305
0
                PORT_SetError(SEC_ERROR_NO_MEMORY);
1306
0
                goto cleanup;
1307
0
            }
1308
1309
2
            rv = init_blinding_params(rsabp, key, n, modLen);
1310
2
            if (rv != SECSuccess) {
1311
0
                PORT_ZFree(rsabp, sizeof(RSABlindingParams));
1312
0
                goto cleanup;
1313
0
            }
1314
1315
            /* Insert the new element into the list
1316
            ** If inserting in the middle of the list, el points to the link
1317
            ** to insert before.  Otherwise, the link needs to be appended to
1318
            ** the end of the list, which is the same as inserting before the
1319
            ** head (since el would have looped back to the head).
1320
            */
1321
2
            PR_INSERT_BEFORE(&rsabp->link, el);
1322
2
        }
1323
1324
        /* We've found (or created) the RSAblindingParams struct for this key.
1325
         * Now, search its list of ready blinding params for a usable one.
1326
         */
1327
6
        *n0i = rsabp->n0i;
1328
6
        while (0 != (bp = rsabp->bp)) {
1329
#ifdef UNSAFE_FUZZER_MODE
1330
            /* Found a match and there are still remaining uses left */
1331
            /* Return the parameters */
1332
            CHECK_MPI_OK(mp_copy(&bp->f, f));
1333
            CHECK_MPI_OK(mp_copy(&bp->g, g));
1334
1335
            PZ_Unlock(blindingParamsList.lock);
1336
            return SECSuccess;
1337
#else
1338
4
            if (--(bp->counter) > 0) {
1339
                /* Found a match and there are still remaining uses left */
1340
                /* Return the parameters */
1341
4
                CHECK_MPI_OK(mp_copy(&bp->f, f));
1342
4
                CHECK_MPI_OK(mp_copy(&bp->g, g));
1343
1344
4
                PZ_Unlock(blindingParamsList.lock);
1345
4
                return SECSuccess;
1346
4
            }
1347
            /* exhausted this one, give its values to caller, and
1348
             * then retire it.
1349
             */
1350
0
            mp_exch(&bp->f, f);
1351
0
            mp_exch(&bp->g, g);
1352
0
            mp_clear(&bp->f);
1353
0
            mp_clear(&bp->g);
1354
0
            bp->counter = 0;
1355
            /* Move to free list */
1356
0
            rsabp->bp = bp->next;
1357
0
            bp->next = rsabp->free;
1358
0
            rsabp->free = bp;
1359
            /* In case there're threads waiting for new blinding
1360
             * value - notify 1 thread the value is ready
1361
             */
1362
0
            if (blindingParamsList.waitCount > 0) {
1363
0
                PR_NotifyCondVar(blindingParamsList.cVar);
1364
0
                blindingParamsList.waitCount--;
1365
0
            }
1366
0
            PZ_Unlock(blindingParamsList.lock);
1367
0
            return SECSuccess;
1368
4
#endif
1369
4
        }
1370
        /* We did not find a usable set of blinding params.  Can we make one? */
1371
        /* Find a free bp struct. */
1372
2
        if ((bp = rsabp->free) != NULL) {
1373
            /* unlink this bp */
1374
2
            rsabp->free = bp->next;
1375
2
            bp->next = NULL;
1376
2
            bpUnlinked = bp; /* In case we fail */
1377
1378
2
            PZ_Unlock(blindingParamsList.lock);
1379
2
            holdingLock = PR_FALSE;
1380
            /* generate blinding parameter values for the current thread */
1381
2
            CHECK_SEC_OK(generate_blinding_params(key, f, g, n, modLen));
1382
1383
            /* put the blinding parameter values into cache */
1384
2
            CHECK_MPI_OK(mp_init(&bp->f));
1385
2
            CHECK_MPI_OK(mp_init(&bp->g));
1386
2
            CHECK_MPI_OK(mp_copy(f, &bp->f));
1387
2
            CHECK_MPI_OK(mp_copy(g, &bp->g));
1388
1389
            /* Put this at head of queue of usable params. */
1390
2
            PZ_Lock(blindingParamsList.lock);
1391
2
            holdingLock = PR_TRUE;
1392
2
            (void)holdingLock;
1393
            /* initialize RSABlindingParamsStr */
1394
2
            bp->counter = RSA_BLINDING_PARAMS_MAX_REUSE;
1395
2
            bp->next = rsabp->bp;
1396
2
            rsabp->bp = bp;
1397
2
            bpUnlinked = NULL;
1398
            /* In case there're threads waiting for new blinding value
1399
             * just notify them the value is ready
1400
             */
1401
2
            if (blindingParamsList.waitCount > 0) {
1402
0
                PR_NotifyAllCondVar(blindingParamsList.cVar);
1403
0
                blindingParamsList.waitCount = 0;
1404
0
            }
1405
2
            PZ_Unlock(blindingParamsList.lock);
1406
2
            return SECSuccess;
1407
2
        }
1408
        /* Here, there are no usable blinding parameters available,
1409
         * and no free bp blocks, presumably because they're all
1410
         * actively having parameters generated for them.
1411
         * So, we need to wait here and not eat up CPU until some
1412
         * change happens.
1413
         */
1414
0
        blindingParamsList.waitCount++;
1415
0
        PR_WaitCondVar(blindingParamsList.cVar, PR_INTERVAL_NO_TIMEOUT);
1416
0
        PZ_Unlock(blindingParamsList.lock);
1417
0
        holdingLock = PR_FALSE;
1418
0
        (void)holdingLock;
1419
0
    } while (1);
1420
1421
0
cleanup:
1422
    /* It is possible to reach this after the lock is already released.  */
1423
0
    if (bpUnlinked) {
1424
0
        if (!holdingLock) {
1425
0
            PZ_Lock(blindingParamsList.lock);
1426
0
            holdingLock = PR_TRUE;
1427
0
        }
1428
0
        bp = bpUnlinked;
1429
0
        mp_clear(&bp->f);
1430
0
        mp_clear(&bp->g);
1431
0
        bp->counter = 0;
1432
        /* Must put the unlinked bp back on the free list */
1433
0
        bp->next = rsabp->free;
1434
0
        rsabp->free = bp;
1435
0
    }
1436
0
    if (holdingLock) {
1437
0
        PZ_Unlock(blindingParamsList.lock);
1438
0
    }
1439
0
    if (err) {
1440
0
        MP_TO_SEC_ERROR(err);
1441
0
    }
1442
0
    *n0i = 0;
1443
0
    return SECFailure;
1444
0
}
1445
1446
/*
1447
** Perform a raw private-key operation
1448
**  Length of input and output buffers are equal to key's modulus len.
1449
*/
1450
static SECStatus
1451
rsa_PrivateKeyOp(RSAPrivateKey *key,
1452
                 unsigned char *output,
1453
                 const unsigned char *input,
1454
                 PRBool check)
1455
6
{
1456
6
    unsigned int modLen;
1457
6
    unsigned int offset;
1458
6
    SECStatus rv = SECSuccess;
1459
6
    mp_err err;
1460
6
    mp_int n, c, m;
1461
6
    mp_int f, g;
1462
6
    mp_digit n0i;
1463
6
    if (!key || !output || !input) {
1464
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
1465
0
        return SECFailure;
1466
0
    }
1467
    /* check input out of range (needs to be in range [0..n-1]) */
1468
6
    modLen = rsa_modulusLen(&key->modulus);
1469
6
    if (modLen == 0) {
1470
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
1471
0
        return SECFailure;
1472
0
    }
1473
6
    offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
1474
6
    if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
1475
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
1476
0
        return SECFailure;
1477
0
    }
1478
6
    MP_DIGITS(&n) = 0;
1479
6
    MP_DIGITS(&c) = 0;
1480
6
    MP_DIGITS(&m) = 0;
1481
6
    MP_DIGITS(&f) = 0;
1482
6
    MP_DIGITS(&g) = 0;
1483
6
    CHECK_MPI_OK(mp_init(&n));
1484
6
    CHECK_MPI_OK(mp_init(&c));
1485
6
    CHECK_MPI_OK(mp_init(&m));
1486
6
    CHECK_MPI_OK(mp_init(&f));
1487
6
    CHECK_MPI_OK(mp_init(&g));
1488
6
    SECITEM_TO_MPINT(key->modulus, &n);
1489
6
    OCTETS_TO_MPINT(input, &c, modLen);
1490
    /* If blinding, compute pre-image of ciphertext by multiplying by
1491
    ** blinding factor
1492
    */
1493
6
    if (nssRSAUseBlinding) {
1494
6
        CHECK_SEC_OK(get_blinding_params(key, &n, modLen, &f, &g, &n0i));
1495
        /* c' = c*f mod n */
1496
6
        CHECK_MPI_OK(mp_mulmod(&c, &f, &n, &c));
1497
6
    }
1498
    /* Do the private key operation m = c**d mod n */
1499
6
    if (key->prime1.len == 0 ||
1500
6
        key->prime2.len == 0 ||
1501
6
        key->exponent1.len == 0 ||
1502
6
        key->exponent2.len == 0 ||
1503
6
        key->coefficient.len == 0) {
1504
0
        CHECK_SEC_OK(rsa_PrivateKeyOpNoCRT(key, &m, &c, &n, modLen));
1505
6
    } else if (check) {
1506
6
        CHECK_SEC_OK(rsa_PrivateKeyOpCRTCheckedPubKey(key, &m, &c));
1507
6
    } else {
1508
0
        CHECK_SEC_OK(rsa_PrivateKeyOpCRTNoCheck(key, &m, &c));
1509
0
    }
1510
    /* If blinding, compute post-image of plaintext by multiplying by
1511
    ** blinding factor
1512
    */
1513
6
    if (nssRSAUseBlinding) {
1514
        /* m = m'*g mod n */
1515
6
        CHECK_MPI_OK(mp_mulmontmodCT(&m, &g, &n, n0i, &m));
1516
6
    }
1517
6
    err = mp_to_fixlen_octets(&m, output, modLen);
1518
6
    if (err >= 0)
1519
6
        err = MP_OKAY;
1520
6
cleanup:
1521
6
    mp_clear(&n);
1522
6
    mp_clear(&c);
1523
6
    mp_clear(&m);
1524
6
    mp_clear(&f);
1525
6
    mp_clear(&g);
1526
6
    if (err) {
1527
0
        MP_TO_SEC_ERROR(err);
1528
0
        rv = SECFailure;
1529
0
    }
1530
6
    return rv;
1531
6
}
1532
1533
SECStatus
1534
RSA_PrivateKeyOp(RSAPrivateKey *key,
1535
                 unsigned char *output,
1536
                 const unsigned char *input)
1537
0
{
1538
0
    return rsa_PrivateKeyOp(key, output, input, PR_FALSE);
1539
0
}
1540
1541
SECStatus
1542
RSA_PrivateKeyOpDoubleChecked(RSAPrivateKey *key,
1543
                              unsigned char *output,
1544
                              const unsigned char *input)
1545
6
{
1546
6
    return rsa_PrivateKeyOp(key, output, input, PR_TRUE);
1547
6
}
1548
1549
SECStatus
1550
RSA_PrivateKeyCheck(const RSAPrivateKey *key)
1551
0
{
1552
0
    mp_int p, q, n, psub1, qsub1, e, d, d_p, d_q, qInv, res;
1553
0
    mp_err err = MP_OKAY;
1554
0
    SECStatus rv = SECSuccess;
1555
0
    MP_DIGITS(&p) = 0;
1556
0
    MP_DIGITS(&q) = 0;
1557
0
    MP_DIGITS(&n) = 0;
1558
0
    MP_DIGITS(&psub1) = 0;
1559
0
    MP_DIGITS(&qsub1) = 0;
1560
0
    MP_DIGITS(&e) = 0;
1561
0
    MP_DIGITS(&d) = 0;
1562
0
    MP_DIGITS(&d_p) = 0;
1563
0
    MP_DIGITS(&d_q) = 0;
1564
0
    MP_DIGITS(&qInv) = 0;
1565
0
    MP_DIGITS(&res) = 0;
1566
0
    CHECK_MPI_OK(mp_init(&p));
1567
0
    CHECK_MPI_OK(mp_init(&q));
1568
0
    CHECK_MPI_OK(mp_init(&n));
1569
0
    CHECK_MPI_OK(mp_init(&psub1));
1570
0
    CHECK_MPI_OK(mp_init(&qsub1));
1571
0
    CHECK_MPI_OK(mp_init(&e));
1572
0
    CHECK_MPI_OK(mp_init(&d));
1573
0
    CHECK_MPI_OK(mp_init(&d_p));
1574
0
    CHECK_MPI_OK(mp_init(&d_q));
1575
0
    CHECK_MPI_OK(mp_init(&qInv));
1576
0
    CHECK_MPI_OK(mp_init(&res));
1577
1578
0
    if (!key->modulus.data || !key->prime1.data || !key->prime2.data ||
1579
0
        !key->publicExponent.data || !key->privateExponent.data ||
1580
0
        !key->exponent1.data || !key->exponent2.data ||
1581
0
        !key->coefficient.data) {
1582
        /* call RSA_PopulatePrivateKey first, if the application wishes to
1583
         * recover these parameters */
1584
0
        err = MP_BADARG;
1585
0
        goto cleanup;
1586
0
    }
1587
1588
0
    SECITEM_TO_MPINT(key->modulus, &n);
1589
0
    SECITEM_TO_MPINT(key->prime1, &p);
1590
0
    SECITEM_TO_MPINT(key->prime2, &q);
1591
0
    SECITEM_TO_MPINT(key->publicExponent, &e);
1592
0
    SECITEM_TO_MPINT(key->privateExponent, &d);
1593
0
    SECITEM_TO_MPINT(key->exponent1, &d_p);
1594
0
    SECITEM_TO_MPINT(key->exponent2, &d_q);
1595
0
    SECITEM_TO_MPINT(key->coefficient, &qInv);
1596
    /* p and q must be distinct. */
1597
0
    if (mp_cmp(&p, &q) == 0) {
1598
0
        rv = SECFailure;
1599
0
        goto cleanup;
1600
0
    }
1601
0
#define VERIFY_MPI_EQUAL(m1, m2) \
1602
0
    if (mp_cmp(m1, m2) != 0) {   \
1603
0
        rv = SECFailure;         \
1604
0
        goto cleanup;            \
1605
0
    }
1606
0
#define VERIFY_MPI_EQUAL_1(m)  \
1607
0
    if (mp_cmp_d(m, 1) != 0) { \
1608
0
        rv = SECFailure;       \
1609
0
        goto cleanup;          \
1610
0
    }
1611
    /* n == p * q */
1612
0
    CHECK_MPI_OK(mp_mul(&p, &q, &res));
1613
0
    VERIFY_MPI_EQUAL(&res, &n);
1614
    /* gcd(e, p-1) == 1 */
1615
0
    CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1));
1616
0
    CHECK_MPI_OK(mp_gcd(&e, &psub1, &res));
1617
0
    VERIFY_MPI_EQUAL_1(&res);
1618
    /* gcd(e, q-1) == 1 */
1619
0
    CHECK_MPI_OK(mp_sub_d(&q, 1, &qsub1));
1620
0
    CHECK_MPI_OK(mp_gcd(&e, &qsub1, &res));
1621
0
    VERIFY_MPI_EQUAL_1(&res);
1622
    /* d*e == 1 mod p-1 */
1623
0
    CHECK_MPI_OK(mp_mulmod(&d, &e, &psub1, &res));
1624
0
    VERIFY_MPI_EQUAL_1(&res);
1625
    /* d*e == 1 mod q-1 */
1626
0
    CHECK_MPI_OK(mp_mulmod(&d, &e, &qsub1, &res));
1627
0
    VERIFY_MPI_EQUAL_1(&res);
1628
    /* d_p == d mod p-1 */
1629
0
    CHECK_MPI_OK(mp_mod(&d, &psub1, &res));
1630
0
    VERIFY_MPI_EQUAL(&res, &d_p);
1631
    /* d_q == d mod q-1 */
1632
0
    CHECK_MPI_OK(mp_mod(&d, &qsub1, &res));
1633
0
    VERIFY_MPI_EQUAL(&res, &d_q);
1634
    /* q * q**-1 == 1 mod p */
1635
0
    CHECK_MPI_OK(mp_mulmod(&q, &qInv, &p, &res));
1636
0
    VERIFY_MPI_EQUAL_1(&res);
1637
1638
0
cleanup:
1639
0
    mp_clear(&n);
1640
0
    mp_clear(&p);
1641
0
    mp_clear(&q);
1642
0
    mp_clear(&psub1);
1643
0
    mp_clear(&qsub1);
1644
0
    mp_clear(&e);
1645
0
    mp_clear(&d);
1646
0
    mp_clear(&d_p);
1647
0
    mp_clear(&d_q);
1648
0
    mp_clear(&qInv);
1649
0
    mp_clear(&res);
1650
0
    if (err) {
1651
0
        MP_TO_SEC_ERROR(err);
1652
0
        rv = SECFailure;
1653
0
    }
1654
0
    return rv;
1655
0
}
1656
1657
SECStatus
1658
RSA_Init(void)
1659
6
{
1660
6
    if (PR_CallOnce(&coBPInit, init_blinding_params_list) != PR_SUCCESS) {
1661
0
        PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
1662
0
        return SECFailure;
1663
0
    }
1664
6
    return SECSuccess;
1665
6
}
1666
1667
/* cleanup at shutdown */
1668
void
1669
RSA_Cleanup(void)
1670
0
{
1671
0
    blindingParams *bp = NULL;
1672
0
    if (!coBPInit.initialized)
1673
0
        return;
1674
1675
0
    while (!PR_CLIST_IS_EMPTY(&blindingParamsList.head)) {
1676
0
        RSABlindingParams *rsabp =
1677
0
            (RSABlindingParams *)PR_LIST_HEAD(&blindingParamsList.head);
1678
0
        PR_REMOVE_LINK(&rsabp->link);
1679
        /* clear parameters cache */
1680
0
        while (rsabp->bp != NULL) {
1681
0
            bp = rsabp->bp;
1682
0
            rsabp->bp = rsabp->bp->next;
1683
0
            mp_clear(&bp->f);
1684
0
            mp_clear(&bp->g);
1685
0
        }
1686
0
        SECITEM_ZfreeItem(&rsabp->modulus, PR_FALSE);
1687
0
        PORT_Free(rsabp);
1688
0
    }
1689
1690
0
    if (blindingParamsList.cVar) {
1691
0
        PR_DestroyCondVar(blindingParamsList.cVar);
1692
0
        blindingParamsList.cVar = NULL;
1693
0
    }
1694
1695
0
    if (blindingParamsList.lock) {
1696
0
        SKIP_AFTER_FORK(PZ_DestroyLock(blindingParamsList.lock));
1697
0
        blindingParamsList.lock = NULL;
1698
0
    }
1699
1700
0
    coBPInit.initialized = 0;
1701
0
    coBPInit.inProgress = 0;
1702
0
    coBPInit.status = 0;
1703
0
}
1704
1705
/*
1706
 * need a central place for this function to free up all the memory that
1707
 * free_bl may have allocated along the way. Currently only RSA does this,
1708
 * so I've put it here for now.
1709
 */
1710
void
1711
BL_Cleanup(void)
1712
0
{
1713
0
    RSA_Cleanup();
1714
0
}
1715
1716
PRBool bl_parentForkedAfterC_Initialize;
1717
1718
/*
1719
 * Set fork flag so it can be tested in SKIP_AFTER_FORK on relevant platforms.
1720
 */
1721
void
1722
BL_SetForkState(PRBool forked)
1723
0
{
1724
0
    bl_parentForkedAfterC_Initialize = forked;
1725
0
}