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