Mercurial > trustbridge > nss-cmake-static

comparison nss/lib/freebl/rsa.c @ 0:1e5118fa0cb1

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