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