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