File: | src/lib/libcrypto/bn/bn_exp.c |
Warning: | line 1331, column 9 3rd function call argument is an uninitialized value |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: bn_exp.c,v 1.50 2023/10/19 10:27:27 tb Exp $ */ | ||||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||||
3 | * All rights reserved. | ||||
4 | * | ||||
5 | * This package is an SSL implementation written | ||||
6 | * by Eric Young (eay@cryptsoft.com). | ||||
7 | * The implementation was written so as to conform with Netscapes SSL. | ||||
8 | * | ||||
9 | * This library is free for commercial and non-commercial use as long as | ||||
10 | * the following conditions are aheared to. The following conditions | ||||
11 | * apply to all code found in this distribution, be it the RC4, RSA, | ||||
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | ||||
13 | * included with this distribution is covered by the same copyright terms | ||||
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | ||||
15 | * | ||||
16 | * Copyright remains Eric Young's, and as such any Copyright notices in | ||||
17 | * the code are not to be removed. | ||||
18 | * If this package is used in a product, Eric Young should be given attribution | ||||
19 | * as the author of the parts of the library used. | ||||
20 | * This can be in the form of a textual message at program startup or | ||||
21 | * in documentation (online or textual) provided with the package. | ||||
22 | * | ||||
23 | * Redistribution and use in source and binary forms, with or without | ||||
24 | * modification, are permitted provided that the following conditions | ||||
25 | * are met: | ||||
26 | * 1. Redistributions of source code must retain the copyright | ||||
27 | * notice, this list of conditions and the following disclaimer. | ||||
28 | * 2. Redistributions in binary form must reproduce the above copyright | ||||
29 | * notice, this list of conditions and the following disclaimer in the | ||||
30 | * documentation and/or other materials provided with the distribution. | ||||
31 | * 3. All advertising materials mentioning features or use of this software | ||||
32 | * must display the following acknowledgement: | ||||
33 | * "This product includes cryptographic software written by | ||||
34 | * Eric Young (eay@cryptsoft.com)" | ||||
35 | * The word 'cryptographic' can be left out if the rouines from the library | ||||
36 | * being used are not cryptographic related :-). | ||||
37 | * 4. If you include any Windows specific code (or a derivative thereof) from | ||||
38 | * the apps directory (application code) you must include an acknowledgement: | ||||
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | ||||
40 | * | ||||
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND | ||||
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||||
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||||
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | ||||
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||||
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | ||||
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||||
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||||
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | ||||
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||||
51 | * SUCH DAMAGE. | ||||
52 | * | ||||
53 | * The licence and distribution terms for any publically available version or | ||||
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be | ||||
55 | * copied and put under another distribution licence | ||||
56 | * [including the GNU Public Licence.] | ||||
57 | */ | ||||
58 | /* ==================================================================== | ||||
59 | * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. | ||||
60 | * | ||||
61 | * Redistribution and use in source and binary forms, with or without | ||||
62 | * modification, are permitted provided that the following conditions | ||||
63 | * are met: | ||||
64 | * | ||||
65 | * 1. Redistributions of source code must retain the above copyright | ||||
66 | * notice, this list of conditions and the following disclaimer. | ||||
67 | * | ||||
68 | * 2. Redistributions in binary form must reproduce the above copyright | ||||
69 | * notice, this list of conditions and the following disclaimer in | ||||
70 | * the documentation and/or other materials provided with the | ||||
71 | * distribution. | ||||
72 | * | ||||
73 | * 3. All advertising materials mentioning features or use of this | ||||
74 | * software must display the following acknowledgment: | ||||
75 | * "This product includes software developed by the OpenSSL Project | ||||
76 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | ||||
77 | * | ||||
78 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | ||||
79 | * endorse or promote products derived from this software without | ||||
80 | * prior written permission. For written permission, please contact | ||||
81 | * openssl-core@openssl.org. | ||||
82 | * | ||||
83 | * 5. Products derived from this software may not be called "OpenSSL" | ||||
84 | * nor may "OpenSSL" appear in their names without prior written | ||||
85 | * permission of the OpenSSL Project. | ||||
86 | * | ||||
87 | * 6. Redistributions of any form whatsoever must retain the following | ||||
88 | * acknowledgment: | ||||
89 | * "This product includes software developed by the OpenSSL Project | ||||
90 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | ||||
91 | * | ||||
92 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | ||||
93 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||||
94 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | ||||
95 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | ||||
96 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | ||||
97 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||||
98 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | ||||
99 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||||
100 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | ||||
101 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||||
102 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | ||||
103 | * OF THE POSSIBILITY OF SUCH DAMAGE. | ||||
104 | * ==================================================================== | ||||
105 | * | ||||
106 | * This product includes cryptographic software written by Eric Young | ||||
107 | * (eay@cryptsoft.com). This product includes software written by Tim | ||||
108 | * Hudson (tjh@cryptsoft.com). | ||||
109 | * | ||||
110 | */ | ||||
111 | |||||
112 | #include <stdlib.h> | ||||
113 | #include <string.h> | ||||
114 | |||||
115 | #include <openssl/err.h> | ||||
116 | |||||
117 | #include "bn_local.h" | ||||
118 | #include "constant_time.h" | ||||
119 | |||||
120 | /* maximum precomputation table size for *variable* sliding windows */ | ||||
121 | #define TABLE_SIZE32 32 | ||||
122 | |||||
123 | /* Calculates r = a^p by successive squaring of a. Not constant time. */ | ||||
124 | int | ||||
125 | BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) | ||||
126 | { | ||||
127 | BIGNUM *rr, *v; | ||||
128 | int i; | ||||
129 | int ret = 0; | ||||
130 | |||||
131 | if (BN_get_flags(p, BN_FLG_CONSTTIME0x04) != 0) { | ||||
132 | BNerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED)ERR_put_error(3,(0xfff),((2|64)),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,132); | ||||
133 | return -1; | ||||
134 | } | ||||
135 | |||||
136 | BN_CTX_start(ctx); | ||||
137 | |||||
138 | if ((v = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
139 | goto err; | ||||
140 | |||||
141 | rr = r; | ||||
142 | if (r == a || r == p) | ||||
143 | rr = BN_CTX_get(ctx); | ||||
144 | if (rr == NULL((void *)0)) | ||||
145 | goto err; | ||||
146 | |||||
147 | if (!BN_one(rr)) | ||||
148 | goto err; | ||||
149 | if (BN_is_odd(p)) { | ||||
150 | if (!bn_copy(rr, a)) | ||||
151 | goto err; | ||||
152 | } | ||||
153 | |||||
154 | if (!bn_copy(v, a)) | ||||
155 | goto err; | ||||
156 | |||||
157 | for (i = 1; i < BN_num_bits(p); i++) { | ||||
158 | if (!BN_sqr(v, v, ctx)) | ||||
159 | goto err; | ||||
160 | if (!BN_is_bit_set(p, i)) | ||||
161 | continue; | ||||
162 | if (!BN_mul(rr, rr, v, ctx)) | ||||
163 | goto err; | ||||
164 | } | ||||
165 | |||||
166 | if (!bn_copy(r, rr)) | ||||
167 | goto err; | ||||
168 | |||||
169 | ret = 1; | ||||
170 | |||||
171 | err: | ||||
172 | BN_CTX_end(ctx); | ||||
173 | |||||
174 | return ret; | ||||
175 | } | ||||
176 | LCRYPTO_ALIAS(BN_exp)asm(""); | ||||
177 | |||||
178 | /* The old fallback, simple version :-) */ | ||||
179 | int | ||||
180 | BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
181 | BN_CTX *ctx) | ||||
182 | { | ||||
183 | int i, j, bits, wstart, wend, window, wvalue; | ||||
184 | int start = 1; | ||||
185 | BIGNUM *d, *q; | ||||
186 | /* Table of variables obtained from 'ctx' */ | ||||
187 | BIGNUM *val[TABLE_SIZE32]; | ||||
188 | int ret = 0; | ||||
189 | |||||
190 | if (BN_get_flags(p, BN_FLG_CONSTTIME0x04) != 0) { | ||||
191 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ | ||||
192 | BNerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED)ERR_put_error(3,(0xfff),((2|64)),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,192); | ||||
193 | return -1; | ||||
194 | } | ||||
195 | |||||
196 | if (r == m) { | ||||
197 | BNerror(BN_R_INVALID_ARGUMENT)ERR_put_error(3,(0xfff),(118),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,197); | ||||
198 | return 0; | ||||
199 | } | ||||
200 | |||||
201 | bits = BN_num_bits(p); | ||||
202 | if (bits == 0) { | ||||
203 | /* x**0 mod 1 is still zero. */ | ||||
204 | if (BN_abs_is_word(m, 1)) { | ||||
205 | ret = 1; | ||||
206 | BN_zero(r); | ||||
207 | } else | ||||
208 | ret = BN_one(r); | ||||
209 | return ret; | ||||
210 | } | ||||
211 | |||||
212 | BN_CTX_start(ctx); | ||||
213 | if ((d = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
214 | goto err; | ||||
215 | if ((q = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
216 | goto err; | ||||
217 | if ((val[0] = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
218 | goto err; | ||||
219 | |||||
220 | if (!BN_nnmod(val[0], a, m, ctx)) | ||||
221 | goto err; | ||||
222 | if (BN_is_zero(val[0])) { | ||||
223 | BN_zero(r); | ||||
224 | goto done; | ||||
225 | } | ||||
226 | if (!bn_copy(q, p)) | ||||
227 | goto err; | ||||
228 | |||||
229 | window = BN_window_bits_for_exponent_size(bits)((bits) > 671 ? 6 : (bits) > 239 ? 5 : (bits) > 79 ? 4 : (bits) > 23 ? 3 : 1); | ||||
230 | if (window > 1) { | ||||
231 | if (!BN_mod_mul(d, val[0], val[0], m, ctx)) | ||||
232 | goto err; | ||||
233 | j = 1 << (window - 1); | ||||
234 | for (i = 1; i < j; i++) { | ||||
235 | if (((val[i] = BN_CTX_get(ctx)) == NULL((void *)0)) || | ||||
236 | !BN_mod_mul(val[i], val[i - 1], d,m, ctx)) | ||||
237 | goto err; | ||||
238 | } | ||||
239 | } | ||||
240 | |||||
241 | start = 1; /* This is used to avoid multiplication etc | ||||
242 | * when there is only the value '1' in the | ||||
243 | * buffer. */ | ||||
244 | wvalue = 0; /* The 'value' of the window */ | ||||
245 | wstart = bits - 1; /* The top bit of the window */ | ||||
246 | wend = 0; /* The bottom bit of the window */ | ||||
247 | |||||
248 | if (!BN_one(r)) | ||||
249 | goto err; | ||||
250 | |||||
251 | for (;;) { | ||||
252 | if (BN_is_bit_set(q, wstart) == 0) { | ||||
253 | if (!start) | ||||
254 | if (!BN_mod_mul(r, r, r, m, ctx)) | ||||
255 | goto err; | ||||
256 | if (wstart == 0) | ||||
257 | break; | ||||
258 | wstart--; | ||||
259 | continue; | ||||
260 | } | ||||
261 | /* We now have wstart on a 'set' bit, we now need to work out | ||||
262 | * how bit a window to do. To do this we need to scan | ||||
263 | * forward until the last set bit before the end of the | ||||
264 | * window */ | ||||
265 | j = wstart; | ||||
266 | wvalue = 1; | ||||
267 | wend = 0; | ||||
268 | for (i = 1; i < window; i++) { | ||||
269 | if (wstart - i < 0) | ||||
270 | break; | ||||
271 | if (BN_is_bit_set(q, wstart - i)) { | ||||
272 | wvalue <<= (i - wend); | ||||
273 | wvalue |= 1; | ||||
274 | wend = i; | ||||
275 | } | ||||
276 | } | ||||
277 | |||||
278 | /* wend is the size of the current window */ | ||||
279 | j = wend + 1; | ||||
280 | /* add the 'bytes above' */ | ||||
281 | if (!start) | ||||
282 | for (i = 0; i < j; i++) { | ||||
283 | if (!BN_mod_mul(r, r, r, m, ctx)) | ||||
284 | goto err; | ||||
285 | } | ||||
286 | |||||
287 | /* wvalue will be an odd number < 2^window */ | ||||
288 | if (!BN_mod_mul(r, r, val[wvalue >> 1], m, ctx)) | ||||
289 | goto err; | ||||
290 | |||||
291 | /* move the 'window' down further */ | ||||
292 | wstart -= wend + 1; | ||||
293 | wvalue = 0; | ||||
294 | start = 0; | ||||
295 | if (wstart < 0) | ||||
296 | break; | ||||
297 | } | ||||
298 | |||||
299 | done: | ||||
300 | ret = 1; | ||||
301 | |||||
302 | err: | ||||
303 | BN_CTX_end(ctx); | ||||
304 | |||||
305 | return ret; | ||||
306 | } | ||||
307 | LCRYPTO_ALIAS(BN_mod_exp_simple)asm(""); | ||||
308 | |||||
309 | /* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout | ||||
310 | * so that accessing any of these table values shows the same access pattern as far | ||||
311 | * as cache lines are concerned. The following functions are used to transfer a BIGNUM | ||||
312 | * from/to that table. */ | ||||
313 | |||||
314 | static int | ||||
315 | MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top, unsigned char *buf, | ||||
316 | int idx, int window) | ||||
317 | { | ||||
318 | int i, j; | ||||
319 | int width = 1 << window; | ||||
320 | BN_ULONGunsigned long *table = (BN_ULONGunsigned long *)buf; | ||||
321 | |||||
322 | if (top > b->top) | ||||
323 | top = b->top; /* this works because 'buf' is explicitly zeroed */ | ||||
324 | |||||
325 | for (i = 0, j = idx; i < top; i++, j += width) { | ||||
326 | table[j] = b->d[i]; | ||||
327 | } | ||||
328 | |||||
329 | return 1; | ||||
330 | } | ||||
331 | |||||
332 | static int | ||||
333 | MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, | ||||
334 | int window) | ||||
335 | { | ||||
336 | int i, j; | ||||
337 | int width = 1 << window; | ||||
338 | volatile BN_ULONGunsigned long *table = (volatile BN_ULONGunsigned long *)buf; | ||||
339 | |||||
340 | if (!bn_wexpand(b, top)) | ||||
341 | return 0; | ||||
342 | |||||
343 | if (window <= 3) { | ||||
344 | for (i = 0; i < top; i++, table += width) { | ||||
345 | BN_ULONGunsigned long acc = 0; | ||||
346 | |||||
347 | for (j = 0; j < width; j++) { | ||||
348 | acc |= table[j] & | ||||
349 | ((BN_ULONGunsigned long)0 - (constant_time_eq_int(j,idx)&1)); | ||||
350 | } | ||||
351 | |||||
352 | b->d[i] = acc; | ||||
353 | } | ||||
354 | } else { | ||||
355 | int xstride = 1 << (window - 2); | ||||
356 | BN_ULONGunsigned long y0, y1, y2, y3; | ||||
357 | |||||
358 | i = idx >> (window - 2); /* equivalent of idx / xstride */ | ||||
359 | idx &= xstride - 1; /* equivalent of idx % xstride */ | ||||
360 | |||||
361 | y0 = (BN_ULONGunsigned long)0 - (constant_time_eq_int(i,0)&1); | ||||
362 | y1 = (BN_ULONGunsigned long)0 - (constant_time_eq_int(i,1)&1); | ||||
363 | y2 = (BN_ULONGunsigned long)0 - (constant_time_eq_int(i,2)&1); | ||||
364 | y3 = (BN_ULONGunsigned long)0 - (constant_time_eq_int(i,3)&1); | ||||
365 | |||||
366 | for (i = 0; i < top; i++, table += width) { | ||||
367 | BN_ULONGunsigned long acc = 0; | ||||
368 | |||||
369 | for (j = 0; j < xstride; j++) { | ||||
370 | acc |= ( (table[j + 0 * xstride] & y0) | | ||||
371 | (table[j + 1 * xstride] & y1) | | ||||
372 | (table[j + 2 * xstride] & y2) | | ||||
373 | (table[j + 3 * xstride] & y3) ) | ||||
374 | & ((BN_ULONGunsigned long)0 - (constant_time_eq_int(j,idx)&1)); | ||||
375 | } | ||||
376 | |||||
377 | b->d[i] = acc; | ||||
378 | } | ||||
379 | } | ||||
380 | b->top = top; | ||||
381 | bn_correct_top(b); | ||||
382 | return 1; | ||||
383 | } | ||||
384 | |||||
385 | /* Given a pointer value, compute the next address that is a cache line multiple. */ | ||||
386 | #define MOD_EXP_CTIME_ALIGN(x_)((unsigned char*)(x_) + (( 64 ) - (((size_t)(x_)) & ((( 64 ) - 1))))) \ | ||||
387 | ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH( 64 ) - (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK(( 64 ) - 1))))) | ||||
388 | |||||
389 | /* This variant of BN_mod_exp_mont() uses fixed windows and the special | ||||
390 | * precomputation memory layout to limit data-dependency to a minimum | ||||
391 | * to protect secret exponents (cf. the hyper-threading timing attacks | ||||
392 | * pointed out by Colin Percival, | ||||
393 | * http://www.daemonology.net/hyperthreading-considered-harmful/) | ||||
394 | */ | ||||
395 | int | ||||
396 | BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, | ||||
397 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||||
398 | { | ||||
399 | int i, bits, ret = 0, window, wvalue; | ||||
400 | int top; | ||||
401 | BN_MONT_CTX *mont = NULL((void *)0); | ||||
402 | int numPowers; | ||||
403 | unsigned char *powerbufFree = NULL((void *)0); | ||||
404 | int powerbufLen = 0; | ||||
405 | unsigned char *powerbuf = NULL((void *)0); | ||||
406 | BIGNUM tmp, am; | ||||
407 | |||||
408 | |||||
409 | if (!BN_is_odd(m)) { | ||||
410 | BNerror(BN_R_CALLED_WITH_EVEN_MODULUS)ERR_put_error(3,(0xfff),(102),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,410); | ||||
411 | return (0); | ||||
412 | } | ||||
413 | |||||
414 | top = m->top; | ||||
415 | |||||
416 | bits = BN_num_bits(p); | ||||
417 | if (bits == 0) { | ||||
418 | /* x**0 mod 1 is still zero. */ | ||||
419 | if (BN_abs_is_word(m, 1)) { | ||||
420 | ret = 1; | ||||
421 | BN_zero(rr); | ||||
422 | } else | ||||
423 | ret = BN_one(rr); | ||||
424 | return ret; | ||||
425 | } | ||||
426 | |||||
427 | BN_CTX_start(ctx); | ||||
428 | |||||
429 | /* | ||||
430 | * Allocate a Montgomery context if it was not supplied by the caller. | ||||
431 | * If this is not done, things will break in the montgomery part. | ||||
432 | */ | ||||
433 | if (in_mont != NULL((void *)0)) | ||||
434 | mont = in_mont; | ||||
435 | else { | ||||
436 | if ((mont = BN_MONT_CTX_new()) == NULL((void *)0)) | ||||
437 | goto err; | ||||
438 | if (!BN_MONT_CTX_set(mont, m, ctx)) | ||||
439 | goto err; | ||||
440 | } | ||||
441 | |||||
442 | /* Get the window size to use with size of p. */ | ||||
443 | window = BN_window_bits_for_ctime_exponent_size(bits)((bits) > 937 ? 6 : (bits) > 306 ? 5 : (bits) > 89 ? 4 : (bits) > 22 ? 3 : 1); | ||||
444 | #if defined(OPENSSL_BN_ASM_MONT51) | ||||
445 | if (window == 6 && bits <= 1024) | ||||
446 | window = 5; /* ~5% improvement of 2048-bit RSA sign */ | ||||
447 | #endif | ||||
448 | |||||
449 | /* Allocate a buffer large enough to hold all of the pre-computed | ||||
450 | * powers of am, am itself and tmp. | ||||
451 | */ | ||||
452 | numPowers = 1 << window; | ||||
453 | powerbufLen = sizeof(m->d[0]) * (top * numPowers + | ||||
454 | ((2*top) > numPowers ? (2*top) : numPowers)); | ||||
455 | if ((powerbufFree = calloc(powerbufLen + | ||||
456 | MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH( 64 ), 1)) == NULL((void *)0)) | ||||
457 | goto err; | ||||
458 | powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree)((unsigned char*)(powerbufFree) + (( 64 ) - (((size_t)(powerbufFree )) & ((( 64 ) - 1))))); | ||||
459 | |||||
460 | /* lay down tmp and am right after powers table */ | ||||
461 | tmp.d = (BN_ULONGunsigned long *)(powerbuf + sizeof(m->d[0]) * top * numPowers); | ||||
462 | am.d = tmp.d + top; | ||||
463 | tmp.top = am.top = 0; | ||||
464 | tmp.dmax = am.dmax = top; | ||||
465 | tmp.neg = am.neg = 0; | ||||
466 | tmp.flags = am.flags = BN_FLG_STATIC_DATA0x02; | ||||
467 | |||||
468 | /* prepare a^0 in Montgomery domain */ | ||||
469 | #if 1 | ||||
470 | if (!BN_to_montgomery(&tmp, BN_value_one(), mont, ctx)) | ||||
471 | goto err; | ||||
472 | #else | ||||
473 | tmp.d[0] = (0 - m - >d[0]) & BN_MASK2(0xffffffffffffffffL); /* 2^(top*BN_BITS2) - m */ | ||||
474 | for (i = 1; i < top; i++) | ||||
475 | tmp.d[i] = (~m->d[i]) & BN_MASK2(0xffffffffffffffffL); | ||||
476 | tmp.top = top; | ||||
477 | #endif | ||||
478 | |||||
479 | /* prepare a^1 in Montgomery domain */ | ||||
480 | if (!BN_nnmod(&am, a, m, ctx)) | ||||
481 | goto err; | ||||
482 | if (!BN_to_montgomery(&am, &am, mont, ctx)) | ||||
483 | goto err; | ||||
484 | |||||
485 | #if defined(OPENSSL_BN_ASM_MONT51) | ||||
486 | /* This optimization uses ideas from http://eprint.iacr.org/2011/239, | ||||
487 | * specifically optimization of cache-timing attack countermeasures | ||||
488 | * and pre-computation optimization. */ | ||||
489 | |||||
490 | /* Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as | ||||
491 | * 512-bit RSA is hardly relevant, we omit it to spare size... */ | ||||
492 | if (window == 5 && top > 1) { | ||||
493 | void bn_mul_mont_gather5(BN_ULONGunsigned long *rp, const BN_ULONGunsigned long *ap, | ||||
494 | const void *table, const BN_ULONGunsigned long *np, | ||||
495 | const BN_ULONGunsigned long *n0, int num, int power); | ||||
496 | void bn_scatter5(const BN_ULONGunsigned long *inp, size_t num, | ||||
497 | void *table, size_t power); | ||||
498 | void bn_gather5(BN_ULONGunsigned long *out, size_t num, | ||||
499 | void *table, size_t power); | ||||
500 | |||||
501 | BN_ULONGunsigned long *np = mont->N.d, *n0 = mont->n0; | ||||
502 | |||||
503 | /* BN_to_montgomery can contaminate words above .top | ||||
504 | * [in BN_DEBUG[_DEBUG] build]... */ | ||||
505 | for (i = am.top; i < top; i++) | ||||
506 | am.d[i] = 0; | ||||
507 | for (i = tmp.top; i < top; i++) | ||||
508 | tmp.d[i] = 0; | ||||
509 | |||||
510 | bn_scatter5(tmp.d, top, powerbuf, 0); | ||||
511 | bn_scatter5(am.d, am.top, powerbuf, 1); | ||||
512 | bn_mul_mont(tmp.d, am.d, am.d, np, n0, top); | ||||
513 | bn_scatter5(tmp.d, top, powerbuf, 2); | ||||
514 | |||||
515 | #if 0 | ||||
516 | for (i = 3; i < 32; i++) { | ||||
517 | /* Calculate a^i = a^(i-1) * a */ | ||||
518 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, | ||||
519 | n0, top, i - 1); | ||||
520 | bn_scatter5(tmp.d, top, powerbuf, i); | ||||
521 | } | ||||
522 | #else | ||||
523 | /* same as above, but uses squaring for 1/2 of operations */ | ||||
524 | for (i = 4; i < 32; i*=2) { | ||||
525 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
526 | bn_scatter5(tmp.d, top, powerbuf, i); | ||||
527 | } | ||||
528 | for (i = 3; i < 8; i += 2) { | ||||
529 | int j; | ||||
530 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, | ||||
531 | n0, top, i - 1); | ||||
532 | bn_scatter5(tmp.d, top, powerbuf, i); | ||||
533 | for (j = 2 * i; j < 32; j *= 2) { | ||||
534 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
535 | bn_scatter5(tmp.d, top, powerbuf, j); | ||||
536 | } | ||||
537 | } | ||||
538 | for (; i < 16; i += 2) { | ||||
539 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, | ||||
540 | n0, top, i - 1); | ||||
541 | bn_scatter5(tmp.d, top, powerbuf, i); | ||||
542 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
543 | bn_scatter5(tmp.d, top, powerbuf, 2*i); | ||||
544 | } | ||||
545 | for (; i < 32; i += 2) { | ||||
546 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, | ||||
547 | n0, top, i - 1); | ||||
548 | bn_scatter5(tmp.d, top, powerbuf, i); | ||||
549 | } | ||||
550 | #endif | ||||
551 | bits--; | ||||
552 | for (wvalue = 0, i = bits % 5; i >= 0; i--, bits--) | ||||
553 | wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); | ||||
554 | bn_gather5(tmp.d, top, powerbuf, wvalue); | ||||
555 | |||||
556 | /* Scan the exponent one window at a time starting from the most | ||||
557 | * significant bits. | ||||
558 | */ | ||||
559 | while (bits >= 0) { | ||||
560 | for (wvalue = 0, i = 0; i < 5; i++, bits--) | ||||
561 | wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); | ||||
562 | |||||
563 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
564 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
565 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
566 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
567 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | ||||
568 | bn_mul_mont_gather5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue); | ||||
569 | } | ||||
570 | |||||
571 | tmp.top = top; | ||||
572 | bn_correct_top(&tmp); | ||||
573 | } else | ||||
574 | #endif | ||||
575 | { | ||||
576 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0, | ||||
577 | window)) | ||||
578 | goto err; | ||||
579 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am, top, powerbuf, 1, | ||||
580 | window)) | ||||
581 | goto err; | ||||
582 | |||||
583 | /* If the window size is greater than 1, then calculate | ||||
584 | * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) | ||||
585 | * (even powers could instead be computed as (a^(i/2))^2 | ||||
586 | * to use the slight performance advantage of sqr over mul). | ||||
587 | */ | ||||
588 | if (window > 1) { | ||||
589 | if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx)) | ||||
590 | goto err; | ||||
591 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, | ||||
592 | 2, window)) | ||||
593 | goto err; | ||||
594 | for (i = 3; i < numPowers; i++) { | ||||
595 | /* Calculate a^i = a^(i-1) * a */ | ||||
596 | if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, | ||||
597 | mont, ctx)) | ||||
598 | goto err; | ||||
599 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, | ||||
600 | powerbuf, i, window)) | ||||
601 | goto err; | ||||
602 | } | ||||
603 | } | ||||
604 | |||||
605 | bits--; | ||||
606 | for (wvalue = 0, i = bits % window; i >= 0; i--, bits--) | ||||
607 | wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); | ||||
608 | if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&tmp, top, powerbuf, | ||||
609 | wvalue, window)) | ||||
610 | goto err; | ||||
611 | |||||
612 | /* Scan the exponent one window at a time starting from the most | ||||
613 | * significant bits. | ||||
614 | */ | ||||
615 | while (bits >= 0) { | ||||
616 | wvalue = 0; /* The 'value' of the window */ | ||||
617 | |||||
618 | /* Scan the window, squaring the result as we go */ | ||||
619 | for (i = 0; i < window; i++, bits--) { | ||||
620 | if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, | ||||
621 | mont, ctx)) | ||||
622 | goto err; | ||||
623 | wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); | ||||
624 | } | ||||
625 | |||||
626 | /* Fetch the appropriate pre-computed value from the pre-buf */ | ||||
627 | if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&am, top, powerbuf, | ||||
628 | wvalue, window)) | ||||
629 | goto err; | ||||
630 | |||||
631 | /* Multiply the result into the intermediate result */ | ||||
632 | if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx)) | ||||
633 | goto err; | ||||
634 | } | ||||
635 | } | ||||
636 | |||||
637 | /* Convert the final result from montgomery to standard format */ | ||||
638 | if (!BN_from_montgomery(rr, &tmp, mont, ctx)) | ||||
639 | goto err; | ||||
640 | ret = 1; | ||||
641 | |||||
642 | err: | ||||
643 | if ((in_mont == NULL((void *)0)) && (mont != NULL((void *)0))) | ||||
644 | BN_MONT_CTX_free(mont); | ||||
645 | freezero(powerbufFree, powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH( 64 )); | ||||
646 | BN_CTX_end(ctx); | ||||
647 | return (ret); | ||||
648 | } | ||||
649 | LCRYPTO_ALIAS(BN_mod_exp_mont_consttime)asm(""); | ||||
650 | |||||
651 | static int | ||||
652 | BN_mod_exp_mont_internal(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
653 | BN_CTX *ctx, BN_MONT_CTX *in_mont, int ct) | ||||
654 | { | ||||
655 | int i, j, bits, ret = 0, wstart, wend, window, wvalue; | ||||
656 | int start = 1; | ||||
657 | BIGNUM *d, *r; | ||||
658 | const BIGNUM *aa; | ||||
659 | /* Table of variables obtained from 'ctx' */ | ||||
660 | BIGNUM *val[TABLE_SIZE32]; | ||||
661 | BN_MONT_CTX *mont = NULL((void *)0); | ||||
662 | |||||
663 | if (ct) { | ||||
664 | return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); | ||||
665 | } | ||||
666 | |||||
667 | |||||
668 | if (!BN_is_odd(m)) { | ||||
669 | BNerror(BN_R_CALLED_WITH_EVEN_MODULUS)ERR_put_error(3,(0xfff),(102),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,669); | ||||
670 | return (0); | ||||
671 | } | ||||
672 | |||||
673 | bits = BN_num_bits(p); | ||||
674 | if (bits == 0) { | ||||
675 | /* x**0 mod 1 is still zero. */ | ||||
676 | if (BN_abs_is_word(m, 1)) { | ||||
677 | ret = 1; | ||||
678 | BN_zero(rr); | ||||
679 | } else | ||||
680 | ret = BN_one(rr); | ||||
681 | return ret; | ||||
682 | } | ||||
683 | |||||
684 | BN_CTX_start(ctx); | ||||
685 | if ((d = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
686 | goto err; | ||||
687 | if ((r = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
688 | goto err; | ||||
689 | if ((val[0] = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
690 | goto err; | ||||
691 | |||||
692 | /* If this is not done, things will break in the montgomery | ||||
693 | * part */ | ||||
694 | |||||
695 | if (in_mont != NULL((void *)0)) | ||||
696 | mont = in_mont; | ||||
697 | else { | ||||
698 | if ((mont = BN_MONT_CTX_new()) == NULL((void *)0)) | ||||
699 | goto err; | ||||
700 | if (!BN_MONT_CTX_set(mont, m, ctx)) | ||||
701 | goto err; | ||||
702 | } | ||||
703 | |||||
704 | if (!BN_nnmod(val[0], a,m, ctx)) | ||||
705 | goto err; | ||||
706 | aa = val[0]; | ||||
707 | if (BN_is_zero(aa)) { | ||||
708 | BN_zero(rr); | ||||
709 | ret = 1; | ||||
710 | goto err; | ||||
711 | } | ||||
712 | if (!BN_to_montgomery(val[0], aa, mont, ctx)) | ||||
713 | goto err; | ||||
714 | |||||
715 | window = BN_window_bits_for_exponent_size(bits)((bits) > 671 ? 6 : (bits) > 239 ? 5 : (bits) > 79 ? 4 : (bits) > 23 ? 3 : 1); | ||||
716 | if (window > 1) { | ||||
717 | if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx)) | ||||
718 | goto err; | ||||
719 | j = 1 << (window - 1); | ||||
720 | for (i = 1; i < j; i++) { | ||||
721 | if (((val[i] = BN_CTX_get(ctx)) == NULL((void *)0)) || | ||||
722 | !BN_mod_mul_montgomery(val[i], val[i - 1], | ||||
723 | d, mont, ctx)) | ||||
724 | goto err; | ||||
725 | } | ||||
726 | } | ||||
727 | |||||
728 | start = 1; /* This is used to avoid multiplication etc | ||||
729 | * when there is only the value '1' in the | ||||
730 | * buffer. */ | ||||
731 | wvalue = 0; /* The 'value' of the window */ | ||||
732 | wstart = bits - 1; /* The top bit of the window */ | ||||
733 | wend = 0; /* The bottom bit of the window */ | ||||
734 | |||||
735 | if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) | ||||
736 | goto err; | ||||
737 | for (;;) { | ||||
738 | if (BN_is_bit_set(p, wstart) == 0) { | ||||
739 | if (!start) { | ||||
740 | if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) | ||||
741 | goto err; | ||||
742 | } | ||||
743 | if (wstart == 0) | ||||
744 | break; | ||||
745 | wstart--; | ||||
746 | continue; | ||||
747 | } | ||||
748 | /* We now have wstart on a 'set' bit, we now need to work out | ||||
749 | * how bit a window to do. To do this we need to scan | ||||
750 | * forward until the last set bit before the end of the | ||||
751 | * window */ | ||||
752 | j = wstart; | ||||
753 | wvalue = 1; | ||||
754 | wend = 0; | ||||
755 | for (i = 1; i < window; i++) { | ||||
756 | if (wstart - i < 0) | ||||
757 | break; | ||||
758 | if (BN_is_bit_set(p, wstart - i)) { | ||||
759 | wvalue <<= (i - wend); | ||||
760 | wvalue |= 1; | ||||
761 | wend = i; | ||||
762 | } | ||||
763 | } | ||||
764 | |||||
765 | /* wend is the size of the current window */ | ||||
766 | j = wend + 1; | ||||
767 | /* add the 'bytes above' */ | ||||
768 | if (!start) | ||||
769 | for (i = 0; i < j; i++) { | ||||
770 | if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) | ||||
771 | goto err; | ||||
772 | } | ||||
773 | |||||
774 | /* wvalue will be an odd number < 2^window */ | ||||
775 | if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx)) | ||||
776 | goto err; | ||||
777 | |||||
778 | /* move the 'window' down further */ | ||||
779 | wstart -= wend + 1; | ||||
780 | wvalue = 0; | ||||
781 | start = 0; | ||||
782 | if (wstart < 0) | ||||
783 | break; | ||||
784 | } | ||||
785 | if (!BN_from_montgomery(rr, r,mont, ctx)) | ||||
786 | goto err; | ||||
787 | ret = 1; | ||||
788 | |||||
789 | err: | ||||
790 | if ((in_mont == NULL((void *)0)) && (mont != NULL((void *)0))) | ||||
791 | BN_MONT_CTX_free(mont); | ||||
792 | BN_CTX_end(ctx); | ||||
793 | return (ret); | ||||
794 | } | ||||
795 | |||||
796 | int | ||||
797 | BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
798 | BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||||
799 | { | ||||
800 | return BN_mod_exp_mont_internal(rr, a, p, m, ctx, in_mont, | ||||
801 | (BN_get_flags(p, BN_FLG_CONSTTIME0x04) != 0)); | ||||
802 | } | ||||
803 | |||||
804 | int | ||||
805 | BN_mod_exp_mont_ct(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
806 | BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||||
807 | { | ||||
808 | return BN_mod_exp_mont_internal(rr, a, p, m, ctx, in_mont, 1); | ||||
809 | } | ||||
810 | |||||
811 | int | ||||
812 | BN_mod_exp_mont_nonct(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
813 | BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||||
814 | { | ||||
815 | return BN_mod_exp_mont_internal(rr, a, p, m, ctx, in_mont, 0); | ||||
816 | } | ||||
817 | |||||
818 | int | ||||
819 | BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONGunsigned long a, const BIGNUM *p, const BIGNUM *m, | ||||
820 | BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||||
821 | { | ||||
822 | BN_MONT_CTX *mont = NULL((void *)0); | ||||
823 | int b, bits, ret = 0; | ||||
824 | int r_is_one; | ||||
825 | BN_ULONGunsigned long w, next_w; | ||||
826 | BIGNUM *d, *r, *t; | ||||
827 | BIGNUM *swap_tmp; | ||||
828 | |||||
829 | #define BN_MOD_MUL_WORD(r, w, m)(BN_mul_word(r, (w)) && ( (BN_mod_ct(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1)))) \ | ||||
830 | (BN_mul_word(r, (w)) && \ | ||||
831 | (/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \ | ||||
832 | (BN_mod_ct(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1)))) | ||||
833 | /* BN_MOD_MUL_WORD is only used with 'w' large, | ||||
834 | * so the BN_ucmp test is probably more overhead | ||||
835 | * than always using BN_mod (which uses bn_copy if | ||||
836 | * a similar test returns true). */ | ||||
837 | /* We can use BN_mod and do not need BN_nnmod because our | ||||
838 | * accumulator is never negative (the result of BN_mod does | ||||
839 | * not depend on the sign of the modulus). | ||||
840 | */ | ||||
841 | #define BN_TO_MONTGOMERY_WORD(r, w, mont)(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont) , ctx)) \ | ||||
842 | (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) | ||||
843 | |||||
844 | if (BN_get_flags(p, BN_FLG_CONSTTIME0x04) != 0) { | ||||
845 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ | ||||
846 | BNerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED)ERR_put_error(3,(0xfff),((2|64)),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,846); | ||||
847 | return -1; | ||||
848 | } | ||||
849 | |||||
850 | |||||
851 | if (!BN_is_odd(m)) { | ||||
852 | BNerror(BN_R_CALLED_WITH_EVEN_MODULUS)ERR_put_error(3,(0xfff),(102),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,852); | ||||
853 | return (0); | ||||
854 | } | ||||
855 | if (m->top == 1) | ||||
856 | a %= m->d[0]; /* make sure that 'a' is reduced */ | ||||
857 | |||||
858 | bits = BN_num_bits(p); | ||||
859 | if (bits == 0) { | ||||
860 | /* x**0 mod 1 is still zero. */ | ||||
861 | if (BN_abs_is_word(m, 1)) { | ||||
862 | ret = 1; | ||||
863 | BN_zero(rr); | ||||
864 | } else | ||||
865 | ret = BN_one(rr); | ||||
866 | return ret; | ||||
867 | } | ||||
868 | if (a == 0) { | ||||
869 | BN_zero(rr); | ||||
870 | ret = 1; | ||||
871 | return ret; | ||||
872 | } | ||||
873 | |||||
874 | BN_CTX_start(ctx); | ||||
875 | if ((d = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
876 | goto err; | ||||
877 | if ((r = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
878 | goto err; | ||||
879 | if ((t = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
880 | goto err; | ||||
881 | |||||
882 | if (in_mont != NULL((void *)0)) | ||||
883 | mont = in_mont; | ||||
884 | else { | ||||
885 | if ((mont = BN_MONT_CTX_new()) == NULL((void *)0)) | ||||
886 | goto err; | ||||
887 | if (!BN_MONT_CTX_set(mont, m, ctx)) | ||||
888 | goto err; | ||||
889 | } | ||||
890 | |||||
891 | r_is_one = 1; /* except for Montgomery factor */ | ||||
892 | |||||
893 | /* bits-1 >= 0 */ | ||||
894 | |||||
895 | /* The result is accumulated in the product r*w. */ | ||||
896 | w = a; /* bit 'bits-1' of 'p' is always set */ | ||||
897 | for (b = bits - 2; b >= 0; b--) { | ||||
898 | /* First, square r*w. */ | ||||
899 | next_w = w * w; | ||||
900 | if ((next_w / w) != w) /* overflow */ | ||||
901 | { | ||||
902 | if (r_is_one) { | ||||
903 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont) , ctx))) | ||||
904 | goto err; | ||||
905 | r_is_one = 0; | ||||
906 | } else { | ||||
907 | if (!BN_MOD_MUL_WORD(r, w, m)(BN_mul_word(r, (w)) && ( (BN_mod_ct(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))) | ||||
908 | goto err; | ||||
909 | } | ||||
910 | next_w = 1; | ||||
911 | } | ||||
912 | w = next_w; | ||||
913 | if (!r_is_one) { | ||||
914 | if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) | ||||
915 | goto err; | ||||
916 | } | ||||
917 | |||||
918 | /* Second, multiply r*w by 'a' if exponent bit is set. */ | ||||
919 | if (BN_is_bit_set(p, b)) { | ||||
920 | next_w = w * a; | ||||
921 | if ((next_w / a) != w) /* overflow */ | ||||
922 | { | ||||
923 | if (r_is_one) { | ||||
924 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont) , ctx))) | ||||
925 | goto err; | ||||
926 | r_is_one = 0; | ||||
927 | } else { | ||||
928 | if (!BN_MOD_MUL_WORD(r, w, m)(BN_mul_word(r, (w)) && ( (BN_mod_ct(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))) | ||||
929 | goto err; | ||||
930 | } | ||||
931 | next_w = a; | ||||
932 | } | ||||
933 | w = next_w; | ||||
934 | } | ||||
935 | } | ||||
936 | |||||
937 | /* Finally, set r:=r*w. */ | ||||
938 | if (w != 1) { | ||||
939 | if (r_is_one) { | ||||
940 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont) , ctx))) | ||||
941 | goto err; | ||||
942 | r_is_one = 0; | ||||
943 | } else { | ||||
944 | if (!BN_MOD_MUL_WORD(r, w, m)(BN_mul_word(r, (w)) && ( (BN_mod_ct(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))) | ||||
945 | goto err; | ||||
946 | } | ||||
947 | } | ||||
948 | |||||
949 | if (r_is_one) /* can happen only if a == 1*/ | ||||
950 | { | ||||
951 | if (!BN_one(rr)) | ||||
952 | goto err; | ||||
953 | } else { | ||||
954 | if (!BN_from_montgomery(rr, r, mont, ctx)) | ||||
955 | goto err; | ||||
956 | } | ||||
957 | ret = 1; | ||||
958 | |||||
959 | err: | ||||
960 | if ((in_mont == NULL((void *)0)) && (mont != NULL((void *)0))) | ||||
961 | BN_MONT_CTX_free(mont); | ||||
962 | BN_CTX_end(ctx); | ||||
963 | return (ret); | ||||
964 | } | ||||
965 | LCRYPTO_ALIAS(BN_mod_exp_mont_word)asm(""); | ||||
966 | |||||
967 | int | ||||
968 | BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
969 | BN_CTX *ctx) | ||||
970 | { | ||||
971 | int i, j, bits, wstart, wend, window, wvalue; | ||||
972 | int start = 1; | ||||
973 | BIGNUM *aa, *q; | ||||
974 | /* Table of variables obtained from 'ctx' */ | ||||
975 | BIGNUM *val[TABLE_SIZE32]; | ||||
976 | BN_RECP_CTX recp; | ||||
977 | int ret = 0; | ||||
978 | |||||
979 | if (BN_get_flags(p, BN_FLG_CONSTTIME0x04) != 0) { | ||||
980 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ | ||||
981 | BNerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED)ERR_put_error(3,(0xfff),((2|64)),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,981); | ||||
982 | return -1; | ||||
983 | } | ||||
984 | |||||
985 | bits = BN_num_bits(p); | ||||
986 | if (bits == 0) { | ||||
987 | /* x**0 mod 1 is still zero. */ | ||||
988 | if (BN_abs_is_word(m, 1)) { | ||||
989 | ret = 1; | ||||
990 | BN_zero(r); | ||||
991 | } else | ||||
992 | ret = BN_one(r); | ||||
993 | return ret; | ||||
994 | } | ||||
995 | |||||
996 | BN_RECP_CTX_init(&recp); | ||||
997 | |||||
998 | BN_CTX_start(ctx); | ||||
999 | if ((aa = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
1000 | goto err; | ||||
1001 | if ((q = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
1002 | goto err; | ||||
1003 | if ((val[0] = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
1004 | goto err; | ||||
1005 | |||||
1006 | if (m->neg) { | ||||
1007 | /* ignore sign of 'm' */ | ||||
1008 | if (!bn_copy(aa, m)) | ||||
1009 | goto err; | ||||
1010 | aa->neg = 0; | ||||
1011 | if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0) | ||||
1012 | goto err; | ||||
1013 | } else { | ||||
1014 | if (BN_RECP_CTX_set(&recp, m, ctx) <= 0) | ||||
1015 | goto err; | ||||
1016 | } | ||||
1017 | |||||
1018 | if (!BN_nnmod(val[0], a, m, ctx)) | ||||
1019 | goto err; | ||||
1020 | if (BN_is_zero(val[0])) { | ||||
1021 | BN_zero(r); | ||||
1022 | goto done; | ||||
1023 | } | ||||
1024 | if (!bn_copy(q, p)) | ||||
1025 | goto err; | ||||
1026 | |||||
1027 | window = BN_window_bits_for_exponent_size(bits)((bits) > 671 ? 6 : (bits) > 239 ? 5 : (bits) > 79 ? 4 : (bits) > 23 ? 3 : 1); | ||||
1028 | if (window > 1) { | ||||
1029 | if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx)) | ||||
1030 | goto err; | ||||
1031 | j = 1 << (window - 1); | ||||
1032 | for (i = 1; i < j; i++) { | ||||
1033 | if (((val[i] = BN_CTX_get(ctx)) == NULL((void *)0)) || | ||||
1034 | !BN_mod_mul_reciprocal(val[i], val[i - 1], | ||||
1035 | aa, &recp, ctx)) | ||||
1036 | goto err; | ||||
1037 | } | ||||
1038 | } | ||||
1039 | |||||
1040 | start = 1; /* This is used to avoid multiplication etc | ||||
1041 | * when there is only the value '1' in the | ||||
1042 | * buffer. */ | ||||
1043 | wvalue = 0; /* The 'value' of the window */ | ||||
1044 | wstart = bits - 1; /* The top bit of the window */ | ||||
1045 | wend = 0; /* The bottom bit of the window */ | ||||
1046 | |||||
1047 | if (!BN_one(r)) | ||||
1048 | goto err; | ||||
1049 | |||||
1050 | for (;;) { | ||||
1051 | if (BN_is_bit_set(q, wstart) == 0) { | ||||
1052 | if (!start) | ||||
1053 | if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) | ||||
1054 | goto err; | ||||
1055 | if (wstart == 0) | ||||
1056 | break; | ||||
1057 | wstart--; | ||||
1058 | continue; | ||||
1059 | } | ||||
1060 | /* We now have wstart on a 'set' bit, we now need to work out | ||||
1061 | * how bit a window to do. To do this we need to scan | ||||
1062 | * forward until the last set bit before the end of the | ||||
1063 | * window */ | ||||
1064 | j = wstart; | ||||
1065 | wvalue = 1; | ||||
1066 | wend = 0; | ||||
1067 | for (i = 1; i < window; i++) { | ||||
1068 | if (wstart - i < 0) | ||||
1069 | break; | ||||
1070 | if (BN_is_bit_set(q, wstart - i)) { | ||||
1071 | wvalue <<= (i - wend); | ||||
1072 | wvalue |= 1; | ||||
1073 | wend = i; | ||||
1074 | } | ||||
1075 | } | ||||
1076 | |||||
1077 | /* wend is the size of the current window */ | ||||
1078 | j = wend + 1; | ||||
1079 | /* add the 'bytes above' */ | ||||
1080 | if (!start) | ||||
1081 | for (i = 0; i < j; i++) { | ||||
1082 | if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) | ||||
1083 | goto err; | ||||
1084 | } | ||||
1085 | |||||
1086 | /* wvalue will be an odd number < 2^window */ | ||||
1087 | if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx)) | ||||
1088 | goto err; | ||||
1089 | |||||
1090 | /* move the 'window' down further */ | ||||
1091 | wstart -= wend + 1; | ||||
1092 | wvalue = 0; | ||||
1093 | start = 0; | ||||
1094 | if (wstart < 0) | ||||
1095 | break; | ||||
1096 | } | ||||
1097 | |||||
1098 | done: | ||||
1099 | ret = 1; | ||||
1100 | |||||
1101 | err: | ||||
1102 | BN_CTX_end(ctx); | ||||
1103 | BN_RECP_CTX_free(&recp); | ||||
1104 | |||||
1105 | return ret; | ||||
1106 | } | ||||
1107 | |||||
1108 | static int | ||||
1109 | BN_mod_exp_internal(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
1110 | BN_CTX *ctx, int ct) | ||||
1111 | { | ||||
1112 | int ret; | ||||
1113 | |||||
1114 | |||||
1115 | /* For even modulus m = 2^k*m_odd, it might make sense to compute | ||||
1116 | * a^p mod m_odd and a^p mod 2^k separately (with Montgomery | ||||
1117 | * exponentiation for the odd part), using appropriate exponent | ||||
1118 | * reductions, and combine the results using the CRT. | ||||
1119 | * | ||||
1120 | * For now, we use Montgomery only if the modulus is odd; otherwise, | ||||
1121 | * exponentiation using the reciprocal-based quick remaindering | ||||
1122 | * algorithm is used. | ||||
1123 | * | ||||
1124 | * (Timing obtained with expspeed.c [computations a^p mod m | ||||
1125 | * where a, p, m are of the same length: 256, 512, 1024, 2048, | ||||
1126 | * 4096, 8192 bits], compared to the running time of the | ||||
1127 | * standard algorithm: | ||||
1128 | * | ||||
1129 | * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration] | ||||
1130 | * 55 .. 77 % [UltraSparc processor, but | ||||
1131 | * debug-solaris-sparcv8-gcc conf.] | ||||
1132 | * | ||||
1133 | * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration] | ||||
1134 | * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc] | ||||
1135 | * | ||||
1136 | * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont | ||||
1137 | * at 2048 and more bits, but at 512 and 1024 bits, it was | ||||
1138 | * slower even than the standard algorithm! | ||||
1139 | * | ||||
1140 | * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations] | ||||
1141 | * should be obtained when the new Montgomery reduction code | ||||
1142 | * has been integrated into OpenSSL.) | ||||
1143 | */ | ||||
1144 | |||||
1145 | if (BN_is_odd(m)) { | ||||
1146 | if (a->top == 1 && !a->neg && !ct) { | ||||
1147 | BN_ULONGunsigned long A = a->d[0]; | ||||
1148 | ret = BN_mod_exp_mont_word(r, A,p, m,ctx, NULL((void *)0)); | ||||
1149 | } else | ||||
1150 | ret = BN_mod_exp_mont_ct(r, a,p, m,ctx, NULL((void *)0)); | ||||
1151 | } else { | ||||
1152 | ret = BN_mod_exp_recp(r, a,p, m, ctx); | ||||
1153 | } | ||||
1154 | |||||
1155 | return (ret); | ||||
1156 | } | ||||
1157 | |||||
1158 | int | ||||
1159 | BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
1160 | BN_CTX *ctx) | ||||
1161 | { | ||||
1162 | return BN_mod_exp_internal(r, a, p, m, ctx, | ||||
1163 | (BN_get_flags(p, BN_FLG_CONSTTIME0x04) != 0)); | ||||
1164 | } | ||||
1165 | |||||
1166 | int | ||||
1167 | BN_mod_exp_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
1168 | BN_CTX *ctx) | ||||
1169 | { | ||||
1170 | return BN_mod_exp_internal(r, a, p, m, ctx, 1); | ||||
1171 | } | ||||
1172 | |||||
1173 | int | ||||
1174 | BN_mod_exp_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||||
1175 | BN_CTX *ctx) | ||||
1176 | { | ||||
1177 | return BN_mod_exp_internal(r, a, p, m, ctx, 0); | ||||
1178 | } | ||||
1179 | |||||
1180 | int | ||||
1181 | BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, | ||||
1182 | const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, BN_CTX *ctx, | ||||
1183 | BN_MONT_CTX *in_mont) | ||||
1184 | { | ||||
1185 | int i, j, bits, b, bits1, bits2, ret = 0, wpos1, wpos2, window1, window2, wvalue1, wvalue2; | ||||
1186 | int r_is_one = 1; | ||||
1187 | BIGNUM *d, *r; | ||||
1188 | const BIGNUM *a_mod_m; | ||||
1189 | /* Tables of variables obtained from 'ctx' */ | ||||
1190 | BIGNUM *val1[TABLE_SIZE32], *val2[TABLE_SIZE32]; | ||||
1191 | BN_MONT_CTX *mont = NULL((void *)0); | ||||
1192 | |||||
1193 | |||||
1194 | if (!BN_is_odd(m)) { | ||||
| |||||
1195 | BNerror(BN_R_CALLED_WITH_EVEN_MODULUS)ERR_put_error(3,(0xfff),(102),"/usr/src/lib/libcrypto/bn/bn_exp.c" ,1195); | ||||
1196 | return (0); | ||||
1197 | } | ||||
1198 | bits1 = BN_num_bits(p1); | ||||
1199 | bits2 = BN_num_bits(p2); | ||||
1200 | if ((bits1 == 0) && (bits2 == 0)) { | ||||
1201 | ret = BN_one(rr); | ||||
1202 | return ret; | ||||
1203 | } | ||||
1204 | |||||
1205 | bits = (bits1 > bits2) ? bits1 : bits2; | ||||
1206 | |||||
1207 | BN_CTX_start(ctx); | ||||
1208 | if ((d = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
1209 | goto err; | ||||
1210 | if ((r = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
1211 | goto err; | ||||
1212 | if ((val1[0] = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
1213 | goto err; | ||||
1214 | if ((val2[0] = BN_CTX_get(ctx)) == NULL((void *)0)) | ||||
1215 | goto err; | ||||
1216 | |||||
1217 | if (in_mont != NULL((void *)0)) | ||||
1218 | mont = in_mont; | ||||
1219 | else { | ||||
1220 | if ((mont = BN_MONT_CTX_new()) == NULL((void *)0)) | ||||
1221 | goto err; | ||||
1222 | if (!BN_MONT_CTX_set(mont, m, ctx)) | ||||
1223 | goto err; | ||||
1224 | } | ||||
1225 | |||||
1226 | window1 = BN_window_bits_for_exponent_size(bits1)((bits1) > 671 ? 6 : (bits1) > 239 ? 5 : (bits1) > 79 ? 4 : (bits1) > 23 ? 3 : 1); | ||||
1227 | window2 = BN_window_bits_for_exponent_size(bits2)((bits2) > 671 ? 6 : (bits2) > 239 ? 5 : (bits2) > 79 ? 4 : (bits2) > 23 ? 3 : 1); | ||||
1228 | |||||
1229 | /* | ||||
1230 | * Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 2^(window1-1) | ||||
1231 | */ | ||||
1232 | if (!BN_nnmod(val1[0], a1, m, ctx)) | ||||
1233 | goto err; | ||||
1234 | a_mod_m = val1[0]; | ||||
1235 | if (BN_is_zero(a_mod_m)) { | ||||
1236 | BN_zero(rr); | ||||
1237 | ret = 1; | ||||
1238 | goto err; | ||||
1239 | } | ||||
1240 | |||||
1241 | if (!BN_to_montgomery(val1[0], a_mod_m, mont, ctx)) | ||||
1242 | goto err; | ||||
1243 | if (window1
| ||||
1244 | if (!BN_mod_mul_montgomery(d, val1[0], val1[0], mont, ctx)) | ||||
1245 | goto err; | ||||
1246 | |||||
1247 | j = 1 << (window1 - 1); | ||||
1248 | for (i = 1; i < j; i++) { | ||||
1249 | if (((val1[i] = BN_CTX_get(ctx)) == NULL((void *)0)) || | ||||
1250 | !BN_mod_mul_montgomery(val1[i], val1[i - 1], | ||||
1251 | d, mont, ctx)) | ||||
1252 | goto err; | ||||
1253 | } | ||||
1254 | } | ||||
1255 | |||||
1256 | |||||
1257 | /* | ||||
1258 | * Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 2^(window2-1) | ||||
1259 | */ | ||||
1260 | if (!BN_nnmod(val2[0], a2, m, ctx)) | ||||
1261 | goto err; | ||||
1262 | a_mod_m = val2[0]; | ||||
1263 | if (BN_is_zero(a_mod_m)) { | ||||
1264 | BN_zero(rr); | ||||
1265 | ret = 1; | ||||
1266 | goto err; | ||||
1267 | } | ||||
1268 | if (!BN_to_montgomery(val2[0], a_mod_m, mont, ctx)) | ||||
1269 | goto err; | ||||
1270 | if (window2
| ||||
1271 | if (!BN_mod_mul_montgomery(d, val2[0], val2[0], mont, ctx)) | ||||
1272 | goto err; | ||||
1273 | |||||
1274 | j = 1 << (window2 - 1); | ||||
1275 | for (i = 1; i < j; i++) { | ||||
1276 | if (((val2[i] = BN_CTX_get(ctx)) == NULL((void *)0)) || | ||||
1277 | !BN_mod_mul_montgomery(val2[i], val2[i - 1], | ||||
1278 | d, mont, ctx)) | ||||
1279 | goto err; | ||||
1280 | } | ||||
1281 | } | ||||
1282 | |||||
1283 | |||||
1284 | /* Now compute the power product, using independent windows. */ | ||||
1285 | r_is_one = 1; | ||||
1286 | wvalue1 = 0; /* The 'value' of the first window */ | ||||
1287 | wvalue2 = 0; /* The 'value' of the second window */ | ||||
1288 | wpos1 = 0; /* If wvalue1 > 0, the bottom bit of the first window */ | ||||
1289 | wpos2 = 0; /* If wvalue2 > 0, the bottom bit of the second window */ | ||||
1290 | |||||
1291 | if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) | ||||
1292 | goto err; | ||||
1293 | for (b = bits - 1; b >= 0; b--) { | ||||
1294 | if (!r_is_one
| ||||
1295 | if (!BN_mod_mul_montgomery(r, r,r, mont, ctx)) | ||||
1296 | goto err; | ||||
1297 | } | ||||
1298 | |||||
1299 | if (!wvalue1
| ||||
1300 | if (BN_is_bit_set(p1, b)) { | ||||
1301 | /* consider bits b-window1+1 .. b for this window */ | ||||
1302 | i = b - window1 + 1; | ||||
1303 | while (!BN_is_bit_set(p1, i)) /* works for i<0 */ | ||||
1304 | i++; | ||||
1305 | wpos1 = i; | ||||
1306 | wvalue1 = 1; | ||||
1307 | for (i = b - 1; i >= wpos1; i--) { | ||||
1308 | wvalue1 <<= 1; | ||||
1309 | if (BN_is_bit_set(p1, i)) | ||||
1310 | wvalue1++; | ||||
1311 | } | ||||
1312 | } | ||||
1313 | |||||
1314 | if (!wvalue2
| ||||
1315 | if (BN_is_bit_set(p2, b)) { | ||||
1316 | /* consider bits b-window2+1 .. b for this window */ | ||||
1317 | i = b - window2 + 1; | ||||
1318 | while (!BN_is_bit_set(p2, i)) | ||||
1319 | i++; | ||||
1320 | wpos2 = i; | ||||
1321 | wvalue2 = 1; | ||||
1322 | for (i = b - 1; i >= wpos2; i--) { | ||||
1323 | wvalue2 <<= 1; | ||||
1324 | if (BN_is_bit_set(p2, i)) | ||||
1325 | wvalue2++; | ||||
1326 | } | ||||
1327 | } | ||||
1328 | |||||
1329 | if (wvalue1
| ||||
1330 | /* wvalue1 is odd and < 2^window1 */ | ||||
1331 | if (!BN_mod_mul_montgomery(r, r, val1[wvalue1 >> 1], | ||||
| |||||
1332 | mont, ctx)) | ||||
1333 | goto err; | ||||
1334 | wvalue1 = 0; | ||||
1335 | r_is_one = 0; | ||||
1336 | } | ||||
1337 | |||||
1338 | if (wvalue2 && b == wpos2) { | ||||
1339 | /* wvalue2 is odd and < 2^window2 */ | ||||
1340 | if (!BN_mod_mul_montgomery(r, r, val2[wvalue2 >> 1], | ||||
1341 | mont, ctx)) | ||||
1342 | goto err; | ||||
1343 | wvalue2 = 0; | ||||
1344 | r_is_one = 0; | ||||
1345 | } | ||||
1346 | } | ||||
1347 | if (!BN_from_montgomery(rr, r,mont, ctx)) | ||||
1348 | goto err; | ||||
1349 | ret = 1; | ||||
1350 | |||||
1351 | err: | ||||
1352 | if ((in_mont == NULL((void *)0)) && (mont != NULL((void *)0))) | ||||
1353 | BN_MONT_CTX_free(mont); | ||||
1354 | BN_CTX_end(ctx); | ||||
1355 | return (ret); | ||||
1356 | } | ||||
1357 | LCRYPTO_ALIAS(BN_mod_exp2_mont)asm(""); |