File: | src/lib/libcrypto/bn/bn_exp.c |
Warning: | line 1064, column 3 Value stored to 'j' is never read |
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; |
Value stored to 'j' is never read | |
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 > 1) { |
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 > 1) { |
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 && b == wpos1) { |
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(""); |