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